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