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