"Fossies" - the Fresh Open Source Software Archive

Member "redis-5.0.7/utils/hashtable/rehashing.c" (19 Nov 2019, 3504 Bytes) of package /linux/misc/redis-5.0.7.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "rehashing.c" see the Fossies "Dox" file reference documentation.

    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 }