Mercurial > hg > early-roguelike

comparison urogue/dict.c @ 256:c495a4f288c6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import UltraRogue from the Roguelike Restoration Project (r1490)
author John "Elwin" Edwards
date Tue, 31 Jan 2017 19:56:04 -0500
parents
children 13b482bd9e66
comparison
equal deleted inserted replaced
253:d9badb9c0179 256:c495a4f288c6
1 /*
2 dict.c
3
4 UltraRogue: The Ultimate Adventure in the Dungeons of Doom
5 Copyright (C) 1995 Herb Chong
6 All rights reserved.
7
8 See the file LICENSE.TXT for full copyright and licensing information.
9 */
10
11 /******************
12 ** Change history:
13 **
14 ** (AK:04/03/95) - In dict_create, initialize hook for extensions to dictionary structure.
15 ** (AK:04/04/95) - In dict_insert, only set any_ptr when a new string entry is created.
16 ** (AK:04/17/95) - Added dict_union and dict_merge.
17 ** (AK:04/18/95) - In dict_create, added code to create signature,
18 ** table of contents, and parameter array.
19 ** (AK:04/18/95) - Revised dict_load, dict_save
20 ** (AK:04/18/95) - Added dict_import
21 **
22 ******************/
23
24 static char sccsid[] = "%W% %G%";
25
26 #include <stdlib.h>
27 #include <string.h>
28 #if !defined(OS2) && !defined(_WIN32)
29 #include <unistd.h>
30 #endif
31
32 #include "dict.h"
33 #include "dictutil.h"
34
35 #define BUFLEN 300
36
37 /*************************************************************************
38 * Generic dictionary and hash table functions for word and
39 * string storage.
40 *
41 * Implements generic dictionary management by using a
42 * hash table with direct chaining. All terms are stored in a
43 * separate, unsorted, string table. When inserting into the
44 * hash table exceeds the current size, allocate a new hash table
45 * and rehash the old contents into the new table. When the string
46 * table fills, append more empty entries onto the old table and
47 * continue adding. Inserting a string that already exists increments
48 * the count for the string. Deleting a string only decrements the
49 * count to no less than 0. This will allow a 0 occurence string to be
50 * retrieved. To remove the 0 occurence string table entries, you must
51 * rebuild the dictionary. Merging from one dictionary to a new one will
52 * do this because it only copies nonzero occurences.
53 *
54 * Assumptions:
55 * unsigned long >= 32 bits
56 * int >= 16 bits
57 * char == 8 bits
58 * number of entries < 2^28
59 *************************************************************************/
60
61 /*************************************************************************
62 * hash_string: calculate hash value for string, modified
63 * version of hashpjw() from the new Dragon book.
64 *
65 * s - string to calculate hash for
66 *
67 * Returns: hash value
68 *************************************************************************/
69 static unsigned long hash_string(const char *s)
70 {
71 unsigned long h = 0;
72 unsigned long g = 0;
73
74 while (*s) {
75 h <<= 4;
76 h += *s++;
77 if ((g = h & 0xf0000000) != 0)
78 h ^= g >> 24;
79 }
80 return h ^ g;
81 }
82
83 /*************************************************************************
84 * dict_create: create a dictionary and initialize its structures
85 *
86 * toc_size - number of entries in table of contents ( >= 4 )
87 * initial_string_count - number of strings to hold as initial allocation
88 * initial_hash_chains - size of hash table, must be power of 4
89 * max_chain_length - max number of elements in hash chain before signalling growth
90 *
91 * Returns: pointer to dictionary
92 * NULL - error creating dictionary
93 * non-NULL - sucessful creation
94 *************************************************************************/
95
96 DICTIONARY *dict_create(
97 const long toc_size,
98 const long initial_string_count,
99 const long initial_hash_chains,
100 const long max_chain_length )
101 {
102 DICTIONARY *dtemp = NULL;
103 STRING_ENTRY *stemp = NULL;
104 long *ltemp = NULL;
105 char *sltemp;
106 long i, j, tocsize;
107
108 /* check for a power of 4 in number of initial hash entries */
109 switch(initial_hash_chains) {
110 case 0x00000004:
111 case 0x00000010:
112 case 0x00000040:
113 case 0x00000100:
114 case 0x00000400:
115 case 0x00001000:
116 case 0x00004000:
117 case 0x00010000:
118 case 0x00040000:
119 case 0x00100000:
120 case 0x00400000:
121 case 0x01000000:
122 case 0x04000000:
123 break;
124 default:
125 return NULL;
126 }
127
128 /* Allocate the dictionary structure */
129 if ((dtemp = (DICTIONARY *)malloc(sizeof(DICTIONARY))) == NULL)
130 goto err_exit;
131
132 /* string count has to be within range */
133 j = initial_string_count;
134 if (j > 0x04000000)
135 return NULL;
136
137 /* force a reasonable value */
138 if (j < 100)
139 j = 100;
140
141 /* Allocate the string table and string array */
142 if ((stemp = (STRING_ENTRY *)malloc(sizeof(STRING_ENTRY) * j)) == NULL)
143 goto err_exit;
144 if ((sltemp = (char *)malloc(8 * j)) == NULL)
145 goto err_exit;
146
147 /* Allocate the hash table */
148 if ((ltemp = (long *)malloc(sizeof(long) * initial_hash_chains)) == NULL)
149 goto err_exit;
150
151 /* Allocate the parameter array */
152 if ( (dtemp->parm = (DICT_PARM_ENTRY *)malloc(14*sizeof(DICT_PARM_ENTRY))) == NULL)
153 goto err_exit;
154
155 /* Allocate the signature structure */
156 if ( (dtemp->sig=(DICT_SIG*)malloc(sizeof(DICT_SIG))) == NULL )
157 goto err_exit;
158
159 /* Allocate the Table of Contents */
160 tocsize = toc_size;
161 if ( tocsize < 4 )
162 tocsize = 4;
163 dtemp->sig->toc_size = tocsize;
164 if ( (dtemp->toc=(DICT_TOC_ENTRY*)malloc(dtemp->sig->toc_size*sizeof(DICT_TOC_ENTRY))) == NULL )
165 goto err_exit;
166
167 dtemp->check_value = DICT_VALIDATE; /* validation value */
168 dtemp->flags = DICT_NONE; /* no flags set */
169 dtemp->entry_count = 0; /* nothing in either table */
170
171 dtemp->string_table = stemp; /* connect string table */
172 dtemp->string_max = j; /* size of string table */
173 dtemp->scan_string_index = DICT_ENTRY_NONE; /* not pointing to anything in scan */
174 dtemp->string_growth_count = 0; /* haven't grown any */
175
176 dtemp->string_array = sltemp; /* character array for strings */
177 dtemp->array_size = j * 8; /* how many bytes available */
178 dtemp->array_used = 0; /* nothing used yet */
179 dtemp->array_growth_count = 0; /* haven't grown any */
180
181 /* force maximum hash chain length to a reasonable value */
182 i = max_chain_length;
183 if (i < 1 || i > 200)
184 i = 200;
185 dtemp->chains = ltemp; /* connect hash table */
186 dtemp->longest_chain_length = 0; /* nothing in table yet */
187 dtemp->allowable_chain_length = i; /* chain length limit */
188 dtemp->table_size = initial_hash_chains; /* size of hash table */
189 dtemp->hash_mask = initial_hash_chains - 1; /* mask for mod() function */
190 dtemp->hash_growth_count = 0; /* haven't grown any */
191
192 /* string table is empty */
193 for (i = 0 ; i < j ; i++) {
194 dtemp->string_table[i].string_offset = DICT_ENTRY_NONE;
195 dtemp->string_table[i].count = 0;
196 dtemp->string_table[i].next = DICT_ENTRY_NONE;
197 dtemp->string_table[i].flags = 0;
198 dtemp->string_table[i].hash_value = 0;
199 }
200
201 /* no entries chained */
202 for (i = 0; i < initial_hash_chains; i++)
203 dtemp->chains[i] = DICT_ENTRY_NONE;
204
205 /* Initialize hook to extended dictionary structure */
206 dtemp->ext = NULL;
207
208 /* Set up the parameter array */
209 if ( dict_set_parm_ids(dtemp) == FALSE )
210 goto err_exit;
211 if ( dict_set_parm_values(dtemp) == FALSE )
212 goto err_exit;
213
214 /* Set up the Table of Contents */
215 strcpy( dtemp->toc[0].id , "PARM" );
216 dtemp->toc[0].size = dtemp->sig->nparms * sizeof(DICT_PARM_ENTRY);
217 dtemp->toc[0].ptr = dtemp->parm;
218 dtemp->toc[0].type = 0;
219
220 strcpy( dtemp->toc[1].id , "HASH" );
221 dtemp->toc[1].size = dtemp->table_size * sizeof(long);
222 dtemp->toc[1].ptr = dtemp->chains;
223 dtemp->toc[1].type = 0;
224
225 strcpy( dtemp->toc[2].id , "STTB" );
226 dtemp->toc[2].size = dtemp->string_max * sizeof(char);
227 dtemp->toc[2].ptr = dtemp->string_table;
228 dtemp->toc[2].type = 0;
229
230 strcpy( dtemp->toc[3].id , "STAR" );
231 dtemp->toc[3].size = dtemp->array_size * sizeof(STRING_ENTRY);
232 dtemp->toc[3].ptr = dtemp->string_array;
233 dtemp->toc[3].type = 0;
234
235 /* Set up the signature */
236 dtemp->sig->check_value = DICT_VALIDATE;
237 dtemp->sig->toc_size = tocsize;
238 dtemp->sig->nparms = 14;
239
240 return dtemp;
241
242 /* error exit - saves duplicate code */
243 err_exit:
244
245 dict_destroy( dtemp );
246 return NULL;
247 }
248
249 /*************************************************************************
250 * dict_destroy: discard a dictionary and its contents
251 * multiple calls to destroy the same dictionary is safe
252 *
253 * dict - pointer to a dictionary to discard
254 *
255 * Returns: status code
256 * TRUE - dictionary destroyed
257 * FALSE - error when destroying dictionary
258 * Note: Does free the dictionary structure itself.
259 *************************************************************************/
260 BOOLEANC dict_destroy(DICTIONARY *dict)
261 {
262 int i;
263
264 /* have to point to something */
265 if (dict == NULL)
266 return FALSE;
267
268 /* check value has to be OK */
269 if (dict->check_value != DICT_VALIDATE)
270 return FALSE;
271
272 if ( (dict->sig==NULL) || (dict->toc==NULL) || (dict->parm==NULL) )
273 return FALSE;
274
275 /* Free the type=0 tables */
276 for ( i = 0 ; i < dict->sig->toc_size ; i++ ) {
277 if ( dict->toc[i].ptr != NULL && dict->toc[i].type == 0 )
278 free( dict->toc[i].ptr );
279 } /* endfor */
280
281 /* Free the Table of Contents and signature */
282 free( dict->toc );
283 free( dict->sig );
284
285 /* Free the dictionary structure itself */
286 free( dict );
287
288 return TRUE;
289 }
290
291 /*************************************************************************
292 * dict_insert: add entries into the dictionary, growing as necessary
293 *
294 * dict - pointer to dictionary to insert into
295 * s - string to insert
296 * count - count of occurences of string
297 * flags - flag bits associated with the string
298 * number - pointer to long to return word number
299 *
300 * Returns: pointer to new entry in dictionary
301 * NULL - error during insert
302 * non-NULL - pointer to inserted or updated entry
303 *
304 * Notes: if the entry already exists, increment the count.
305 * If NULL is returned, the dictionary state can no longer
306 * be trusted. Terminating with an error code would be
307 * safest.
308 *************************************************************************/
309 STRING_ENTRY *dict_insert(DICTIONARY *dict, char *s,
310 const long occurences, const unsigned long flags,
311 void *any_ptr, long *number)
312 {
313 unsigned long hash_value;
314 long hash_index;
315 long string_index = -1;
316 long he2;
317 int chain_len;
318
319 /* have to point to something */
320 if (dict == NULL)
321 return FALSE;
322
323 /* check value has to be OK */
324 if (dict->check_value != DICT_VALIDATE)
325 return FALSE;
326
327 /* must have a string */
328 if (s == NULL) {
329 *number = -1;
330 return FALSE;
331 }
332
333 /* must be non-NULL */
334 if (s[0] == '\0') {
335 *number = -1;
336 return FALSE;
337 }
338
339 /* figure out which chain it should go into */
340 hash_value = hash_string(s);
341 hash_index = hash_value & dict->hash_mask;
342
343 /* look for the entry in the chain */
344 for (he2 = dict->chains[hash_index], chain_len = 0; he2 != DICT_ENTRY_NONE;
345 he2 = dict->string_table[he2].next, chain_len++) {
346 char *sa = &dict->string_array[dict->string_table[he2].string_offset];
347
348 /* compare hash_value and then string, in that order, for speed */
349 if (dict->string_table[he2].hash_value == hash_value && !strcmp(s, sa)) {
350 string_index = he2;