git.maemo.org Git - monky/blob - tests/test-hash.c

   1 /* ------------------------------------------------------
   2  * test-hash.c: unit testing for hash functions in hash.h
   3  * Philip Kovacs kovacsp3@comcast.net 2005
   4  *
   5  * $Id$
   6  * ------------------------------------------------------*/
   7
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11 #include "hash.h"
  12
  13 char *data[] = {
  14         "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
  15         "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen",
  16         "eighteen", "nineteen", "twenty", "twenty-one", "twenty-two", "twenty-three",
  17         "twenty-four", "twenty-five", "twenty-six", "twenty-seven", "twenty-eight",
  18         "twenty-nine", "thirty", "thirty-one", "thirty-two"
  19 };
  20
  21 /* Primary hash function is DJB with a 65521 prime modulus to govern the range. */
  22 unsigned int DJBHash(const char* str, unsigned int len)
  23 {
  24    unsigned int hash = 5381;
  25    unsigned int i    = 0;
  26
  27    for(i = 0; i < len; str++, i++)
  28    {
  29       hash = ((hash << 5) + hash) + (*str);
  30    }
  31
  32    return (hash & 0x7FFFFFFF) % 65521;
  33 }
  34
  35 /* Second hash function is DEK, modified to always return an odd number,
  36    as required for open-address hashing using double-hash probing and
  37    also with a 65521 prime modulus to govern the range. */
  38 unsigned int DEKHash(const char* str, unsigned int len)
  39 {
  40    unsigned int hash = len;
  41    unsigned int i    = 0;
  42
  43    for(i = 0; i < len; str++, i++)
  44    {
  45       hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
  46    }
  47    return (( hash & 0x7FFFFFFF ) % 65521 ) | 0x00000001;
  48 }
  49
  50 int hash_fun1( const void *p_data )
  51 {
  52    char *p_item = (char *)p_data;
  53
  54    return DJBHash( p_item, strlen(p_item) );
  55 }
  56
  57 int hash_fun2( const void *p_data )
  58 {
  59    char *p_item = (char *)p_data;
  60
  61    return DEKHash( p_item, strlen(p_item) );
  62 }
  63
  64 /* must return non-zero if a match */
  65 int match_fun( const void *p_data1, const void *p_data2 )
  66 {
  67    int l1,l2;
  68    char *p_item1, *p_item2;
  69
  70    p_item1 = (char *)p_data1;
  71    p_item2 = (char *)p_data2;
  72
  73    l1=strlen( p_item1 );
  74    l2=strlen( p_item2 );
  75
  76    return (l1==l2) && (strncmp( p_item1, p_item2, l1 ) == 0);
  77 }
  78
  79 int main()
  80 {
  81    int i,size,modulus;
  82    size=128;
  83    modulus=32;
  84
  85    hash_table_t hash;
  86
  87    printf("testing hash functions 1 and 2...\n");
  88    for ( i=0; i<31; i++ ) {
  89       printf("(func 1,func 2): hash of \"%s\" mod %d is (%d,%d)\n",
  90                 data[i], modulus, hash_fun1(data[i]) % modulus, hash_fun2(data[i]) % modulus );
  91    }
  92
  93    printf("creating hash table with %d positions...\n",size);
  94    if ( hash_create( &hash, size, &hash_fun1, &hash_fun2, &match_fun, NULL ) != 0 ) {
  95       fprintf(stderr,"error creating hash table!\n");
  96       exit(1);
  97    }
  98
  99    printf("testing that double-hashes can visit all slots...\n");
 100    for ( i=0; i<31; i++ ) {
 101       printf("inserting \"%s\" into hash...\n", data[i]); fflush(stdout);
 102       if ( hash_insert( &hash, data[i] ) != 0 ) {
 103          fprintf(stderr, "error inserting value!\n");
 104          exit(1);
 105       }
 106       printf("ok\n");
 107       printf("looking up \"%s\"...\n", data[i]); fflush(stdout);
 108       if ( hash_lookup( &hash, (void **)&data[i] ) != 0 ) {
 109          fprintf(stderr, "error looking up value!\n");
 110          exit(1);
 111       }
 112       printf("found\n");
 113       printf("hash size now %d, vacated slots %d\n",hash_size(&hash),hash.vacated);
 114    }
 115
 116    printf("removing all items from hash...\n");
 117    for ( i=0; i<31; i++ ) {
 118       printf("deleting \"%s\" from hash...\n", data[i]); fflush(stdout);
 119       if ( hash_remove( &hash, (void **)&data[i] ) != 0 ) {
 120          fprintf(stderr, "error deleting value!\n");
 121          exit(1);
 122       }
 123       printf("ok\n");
 124       printf("looking up \"%s\"...\n", data[i]); fflush(stdout);
 125       if ( hash_lookup( &hash, (void **)&data[i] ) != -1 ) {
 126          fprintf(stderr, "error: deleted value still found in hash!\n");
 127          exit(1);
 128       }
 129       printf("not found, good\n");
 130       printf("hash size now %d, vacated slots %d\n",hash_size(&hash),hash.vacated);
 131    }
 132
 133    printf("destroying hash table...\n");
 134    hash_destroy(&hash);
 135
 136    return 0;
 137 }