name.c

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