symbol.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 "cos-i.h"
  22
  23 unsigned long concord_hash_c_string (const unsigned char *ptr);
  24 unsigned long cos_hash_c_string_n (const unsigned char *ptr, size_t size);
  25 unsigned long cos_symbol_hash_string (COS_String string);
  26
  27
  28 COS_Symbol
  29 cos_make_symbol (COS_String string)
  30 {
  31   COS_Symbol obj = COS_ALLOCATE_OBJECT (Symbol);
  32
  33   if (obj == NULL)
  34     return NULL;
  35
  36   obj->name = string;
  37   obj->value = NULL;
  38   return obj;
  39 }
  40
  41 int
  42 cos_release_symbol (COS_Object obj)
  43 {
  44   if (obj == NULL)
  45     return 0;
  46
  47   if ( ((COS_Symbol)obj)->value != NULL)
  48     cos_release_object (((COS_Symbol)obj)->value);
  49
  50   cos_release_object (((COS_Symbol)obj)->name);
  51   free (obj);
  52   return 0;
  53 }
  54
  55 COS_Symbol
  56 cos_symbol_table_intern (COS_Symbol_Table table, COS_object name)
  57 {
  58   unsigned char* key;
  59   COS_String key_string;
  60   unsigned long i, index;
  61   COS_Symbol entry;
  62
  63   if (table == NULL)
  64     return NULL;
  65
  66   if (COS_OBJECT_C_STRING_P (name))
  67     {
  68       key_string = cos_build_string ((char*)name);
  69     }
  70   else
  71     {
  72       key_string = (COS_String)name;
  73     }
  74   key = key_string->data;
  75   index = cos_symbol_hash_string (key_string) % table->size;
  76   for (i = index; i < table->size; i++)
  77     {
  78       entry = table->data[i];
  79       if (entry == NULL)
  80         {
  81           entry = cos_make_symbol (key_string);
  82           cos_retain_object ((COS_object)entry);
  83           table->data[i] = entry;
  84           return entry;
  85         }
  86       else if ( (entry->name->size == key_string->size)
  87                 && (memcmp (entry->name->data,
  88                             key_string->data, key_string->size) == 0) )
  89         {
  90           return entry;
  91         }
  92     }
  93   if (cos_symbol_table_grow (table) == 0)
  94     return cos_symbol_table_intern (table, key_string);
  95   return NULL;
  96 }
  97
  98 COS_String
  99 cos_symbol_name (COS_Symbol symbol)
 100 {
 101   return symbol->name;
 102 }
 103
 104
 105 COS_Symbol_Table cos_default_symbol_table = NULL;
 106
 107 COS_Symbol_Table cos_make_symbol_table_0 (size_t size);
 108 void cos_destroy_symbol_table_0 (COS_Symbol_Table hash);
 109
 110
 111 /* derived from hashpjw, Dragon Book P436. */
 112 unsigned long
 113 cos_hash_c_string_n (const unsigned char *ptr, size_t size)
 114 {
 115   unsigned long hash = 0;
 116   int i;
 117
 118   for ( i = 0; i < size; i++ )
 119     {
 120       unsigned long g;
 121       hash = (hash << 4) + ptr[i];
 122       g = hash & 0xf0000000;
 123       if (g)
 124         hash = (hash ^ (g >> 24)) ^ g;
 125     }
 126   return hash & 07777777777;
 127 }
 128
 129 unsigned long
 130 cos_symbol_hash_string (COS_String string)
 131 {
 132   return cos_hash_c_string_n (string->data, string->size);
 133 }
 134
 135
 136 COS_Symbol_Table
 137 cos_make_symbol_table_0 (size_t size)
 138 {
 139   COS_Symbol_Table hash
 140     = (COS_Symbol_Table)malloc (sizeof (COS_Symbol_Table_ent));
 141
 142   if (hash == NULL)
 143     return NULL;
 144
 145   hash->data
 146     = (COS_Symbol*) malloc (sizeof (COS_Symbol) * size);
 147   if (hash->data == NULL)
 148     {
 149       free (hash);
 150       return NULL;
 151     }
 152
 153   hash->size = size;
 154   memset (hash->data, 0, sizeof (COS_Symbol) * size);
 155   return hash;
 156 }
 157
 158 void
 159 cos_destroy_symbol_table_0 (COS_Symbol_Table table)
 160 {
 161   if (table == NULL)
 162     return;
 163   free (table->data);
 164   free (table);
 165 }
 166
 167
 168 COS_Symbol_Table
 169 cos_make_symbol_table ()
 170 {
 171   return cos_make_symbol_table_0 (2 /* 256 */);
 172 }
 173
 174 void
 175 cos_destroy_symbol_table (COS_Symbol_Table table)
 176 {
 177   int i;
 178
 179   for (i = 0; i < table->size; i++)
 180     {
 181       COS_Symbol entry = table->data[i];
 182
 183       if (entry != NULL)
 184         {
 185           if (entry->name != NULL)
 186             cos_release_object (entry->name);
 187           if (entry->value != NULL)
 188             cos_release_object (entry->value);
 189           free (entry);
 190         }
 191     }
 192   cos_destroy_symbol_table_0 (table);
 193 }
 194
 195 COS_Symbol
 196 cos_intern (COS_object name)
 197 {
 198   if (cos_default_symbol_table == NULL)
 199     cos_default_symbol_table = cos_make_symbol_table();
 200
 201   return cos_symbol_table_intern (cos_default_symbol_table, name);
 202 }
 203
 204 int
 205 cos_symbol_table_set (COS_Symbol_Table table, COS_Symbol symbol)
 206 {
 207   int i, index;
 208   COS_Symbol entry;
 209
 210   if (table == NULL)
 211     return -1;
 212
 213   index = cos_symbol_hash_string (symbol->name) % table->size;
 214   for (i = index; i < table->size; i++)
 215     {
 216       entry = table->data[i];
 217       if (entry == NULL)
 218         {
 219           entry = symbol;
 220           cos_retain_object ((COS_object)entry);
 221           table->data[i] = entry;
 222           return 0;
 223         }
 224       else if (entry == symbol)
 225         {
 226           return 0;
 227         }
 228     }
 229   if (cos_symbol_table_grow (table) == 0)
 230     return cos_symbol_table_set (table, symbol);
 231   return -1;
 232 }
 233
 234 int
 235 cos_symbol_table_grow (COS_Symbol_Table table)
 236 {
 237   COS_Symbol_Table new_table
 238     = cos_make_symbol_table_0 ( table->size * 2
 239                                 /* - (table->size * 4 / 5) */ );
 240   int i;
 241
 242   if (new_table == NULL)
 243     return -1;
 244
 245   for (i = 0; i < table->size; i++)
 246     {
 247       COS_Symbol entry = table->data[i];
 248
 249       if (entry != NULL)
 250         {
 251           int status = cos_symbol_table_set (new_table, entry);
 252
 253           if (status != 0)
 254             {
 255               cos_destroy_symbol_table_0 (new_table);
 256               return -1;
 257             }
 258         }
 259     }
 260   table->size = new_table->size;
 261   table->data = new_table->data;
 262   free (new_table);
 263   return 0;
 264 }