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