name.c

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