1 #include "redis.h" 2 #include "dict.h" 3 4 void _redisAssert(char *x, char *y, int l) { 5 printf("ASSERT: %s %s %d\n",x,y,l); 6 exit(1); 7 } 8 9 unsigned int dictKeyHash(const void *keyp) { 10 unsigned long key = (unsigned long)keyp; 11 key = dictGenHashFunction(&key,sizeof(key)); 12 key += ~(key << 15); 13 key ^= (key >> 10); 14 key += (key << 3); 15 key ^= (key >> 6); 16 key += ~(key << 11); 17 key ^= (key >> 16); 18 return key; 19 } 20 21 int dictKeyCompare(void *privdata, const void *key1, const void *key2) { 22 unsigned long k1 = (unsigned long)key1; 23 unsigned long k2 = (unsigned long)key2; 24 return k1 == k2; 25 } 26 27 dictType dictTypeTest = { 28 dictKeyHash, /* hash function */ 29 NULL, /* key dup */ 30 NULL, /* val dup */ 31 dictKeyCompare, /* key compare */ 32 NULL, /* key destructor */ 33 NULL /* val destructor */ 34 }; 35 36 void showBuckets(dictht ht) { 37 if (ht.table == NULL) { 38 printf("NULL\n"); 39 } else { 40 int j; 41 for (j = 0; j < ht.size; j++) { 42 printf("%c", ht.table[j] ? '1' : '0'); 43 } 44 printf("\n"); 45 } 46 } 47 48 void show(dict *d) { 49 int j; 50 if (d->rehashidx != -1) { 51 printf("rhidx: "); 52 for (j = 0; j < d->rehashidx; j++) 53 printf("."); 54 printf("|\n"); 55 } 56 printf("ht[0]: "); 57 showBuckets(d->ht[0]); 58 printf("ht[1]: "); 59 showBuckets(d->ht[1]); 60 printf("\n"); 61 } 62 63 int sortPointers(const void *a, const void *b) { 64 unsigned long la, lb; 65 66 la = (long) (*((dictEntry**)a)); 67 lb = (long) (*((dictEntry**)b)); 68 return la-lb; 69 } 70 71 void stressGetKeys(dict *d, int times, int *perfect_run, int *approx_run) { 72 int j; 73 74 dictEntry **des = zmalloc(sizeof(dictEntry*)*dictSize(d)); 75 for (j = 0; j < times; j++) { 76 int requested = rand() % (dictSize(d)+1); 77 int returned = dictGetSomeKeys(d, des, requested); 78 int dup = 0; 79 80 qsort(des,returned,sizeof(dictEntry*),sortPointers); 81 if (returned > 1) { 82 int i; 83 for (i = 0; i < returned-1; i++) { 84 if (des[i] == des[i+1]) dup++; 85 } 86 } 87 88 if (requested == returned && dup == 0) { 89 (*perfect_run)++; 90 } else { 91 (*approx_run)++; 92 printf("Requested, returned, duplicated: %d %d %d\n", 93 requested, returned, dup); 94 } 95 } 96 zfree(des); 97 } 98 99 #define MAX1 120 100 #define MAX2 1000 101 int main(void) { 102 dict *d = dictCreate(&dictTypeTest,NULL); 103 unsigned long i; 104 srand(time(NULL)); 105 106 for (i = 0; i < MAX1; i++) { 107 dictAdd(d,(void*)i,NULL); 108 show(d); 109 } 110 printf("Size: %d\n", (int)dictSize(d)); 111 112 for (i = 0; i < MAX1; i++) { 113 dictDelete(d,(void*)i); 114 dictResize(d); 115 show(d); 116 } 117 dictRelease(d); 118 119 d = dictCreate(&dictTypeTest,NULL); 120 121 printf("Stress testing dictGetSomeKeys\n"); 122 int perfect_run = 0, approx_run = 0; 123 124 for (i = 0; i < MAX2; i++) { 125 dictAdd(d,(void*)i,NULL); 126 stressGetKeys(d,100,&perfect_run,&approx_run); 127 } 128 129 for (i = 0; i < MAX2; i++) { 130 dictDelete(d,(void*)i); 131 dictResize(d); 132 stressGetKeys(d,100,&perfect_run,&approx_run); 133 } 134 135 printf("dictGetSomeKey, %d perfect runs, %d approximated runs\n", 136 perfect_run, approx_run); 137 138 dictRelease(d); 139 140 printf("TEST PASSED!\n"); 141 return 0; 142 } 143