1 #include "redis.h"
2 #include "dict.h"
3
_redisAssert(char * x,char * y,int l)4 void _redisAssert(char *x, char *y, int l) {
5 printf("ASSERT: %s %s %d\n",x,y,l);
6 exit(1);
7 }
8
dictKeyHash(const void * keyp)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
dictKeyCompare(void * privdata,const void * key1,const void * key2)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
showBuckets(dictht ht)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
show(dict * d)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
sortPointers(const void * a,const void * b)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
stressGetKeys(dict * d,int times,int * perfect_run,int * approx_run)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
main(void)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