(SIZEOF_INT): New macro.
[chise/concord.git] / name.c
1 /* Copyright (C) 2003,2004,2005,2006 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 "concord-name.h"
22
23 struct CONCORD_HASH_TABLE_ENTRY
24 {
25   void *key;
26   void *value;
27 };
28
29 struct CONCORD_HASH_TABLE
30 {
31   size_t size;
32   CONCORD_HASH_TABLE_ENTRY *data;
33 };
34
35 CONCORD_HASH_TABLE* concord_make_hash_table (size_t size);
36 void concord_destroy_hash_table (CONCORD_HASH_TABLE* hash);
37 unsigned long concord_hash_c_string (const unsigned char *ptr);
38
39 CONCORD_HASH_TABLE*
40 concord_make_hash_table (size_t size)
41 {
42   CONCORD_HASH_TABLE* hash
43     = (CONCORD_HASH_TABLE*)malloc (sizeof (CONCORD_HASH_TABLE));
44
45   if (hash == NULL)
46     return NULL;
47
48   hash->data
49     = (CONCORD_HASH_TABLE_ENTRY*) malloc (sizeof (CONCORD_HASH_TABLE_ENTRY)
50                                           * size);
51   if (hash->data == NULL)
52     {
53       free (hash);
54       return NULL;
55     }
56
57   hash->size = size;
58   memset (hash->data, 0, sizeof (CONCORD_HASH_TABLE_ENTRY) * size);
59   return hash;
60 }
61
62 void
63 concord_destroy_hash_table (CONCORD_HASH_TABLE* table)
64 {
65   if (table == NULL)
66     return;
67   free (table->data);
68   free (table);
69 }
70
71
72 /* derived from hashpjw, Dragon Book P436. */
73 unsigned long
74 concord_hash_c_string (const unsigned char *ptr)
75 {
76   unsigned long hash = 0;
77
78   while (*ptr != '\0')
79     {
80       unsigned long g;
81       hash = (hash << 4) + *ptr++;
82       g = hash & 0xf0000000;
83       if (g)
84         hash = (hash ^ (g >> 24)) ^ g;
85     }
86   return hash & 07777777777;
87 }
88
89
90 CONCORD_NAME_TABLE*
91 concord_make_name_table ()
92 {
93   return concord_make_hash_table (256);
94 }
95
96 void
97 concord_destroy_name_table (CONCORD_NAME_TABLE* table)
98 {
99   int i;
100
101   for (i = 0; i < table->size; i++)
102     {
103       CONCORD_NAME_TABLE_ENTRY entry = table->data[i];
104
105       if (entry.key != NULL)
106         {
107           if (entry.value != NULL)
108             free (entry.value);
109           free (entry.key);
110         }
111     }
112   concord_destroy_hash_table (table);
113 }
114
115 int
116 concord_name_table_put (CONCORD_NAME_TABLE* table,
117                         const char *key, void *value)
118 {
119   int i, index;
120   CONCORD_NAME_TABLE_ENTRY* entry;
121
122   if (table == NULL)
123     return -1;
124
125   index = concord_hash_c_string ((unsigned char*)key) % table->size;
126   for (i = index; i < table->size; i++)
127     {
128       entry = &table->data[i];
129       if (entry->key == NULL)
130         {
131           size_t len = strlen (key);
132
133           entry->key = (unsigned char*)malloc (len + 1);
134           if (entry->key == NULL)
135             return -1;
136           strcpy (entry->key, key);
137           entry->value = value;
138           return 0;
139         }
140       else if (strcmp (entry->key, key) == 0)
141         {
142           entry->value = value;
143           return 0;
144         }
145     }
146   if (concord_name_table_grow (table) == 0)
147     return concord_name_table_put (table, key, value);
148   return -1;
149 }
150
151 void *
152 concord_name_table_get (CONCORD_NAME_TABLE* table, const char *key)
153 {
154   int i, index;
155   CONCORD_NAME_TABLE_ENTRY entry;
156
157   if (table == NULL)
158     return NULL;
159
160   index = concord_hash_c_string ((unsigned char*)key) % table->size;
161   for (i = index; i < table->size; i++)
162     {
163       entry = table->data[i];
164       if (entry.key == NULL)
165         return NULL;
166       else if (strcmp (entry.key, key) == 0)
167         return entry.value;
168     }
169   return NULL;
170 }
171
172 int
173 concord_name_table_grow (CONCORD_NAME_TABLE* table)
174 {
175   CONCORD_NAME_TABLE *new_table
176     = concord_make_hash_table ( table->size * 2
177                                 /* - (table->size * 4 / 5) */ );
178   int i;
179
180   if (new_table == NULL)
181     return -1;
182
183   for (i = 0; i < table->size; i++)
184     {
185       CONCORD_NAME_TABLE_ENTRY entry = table->data[i];
186       if ( (entry.key != NULL) && (entry.value != NULL) )
187         {
188           int status
189             = concord_name_table_put (new_table, entry.key, entry.value);
190           if (status != 0)
191             {
192               concord_destroy_hash_table (new_table);
193               return -1;
194             }
195         }
196     }
197   table->size = new_table->size;
198   table->data = new_table->data;
199   free (new_table);
200   return 0;
201 }