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
00030 #ifndef DISABLE_DATASTRUCTURE
00031
00032 #include <stdio.h>
00033 #include <stdlib.h>
00034 #include <stdbool.h>
00035 #include <string.h>
00036 #include "qDecoder.h"
00037 #include "qInternal.h"
00038
00039 static int _findEmpty(Q_HASHTBL *tbl, int startidx);
00040 static int _getIdx(Q_HASHTBL *tbl, const char *key, int hash);
00041 static bool _putData(Q_HASHTBL *tbl, int idx, int hash, const char *key, const void *value, int size, int count);
00042 static bool _removeData(Q_HASHTBL *tbl, int idx);
00043
00056 Q_HASHTBL *qHashtblInit(int max) {
00057 if(max <= 0) return NULL;
00058
00059 Q_HASHTBL *tbl = (Q_HASHTBL *)malloc(sizeof(Q_HASHTBL));
00060 if(tbl == NULL) return NULL;
00061
00062 memset((void *)tbl, 0, sizeof(Q_HASHTBL));
00063
00064 tbl->count = (int *)malloc(sizeof(int) * max);
00065 if(tbl->count != NULL) memset((void *)(tbl->count), 0, (sizeof(int) * max));
00066 tbl->hash = (int *)malloc(sizeof(int) * max);
00067 if(tbl->hash != NULL) memset((void *)(tbl->hash), 0, (sizeof(int) * max));
00068
00069 tbl->key = (char **)malloc(sizeof(char *) * max);
00070 if(tbl->key != NULL) memset((void *)(tbl->key), 0, (sizeof(char *) * max));
00071 tbl->value = (void **)malloc(sizeof(char *) * max);
00072 if(tbl->value != NULL) memset((void *)(tbl->value), 0, (sizeof(void *) * max));
00073 tbl->size = (int *)malloc(sizeof(int) * max);
00074 if(tbl->size != NULL) memset((void *)(tbl->size), 0, (sizeof(int) * max));
00075
00076 if(tbl->count == NULL || tbl->hash == NULL || tbl->key == NULL || tbl->value == NULL || tbl->size == NULL) {
00077 qHashtblFree(tbl);
00078 return NULL;
00079 }
00080
00081 tbl->max = max;
00082 return tbl;
00083 }
00084
00092 bool qHashtblFree(Q_HASHTBL *tbl) {
00093 if(tbl == NULL) return false;
00094
00095 int idx, num;
00096 for (idx = 0, num = 0; idx < tbl->max && num < tbl->num; idx++) {
00097 if (tbl->count[idx] == 0) continue;
00098 free(tbl->key[idx]);
00099 free(tbl->value[idx]);
00100
00101 num++;
00102 if(num >= tbl->num) break;
00103 }
00104
00105 if(tbl->count != NULL) free(tbl->count);
00106 if(tbl->hash != NULL) free(tbl->hash);
00107 if(tbl->key != NULL) free(tbl->key);
00108 if(tbl->value != NULL) free(tbl->value);
00109 if(tbl->size != NULL) free(tbl->size);
00110 free(tbl);
00111
00112 return true;
00113 }
00114
00125 bool qHashtblPut(Q_HASHTBL *tbl, const char *key, const void *value, int size) {
00126 if(tbl == NULL || key == NULL || value == NULL) return false;
00127
00128
00129 int hash = (int)qHashFnv32(tbl->max, key, strlen(key));
00130
00131
00132 if (tbl->count[hash] == 0) {
00133
00134 _putData(tbl, hash, hash, key, value, size, 1);
00135
00136 DEBUG("hashtbl: put(new) %s (idx=%d,hash=%d,tot=%d)", key, hash, hash, tbl->num);
00137 } else if (tbl->count[hash] > 0) {
00138
00139 int idx = _getIdx(tbl, key, hash);
00140 if (idx >= 0) {
00141
00142 qHashtblRemove(tbl, key);
00143 return qHashtblPut(tbl, key, value, size);
00144 } else {
00145
00146 int idx = _findEmpty(tbl, hash);
00147 if (idx < 0) return false;
00148
00149
00150 _putData(tbl, idx, hash, key, value, size, -1);
00151
00152
00153 tbl->count[hash]++;
00154
00155 DEBUG("hashtbl: put(col) %s (idx=%d,hash=%d,tot=%d)", key, idx, hash, tbl->num);
00156 }
00157 } else {
00158
00159 int idx = _findEmpty(tbl, hash);
00160 if (idx < 0) return false;
00161
00162
00163 _putData(tbl, idx, tbl->hash[hash], tbl->key[hash], tbl->value[hash], tbl->size[hash], tbl->count[hash]);
00164 _removeData(tbl, hash);
00165
00166
00167 _putData(tbl, hash, hash, key, value, size, 1);
00168
00169 DEBUG("hashtbl: put(swp) %s (idx=%d,hash=%d,tot=%d)", key, hash, hash, tbl->num);
00170 }
00171
00172 return true;
00173 }
00174
00184 bool qHashtblPutStr(Q_HASHTBL *tbl, const char *key, const char *value) {
00185 int size = (value != NULL) ? (strlen(value) + 1) : 0;
00186 return qHashtblPut(tbl, key, value, size);
00187 }
00188
00198 bool qHashtblPutInt(Q_HASHTBL *tbl, const char *key, const int value) {
00199 char data[10+1];
00200 sprintf(data, "%d", value);
00201 return qHashtblPut(tbl, key, data, strlen(data) + 1);
00202 }
00203
00216 void *qHashtblGet(Q_HASHTBL *tbl, const char *key, int *size) {
00217 if(tbl == NULL || key == NULL) return NULL;
00218
00219 int hash = (int)qHashFnv32(tbl->max, key, strlen(key));
00220 int idx = _getIdx(tbl, key, hash);
00221 if (idx < 0) return NULL;
00222
00223 void *value = (char *)malloc(tbl->size[idx]);
00224 memcpy(value, tbl->value[idx], tbl->size[idx]);
00225
00226 if(size != NULL) *size = tbl->size[idx];
00227 return value;
00228 }
00229
00241 char *qHashtblGetStr(Q_HASHTBL *tbl, const char *key) {
00242 return qHashtblGet(tbl, key, NULL);
00243 }
00244
00253 int qHashtblGetInt(Q_HASHTBL *tbl, const char *key) {
00254 char *data = qHashtblGet(tbl, key, NULL);
00255 if(data == NULL) return 0;
00256
00257 int value = atoi(data);
00258 free(data);
00259
00260 return value;
00261 }
00262
00283 const char *qHashtblGetFirstKey(Q_HASHTBL *tbl, int *idx) {
00284 if(idx != NULL) *idx = -1;
00285 return qHashtblGetNextKey(tbl, idx);
00286 }
00287
00299 const char *qHashtblGetNextKey(Q_HASHTBL *tbl, int *idx) {
00300 if(tbl == NULL || idx == NULL) return NULL;
00301
00302 for ((*idx)++; *idx < tbl->max; (*idx)++) {
00303 if (tbl->count[*idx] == 0) continue;
00304 return tbl->key[*idx];
00305 }
00306
00307 *idx = tbl->max;
00308 return NULL;
00309 }
00310
00319 bool qHashtblRemove(Q_HASHTBL *tbl, const char *key) {
00320 if(tbl == NULL || key == NULL) return false;
00321
00322 int hash = (int)qHashFnv32(tbl->max, key, strlen(key));
00323 int idx = _getIdx(tbl, key, hash);
00324 if (idx < 0) return false;
00325
00326 if (tbl->count[idx] == 1) {
00327
00328 _removeData(tbl, idx);
00329
00330 DEBUG("hashtbl: rem %s (idx=%d,tot=%d)", key, idx, tbl->num);
00331 } else if (tbl->count[idx] > 1) {
00332
00333 int idx2;
00334 for (idx2 = idx + 1; ; idx2++) {
00335 if (idx2 >= tbl->max) idx2 = 0;
00336 if (idx2 == idx) {
00337 DEBUG("hashtbl: BUG remove failed %s. dup not found.", key);
00338 return false;
00339 }
00340 if (tbl->count[idx2] == -1 && tbl->hash[idx2] == idx) break;
00341 }
00342
00343
00344 int backupcount = tbl->count[idx];
00345 _removeData(tbl, idx);
00346 _putData(tbl, idx, tbl->hash[idx2], tbl->key[idx2], tbl->value[idx2], tbl->size[idx2], backupcount - 1);
00347 _removeData(tbl, idx2);
00348
00349 DEBUG("hashtbl: rem(lead) %s (idx=%d,tot=%d)", key, idx, tbl->num);
00350 } else {
00351
00352 if(tbl->count[tbl->hash[idx]] <= 1) {
00353 DEBUG("hashtbl: BUG remove failed %s. counter of leading slot mismatch.", key);
00354 return false;
00355 }
00356 tbl->count[tbl->hash[idx]]--;
00357
00358
00359 _removeData(tbl, idx);
00360
00361 DEBUG("hashtbl: rem(dup) %s (idx=%d,tot=%d)", key, idx, tbl->num);
00362 }
00363
00364 return true;
00365 }
00366
00376 bool qHashtblPrint(Q_HASHTBL *tbl, FILE *out, bool showvalue) {
00377 if(tbl == NULL || out == NULL) return false;
00378
00379 int idx, num;
00380 for (idx = 0, num = 0; idx < tbl->max && num < tbl->num; idx++) {
00381 if (tbl->count[idx] == 0) continue;
00382 fprintf(out, "%s=%s (idx=%d,hash=%d,size=%d)\n", tbl->key[idx], (showvalue)?(char*)tbl->value[idx]:"_binary_", idx, tbl->hash[idx], tbl->size[idx]);
00383 num++;
00384 }
00385
00386 return true;
00387 }
00388
00398 bool qHashtblStatus(Q_HASHTBL *tbl, int *used, int *max) {
00399 if(tbl == NULL) return false;
00400
00401 if(used != NULL) *used = tbl->num;
00402 if(max != NULL) *max = tbl->max;
00403
00404 return true;
00405 }
00406
00408
00410
00411
00412 static int _findEmpty(Q_HASHTBL *tbl, int startidx) {
00413 if (startidx >= tbl->max) startidx = 0;
00414
00415 int idx = startidx;
00416 while (true) {
00417 if (tbl->count[idx] == 0) return idx;
00418
00419 idx++;
00420 if (idx >= tbl->max) idx = 0;
00421 if(idx == startidx) break;
00422 }
00423
00424 return -1;
00425 }
00426
00427 static int _getIdx(Q_HASHTBL *tbl, const char *key, int hash) {
00428 if (tbl->count[hash] > 0) {
00429 int count, idx;
00430 for (count = 0, idx = hash; count < tbl->count[hash]; ) {
00431
00432 while(true) {
00433 if (idx >= tbl->max) idx = 0;
00434
00435 if (tbl->count[idx] != 0 && tbl->hash[idx] == hash) {
00436
00437 count++;
00438 break;
00439 }
00440
00441 idx++;
00442 if(idx == hash) return -1;
00443 }
00444
00445
00446 if (!strcmp(tbl->key[idx], key)) return idx;
00447
00448 idx++;
00449 if (idx >= tbl->max) idx = 0;
00450 if(idx == hash) break;
00451 }
00452 }
00453
00454 return -1;
00455 }
00456
00457 static bool _putData(Q_HASHTBL *tbl, int idx, int hash, const char *key, const void *value, int size, int count) {
00458
00459 if(tbl->count[idx] != 0) return false;
00460
00461
00462 tbl->hash[idx] = hash;
00463 tbl->key[idx] = strdup(key);
00464 tbl->value[idx] = malloc(size);
00465 if(tbl->value[idx] == NULL) {
00466 free(tbl->key[idx]);
00467 return false;
00468 }
00469 memcpy(tbl->value[idx], value, size);
00470 tbl->size[idx] = size;
00471 tbl->count[idx] = count;
00472
00473
00474 tbl->num++;
00475
00476 return true;
00477 }
00478
00479 static bool _removeData(Q_HASHTBL *tbl, int idx) {
00480 if(tbl->count[idx] == 0) return false;
00481
00482 free(tbl->key[idx]);
00483 free(tbl->value[idx]);
00484 tbl->count[idx] = 0;
00485
00486
00487 tbl->num--;
00488
00489 return true;
00490 }
00491
00492 #endif