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