1 /* Copyright (C) 2003,2004 MORIOKA Tomohiko
2 This file is part of the CHISE Library.
4 The CHISE 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 CHISE 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 CHISE Library; if not, write to the Free
16 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 #include "chise-name.h"
23 struct CHISE_HASH_TABLE_ENTRY
29 struct CHISE_HASH_TABLE
32 CHISE_HASH_TABLE_ENTRY *data;
35 CHISE_HASH_TABLE* chise_make_hash_table (size_t size);
36 void chise_destroy_hash_table (CHISE_HASH_TABLE* hash);
37 int chise_hash_c_string (const unsigned char *ptr);
40 chise_make_hash_table (size_t size)
42 CHISE_HASH_TABLE* hash
43 = (CHISE_HASH_TABLE*)malloc (sizeof (CHISE_HASH_TABLE));
49 = (CHISE_HASH_TABLE_ENTRY*) malloc (sizeof (CHISE_HASH_TABLE_ENTRY)
51 if (hash->data == NULL)
58 memset (hash->data, 0, sizeof (CHISE_HASH_TABLE_ENTRY) * size);
63 chise_destroy_hash_table (CHISE_HASH_TABLE* table)
72 /* derived from hashpjw, Dragon Book P436. */
74 chise_hash_c_string (const unsigned char *ptr)
81 hash = (hash << 4) + *ptr++;
82 g = hash & 0xf0000000;
84 hash = (hash ^ (g >> 24)) ^ g;
86 return hash & 07777777777;
91 chise_make_name_table ()
93 return chise_make_hash_table (256);
97 chise_destroy_name_table (CHISE_NAME_TABLE* table)
101 for (i = 0; i < table->size; i++)
103 CHISE_NAME_TABLE_ENTRY entry = table->data[i];
105 if (entry.key != NULL)
107 if (entry.value != NULL)
112 chise_destroy_hash_table (table);
116 chise_name_table_put (CHISE_NAME_TABLE* table,
117 const unsigned char *key, void *value)
120 CHISE_NAME_TABLE_ENTRY* entry;
125 index = chise_hash_c_string (key) % table->size;
126 for (i = index; i < table->size; i++)
128 entry = &table->data[i];
129 if (entry->key == NULL)
131 size_t len = strlen (key);
133 entry->key = (unsigned char*)malloc (len + 1);
134 if (entry->key == NULL)
136 strcpy (entry->key, key);
137 entry->value = value;
140 else if (strcmp (entry->key, key) == 0)
142 entry->value = value;
146 if (chise_name_table_grow (table) == 0)
147 return chise_name_table_put (table, key, value);
152 chise_name_table_get (CHISE_NAME_TABLE* table,
153 const unsigned char *key)
156 CHISE_NAME_TABLE_ENTRY entry;
161 index = chise_hash_c_string (key) % table->size;
162 for (i = index; i < table->size; i++)
164 entry = table->data[i];
165 if (entry.key == NULL)
167 else if (strcmp (entry.key, key) == 0)
174 chise_name_table_grow (CHISE_NAME_TABLE* table)
176 CHISE_NAME_TABLE *new_table
177 = chise_make_hash_table ( table->size * 2
178 /* - (table->size * 4 / 5) */ );
181 if (new_table == NULL)
184 for (i = 0; i < table->size; i++)
186 CHISE_NAME_TABLE_ENTRY entry = table->data[i];
187 if ( (entry.key != NULL) && (entry.value != NULL) )
190 = chise_name_table_put (new_table, entry.key, entry.value);
193 chise_destroy_hash_table (new_table);
198 table->size = new_table->size;
199 table->data = new_table->data;