1 | /* |
1 | /* |
2 | * static char *rcsid_shstr_c = |
2 | * This file is part of Deliantra, the Roguelike Realtime MMORPG. |
3 | * "$Id: shstr.C,v 1.1 2006/08/13 17:16:01 elmex Exp $"; |
|
|
4 | * |
3 | * |
5 | * shstr.c |
4 | * Copyright (©) 2005,2006,2007,2008 Marc Alexander Lehmann / Robin Redeker / the Deliantra team |
6 | * |
5 | * |
7 | * This is a simple shared strings package with a simple interface. |
6 | * Deliantra is free software: you can redistribute it and/or modify |
|
|
7 | * it under the terms of the GNU General Public License as published by |
|
|
8 | * the Free Software Foundation, either version 3 of the License, or |
|
|
9 | * (at your option) any later version. |
8 | * |
10 | * |
9 | * char *find_string(const char *str) |
11 | * This program is distributed in the hope that it will be useful, |
10 | * char *add_string(const char *str) |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | * char *add_refcount(char *str) |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
12 | * void free_string(char *str) |
14 | * GNU General Public License for more details. |
13 | * char *ss_dump_table(int what) |
|
|
14 | * void ss_dump_statistics() |
|
|
15 | * |
15 | * |
16 | * Author: Kjetil T. Homme, Oslo 1992. |
16 | * You should have received a copy of the GNU General Public License |
|
|
17 | * along with this program. If not, see <http://www.gnu.org/licenses/>. |
|
|
18 | * |
|
|
19 | * The authors can be reached via e-mail to <support@deliantra.net> |
17 | */ |
20 | */ |
18 | |
21 | |
19 | #include <stdio.h> |
|
|
20 | #include <stddef.h> |
|
|
21 | #include <stdlib.h> |
|
|
22 | #include <sys/types.h> |
|
|
23 | #include <limits.h> |
|
|
24 | #include <string.h> |
|
|
25 | |
|
|
26 | #if defined (__sun__) && defined (StupidSunHeaders) |
|
|
27 | #include <sys/time.h> |
|
|
28 | #include "sunos.h" |
|
|
29 | #endif |
|
|
30 | |
|
|
31 | #include "shstr.h" |
|
|
32 | |
|
|
33 | #ifndef WIN32 |
|
|
34 | #include <autoconf.h> |
|
|
35 | #endif |
|
|
36 | #ifdef HAVE_LIBDMALLOC |
|
|
37 | #include <dmalloc.h> |
|
|
38 | #endif |
|
|
39 | |
|
|
40 | static shared_string *hash_table[TABLESIZE]; |
|
|
41 | |
|
|
42 | /* |
22 | /* |
43 | * Initialises the hash-table used by the shared string library. |
23 | * shstr.C |
44 | */ |
24 | */ |
45 | |
25 | |
46 | void |
26 | #include <cstring> |
47 | init_hash_table(void) { |
27 | #include <cstdlib> |
48 | /* A static object should be zeroed out always */ |
28 | #include <glib.h> |
49 | #if !defined(__STDC__) |
29 | #include <tr1/unordered_set> |
50 | (void) memset((void *)hash_table, 0, TABLESIZE * sizeof(shared_string *)); |
30 | |
51 | #endif |
31 | #include "global.h" |
|
|
32 | |
|
|
33 | size_t shstr_alloc; |
|
|
34 | |
|
|
35 | typedef std::tr1::unordered_set <const char *, str_hash, str_equal, slice_allocator<const char *> > HT; |
|
|
36 | |
|
|
37 | static HT ht; |
|
|
38 | static int next_gc; |
|
|
39 | |
|
|
40 | static const char * |
|
|
41 | makevec (const char *s) |
|
|
42 | { |
|
|
43 | int len = strlen (s); |
|
|
44 | |
|
|
45 | shstr_alloc += sizeof (uint32_t) * 2 + len + 1; |
|
|
46 | const char *v = (const char *) (2 + (int *)g_slice_alloc (sizeof (uint32_t) * 2 + len + 1)); |
|
|
47 | |
|
|
48 | shstr::length (v) = len; |
|
|
49 | shstr::refcnt (v) = 1; |
|
|
50 | |
|
|
51 | memcpy ((char *) v, s, len + 1); |
|
|
52 | |
|
|
53 | return v; |
52 | } |
54 | } |
53 | |
55 | |
54 | /* |
56 | shstr_vec<sizeof "(null)"> shstr_tmp::nullvec = { 0, 0xffffffff, "(null)" }; |
55 | * Hashing-function used by the shared string library. |
|
|
56 | */ |
|
|
57 | |
57 | |
58 | static int |
|
|
59 | hashstr(const char *str) { |
|
|
60 | unsigned long hash = 0; |
|
|
61 | int i = 0; |
|
|
62 | unsigned rot = 0; |
|
|
63 | const char *p; |
58 | const char * |
|
|
59 | shstr::find (const char *s) |
|
|
60 | { |
|
|
61 | if (!s) |
|
|
62 | return s; |
64 | |
63 | |
65 | GATHER(hash_stats.calls); |
64 | auto (i, ht.find (s)); |
66 | |
65 | |
67 | for (p = str; i < MAXSTRING && *p; p++, i++) { |
66 | return i != ht.end ()? *i : 0; |
68 | hash ^= (unsigned long) *p << rot; |
|
|
69 | rot += 2; |
|
|
70 | if (rot >= (sizeof(long) - sizeof(char)) * CHAR_BIT) |
|
|
71 | rot = 0; |
|
|
72 | } |
|
|
73 | return (hash % TABLESIZE); |
|
|
74 | } |
67 | } |
75 | |
68 | |
76 | /* |
69 | const char * |
77 | * Allocates and initialises a new shared_string structure, containing |
70 | shstr::intern (const char *s) |
78 | * the string str. |
71 | { |
79 | */ |
72 | if (!s) |
|
|
73 | return null (); |
80 | |
74 | |
81 | static shared_string * |
75 | if (const char *found = find (s)) |
82 | new_shared_string(const char *str) { |
76 | { |
83 | shared_string *ss; |
77 | ++refcnt (found); |
|
|
78 | return found; |
|
|
79 | } |
84 | |
80 | |
85 | /* Allocate room for a struct which can hold str. Note |
81 | --next_gc; |
86 | * that some bytes for the string are already allocated in the |
82 | s = makevec (s); |
87 | * shared_string struct. |
83 | ht.insert (s); |
88 | */ |
|
|
89 | ss = (shared_string *) malloc(sizeof(shared_string) - PADDING + |
|
|
90 | strlen(str) + 1); |
|
|
91 | ss->u.previous = NULL; |
|
|
92 | ss->next = NULL; |
|
|
93 | ss->refcount = 1; |
|
|
94 | strcpy(ss->string, str); |
|
|
95 | |
|
|
96 | return ss; |
84 | return s; |
97 | } |
85 | } |
98 | |
86 | |
99 | /* |
87 | // periodically test refcounts == 0 for a few strings |
100 | * Description: |
88 | // this is the ONLY thing that erases stuff from ht. keep it that way. |
101 | * This will add 'str' to the hash table. If there's no entry for this |
89 | void |
102 | * string, a copy will be allocated, and a pointer to that is returned. |
90 | shstr::gc () |
103 | * Return values: |
91 | { |
104 | * - pointer to string identical to str |
92 | if (expect_true (next_gc > 0)) |
105 | */ |
93 | return; |
106 | |
94 | |
107 | const char * |
95 | static const char *curpos; |
108 | add_string(const char *str) { |
|
|
109 | shared_string *ss; |
|
|
110 | int ind; |
|
|
111 | |
96 | |
112 | GATHER(add_stats.calls); |
97 | auto (i, curpos ? ht.find (curpos) : ht.begin ()); |
113 | |
98 | |
114 | /* Should really core dump here, since functions should not be calling |
99 | if (i == ht.end ()) |
115 | * add_string with a null parameter. But this will prevent a few |
100 | i = ht.begin (); |
116 | * core dumps. |
101 | |
117 | */ |
102 | int n = ht.size () / 256 + 16; |
118 | if (str==NULL) { |
103 | next_gc += n >> 1; |
119 | #ifdef MANY_CORES |
104 | |
120 | abort(); |
105 | for (;;) |
121 | #else |
106 | { |
122 | return NULL; |
107 | if (i == ht.end ()) |
123 | #endif |
108 | { |
|
|
109 | curpos = 0; |
|
|
110 | return; |
|
|
111 | } |
|
|
112 | else if (!--n) |
|
|
113 | break; |
|
|
114 | else if (!refcnt (*i)) |
|
|
115 | { |
|
|
116 | auto (o, i++); |
|
|
117 | const char *s = *o; |
|
|
118 | |
|
|
119 | ht.erase (o); |
|
|
120 | |
|
|
121 | //printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s)); |
|
|
122 | shstr_alloc -= sizeof (uint32_t) * 2 + length (s) + 1; |
|
|
123 | g_slice_free1 (sizeof (uint32_t) * 2 + length (s) + 1, -2 + (int *) s); |
|
|
124 | } |
|
|
125 | else |
|
|
126 | ++i; |
124 | } |
127 | } |
125 | |
128 | |
126 | ind = hashstr(str); |
129 | curpos = *i; |
127 | ss = hash_table[ind]; |
|
|
128 | |
|
|
129 | /* Is there an entry for that hash? |
|
|
130 | */ |
|
|
131 | if (ss) { |
|
|
132 | /* Simple case first: See if the first pointer matches. |
|
|
133 | */ |
|
|
134 | if (str != ss->string) { |
|
|
135 | GATHER(add_stats.strcmps); |
|
|
136 | if (strcmp(ss->string, str)) { |
|
|
137 | /* Apparantly, a string with the same hash value has this |
|
|
138 | * slot. We must see in the list if "str" has been |
|
|
139 | * registered earlier. |
|
|
140 | */ |
|
|
141 | while (ss->next) { |
|
|
142 | GATHER(add_stats.search); |
|
|
143 | ss = ss->next; |
|
|
144 | if (ss->string != str) { |
|
|
145 | GATHER(add_stats.strcmps); |
|
|
146 | if (strcmp(ss->string, str)) { |
|
|
147 | /* This wasn't the right string... |
|
|
148 | */ |
|
|
149 | continue; |
|
|
150 | } |
|
|
151 | } |
|
|
152 | /* We found an entry for this string. Fix the |
|
|
153 | * refcount and exit. |
|
|
154 | */ |
|
|
155 | GATHER(add_stats.linked); |
|
|
156 | ++(ss->refcount); |
|
|
157 | |
|
|
158 | return ss->string; |
|
|
159 | } |
|
|
160 | /* There are no occurences of this string in the hash table. |
|
|
161 | */ |
|
|
162 | { |
|
|
163 | shared_string *new_ss; |
|
|
164 | |
|
|
165 | GATHER(add_stats.linked); |
|
|
166 | new_ss = new_shared_string(str); |
|
|
167 | ss->next = new_ss; |
|
|
168 | new_ss->u.previous = ss; |
|
|
169 | return new_ss->string; |
|
|
170 | } |
|
|
171 | } |
|
|
172 | /* Fall through. |
|
|
173 | */ |
|
|
174 | } |
|
|
175 | GATHER(add_stats.hashed); |
|
|
176 | ++(ss->refcount); |
|
|
177 | return ss->string; |
|
|
178 | } else { |
|
|
179 | /* The string isn't registered, and the slot is empty. |
|
|
180 | */ |
|
|
181 | GATHER(add_stats.hashed); |
|
|
182 | hash_table[ind] = new_shared_string(str); |
|
|
183 | |
|
|
184 | /* One bit in refcount is used to keep track of the union. |
|
|
185 | */ |
|
|
186 | hash_table[ind]->refcount |= TOPBIT; |
|
|
187 | hash_table[ind]->u.array = &(hash_table[ind]); |
|
|
188 | |
|
|
189 | return hash_table[ind]->string; |
|
|
190 | } |
|
|
191 | } |
130 | } |
192 | |
131 | |
193 | /* |
132 | // declare these here to get correct initialisation order |
194 | * Description: |
133 | #define def2(id,str) const shstr shstr_ ## id (str); |
195 | * This will increase the refcount of the string str, which *must* |
134 | #define def(id) def2(id, # id) |
196 | * have been returned from a previous add_string(). |
135 | # include "shstrinc.h" |
197 | * Return values: |
136 | #undef def |
198 | * - str |
137 | #undef def2 |
199 | */ |
|
|
200 | |
138 | |
201 | const char * |
139 | shstr skill_names[NUM_SKILLS]; |
202 | add_refcount(const char *str) { |
|
|
203 | GATHER(add_ref_stats.calls); |
|
|
204 | ++(SS(str)->refcount); |
|
|
205 | /* This function should be declared |
|
|
206 | * const char *add_refcount(const char *) |
|
|
207 | * Unfortunately, that would require changing a lot of structs |
|
|
208 | * |
|
|
209 | * Yup, many changes, but may have make some bugs more visible :) |
|
|
210 | * -- Ryo 2005-08-12 |
|
|
211 | */ |
|
|
212 | return (char*)str; |
|
|
213 | } |
|
|
214 | |
140 | |
215 | /* |
141 | //TODO: this should of course not be here |
216 | * Description: |
|
|
217 | * This will return the refcount of the string str, which *must* |
|
|
218 | * have been returned from a previous add_string(). |
|
|
219 | * Return values: |
|
|
220 | * - length |
|
|
221 | */ |
|
|
222 | |
|
|
223 | int |
|
|
224 | query_refcount(const char *str) { |
|
|
225 | return (SS(str)->refcount) & ~TOPBIT; |
|
|
226 | } |
|
|
227 | |
|
|
228 | /* |
|
|
229 | * Description: |
|
|
230 | * This will see if str is in the hash table, and return the address |
|
|
231 | * of that string if it exists. |
|
|
232 | * Return values: |
|
|
233 | * - pointer to identical string or NULL |
|
|
234 | */ |
|
|
235 | |
|
|
236 | const char * |
|
|
237 | find_string(const char *str) { |
|
|
238 | shared_string *ss; |
|
|
239 | int ind; |
|
|
240 | |
|
|
241 | GATHER(find_stats.calls); |
|
|
242 | |
|
|
243 | ind = hashstr(str); |
|
|
244 | ss = hash_table[ind]; |
|
|
245 | |
|
|
246 | /* Is there an entry for that hash? |
|
|
247 | */ |
|
|
248 | if (ss) { |
|
|
249 | /* Simple case first: Is the first string the right one? |
|
|
250 | */ |
|
|
251 | GATHER(find_stats.strcmps); |
|
|
252 | if (!strcmp(ss->string, str)) { |
|
|
253 | GATHER(find_stats.hashed); |
|
|
254 | return ss->string; |
|
|
255 | } else { |
|
|
256 | /* Recurse through the linked list, if there's one. |
|
|
257 | */ |
|
|
258 | while (ss->next) { |
|
|
259 | GATHER(find_stats.search); |
|
|
260 | GATHER(find_stats.strcmps); |
|
|
261 | ss = ss->next; |
|
|
262 | if (!strcmp(ss->string, str)) { |
|
|
263 | GATHER(find_stats.linked); |
|
|
264 | return ss->string; |
|
|
265 | } |
|
|
266 | } |
|
|
267 | /* No match. Fall through. |
|
|
268 | */ |
|
|
269 | } |
|
|
270 | } |
|
|
271 | return NULL; |
|
|
272 | } |
|
|
273 | |
|
|
274 | /* |
|
|
275 | * Description: |
|
|
276 | * This will reduce the refcount, and if it has reached 0, str will |
|
|
277 | * be freed. |
|
|
278 | * Return values: |
|
|
279 | * None |
|
|
280 | */ |
|
|
281 | |
|
|
282 | void |
|
|
283 | free_string(const char *str) { |
|
|
284 | shared_string *ss; |
|
|
285 | |
|
|
286 | GATHER(free_stats.calls); |
|
|
287 | |
|
|
288 | ss = SS(str); |
|
|
289 | |
|
|
290 | if ((--ss->refcount & ~TOPBIT) == 0) { |
|
|
291 | /* Remove this entry. |
|
|
292 | */ |
|
|
293 | if (ss->refcount & TOPBIT) { |
|
|
294 | /* We must put a new value into the hash_table[]. |
|
|
295 | */ |
|
|
296 | if (ss->next) { |
|
|
297 | *(ss->u.array) = ss->next; |
|
|
298 | ss->next->u.array = ss->u.array; |
|
|
299 | ss->next->refcount |= TOPBIT; |
|
|
300 | } else { |
|
|
301 | *(ss->u.array) = NULL; |
|
|
302 | } |
|
|
303 | free(ss); |
|
|
304 | } else { |
|
|
305 | /* Relink and free this struct. |
|
|
306 | */ |
|
|
307 | if (ss->next) |
|
|
308 | ss->next->u.previous = ss->u.previous; |
|
|
309 | ss->u.previous->next = ss->next; |
|
|
310 | free(ss); |
|
|
311 | } |
|
|
312 | } |
|
|
313 | } |
|
|
314 | |
|
|
315 | #ifdef SS_STATISTICS |
|
|
316 | |
|
|
317 | extern char errmsg[]; |
|
|
318 | |
|
|
319 | /* |
|
|
320 | * Description: |
|
|
321 | * The routines will gather statistics if SS_STATISTICS is defined. |
|
|
322 | * A call to this function will cause the statistics to be dumped |
|
|
323 | * into an external string errmsg, which must be large. |
|
|
324 | * Return values: |
|
|
325 | * None |
|
|
326 | */ |
|
|
327 | |
|
|
328 | void |
|
|
329 | ss_dump_statistics(void) { |
|
|
330 | static char line[80]; |
|
|
331 | |
|
|
332 | sprintf(errmsg, "%-13s %6s %6s %6s %6s %6s\n", |
|
|
333 | "", "calls", "hashed", "strcmp", "search", "linked"); |
|
|
334 | sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", |
|
|
335 | "add_string:", add_stats.calls, add_stats.hashed, |
|
|
336 | add_stats.strcmps, add_stats.search, add_stats.linked); |
|
|
337 | strcat(errmsg, line); |
|
|
338 | sprintf(line, "%-13s %6d\n", |
|
|
339 | "add_refcount:", add_ref_stats.calls); |
|
|
340 | strcat(errmsg, line); |
|
|
341 | sprintf(line, "%-13s %6d\n", |
|
|
342 | "free_string:", free_stats.calls); |
|
|
343 | strcat(errmsg, line); |
|
|
344 | sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", |
|
|
345 | "find_string:", find_stats.calls, find_stats.hashed, |
|
|
346 | find_stats.strcmps, find_stats.search, find_stats.linked); |
|
|
347 | strcat(errmsg, line); |
|
|
348 | sprintf(line, "%-13s %6d\n", |
|
|
349 | "hashstr:", hash_stats.calls); |
|
|
350 | strcat(errmsg, line); |
|
|
351 | } |
|
|
352 | #endif /* SS_STATISTICS */ |
|
|
353 | |
|
|
354 | /* |
|
|
355 | * Description: |
|
|
356 | * If (what & SS_DUMP_TABLE) dump the contents of the hash table to |
|
|
357 | * stderr. If (what & SS_DUMP_TOTALS) return a string which |
|
|
358 | * says how many entries etc. there are in the table. |
|
|
359 | * Return values: |
|
|
360 | * - a string or NULL |
|
|
361 | */ |
|
|
362 | |
|
|
363 | const char * |
|
|
364 | ss_dump_table(int what) { |
|
|
365 | static char totals[80]; |
|
|
366 | int entries = 0, refs = 0, links = 0; |
|
|
367 | int i; |
|
|
368 | |
|
|
369 | for (i = 0; i < TABLESIZE; i++) { |
|
|
370 | shared_string *ss; |
|
|
371 | |
|
|
372 | if ((ss = hash_table[i])!=NULL) { |
|
|
373 | ++entries; |
|
|
374 | refs += (ss->refcount & ~TOPBIT); |
|
|
375 | #if 1 /* Can't use stderr any longer, need to include global.h and |
|
|
376 | if (what & SS_DUMP_TABLE) |
|
|
377 | * use logfile. */ |
|
|
378 | fprintf(stderr, "%4d -- %4d refs '%s' %c\n", |
|
|
379 | i, (ss->refcount & ~TOPBIT), ss->string, |
|
|
380 | (ss->refcount & TOPBIT ? ' ' : '#')); |
|
|
381 | #endif |
|
|
382 | while (ss->next) { |
|
|
383 | ss = ss->next; |
|
|
384 | ++links; |
|
|
385 | refs += (ss->refcount & ~TOPBIT); |
|
|
386 | #if 1 |
|
|
387 | if (what & SS_DUMP_TABLE) |
|
|
388 | fprintf(stderr, " -- %4d refs '%s' %c\n", |
|
|
389 | (ss->refcount & ~TOPBIT), ss->string, |
|
|
390 | (ss->refcount & TOPBIT ? '*' : ' ')); |
|
|
391 | #endif |
|
|
392 | } |
|
|
393 | } |
|
|
394 | } |
|
|
395 | |
|
|
396 | if (what & SS_DUMP_TOTALS) { |
|
|
397 | sprintf(totals, "\n%d entries, %d refs, %d links.", |
|
|
398 | entries, refs, links); |
|
|
399 | return totals; |
|
|
400 | } |
|
|
401 | return NULL; |
|
|
402 | } |
|
|
403 | |
142 | |
404 | /* buf_overflow() - we don't want to exceed the buffer size of |
143 | /* buf_overflow() - we don't want to exceed the buffer size of |
405 | * buf1 by adding on buf2! Returns true if overflow will occur. |
144 | * buf1 by adding on buf2! Returns true if overflow will occur. |
406 | */ |
145 | */ |
407 | |
|
|
408 | int |
146 | int |
409 | buf_overflow (const char *buf1, const char *buf2, int bufsize) |
147 | buf_overflow (const char *buf1, const char *buf2, int bufsize) |
410 | { |
148 | { |
411 | int len1 = 0, len2 = 0; |
149 | int len1 = 0, len2 = 0; |
412 | |
150 | |
413 | if (buf1) |
151 | if (buf1) |
414 | len1 = strlen (buf1); |
152 | len1 = strlen (buf1); |
|
|
153 | |
415 | if (buf2) |
154 | if (buf2) |
416 | len2 = strlen (buf2); |
155 | len2 = strlen (buf2); |
|
|
156 | |
417 | if ((len1 + len2) >= bufsize) |
157 | if ((len1 + len2) >= bufsize) |
418 | return 1; |
|
|
419 | return 0; |
158 | return 1; |
|
|
159 | |
|
|
160 | return 0; |
420 | } |
161 | } |
421 | |
|
|