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 #include "hash-i.h"
  23
  24 CONCORD_HASH_TABLE*
  25 concord_make_hash_table (size_t size)
  26 {
  27   CONCORD_HASH_TABLE* hash
  28     = (CONCORD_HASH_TABLE*)malloc (sizeof (CONCORD_HASH_TABLE));
  29
  30   if (hash == NULL)
  31     return NULL;
  32
  33   hash->data
  34     = (CONCORD_HASH_TABLE_ENTRY*) malloc (sizeof (CONCORD_HASH_TABLE_ENTRY)
  35                                           * size);
  36   if (hash->data == NULL)
  37     {
  38       free (hash);
  39       return NULL;
  40     }
  41
  42   hash->size = size;
  43   memset (hash->data, 0, sizeof (CONCORD_HASH_TABLE_ENTRY) * size);
  44   return hash;
  45 }
  46
  47 void
  48 concord_destroy_hash_table (CONCORD_HASH_TABLE* table)
  49 {
  50   if (table == NULL)
  51     return;
  52   free (table->data);
  53   free (table);
  54 }
  55
  56
  57 /* derived from hashpjw, Dragon Book P436. */
  58 unsigned long
  59 concord_hash_c_string (const unsigned char *ptr)
  60 {
  61   unsigned long hash = 0;
  62
  63   while (*ptr != '\0')
  64     {
  65       unsigned long g;
  66       hash = (hash << 4) + *ptr++;
  67       g = hash & 0xf0000000;
  68       if (g)
  69         hash = (hash ^ (g >> 24)) ^ g;
  70     }
  71   return hash & 07777777777;
  72 }
  73
  74
  75 CONCORD_NAME_TABLE*
  76 concord_make_name_table ()
  77 {
  78   return concord_make_hash_table (256);
  79 }
  80
  81 void
  82 concord_destroy_name_table (CONCORD_NAME_TABLE* table)
  83 {
  84   int i;
  85
  86   for (i = 0; i < table->size; i++)
  87     {
  88       CONCORD_NAME_TABLE_ENTRY entry = table->data[i];
  89
  90       if (entry.key != NULL)
  91         {
  92           if (entry.value != NULL)
  93             free (entry.value);
  94           free (entry.key);
  95         }
  96     }
  97   concord_destroy_hash_table (table);
  98 }
  99
 100 int
 101 concord_name_table_put (CONCORD_NAME_TABLE* table,
 102                         const char *key, void *value)
 103 {
 104   int i, index;
 105   CONCORD_NAME_TABLE_ENTRY* entry;
 106
 107   if (table == NULL)
 108     return -1;
 109
 110   index = concord_hash_c_string ((unsigned char*)key) % table->size;
 111   for (i = index; i < table->size; i++)
 112     {
 113       entry = &table->data[i];
 114       if (entry->key == NULL)
 115         {
 116           size_t len = strlen (key);
 117
 118           entry->key = (unsigned char*)malloc (len + 1);
 119           if (entry->key == NULL)
 120             return -1;
 121           strcpy (entry->key, key);
 122           entry->value = value;
 123           return 0;
 124         }
 125       else if (strcmp (entry->key, key) == 0)
 126         {
 127           entry->value = value;
 128           return 0;
 129         }
 130     }
 131   if (concord_name_table_grow (table) == 0)
 132     return concord_name_table_put (table, key, value);
 133   return -1;
 134 }
 135
 136 void *
 137 concord_name_table_get (CONCORD_NAME_TABLE* table, const char *key)
 138 {
 139   int i, index;
 140   CONCORD_NAME_TABLE_ENTRY entry;
 141
 142   if (table == NULL)
 143     return NULL;
 144
 145   index = concord_hash_c_string ((unsigned char*)key) % table->size;
 146   for (i = index; i < table->size; i++)
 147     {
 148       entry = table->data[i];
 149       if (entry.key == NULL)
 150         return NULL;
 151       else if (strcmp (entry.key, key) == 0)
 152         return entry.value;
 153     }
 154   return NULL;
 155 }
 156
 157 int
 158 concord_name_table_grow (CONCORD_NAME_TABLE* table)
 159 {
 160   CONCORD_NAME_TABLE *new_table
 161     = concord_make_hash_table ( table->size * 2
 162                                 /* - (table->size * 4 / 5) */ );
 163   int i;
 164
 165   if (new_table == NULL)
 166     return -1;
 167
 168   for (i = 0; i < table->size; i++)
 169     {
 170       CONCORD_NAME_TABLE_ENTRY entry = table->data[i];
 171       if ( (entry.key != NULL) && (entry.value != NULL) )
 172         {
 173           int status
 174             = concord_name_table_put (new_table, entry.key, entry.value);
 175           if (status != 0)
 176             {
 177               concord_destroy_hash_table (new_table);
 178               return -1;
 179             }
 180         }
 181     }
 182   free (table->data);
 183   table->size = new_table->size;
 184   table->data = new_table->data;
 185   free (new_table);
 186   return 0;
 187 }