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 NULL /* allow to expand */
35 };
36
showBuckets(dictht ht)37 void showBuckets(dictht ht) {
38 if (ht.table == NULL) {
39 printf("NULL\n");
40 } else {
41 int j;
42 for (j = 0; j < ht.size; j++) {
43 printf("%c", ht.table[j] ? '1' : '0');
44 }
45 printf("\n");
46 }
47 }
48
show(dict * d)49 void show(dict *d) {
50 int j;
51 if (d->rehashidx != -1) {
52 printf("rhidx: ");
53 for (j = 0; j < d->rehashidx; j++)
54 printf(".");
55 printf("|\n");
56 }
57 printf("ht[0]: ");
58 showBuckets(d->ht[0]);
59 printf("ht[1]: ");
60 showBuckets(d->ht[1]);
61 printf("\n");
62 }
63
sortPointers(const void * a,const void * b)64 int sortPointers(const void *a, const void *b) {
65 unsigned long la, lb;
66
67 la = (long) (*((dictEntry**)a));
68 lb = (long) (*((dictEntry**)b));
69 return la-lb;
70 }
71
stressGetKeys(dict * d,int times,int * perfect_run,int * approx_run)72 void stressGetKeys(dict *d, int times, int *perfect_run, int *approx_run) {
73 int j;
74
75 dictEntry **des = zmalloc(sizeof(dictEntry*)*dictSize(d));
76 for (j = 0; j < times; j++) {
77 int requested = rand() % (dictSize(d)+1);
78 int returned = dictGetSomeKeys(d, des, requested);
79 int dup = 0;
80
81 qsort(des,returned,sizeof(dictEntry*),sortPointers);
82 if (returned > 1) {
83 int i;
84 for (i = 0; i < returned-1; i++) {
85 if (des[i] == des[i+1]) dup++;
86 }
87 }
88
89 if (requested == returned && dup == 0) {
90 (*perfect_run)++;
91 } else {
92 (*approx_run)++;
93 printf("Requested, returned, duplicated: %d %d %d\n",
94 requested, returned, dup);
95 }
96 }
97 zfree(des);
98 }
99
100 #define MAX1 120
101 #define MAX2 1000
main(void)102 int main(void) {
103 dict *d = dictCreate(&dictTypeTest,NULL);
104 unsigned long i;
105 srand(time(NULL));
106
107 for (i = 0; i < MAX1; i++) {
108 dictAdd(d,(void*)i,NULL);
109 show(d);
110 }
111 printf("Size: %d\n", (int)dictSize(d));
112
113 for (i = 0; i < MAX1; i++) {
114 dictDelete(d,(void*)i);
115 dictResize(d);
116 show(d);
117 }
118 dictRelease(d);
119
120 d = dictCreate(&dictTypeTest,NULL);
121
122 printf("Stress testing dictGetSomeKeys\n");
123 int perfect_run = 0, approx_run = 0;
124
125 for (i = 0; i < MAX2; i++) {
126 dictAdd(d,(void*)i,NULL);
127 stressGetKeys(d,100,&perfect_run,&approx_run);
128 }
129
130 for (i = 0; i < MAX2; i++) {
131 dictDelete(d,(void*)i);
132 dictResize(d);
133 stressGetKeys(d,100,&perfect_run,&approx_run);
134 }
135
136 printf("dictGetSomeKey, %d perfect runs, %d approximated runs\n",
137 perfect_run, approx_run);
138
139 dictRelease(d);
140
141 printf("TEST PASSED!\n");
142 return 0;
143 }
144