few comments on hash distribution added
authorJiri Kuthan <jiri@iptel.org>
Thu, 29 Aug 2002 18:22:49 +0000 (18:22 +0000)
committerJiri Kuthan <jiri@iptel.org>
Thu, 29 Aug 2002 18:22:49 +0000 (18:22 +0000)
hash_func.c

index f16d26f..5920be0 100644 (file)
@@ -111,15 +111,24 @@ int new_hash( str call_id, str cseq_nr )
                //hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
                hash_code+=ccitt_tab[*(cs+i)+123];
 
+       /* hash_code conditioning */
 #ifdef _BUG
+       /* not flat ... % 111b has shorter period than
+       & 111b by one and results in different distribution;
+          ( 7 % 7 == 0, 7 %7 == 1 )
+          % is used as a part of the hash function too, not only
+          for rounding; & is not flat; whoever comes up with
+          a nicer flat hash function which does not take
+          costly division is welcome; feel free to verify
+          distribution using hashtest()
+    */
        hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
 #endif
-       /* hash_code conditioning */
        hash_code=hash_code%(TABLE_ENTRIES-1)+1;
        return hash_code;
 }
 
-void hashtest_cycle( int hits[TABLE_ENTRIES], char *ip )
+void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
 {
        long int i,j,k, l;
        int  hashv;
@@ -151,20 +160,23 @@ int init_hash()
                        1<<10);
                LOG(L_WARN, "WARNING: use of %d entries may lead "
                        "to unflat distribution\n", TABLE_ENTRIES );
+       } else {
+               DBG("DEBUG: hash function initialized with optimum table size\n");
        }
        return 1;
 }
 
 void hashtest()
 {
-       int hits[TABLE_ENTRIES];
+       int hits[TABLE_ENTRIES+5];
        int i;
-       
+
+       init_hash();    
        memset( hits, 0, sizeof hits );
        hashtest_cycle( hits, "192.168.99.100" );
        hashtest_cycle( hits, "172.168.99.100" );
        hashtest_cycle( hits, "142.168.99.100" );
-       for (i=0; i<TABLE_ENTRIES; i++)
+       for (i=0; i<TABLE_ENTRIES+5; i++)
                printf("[%d. %d]\n", i, hits[i] );
        exit(0);
 }