name.c

   1 #include <string.h>
   2
   3 typedef struct CHISE_HASH_TABLE_ENTRY
   4 {
   5   void *key;
   6   void *value;
   7 } CHISE_HASH_TABLE_ENTRY;
   8
   9 typedef struct CHISE_HASH_TABLE
  10 {
  11   size_t size;
  12   CHISE_HASH_TABLE_ENTRY *data;
  13 } CHISE_HASH_TABLE;
  14
  15 CHISE_HASH_TABLE*
  16 chise_make_hash_table (size_t size)
  17 {
  18   CHISE_HASH_TABLE* hash
  19     = (CHISE_HASH_TABLE*)malloc (sizeof (CHISE_HASH_TABLE));
  20
  21   if (hash == NULL)
  22     return NULL;
  23
  24   hash->data
  25     = (CHISE_HASH_TABLE_ENTRY*) malloc (sizeof (CHISE_HASH_TABLE_ENTRY)
  26                                         * size);
  27   if (hash->data == NULL)
  28     {
  29       free (hash);
  30       return NULL;
  31     }
  32
  33   hash->size = size;
  34   memset (hash->data, 0, sizeof (CHISE_HASH_TABLE_ENTRY) * size);
  35   return hash;
  36 }
  37
  38 void
  39 chise_destroy_hash_table (CHISE_HASH_TABLE* hash)
  40 {
  41   if (hash == NULL)
  42     return;
  43   free (hash->data);
  44   free (hash);
  45 }
  46
  47
  48 /* derived from hashpjw, Dragon Book P436. */
  49 int
  50 chise_hash_c_string (const unsigned char *ptr)
  51 {
  52   int hash = 0;
  53
  54   while (*ptr != '\0')
  55     {
  56       int g;
  57       hash = (hash << 4) + *ptr++;
  58       g = hash & 0xf0000000;
  59       if (g)
  60         hash = (hash ^ (g >> 24)) ^ g;
  61     }
  62   return hash & 07777777777;
  63 }
  64
  65
  66 typedef CHISE_HASH_TABLE CHISE_NAME_TABLE;
  67 typedef CHISE_HASH_TABLE_ENTRY CHISE_NAME_TABLE_ENTRY;
  68
  69 CHISE_NAME_TABLE*
  70 chise_make_name_table ()
  71 {
  72   return chise_make_hash_table (32);
  73 }
  74
  75 void
  76 chise_destroy_name_table (CHISE_NAME_TABLE* table)
  77 {
  78   chise_destroy_hash_table (table);
  79 }
  80
  81 int
  82 chise_name_table_put (CHISE_NAME_TABLE* table,
  83                       unsigned char *key, void *value)
  84 {
  85   int i, index;
  86   CHISE_NAME_TABLE_ENTRY* entry;
  87
  88   if (table == NULL)
  89     return -1;
  90
  91   index = chise_hash_c_string (key) % table->size;
  92   for (i = index; i < table->size; i++)
  93     {
  94       entry = &table->data[i];
  95       if (entry->key == NULL)
  96         {
  97           size_t len = strlen (key);
  98
  99           entry->key = (unsigned char*)malloc (len + 1);
 100           if (entry->key == NULL)
 101             return -1;
 102           strcpy (entry->key, key);
 103           entry->value = value;
 104           return 0;
 105         }
 106       else if (strcmp (entry->key, key) == 0)
 107         {
 108           entry->value = value;
 109           return 0;
 110         }
 111     }
 112   if (chise_name_table_grow (table) == 0)
 113     return chise_name_table_put (table, key, value);
 114   return -1;
 115 }
 116
 117 void *
 118 chise_name_table_get (CHISE_NAME_TABLE* table,
 119                       unsigned char *key)
 120 {
 121   int i, index;
 122   CHISE_NAME_TABLE_ENTRY entry;
 123
 124   if (table == NULL)
 125     return NULL;
 126
 127   index = chise_hash_c_string (key) % table->size;
 128   for (i = index; i < table->size; i++)
 129     {
 130       entry = table->data[i];
 131       if (entry.key == NULL)
 132         return NULL;
 133       else if (strcmp (entry.key, key) == 0)
 134         return entry.value;
 135     }
 136   return NULL;
 137 }
 138
 139 int
 140 chise_name_table_grow (CHISE_NAME_TABLE* table)
 141 {
 142   CHISE_NAME_TABLE *new_table
 143     = chise_make_hash_table (table->size * 2);
 144   int i;
 145
 146   if (new_table == NULL)
 147     return -1;
 148
 149   for (i = 0; i < table->size; i++)
 150     {
 151       CHISE_NAME_TABLE_ENTRY entry = table->data[i];
 152       if ( (entry.key != NULL) && (entry.value != NULL) )
 153         {
 154           int status
 155             = chise_name_table_put (new_table, entry.key, entry.value);
 156           if (status != 0)
 157             {
 158               chise_destroy_hash_table (new_table);
 159               return -1;
 160             }
 161         }
 162     }
 163   table->size = new_table->size;
 164   table->data = new_table->data;
 165   free (new_table);
 166   return 0;
 167 }