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 int
  96 cos_symbol_p (COS_object obj)
  97 {
  98   return COS_OBJECT_SYMBOL_P (obj);
  99 }
 100
 101 COS_Symbol
 102 cos_symbol_table_intern (COS_Symbol_Table table, COS_object name)
 103 {
 104   unsigned char* key;
 105   COS_String key_string;
 106   unsigned long i, index;
 107   COS_Symbol entry;
 108
 109   if (table == NULL)
 110     return NULL;
 111
 112   if (COS_OBJECT_C_STRING_P (name))
 113     {
 114       key_string = cos_build_string ((char*)name);
 115     }
 116   else
 117     {
 118       key_string = (COS_String)name;
 119     }
 120   key = key_string->data;
 121   index = cos_symbol_hash_string (key_string) % table->size;
 122   for (i = index; i < table->size; i++)
 123     {
 124       entry = table->data[i];
 125       if (entry == NULL)
 126         {
 127           entry = cos_make_symbol (key_string);
 128           cos_retain_object ((COS_object)entry);
 129           table->data[i] = entry;
 130           return entry;
 131         }
 132       else if ( COS_OBJECT_SYMBOL_P (entry)
 133                 && COS_OBJECT_STRING_P (entry->name)
 134                 && (entry->name->size == key_string->size)
 135                 && (memcmp (entry->name->data,
 136                             key_string->data, key_string->size) == 0) )
 137         {
 138           cos_retain_object ((COS_object)entry);
 139           return entry;
 140         }
 141     }
 142   if (cos_symbol_table_grow (table) == 0)
 143     return cos_symbol_table_intern (table, key_string);
 144   return NULL;
 145 }
 146
 147 COS_String
 148 cos_symbol_name (COS_Symbol symbol)
 149 {
 150   return symbol->name;
 151 }
 152
 153
 154 COS_Symbol_Table cos_make_symbol_table_0 (size_t size);
 155 void cos_destroy_symbol_table_0 (COS_Symbol_Table hash);
 156
 157
 158 /* derived from hashpjw, Dragon Book P436. */
 159 unsigned long
 160 cos_hash_c_string_n (const unsigned char *ptr, size_t size)
 161 {
 162   unsigned long hash = 0;
 163   int i;
 164
 165   for ( i = 0; i < size; i++ )
 166     {
 167       unsigned long g;
 168       hash = (hash << 4) + ptr[i];
 169       g = hash & 0xf0000000;
 170       if (g)
 171         hash = (hash ^ (g >> 24)) ^ g;
 172     }
 173   return hash & 07777777777;
 174 }
 175
 176 unsigned long
 177 cos_symbol_hash_string (COS_String string)
 178 {
 179   return cos_hash_c_string_n (string->data, string->size);
 180 }
 181
 182
 183 COS_Symbol_Table
 184 cos_make_symbol_table_0 (size_t size)
 185 {
 186   COS_Symbol_Table hash
 187     = (COS_Symbol_Table)malloc (sizeof (COS_Symbol_Table_ent));
 188
 189   if (hash == NULL)
 190     return NULL;
 191
 192   hash->data
 193     = (COS_Symbol*) malloc (sizeof (COS_Symbol) * size);
 194   if (hash->data == NULL)
 195     {
 196       free (hash);
 197       return NULL;
 198     }
 199
 200   hash->size = size;
 201   memset (hash->data, 0, sizeof (COS_Symbol) * size);
 202   return hash;
 203 }
 204
 205 void
 206 cos_destroy_symbol_table_0 (COS_Symbol_Table table)
 207 {
 208   if (table == NULL)
 209     return;
 210   free (table->data);
 211   free (table);
 212 }
 213
 214
 215 COS_Symbol_Table
 216 cos_make_symbol_table ()
 217 {
 218   return cos_make_symbol_table_0 (2 /* 256 */);
 219 }
 220
 221 void
 222 cos_destroy_symbol_table (COS_Symbol_Table table)
 223 {
 224   int i;
 225
 226   for (i = 0; i < table->size; i++)
 227     {
 228       COS_Symbol entry = table->data[i];
 229
 230       if (entry != NULL)
 231         {
 232           if (entry->name != NULL)
 233             cos_release_object (entry->name);
 234           if (entry->value != NULL)
 235             cos_release_object (entry->value);
 236           free (entry);
 237         }
 238     }
 239   cos_destroy_symbol_table_0 (table);
 240 }
 241
 242 COS_Symbol
 243 cos_intern (COS_object name)
 244 {
 245   if (cos_default_symbol_table == NULL)
 246     {
 247       cos_default_symbol_table = cos_make_symbol_table();
 248       cos_symbol_table_set (cos_default_symbol_table, cos_Qnil);
 249       cos_symbol_table_set (cos_default_symbol_table, cos_Qt);
 250     }
 251   return cos_symbol_table_intern (cos_default_symbol_table, name);
 252 }
 253
 254 int
 255 cos_symbol_table_set (COS_Symbol_Table table, COS_Symbol symbol)
 256 {
 257   int i, index;
 258   COS_Symbol entry;
 259
 260   if (table == NULL)
 261     return -1;
 262
 263   index = cos_symbol_hash_string (symbol->name) % table->size;
 264   for (i = index; i < table->size; i++)
 265     {
 266       entry = table->data[i];
 267       if (entry == NULL)
 268         {
 269           entry = symbol;
 270           cos_retain_object ((COS_object)entry);
 271           table->data[i] = entry;
 272           return 0;
 273         }
 274       else if (entry == symbol)
 275         {
 276           return 0;
 277         }
 278     }
 279   if (cos_symbol_table_grow (table) == 0)
 280     return cos_symbol_table_set (table, symbol);
 281   return -1;
 282 }
 283
 284 int
 285 cos_print_symbol_table (COS_Symbol_Table table)
 286 {
 287   int i;
 288   COS_Symbol entry;
 289
 290   if (table == NULL)
 291     table = cos_default_symbol_table;
 292
 293   printf ("#[symbol_table %lX\tsize = %d", table->size);
 294   for (i = 0; i < table->size; i++)
 295     {
 296       entry = table->data[i];
 297       printf ("\n\t%d : ", i);
 298       cos_print_object (entry);
 299     }
 300   printf ("\t]\n");
 301   return 0;
 302 }
 303
 304 int
 305 cos_symbol_table_grow (COS_Symbol_Table table)
 306 {
 307   COS_Symbol_Table new_table
 308     = cos_make_symbol_table_0 ( table->size * 2
 309                                 /* - (table->size * 4 / 5) */ );
 310   int i;
 311
 312   if (new_table == NULL)
 313     return -1;
 314
 315   //printf ("\n(old table is ");
 316   //cos_print_symbol_table (table);
 317   for (i = 0; i < table->size; i++)
 318     {
 319       COS_Symbol entry = table->data[i];
 320
 321       if (entry != NULL)
 322         {
 323           int status = cos_symbol_table_set (new_table, entry);
 324
 325           if (status != 0)
 326             {
 327               cos_destroy_symbol_table_0 (new_table);
 328               return -1;
 329             }
 330         }
 331     }
 332   free (table->data);
 333   table->size = new_table->size;
 334   table->data = new_table->data;
 335   free (new_table);
 336   //printf ("\t)\n(new table is ");
 337   //cos_print_symbol_table (table);
 338   //printf ("\t)\n");
 339   return 0;
 340 }