1 /* Copyright (C) 2013 MORIOKA Tomohiko
2 This file is part of the CONCORD Library.
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.
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.
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
22 #include "concord-name.h"
27 cos_make_hash_table ()
29 return concord_make_hash_table (256);
33 cos_destroy_hash_table (COS_Hash_Table table)
37 for (i = 0; i < table->size; i++)
39 COS_Hash_Table_Entry entry = table->data[i];
41 if (entry.key != NULL)
43 cos_release_object (entry.key);
44 cos_release_object (entry.value);
47 concord_destroy_hash_table (table);
50 unsigned long cos_symbol_hash_string (COS_String string);
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))
64 cos_hash_object0 (COS_object obj, int depth)
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) )
81 return HASH2 (cos_hash_object0 (cos_car (obj), depth + 1),
82 cos_hash_object0 (cos_cdr (obj), depth + 1));
89 cos_hash_object (COS_object obj)
91 return cos_hash_object0 (obj, 0);
95 cos_hash_table_put (COS_Hash_Table table,
96 COS_object key, COS_object value)
98 unsigned long i, index;
99 COS_Hash_Table_Entry* entry;
104 index = cos_hash_object (key) % table->size;
105 for (i = index; i < table->size; i++)
107 entry = &table->data[i];
108 if (entry->key == NULL)
110 cos_retain_object (key);
111 cos_retain_object (value);
113 entry->value = value;
116 else if (entry->key == key)
118 cos_release_object (entry->value);
119 cos_retain_object (value);
120 entry->value = value;
124 if (cos_hash_table_grow (table) == 0)
125 return cos_hash_table_put (table, key, value);
130 cos_hash_table_get (COS_Hash_Table table, COS_object key)
132 unsigned long i, index;
133 COS_Hash_Table_Entry* entry;
138 index = cos_hash_object (key) % table->size;
139 for (i = index; i < table->size; i++)
141 entry = &table->data[i];
142 if (entry->key == NULL)
144 else if (entry->key == key)
151 cos_hash_table_grow (COS_Hash_Table table)
153 COS_Hash_Table new_table
154 = concord_make_hash_table ( table->size * 2
155 /* - (table->size * 4 / 5) */ );
158 if (new_table == NULL)
161 for (i = 0; i < table->size; i++)
163 COS_Hash_Table_Entry* entry = &table->data[i];
165 if ( (entry->key != NULL) && (entry->value != NULL) )
168 = cos_hash_table_put (new_table, entry->key, entry->value);
172 concord_destroy_hash_table (new_table);
178 table->size = new_table->size;
179 table->data = new_table->data;