name.c

   1 /* Copyright (C) 2003, 2004, 2005, 2006, 2013 MORIOKA Tomohiko
   2    This file is part of the CONCORD Library.
   3
   4    The CONCORD 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 CONCORD 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 CONCORD 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 "concord-name.h"
  22
  23 struct CONCORD_HASH_TABLE_ENTRY
  24 {
  25   void *key;
  26   void *value;
  27 };
  28
  29 struct CONCORD_HASH_TABLE
  30 {
  31   size_t size;
  32   CONCORD_HASH_TABLE_ENTRY *data;
  33 };
  34
  35 CONCORD_HASH_TABLE* concord_make_hash_table (size_t size);
  36 void concord_destroy_hash_table (CONCORD_HASH_TABLE* hash);
  37 unsigned long concord_hash_c_string (const unsigned char *ptr);
  38
  39 CONCORD_HASH_TABLE*
  40 concord_make_hash_table (size_t size)
  41 {
  42   CONCORD_HASH_TABLE* hash
  43     = (CONCORD_HASH_TABLE*)malloc (sizeof (CONCORD_HASH_TABLE));
  44
  45   if (hash == NULL)
  46     return NULL;
  47
  48   hash->data
  49     = (CONCORD_HASH_TABLE_ENTRY*) malloc (sizeof (CONCORD_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 (CONCORD_HASH_TABLE_ENTRY) * size);
  59   return hash;
  60 }
  61
  62 void
  63 concord_destroy_hash_table (CONCORD_HASH_TABLE* table)
  64 {
  65   if (table == NULL)
  66     return;
  67   free (table->data);
  68   free (table);
  69 }
  70
  71
  72 /* derived from hashpjw, Dragon Book P436. */
  73 unsigned long
  74 concord_hash_c_string (const unsigned char *ptr)
  75 {
  76   unsigned long hash = 0;
  77
  78   while (*ptr != '\0')
  79     {
  80       unsigned long 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 CONCORD_NAME_TABLE*
  91 concord_make_name_table ()
  92 {
  93   return concord_make_hash_table (256);
  94 }
  95
  96 void
  97 concord_destroy_name_table (CONCORD_NAME_TABLE* table)
  98 {
  99   int i;
 100
 101   for (i = 0; i < table->size; i++)
 102     {
 103       CONCORD_NAME_TABLE_ENTRY entry = table->data[i];
 104
 105       if (entry.key != NULL)
 106         {
 107           if (entry.value != NULL)
 108             free (entry.value);
 109           free (entry.key);
 110         }
 111     }
 112   concord_destroy_hash_table (table);
 113 }
 114
 115 int
 116 concord_name_table_put (CONCORD_NAME_TABLE* table,
 117                         const char *key, void *value)
 118 {
 119   int i, index;
 120   CONCORD_NAME_TABLE_ENTRY* entry;
 121
 122   if (table == NULL)
 123     return -1;
 124
 125   index = concord_hash_c_string ((unsigned char*)key) % table->size;
 126   for (i = index; i < table->size; i++)
 127     {
 128       entry = &table->data[i];
 129       if (entry->key == NULL)
 130         {
 131           size_t len = strlen (key);
 132
 133           entry->key = (unsigned char*)malloc (len + 1);
 134           if (entry->key == NULL)
 135             return -1;
 136           strcpy (entry->key, key);
 137           entry->value = value;
 138           return 0;
 139         }
 140       else if (strcmp (entry->key, key) == 0)
 141         {
 142           entry->value = value;
 143           return 0;
 144         }
 145     }
 146   if (concord_name_table_grow (table) == 0)
 147     return concord_name_table_put (table, key, value);
 148   return -1;
 149 }
 150
 151 void *
 152 concord_name_table_get (CONCORD_NAME_TABLE* table, const char *key)
 153 {
 154   int i, index;
 155   CONCORD_NAME_TABLE_ENTRY entry;
 156
 157   if (table == NULL)
 158     return NULL;
 159
 160   index = concord_hash_c_string ((unsigned char*)key) % table->size;
 161   for (i = index; i < table->size; i++)
 162     {
 163       entry = table->data[i];
 164       if (entry.key == NULL)
 165         return NULL;
 166       else if (strcmp (entry.key, key) == 0)
 167         return entry.value;
 168     }
 169   return NULL;
 170 }
 171
 172 int
 173 concord_name_table_grow (CONCORD_NAME_TABLE* table)
 174 {
 175   CONCORD_NAME_TABLE *new_table
 176     = concord_make_hash_table ( table->size * 2
 177                                 /* - (table->size * 4 / 5) */ );
 178   int i;
 179
 180   if (new_table == NULL)
 181     return -1;
 182
 183   for (i = 0; i < table->size; i++)
 184     {
 185       CONCORD_NAME_TABLE_ENTRY entry = table->data[i];
 186       if ( (entry.key != NULL) && (entry.value != NULL) )
 187         {
 188           int status
 189             = concord_name_table_put (new_table, entry.key, entry.value);
 190           if (status != 0)
 191             {
 192               concord_destroy_hash_table (new_table);
 193               return -1;
 194             }
 195         }
 196     }
 197   table->size = new_table->size;
 198   table->data = new_table->data;
 199   free (new_table);
 200   return 0;
 201 }