1/*****************************************************************************/
2/* */
3/* strpool.c */
4/* */
5/* A string pool */
6/* */
7/* */
8/* */
9/* (C) 2003-2011, Ullrich von Bassewitz */
10/* Roemerstrasse 52 */
11/* D-70794 Filderstadt */
12/* EMail: uz@cc65.org */
13/* */
14/* */
15/* This software is provided 'as-is', without any expressed or implied */
16/* warranty. In no event will the authors be held liable for any damages */
17/* arising from the use of this software. */
18/* */
19/* Permission is granted to anyone to use this software for any purpose, */
20/* including commercial applications, and to alter it and redistribute it */
21/* freely, subject to the following restrictions: */
22/* */
23/* 1. The origin of this software must not be misrepresented; you must not */
24/* claim that you wrote the original software. If you use this software */
25/* in a product, an acknowledgment in the product documentation would be */
26/* appreciated but is not required. */
27/* 2. Altered source versions must be plainly marked as such, and must not */
28/* be misrepresented as being the original software. */
29/* 3. This notice may not be removed or altered from any source */
30/* distribution. */
31/* */
32/*****************************************************************************/
33
34
35
36/* A string pool is used to store identifiers and other strings. Each string
37** stored in the pool has a unique id, which may be used to access the string
38** in the pool. Identical strings are stored only once in the pool and have
39** identical ids. This means that instead of comparing strings, just the
40** string pool ids must be compared.
41*/
42
43
44
45#include <string.h>
46
47/* common */
48#include "coll.h"
49#include "hashfunc.h"
50#include "hashtab.h"
51#include "strbuf.h"
52#include "strpool.h"
53#include "xmalloc.h"
54
55
56
57/*****************************************************************************/
58/* Forwards */
59/*****************************************************************************/
60
61
62
63static unsigned HT_GenHash (const void* Key);
64/* Generate the hash over a key. */
65
66static const void* HT_GetKey (const void* Entry);
67/* Given a pointer to the user entry data, return a pointer to the key */
68
69static int HT_Compare (const void* Key1, const void* Key2);
70/* Compare two keys. The function must return a value less than zero if
71** Key1 is smaller than Key2, zero if both are equal, and a value greater
72** than zero if Key1 is greater then Key2.
73*/
74
75
76
77/*****************************************************************************/
78/* Data */
79/*****************************************************************************/
80
81
82
83/* A string pool entry */
84struct StringPoolEntry {
85 HashNode Node; /* Node for the hash table */
86 unsigned Id; /* The numeric string id */
87 StrBuf Buf; /* The string itself */
88};
89
90/* A string pool */
91struct StringPool {
92 Collection Entries; /* Entries sorted by number */
93 unsigned TotalSize; /* Total size of all string data */
94 HashTable Tab; /* Hash table */
95};
96
97/* Hash table functions */
98static const HashFunctions HashFunc = {
99 HT_GenHash,
100 HT_GetKey,
101 HT_Compare
102};
103
104
105
106/*****************************************************************************/
107/* struct StringPoolEntry */
108/*****************************************************************************/
109
110
111
112static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Id)
113/* Create a new string pool entry and return it. */
114{
115 /* Allocate memory */
116 StringPoolEntry* E = xmalloc (sizeof (StringPoolEntry));
117
118 /* Initialize the fields */
119 InitHashNode (&E->Node);
120 E->Id = Id;
121 SB_Init (&E->Buf);
122 SB_Copy (&E->Buf, S);
123
124 /* Always zero terminate the string */
125 SB_Terminate (&E->Buf);
126
127 /* Return the new entry */
128 return E;
129}
130
131
132
133/*****************************************************************************/
134/* Hash table functions */
135/*****************************************************************************/
136
137
138
139static unsigned HT_GenHash (const void* Key)
140/* Generate the hash over a key. */
141{
142 return HashBuf (Key);
143}
144
145
146
147static const void* HT_GetKey (const void* Entry)
148/* Given a pointer to the user entry data, return a pointer to the index */
149{
150 return &((const StringPoolEntry*) Entry)->Buf;
151}
152
153
154
155static int HT_Compare (const void* Key1, const void* Key2)
156/* Compare two keys. The function must return a value less than zero if
157** Key1 is smaller than Key2, zero if both are equal, and a value greater
158** than zero if Key1 is greater then Key2.
159*/
160{
161 return SB_Compare (Key1, Key2);
162}
163
164
165
166/*****************************************************************************/
167/* Code */
168/*****************************************************************************/
169
170
171
172StringPool* NewStringPool (unsigned HashSlots)
173/* Allocate, initialize and return a new string pool */
174{
175 /* Allocate memory */
176 StringPool* P = xmalloc (sizeof (*P));
177
178 /* Initialize the fields */
179 P->Entries = EmptyCollection;
180 P->TotalSize = 0;
181 InitHashTable (&P->Tab, HashSlots, &HashFunc);
182
183 /* Return a pointer to the new pool */
184 return P;
185}
186
187
188
189void FreeStringPool (StringPool* P)
190/* Free a string pool */
191{
192 unsigned I;
193
194 /* Free all entries and clear the entry collection */
195 for (I = 0; I < CollCount (&P->Entries); ++I) {
196
197 /* Get a pointer to the entry */
198 StringPoolEntry* E = CollAtUnchecked (&P->Entries, I);
199
200 /* Free string buffer memory */
201 SB_Done (&E->Buf);
202
203 /* Free the memory for the entry itself */
204 xfree (E);
205 }
206 CollDeleteAll (&P->Entries);
207
208 /* Free the hash table */
209 DoneHashTable (&P->Tab);
210
211 /* Free the string pool itself */
212 xfree (P);
213}
214
215
216
217const StrBuf* SP_Get (const StringPool* P, unsigned Index)
218/* Return a string from the pool. Index must exist, otherwise FAIL is called. */
219{
220 /* Get the collection entry */
221 const StringPoolEntry* E = CollConstAt (&P->Entries, Index);
222
223 /* Return the string from the entry */
224 return &E->Buf;
225}
226
227
228
229unsigned SP_Add (StringPool* P, const StrBuf* S)
230/* Add a string buffer to the buffer and return the index. If the string does
231** already exist in the pool, SP_AddBuf will just return the index of the
232** existing string.
233*/
234{
235 /* Search for a matching entry in the hash table */
236 StringPoolEntry* E = HT_Find (&P->Tab, S);
237
238 /* Did we find it? */
239 if (E == 0) {
240
241 /* We didn't find the entry, so create a new one */
242 E = NewStringPoolEntry (S, CollCount (&P->Entries));
243
244 /* Insert the new entry into the entries collection */
245 CollAppend (&P->Entries, E);
246
247 /* Insert the new entry into the hash table */
248 HT_Insert (&P->Tab, E);
249
250 /* Add up the string size */
251 P->TotalSize += SB_GetLen (&E->Buf);
252 }
253
254 /* Return the id of the entry */
255 return E->Id;
256}
257
258
259
260unsigned SP_AddStr (StringPool* P, const char* S)
261/* Add a string to the buffer and return the index. If the string does already
262** exist in the pool, SP_Add will just return the index of the existing string.
263*/
264{
265 unsigned Id;
266
267 /* First make a string buffer, then add it. This is some overhead, but the
268 ** routine will probably go.
269 */
270 StrBuf Buf;
271 Id = SP_Add (P, SB_InitFromString (&Buf, S));
272
273 /* Return the id of the new entry */
274 return Id;
275}
276
277
278
279unsigned SP_GetCount (const StringPool* P)
280/* Return the number of strings in the pool */
281{
282 return CollCount (&P->Entries);
283}
284