00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00102 #ifndef DISABLE_DATASTRUCTURE
00103
00104 #include <stdio.h>
00105 #include <stdlib.h>
00106 #include <stdbool.h>
00107 #include <string.h>
00108 #include "qDecoder.h"
00109 #include "qInternal.h"
00110
00111 static int _findEmpty(Q_HASHARR *tbl, int startidx);
00112 static int _getIdx(Q_HASHARR *tbl, const char *key, int hash);
00113 static bool _putData(Q_HASHARR *tbl, int idx, int hash, const char *key, const void *value, int size, int count);
00114 static bool _copySlot(Q_HASHARR *tbl, int idx1, int idx2);
00115 static bool _removeSlot(Q_HASHARR *tbl, int idx);
00116 static bool _removeData(Q_HASHARR *tbl, int idx);
00117
00132 size_t qHasharrSize(int max) {
00133 size_t memsize = sizeof(Q_HASHARR) * (max + 1);
00134 return memsize;
00135 }
00136
00154 int qHasharrInit(Q_HASHARR *tbl, size_t memsize) {
00155
00156 int max = (memsize / sizeof(Q_HASHARR)) - 1;
00157 if(max < 1) return 0;
00158
00159
00160 memset((void *)tbl, 0, memsize);
00161
00162
00163 tbl[0].count = 0;
00164 tbl[0].keylen = max;
00165
00166 return max;
00167 }
00168
00180 bool qHasharrClear(Q_HASHARR *tbl) {
00181
00182 int max = tbl[0].keylen;
00183
00184
00185 memset((void *)tbl, 0, qHasharrSize(max));
00186
00187
00188 tbl[0].count = 0;
00189 tbl[0].keylen = max;
00190
00191 return true;
00192 }
00193
00204 bool qHasharrPut(Q_HASHARR *tbl, const char *key, const void *value, int size) {
00205 if(tbl == NULL || key == NULL || value == NULL) return false;
00206
00207
00208
00209
00210
00211 int hash = ((int)qHashFnv32(tbl[0].keylen, key, strlen(key))) + 1;
00212
00213
00214 if (tbl[hash].count == 0) {
00215
00216 if(_putData(tbl, hash, hash, key, value, size, 1) == false) {
00217 DEBUG("hasharr: FAILED put(new) %s", key);
00218 return false;
00219 }
00220 DEBUG("hasharr: put(new) %s (idx=%d,hash=%d,tot=%d)", key, hash, hash, tbl[0].count);
00221 } else if (tbl[hash].count > 0) {
00222
00223 int idx = _getIdx(tbl, key, hash);
00224 if (idx >= 0) {
00225
00226 qHasharrRemove(tbl, key);
00227 return qHasharrPut(tbl, key, value, size);
00228 } else {
00229
00230 int idx = _findEmpty(tbl, hash);
00231 if (idx < 0) return false;
00232
00233
00234 if(_putData(tbl, idx, hash, key, value, size, -1) == false) {
00235 DEBUG("hasharr: FAILED put(col) %s", key);
00236 return false;
00237 }
00238
00239
00240 tbl[hash].count++;
00241
00242 DEBUG("hasharr: put(col) %s (idx=%d,hash=%d,tot=%d)", key, idx, hash, tbl[0].count);
00243 }
00244 } else {
00245
00246
00247 int idx = _findEmpty(tbl, hash);
00248 if (idx < 0) return false;
00249
00250
00251 _copySlot(tbl, idx, hash);
00252 _removeSlot(tbl, hash);
00253
00254
00255 if(tbl[hash].count == -2) {
00256 tbl[ tbl[idx].hash ].link = idx;
00257 }
00258
00259
00260 if(_putData(tbl, hash, hash, key, value, size, 1) == false) {
00261 DEBUG("hasharr: FAILED put(swp) %s", key);
00262 return false;
00263 }
00264
00265 DEBUG("hasharr: put(swp) %s (idx=%d,hash=%d,tot=%d)", key, hash, hash, tbl[0].count);
00266 }
00267
00268 return true;
00269 }
00270
00280 bool qHasharrPutStr(Q_HASHARR *tbl, const char *key, const char *value) {
00281 int size = (value != NULL) ? (strlen(value) + 1) : 0;
00282 return qHasharrPut(tbl, key, (void *)value, size);
00283 }
00284
00294 bool qHasharrPutInt(Q_HASHARR *tbl, const char *key, int value) {
00295 char data[10+1];
00296 sprintf(data, "%d", value);
00297 return qHasharrPut(tbl, key, (void *)data, -1);
00298 }
00299
00312 void *qHasharrGet(Q_HASHARR *tbl, const char *key, int *size) {
00313 if(tbl == NULL || key == NULL) return NULL;
00314
00315
00316 int hash = ((int)qHashFnv32(tbl[0].keylen, key, strlen(key))) + 1;
00317
00318 int idx = _getIdx(tbl, key, hash);
00319 if (idx < 0) return NULL;
00320
00321 int newidx, valsize;
00322 for(newidx = idx, valsize = 0; ; newidx = tbl[newidx].link) {
00323 valsize += tbl[newidx].size;
00324 if(tbl[newidx].link == 0) break;
00325 }
00326
00327 void *value, *vp;
00328 value = (void *)malloc(valsize);
00329 if(value == NULL) return NULL;
00330
00331 for(newidx = idx, vp = value; ; newidx = tbl[newidx].link) {
00332 memcpy(vp, (void *)tbl[newidx].value, tbl[newidx].size);
00333 vp += tbl[newidx].size;
00334 if(tbl[newidx].link == 0) break;
00335 }
00336
00337 if(size != NULL) *size = valsize;
00338 return value;
00339 }
00340
00352 char *qHasharrGetStr(Q_HASHARR *tbl, const char *key) {
00353 return (char*)qHasharrGet(tbl, key, NULL);
00354 }
00355
00364 int qHasharrGetInt(Q_HASHARR *tbl, const char *key) {
00365 char *data = qHasharrGet(tbl, key, NULL);
00366 if(data == NULL) return 0;
00367
00368 int value = atoi(data);
00369 free(data);
00370
00371 return value;
00372 }
00373
00394 const char *qHasharrGetFirstKey(Q_HASHARR *tbl, int *idx) {
00395 if(idx != NULL) *idx = 0;
00396 return qHasharrGetNextKey(tbl, idx);
00397 }
00398
00410 const char *qHasharrGetNextKey(Q_HASHARR *tbl, int *idx) {
00411 if(tbl == NULL || idx == NULL) return NULL;
00412
00413 for (*idx += 1; *idx <= tbl[0].keylen; (*idx)++) {
00414 if (tbl[*idx].count == 0 || tbl[*idx].count == -2) continue;
00415 return tbl[*idx].key;
00416 }
00417
00418 *idx = tbl[0].keylen;
00419 return NULL;
00420 }
00421
00430 bool qHasharrRemove(Q_HASHARR *tbl, const char *key) {
00431 if(tbl == NULL || key == NULL) return false;
00432
00433
00434 int hash = ((int)qHashFnv32(tbl[0].keylen, key, strlen(key))) + 1;
00435
00436 int idx = _getIdx(tbl, key, hash);
00437 if (idx < 0) {
00438 DEBUG("not found %s", key);
00439 return false;
00440 }
00441
00442 if (tbl[idx].count == 1) {
00443
00444 _removeData(tbl, idx);
00445
00446 DEBUG("hasharr: rem %s (idx=%d,tot=%d)", key, idx, tbl[0].count);
00447 } else if (tbl[idx].count > 1) {
00448
00449 int idx2;
00450 for (idx2 = idx + 1; ; idx2++) {
00451 if (idx2 > tbl[0].keylen) idx2 = 1;
00452 if (idx2 == idx) {
00453 DEBUG("BUG: failed to remove dup key %s.", key);
00454 return false;
00455 }
00456 if (tbl[idx2].count == -1 && tbl[idx2].hash == idx) break;
00457 }
00458
00459
00460 int backupcount = tbl[idx].count;
00461 _removeData(tbl, idx);
00462 _copySlot(tbl, idx, idx2);
00463 tbl[idx].count = backupcount - 1;
00464 _removeSlot(tbl, idx2);
00465
00466 DEBUG("hasharr: rem(lead) %s (idx=%d,tot=%d)", key, idx, tbl[0].count);
00467 } else {
00468
00469 if(tbl[ tbl[idx].hash ].count <= 1) {
00470 DEBUG("hasharr: BUG remove failed %s. counter of leading slot mismatch.", key);
00471 return false;
00472 }
00473 tbl[ tbl[idx].hash ].count--;
00474
00475
00476 _removeData(tbl, idx);
00477
00478 DEBUG("hasharr: rem(dup) %s (idx=%d,tot=%d)", key, idx, tbl[0].count);
00479 }
00480
00481 return true;
00482 }
00483
00492 bool qHasharrPrint(Q_HASHARR *tbl, FILE *out) {
00493 if(tbl == NULL || out == NULL) return false;
00494
00495 int idx, num;
00496 for (idx = 1, num = 0; idx <= tbl[0].keylen && num < tbl[0].count; idx++) {
00497 if (tbl[idx].count == 0) continue;
00498 fprintf(out, "idx=%d,count=%d,hash=%d,key=%s,keylen=%d,size=%d,link=%d\n",
00499 idx, tbl[idx].count, tbl[idx].hash, tbl[idx].key, tbl[idx].keylen, tbl[idx].size, tbl[idx].link);
00500 num++;
00501 }
00502
00503 return true;
00504 }
00505
00520 bool qHasharrStatus(Q_HASHARR *tbl, int *used, int *max) {
00521 if(tbl == NULL) return false;
00522
00523 if(used != NULL) *used = tbl[0].count;
00524 if(max != NULL) *max = tbl[0].keylen;
00525
00526 return true;
00527 }
00528
00530
00532
00533
00534 static int _findEmpty(Q_HASHARR *tbl, int startidx) {
00535 if(startidx > tbl[0].keylen) startidx = 1;
00536
00537 int idx = startidx;
00538 while (true) {
00539 if (tbl[idx].count == 0) return idx;
00540
00541 idx++;
00542 if(idx > tbl[0].keylen) idx = 1;
00543 if(idx == startidx) break;
00544 }
00545
00546 return -1;
00547 }
00548
00549 static int _getIdx(Q_HASHARR *tbl, const char *key, int hash) {
00550 if (tbl[hash].count > 0) {
00551 int keylen = strlen(key);
00552 unsigned char keymd5[16];
00553
00554 unsigned char *tmpmd5 = qHashMd5(key, keylen);
00555 qStrCpy(keymd5, sizeof(keymd5), tmpmd5, sizeof(keymd5));
00556 free(tmpmd5);
00557
00558 int count, idx;
00559 for (count = 0, idx = hash; count < tbl[hash].count; ) {
00560
00561 while(true) {
00562 if (idx > tbl[0].keylen) idx = 1;
00563
00564 if ((tbl[idx].count > 0 || tbl[idx].count == -1) && tbl[idx].hash == hash) {
00565
00566 count++;
00567 break;
00568 }
00569
00570 idx++;
00571 if(idx == hash) return -1;
00572 }
00573
00574
00575 if (keylen == tbl[idx].keylen) {
00576 if (keylen <= (_Q_HASHARR_MAX_KEYSIZE - 1)) {
00577 if (!strcmp(key, tbl[idx].key)) return idx;
00578 } else {
00579 if (!memcmp(keymd5, tbl[idx].keymd5, 16)) return idx;
00580 }
00581 }
00582
00583
00584 idx++;
00585 if(idx > tbl[0].keylen) idx = 1;
00586
00587
00588 if(idx == hash) break;
00589 }
00590 }
00591
00592 return -1;
00593 }
00594
00595 static bool _putData(Q_HASHARR *tbl, int idx, int hash, const char *key, const void *value, int size, int count) {
00596
00597 if(tbl[idx].count != 0) {
00598 DEBUG("hasharr: BUG found.");
00599 return false;
00600 }
00601
00602 int keylen = strlen(key);
00603 unsigned char *keymd5 = qHashMd5(key, keylen);
00604
00605
00606 tbl[idx].count = count;
00607 tbl[idx].hash = hash;
00608 qStrCpy(tbl[idx].key, _Q_HASHARR_MAX_KEYSIZE, key, _Q_HASHARR_MAX_KEYSIZE);
00609 strncpy(tbl[idx].keymd5, keymd5, 16);
00610 tbl[idx].keylen = keylen;
00611 tbl[idx].link = 0;
00612
00613 free(keymd5);
00614
00615
00616 int newidx, savesize, copysize;
00617 for (newidx = idx, savesize = 0, copysize = 0; savesize < size; savesize += copysize) {
00618 copysize = size - savesize;
00619 if(copysize > _Q_HASHARR_DEF_VALUESIZE) copysize = _Q_HASHARR_DEF_VALUESIZE;
00620
00621 if(savesize > 0) {
00622 int tmpidx = _findEmpty(tbl, newidx + 1);
00623
00624 tmpidx = _findEmpty(tbl, newidx + 1);
00625 if(tmpidx < 0) {
00626 DEBUG("hasharr: Can't expand slot for key %s.", key);
00627 _removeData(tbl, idx);
00628 return false;
00629 }
00630
00631
00632 memset((void *)(&tbl[tmpidx]), 0, sizeof(Q_HASHARR));
00633
00634 tbl[tmpidx].count = -2;
00635 tbl[tmpidx].hash = newidx;
00636 tbl[tmpidx].link = 0;
00637 tbl[tmpidx].size = 0;
00638
00639 tbl[newidx].link = tmpidx;
00640
00641 DEBUG("hasharr: slot %d is linked to slot %d for key %s.", tmpidx, newidx, key);
00642 newidx = tmpidx;
00643 }
00644
00645 memcpy(tbl[newidx].value, value + savesize, copysize);
00646 tbl[newidx].size = copysize;
00647
00648
00649 tbl[0].count++;
00650 }
00651
00652 return true;
00653 }
00654
00655 static bool _copySlot(Q_HASHARR *tbl, int idx1, int idx2) {
00656 if(tbl[idx1].count != 0 || tbl[idx2].count == 0) {
00657 DEBUG("hasharr: BUG found.");
00658 return false;
00659 }
00660
00661 memcpy((void *)(&tbl[idx1]), (void *)(&tbl[idx2]), sizeof(Q_HASHARR));
00662
00663
00664 tbl[0].count++;
00665
00666 return true;
00667 }
00668
00669 static bool _removeSlot(Q_HASHARR *tbl, int idx) {
00670 if(tbl[idx].count == 0) {
00671 DEBUG("hasharr: BUG found.");
00672 return false;
00673 }
00674
00675 tbl[idx].count = 0;
00676
00677
00678 tbl[0].count--;
00679
00680 return true;
00681 }
00682
00683 static bool _removeData(Q_HASHARR *tbl, int idx) {
00684 if(tbl[idx].count == 0) {
00685 DEBUG("hasharr: BUG found.");
00686 return false;
00687 }
00688
00689 while(true) {
00690 int link = tbl[idx].link;
00691 _removeSlot(tbl, idx);
00692
00693 if(link == 0) break;
00694 idx = link;
00695 }
00696
00697 return true;
00698 }
00699
00700 #endif