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 | |
63 | static unsigned HT_GenHash (const void* Key); |
64 | /* Generate the hash over a key. */ |
65 | |
66 | static const void* HT_GetKey (const void* Entry); |
67 | /* Given a pointer to the user entry data, return a pointer to the key */ |
68 | |
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. |
73 | */ |
74 | |
75 | |
76 | |
77 | /*****************************************************************************/ |
78 | /* Data */ |
79 | /*****************************************************************************/ |
80 | |
81 | |
82 | |
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 */ |
88 | }; |
89 | |
90 | /* A string pool */ |
91 | struct 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 */ |
98 | static const HashFunctions HashFunc = { |
99 | HT_GenHash, |
100 | HT_GetKey, |
101 | HT_Compare |
102 | }; |
103 | |
104 | |
105 | |
106 | /*****************************************************************************/ |
107 | /* struct StringPoolEntry */ |
108 | /*****************************************************************************/ |
109 | |
110 | |
111 | |
112 | static 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 | |
139 | static unsigned HT_GenHash (const void* Key) |
140 | /* Generate the hash over a key. */ |
141 | { |
142 | return HashBuf (Key); |
143 | } |
144 | |
145 | |
146 | |
147 | static 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 | |
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. |
159 | */ |
160 | { |
161 | return SB_Compare (Key1, Key2); |
162 | } |
163 | |
164 | |
165 | |
166 | /*****************************************************************************/ |
167 | /* Code */ |
168 | /*****************************************************************************/ |
169 | |
170 | |
171 | |
172 | StringPool* 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 | |
189 | void 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 | |
217 | const 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 | |
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 |
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 | |
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. |
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 | |
279 | unsigned SP_GetCount (const StringPool* P) |
280 | /* Return the number of strings in the pool */ |
281 | { |
282 | return CollCount (&P->Entries); |
283 | } |
284 | |