name.c

   1 /* Copyright (C) 2003 MORIOKA Tomohiko
   2    This file is part of the CHISE Library.
   3
   4    The CHISE Library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Lesser General Public
   6    License as published by the Free Software Foundation; either
   7    version 2.1 of the License, or (at your option) any later version.
   8
   9    The CHISE Library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public
  15    License along with the CHISE Library; if not, write to the Free
  16    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  17    02111-1307 USA.  */
  18
  19 #include <string.h>
  20 #include <stdlib.h>
  21 #include "chise-name.h"
  22
  23 struct CHISE_HASH_TABLE_ENTRY
  24 {
  25   void *key;
  26   void *value;
  27 };
  28
  29 struct CHISE_HASH_TABLE
  30 {
  31   size_t size;
  32   CHISE_HASH_TABLE_ENTRY *data;
  33 };
  34
  35 CHISE_HASH_TABLE* chise_make_hash_table (size_t size);
  36 void chise_destroy_hash_table (CHISE_HASH_TABLE* hash);
  37 int chise_hash_c_string (const unsigned char *ptr);
  38
  39 CHISE_HASH_TABLE*
  40 chise_make_hash_table (size_t size)
  41 {
  42   CHISE_HASH_TABLE* hash
  43     = (CHISE_HASH_TABLE*)malloc (sizeof (CHISE_HASH_TABLE));
  44
  45   if (hash == NULL)
  46     return NULL;
  47
  48   hash->data
  49     = (CHISE_HASH_TABLE_ENTRY*) malloc (sizeof (CHISE_HASH_TABLE_ENTRY)
  50                                         * size);
  51   if (hash->data == NULL)
  52     {
  53       free (hash);
  54       return NULL;
  55     }
  56
  57   hash->size = size;
  58   memset (hash->data, 0, sizeof (CHISE_HASH_TABLE_ENTRY) * size);
  59   return hash;
  60 }
  61
  62 void
  63 chise_destroy_hash_table (CHISE_HASH_TABLE* hash)
  64 {
  65   if (hash == NULL)
  66     return;
  67   free (hash->data);
  68   free (hash);
  69 }
  70
  71
  72 /* derived from hashpjw, Dragon Book P436. */
  73 int
  74 chise_hash_c_string (const unsigned char *ptr)
  75 {
  76   int hash = 0;
  77
  78   while (*ptr != '\0')
  79     {
  80       int g;
  81       hash = (hash << 4) + *ptr++;
  82       g = hash & 0xf0000000;
  83       if (g)
  84         hash = (hash ^ (g >> 24)) ^ g;
  85     }
  86   return hash & 07777777777;
  87 }
  88
  89
  90 CHISE_NAME_TABLE*
  91 chise_make_name_table ()
  92 {
  93   return chise_make_hash_table (32);
  94 }
  95
  96 void
  97 chise_destroy_name_table (CHISE_NAME_TABLE* table)
  98 {
  99   chise_destroy_hash_table (table);
 100 }
 101
 102 int
 103 chise_name_table_put (CHISE_NAME_TABLE* table,
 104                       const unsigned char *key, void *value)
 105 {
 106   int i, index;
 107   CHISE_NAME_TABLE_ENTRY* entry;
 108
 109   if (table == NULL)
 110     return -1;
 111
 112   index = chise_hash_c_string (key) % table->size;
 113   for (i = index; i < table->size; i++)
 114     {
 115       entry = &table->data[i];
 116       if (entry->key == NULL)
 117         {
 118           size_t len = strlen (key);
 119
 120           entry->key = (unsigned char*)malloc (len + 1);
 121           if (entry->key == NULL)
 122             return -1;
 123           strcpy (entry->key, key);
 124           entry->value = value;
 125           return 0;
 126         }
 127       else if (strcmp (entry->key, key) == 0)
 128         {
 129           entry->value = value;
 130           return 0;
 131         }
 132     }
 133   if (chise_name_table_grow (table) == 0)
 134     return chise_name_table_put (table, key, value);
 135   return -1;
 136 }
 137
 138 void *
 139 chise_name_table_get (CHISE_NAME_TABLE* table,
 140                       const unsigned char *key)
 141 {
 142   int i, index;
 143   CHISE_NAME_TABLE_ENTRY entry;
 144
 145   if (table == NULL)
 146     return NULL;
 147
 148   index = chise_hash_c_string (key) % table->size;
 149   for (i = index; i < table->size; i++)
 150     {
 151       entry = table->data[i];
 152       if (entry.key == NULL)
 153         return NULL;
 154       else if (strcmp (entry.key, key) == 0)
 155         return entry.value;
 156     }
 157   return NULL;
 158 }
 159
 160 int
 161 chise_name_table_grow (CHISE_NAME_TABLE* table)
 162 {
 163   CHISE_NAME_TABLE *new_table
 164     = chise_make_hash_table (table->size * 2);
 165   int i;
 166
 167   if (new_table == NULL)
 168     return -1;
 169
 170   for (i = 0; i < table->size; i++)
 171     {
 172       CHISE_NAME_TABLE_ENTRY entry = table->data[i];
 173       if ( (entry.key != NULL) && (entry.value != NULL) )
 174         {
 175           int status
 176             = chise_name_table_put (new_table, entry.key, entry.value);
 177           if (status != 0)
 178             {
 179               chise_destroy_hash_table (new_table);
 180               return -1;
 181             }
 182         }
 183     }
 184   table->size = new_table->size;
 185   table->data = new_table->data;
 186   free (new_table);
 187   return 0;
 188 }