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