1 /*****************************************************************************/
9 /* (C) 2003-2011, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
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. */
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: */
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 */
32 /*****************************************************************************/
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.
57 /*****************************************************************************/
59 /*****************************************************************************/
63 static unsigned HT_GenHash (const void* Key);
64 /* Generate the hash over a key. */
66 static const void* HT_GetKey (const void* Entry);
67 /* Given a pointer to the user entry data, return a pointer to the key */
69 static 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.
77 /*****************************************************************************/
79 /*****************************************************************************/
83 /* A string pool entry */
84 struct StringPoolEntry {
85 HashNode Node; /* Node for the hash table */
86 unsigned Id; /* The numeric string id */
87 StrBuf Buf; /* The string itself */
92 Collection Entries; /* Entries sorted by number */
93 unsigned TotalSize; /* Total size of all string data */
94 HashTable Tab; /* Hash table */
97 /* Hash table functions */
98 static const HashFunctions HashFunc = {
106 /*****************************************************************************/
107 /* struct StringPoolEntry */
108 /*****************************************************************************/
112 static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Id)
113 /* Create a new string pool entry and return it. */
115 /* Allocate memory */
116 StringPoolEntry* E = xmalloc (sizeof (StringPoolEntry));
118 /* Initialize the fields */
119 InitHashNode (&E->Node);
122 SB_Copy (&E->Buf, S);
124 /* Always zero terminate the string */
125 SB_Terminate (&E->Buf);
127 /* Return the new entry */
133 /*****************************************************************************/
134 /* Hash table functions */
135 /*****************************************************************************/
139 static unsigned HT_GenHash (const void* Key)
140 /* Generate the hash over a key. */
142 return HashBuf (Key);
147 static const void* HT_GetKey (const void* Entry)
148 /* Given a pointer to the user entry data, return a pointer to the index */
150 return &((const StringPoolEntry*) Entry)->Buf;
155 static 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.
161 return SB_Compare (Key1, Key2);
166 /*****************************************************************************/
168 /*****************************************************************************/
172 StringPool* NewStringPool (unsigned HashSlots)
173 /* Allocate, initialize and return a new string pool */
175 /* Allocate memory */
176 StringPool* P = xmalloc (sizeof (*P));
178 /* Initialize the fields */
179 P->Entries = EmptyCollection;
181 InitHashTable (&P->Tab, HashSlots, &HashFunc);
183 /* Return a pointer to the new pool */
189 void FreeStringPool (StringPool* P)
190 /* Free a string pool */
194 /* Free all entries and clear the entry collection */
195 for (I = 0; I < CollCount (&P->Entries); ++I) {
197 /* Get a pointer to the entry */
198 StringPoolEntry* E = CollAtUnchecked (&P->Entries, I);
200 /* Free string buffer memory */
203 /* Free the memory for the entry itself */
206 CollDeleteAll (&P->Entries);
208 /* Free the hash table */
209 DoneHashTable (&P->Tab);
211 /* Free the string pool itself */
217 const StrBuf* SP_Get (const StringPool* P, unsigned Index)
218 /* Return a string from the pool. Index must exist, otherwise FAIL is called. */
220 /* Get the collection entry */
221 const StringPoolEntry* E = CollConstAt (&P->Entries, Index);
223 /* Return the string from the entry */
229 unsigned 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
235 /* Search for a matching entry in the hash table */
236 StringPoolEntry* E = HT_Find (&P->Tab, S);
238 /* Did we find it? */
241 /* We didn't find the entry, so create a new one */
242 E = NewStringPoolEntry (S, CollCount (&P->Entries));
244 /* Insert the new entry into the entries collection */
245 CollAppend (&P->Entries, E);
247 /* Insert the new entry into the hash table */
248 HT_Insert (&P->Tab, E);
250 /* Add up the string size */
251 P->TotalSize += SB_GetLen (&E->Buf);
254 /* Return the id of the entry */
260 unsigned 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.
267 /* First make a string buffer, then add it. This is some overhead, but the
268 * routine will probably go.
271 Id = SP_Add (P, SB_InitFromString (&Buf, S));
273 /* Return the id of the new entry */
279 unsigned SP_GetCount (const StringPool* P)
280 /* Return the number of strings in the pool */
282 return CollCount (&P->Entries);