cos-hash.c

   1 /* Copyright (C) 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 <stdlib.h>
  20 #include "cos.h"
  21 #include "cos-i.h"
  22 #include "concord-name.h"
  23 #include "cos-hash.h"
  24 #include "hash-i.h"
  25
  26 COS_Hash_Table
  27 cos_make_hash_table ()
  28 {
  29   return concord_make_hash_table (256);
  30 }
  31
  32 void
  33 cos_destroy_hash_table (COS_Hash_Table table)
  34 {
  35   size_t i;
  36
  37   for (i = 0; i < table->size; i++)
  38     {
  39       COS_Hash_Table_Entry entry = table->data[i];
  40
  41       if (entry.key != NULL)
  42         {
  43           cos_release_object (entry.key);
  44           cos_release_object (entry.value);
  45         }
  46     }
  47   concord_destroy_hash_table (table);
  48 }
  49
  50 unsigned long cos_symbol_hash_string (COS_String string);
  51
  52 /* #### for a 64-bit machine, we should substitute a prime just over 2^32 */
  53 #define GOOD_HASH 65599 /* prime number just over 2^16; Dragon book, p. 435 */
  54 #define HASH2(a,b)               (GOOD_HASH * (a)                     + (b))
  55 #define HASH3(a,b,c)             (GOOD_HASH * HASH2 (a,b)             + (c))
  56 #define HASH4(a,b,c,d)           (GOOD_HASH * HASH3 (a,b,c)           + (d))
  57 #define HASH5(a,b,c,d,e)         (GOOD_HASH * HASH4 (a,b,c,d)         + (e))
  58 #define HASH6(a,b,c,d,e,f)       (GOOD_HASH * HASH5 (a,b,c,d,e)       + (f))
  59 #define HASH7(a,b,c,d,e,f,g)     (GOOD_HASH * HASH6 (a,b,c,d,e,f)     + (g))
  60 #define HASH8(a,b,c,d,e,f,g,h)   (GOOD_HASH * HASH7 (a,b,c,d,e,f,g)   + (h))
  61 #define HASH9(a,b,c,d,e,f,g,h,i) (GOOD_HASH * HASH8 (a,b,c,d,e,f,g,h) + (i))
  62
  63 static size_t
  64 cos_hash_object0 (COS_object obj, int depth)
  65 {
  66   if ( obj == NULL )
  67     return 0;
  68   else if ( COS_OBJECT_INT_P (obj) )
  69     return cos_int_value (obj);
  70   else if ( COS_OBJECT_CHAR_P (obj) )
  71     return cos_char_id (obj);
  72   else if ( COS_OBJECT_STRING_P (obj) )
  73     return cos_symbol_hash_string (obj);
  74   else if ( COS_OBJECT_SYMBOL_P (obj) )
  75     return cos_symbol_hash_string (cos_symbol_name (obj));
  76   else if ( COS_OBJECT_CONS_P (obj) )
  77     {
  78       if ( depth > 5 )
  79         return 0;
  80       else
  81         return HASH2 (cos_hash_object0 (cos_car (obj), depth + 1),
  82                       cos_hash_object0 (cos_cdr (obj), depth + 1));
  83     }
  84
  85   return (size_t)obj;
  86 }
  87
  88 size_t
  89 cos_hash_object (COS_object obj)
  90 {
  91   return cos_hash_object0 (obj, 0);
  92 }
  93
  94 int
  95 cos_hash_table_put (COS_Hash_Table table,
  96                     COS_object key, COS_object value)
  97 {
  98   unsigned long i, index;
  99   COS_Hash_Table_Entry* entry;
 100
 101   if (table == NULL)
 102     return -1;
 103
 104   index = cos_hash_object (key) % table->size;
 105   for (i = index; i < table->size; i++)
 106     {
 107       entry = &table->data[i];
 108       if (entry->key == NULL)
 109         {
 110           cos_retain_object (key);
 111           cos_retain_object (value);
 112           entry->key = key;
 113           entry->value = value;
 114           return 0;
 115         }
 116       else if (entry->key == key)
 117         {
 118           cos_release_object (entry->value);
 119           cos_retain_object (value);
 120           entry->value = value;
 121           return 0;
 122         }
 123     }
 124   if (cos_hash_table_grow (table) == 0)
 125     return cos_hash_table_put (table, key, value);
 126   return -1;
 127 }
 128
 129 COS_object
 130 cos_hash_table_get (COS_Hash_Table table, COS_object key)
 131 {
 132   unsigned long i, index;
 133   COS_Hash_Table_Entry* entry;
 134
 135   if (table == NULL)
 136     return NULL;
 137
 138   index = cos_hash_object (key) % table->size;
 139   for (i = index; i < table->size; i++)
 140     {
 141       entry = &table->data[i];
 142       if (entry->key == NULL)
 143         return NULL;
 144       else if (entry->key == key)
 145         return entry->value;
 146     }
 147   return NULL;
 148 }
 149
 150 int
 151 cos_hash_table_grow (COS_Hash_Table table)
 152 {
 153   COS_Hash_Table new_table
 154     = concord_make_hash_table ( table->size * 2
 155                                 /* - (table->size * 4 / 5) */ );
 156   size_t i;
 157
 158   if (new_table == NULL)
 159     return -1;
 160
 161   for (i = 0; i < table->size; i++)
 162     {
 163       COS_Hash_Table_Entry* entry = &table->data[i];
 164
 165       if ( (entry->key != NULL) && (entry->value != NULL) )
 166         {
 167           int status
 168             = cos_hash_table_put (new_table, entry->key, entry->value);
 169
 170           if (status != 0)
 171             {
 172               concord_destroy_hash_table (new_table);
 173               return -1;
 174             }
 175         }
 176     }
 177   free (table->data);
 178   table->size = new_table->size;
 179   table->data = new_table->data;
 180   free (new_table);
 181   return 0;
 182 }