ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/common/shstr.C
(Generate patch)

Comparing deliantra/server/common/shstr.C (file contents):
Revision 1.1 by elmex, Sun Aug 13 17:16:01 2006 UTC vs.
Revision 1.34 by root, Wed Dec 31 18:25:12 2008 UTC

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
40static 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
46void 26#include <cstring>
47init_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
33size_t shstr_alloc;
34
35typedef std::tr1::unordered_set <const char *, str_hash, str_equal, slice_allocator<const char *> > HT;
36
37static HT ht;
38static int next_gc;
39
40static const char *
41makevec (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/* 56shstr_vec<sizeof "(null)"> shstr_tmp::nullvec = { 0, 0xffffffff, "(null)" };
55 * Hashing-function used by the shared string library.
56 */
57 57
58static int
59hashstr(const char *str) {
60 unsigned long hash = 0;
61 int i = 0;
62 unsigned rot = 0;
63 const char *p; 58const char *
59shstr::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/* 69const char *
77 * Allocates and initialises a new shared_string structure, containing 70shstr::intern (const char *s)
78 * the string str. 71{
79 */ 72 if (!s)
73 return null ();
80 74
81static shared_string * 75 if (const char *found = find (s))
82new_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 89void
102 * string, a copy will be allocated, and a pointer to that is returned. 90shstr::gc ()
103 * Return values: 91{
104 * - pointer to string identical to str 92 if (expect_true (next_gc > 0))
105 */ 93 return;
106 94
107const char * 95 static const char *curpos;
108add_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:
195 * This will increase the refcount of the string str, which *must*
196 * have been returned from a previous add_string().
197 * Return values:
198 * - str
199 */
200 133
201const char * 134#define def(str) \
202add_refcount(const char *str) { 135 shstr_vec<sizeof (# str)> shstr_vec_ ## str = { sizeof (# str) - 1, 0xffffffff, # str }; \
203 GATHER(add_ref_stats.calls); 136 const shstr_const shstr_ ## str (shstr_vec_ ## str.string);
204 ++(SS(str)->refcount); 137# include "shstrinc.h"
205 /* This function should be declared 138#undef def
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 139
215/* 140shstr skill_names[NUM_SKILLS];
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 141
223int 142//TODO: this should of course not be here
224query_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
236const char *
237find_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
282void
283free_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
317extern 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
328void
329ss_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
363const char *
364ss_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 143
404/* buf_overflow() - we don't want to exceed the buffer size of 144/* buf_overflow() - we don't want to exceed the buffer size of
405 * buf1 by adding on buf2! Returns true if overflow will occur. 145 * buf1 by adding on buf2! Returns true if overflow will occur.
406 */ 146 */
407
408int 147int
409buf_overflow (const char *buf1, const char *buf2, int bufsize) 148buf_overflow (const char *buf1, const char *buf2, int bufsize)
410{ 149{
411 int len1 = 0, len2 = 0; 150 int len1 = 0, len2 = 0;
412 151
413 if (buf1) 152 if (buf1)
414 len1 = strlen (buf1); 153 len1 = strlen (buf1);
154
415 if (buf2) 155 if (buf2)
416 len2 = strlen (buf2); 156 len2 = strlen (buf2);
157
417 if ((len1 + len2) >= bufsize) 158 if ((len1 + len2) >= bufsize)
418 return 1;
419 return 0; 159 return 1;
160
161 return 0;
420} 162}
421

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines