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