Crossfire Server, Trunk  1.75.0
shstr.cpp
Go to the documentation of this file.
1 /*
2  * Crossfire -- cooperative multi-player graphical RPG and adventure game
3  *
4  * Copyright (c) 1999-2014 Mark Wedel and the Crossfire Development Team
5  * Copyright (c) 1992 Frank Tore Johansen
6  *
7  * Crossfire is free software and comes with ABSOLUTELY NO WARRANTY. You are
8  * welcome to redistribute it under certain conditions. For details, please
9  * see COPYING and LICENSE.
10  *
11  * The authors can be reached via e-mail at <crossfire@metalforge.org>.
12  */
13 
35 #include <stdio.h>
36 #include <stddef.h>
37 #include <stdlib.h>
38 #include <sys/types.h>
39 #include <limits.h>
40 #include <string.h>
41 #include <global.h>
42 #include <libproto.h> /* For LOG */
43 
44 #if defined(__sun__) && defined(StupidSunHeaders)
45 #include <sys/time.h>
46 #include "sunos.h"
47 #endif
48 
49 #include <logger.h>
50 
51 #define SS_STATISTICS
52 #include "shstr.h"
53 
54 #ifdef WIN32
55 #include <win32.h>
56 #else
57 #include <autoconf.h>
58 #endif
59 #ifdef HAVE_LIBDMALLOC
60 #include <dmalloc.h>
61 #endif
62 
65 
69 void init_hash_table(void) {
70  /* A static object should be zeroed out always */
71 #if !defined(__STDC__)
72  (void)memset((void *)hash_table, 0, TABLESIZE*sizeof(shared_string *));
73 #endif
74 }
75 
84 static unsigned long hashstr(const char *str) {
85  unsigned long hash = 0;
86  int i = 0;
87  unsigned rot = 0;
88  const char *p;
89 
90  GATHER(hash_stats.calls);
91 
92  for (p = str; i < MAXSTRING && *p; p++, i++) {
93  hash ^= (unsigned long)*p<<rot;
94  rot += 2;
95  if (rot >= (sizeof(unsigned long)-sizeof(char))*CHAR_BIT)
96  rot = 0;
97  }
98  return (hash%TABLESIZE);
99 }
100 
112 static shared_string *new_shared_string(const char *str) {
113  shared_string *ss;
114 
115  /* Allocate room for a struct which can hold str. Note
116  * that some bytes for the string are already allocated in the
117  * shared_string struct.
118  */
119  ss = (shared_string *)malloc(sizeof(shared_string)-PADDING+strlen(str)+1);
120  if (ss == NULL)
122  ss->u.previous = NULL;
123  ss->next = NULL;
124  ss->refcount = 1;
125  strcpy(ss->string, str);
126  return ss;
127 }
128 
137 sstring add_string(const char *str) {
138  shared_string *ss;
139  unsigned long ind;
140 
141  GATHER(add_stats.calls);
142 
143  /* Should really core dump here, since functions should not be calling
144  * add_string with a null parameter. But this will prevent a few
145  * core dumps.
146  */
147  if (str == NULL) {
148 #ifdef MANY_CORES
149  abort();
150 #else
151  return NULL;
152 #endif
153  }
154 
155  ind = hashstr(str);
156  ss = hash_table[ind];
157 
158  /* Is there an entry for that hash?
159  */
160  if (ss) {
161  /* Simple case first: See if the first pointer matches. */
162  if (str != ss->string) {
163  GATHER(add_stats.strcmps);
164  if (strcmp(ss->string, str)) {
165  /* Apparantly, a string with the same hash value has this
166  * slot. We must see in the list if "str" has been
167  * registered earlier.
168  */
169  while (ss->next) {
170  GATHER(add_stats.search);
171  ss = ss->next;
172  if (ss->string != str) {
173  GATHER(add_stats.strcmps);
174  if (strcmp(ss->string, str)) {
175  /* This wasn't the right string... */
176  continue;
177  }
178  }
179  /* We found an entry for this string. Fix the
180  * refcount and exit.
181  */
182  GATHER(add_stats.linked);
183  ++(ss->refcount);
184 
185  return ss->string;
186  }
187  /* There are no occurences of this string in the hash table. */
188  {
189  shared_string *new_ss;
190 
191  GATHER(add_stats.linked);
192  new_ss = new_shared_string(str);
193  ss->next = new_ss;
194  new_ss->u.previous = ss;
195  return new_ss->string;
196  }
197  }
198  /* Fall through. */
199  }
200  GATHER(add_stats.hashed);
201  ++(ss->refcount);
202  return ss->string;
203  } else {
204  /* The string isn't registered, and the slot is empty. */
205  GATHER(add_stats.hashed);
206  hash_table[ind] = new_shared_string(str);
207 
208  /* One bit in refcount is used to keep track of the union. */
209  hash_table[ind]->refcount |= TOPBIT;
210  hash_table[ind]->u.array = &(hash_table[ind]);
211 
212  return hash_table[ind]->string;
213  }
214 }
215 
225  GATHER(add_ref_stats.calls);
226  ++(SS(str)->refcount);
227  return str;
228 }
229 
239  return (SS(str)->refcount)&~TOPBIT;
240 }
241 
250 sstring find_string(const char *str) {
251  shared_string *ss;
252  unsigned long ind;
253 
254  GATHER(find_stats.calls);
255 
256  ind = hashstr(str);
257  ss = hash_table[ind];
258 
259  /* Is there an entry for that hash?
260  */
261  if (ss) {
262  /* Simple case first: Is the first string the right one? */
263  GATHER(find_stats.strcmps);
264  if (!strcmp(ss->string, str)) {
265  GATHER(find_stats.hashed);
266  return ss->string;
267  } else {
268  /* Recurse through the linked list, if there's one. */
269  while (ss->next) {
270  GATHER(find_stats.search);
271  GATHER(find_stats.strcmps);
272  ss = ss->next;
273  if (!strcmp(ss->string, str)) {
274  GATHER(find_stats.linked);
275  return ss->string;
276  }
277  }
278  /* No match. Fall through. */
279  }
280  }
281  return NULL;
282 }
283 
294 void free_string(sstring str) {
295  shared_string *ss;
296 
297  GATHER(free_stats.calls);
298 
299  ss = SS(str);
300 
301  if ((--ss->refcount&~TOPBIT) == 0) {
302  /* Remove this entry. */
303  if (ss->refcount&TOPBIT) {
304  /* We must put a new value into the hash_table[].
305  */
306  if (ss->next) {
307  *(ss->u.array) = ss->next;
308  ss->next->u.array = ss->u.array;
309  ss->next->refcount |= TOPBIT;
310  } else {
311  *(ss->u.array) = NULL;
312  }
313  free(ss);
314  } else {
315  /* Relink and free this struct. */
316  if (ss->next)
317  ss->next->u.previous = ss->u.previous;
318  ss->u.previous->next = ss->next;
319  free(ss);
320  }
321  }
322 }
323 
324 #ifdef SS_STATISTICS
325 
337 void ss_dump_statistics(char *buf, size_t size) {
338  static char line[80];
339 
340  snprintf(buf, size, "%-13s %6s %6s %6s %6s %6s\n", "", "calls", "hashed", "strcmp", "search", "linked");
341  snprintf(line, sizeof(line), "%-13s %6d %6d %6d %6d %6d\n", "add_string:", add_stats.calls, add_stats.hashed, add_stats.strcmps, add_stats.search, add_stats.linked);
342  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
343  snprintf(line, sizeof(line), "%-13s %6d\n", "add_refcount:", add_ref_stats.calls);
344  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
345  snprintf(line, sizeof(line), "%-13s %6d\n", "free_string:", free_stats.calls);
346  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
347  snprintf(line, sizeof(line), "%-13s %6d %6d %6d %6d %6d\n", "find_string:", find_stats.calls, find_stats.hashed, find_stats.strcmps, find_stats.search, find_stats.linked);
348  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
349  snprintf(line, sizeof(line), "%-13s %6d\n", "hashstr:", hash_stats.calls);
350  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
351 }
352 #endif /* SS_STATISTICS */
353 
368 char *ss_dump_table(int what, char *buf, size_t size) {
369  int entries = 0, refs = 0, links = 0;
370  int i;
371 
372  for (i = 0; i < TABLESIZE; i++) {
373  shared_string *ss;
374 
375  if ((ss = hash_table[i]) != NULL) {
376  ++entries;
377  refs += (ss->refcount&~TOPBIT);
378  /* Can't use stderr any longer, need to include global.h and
379  if (what&SS_DUMP_TABLE)
380  * use logfile. */
381  LOG(llevDebug, "%4d -- %4d refs '%s' %c\n", i, (ss->refcount&~TOPBIT), ss->string, (ss->refcount&TOPBIT ? ' ' : '#'));
382 
383  while (ss->next) {
384  ss = ss->next;
385  ++links;
386  refs += (ss->refcount&~TOPBIT);
387 
388  if (what&SS_DUMP_TABLE)
389  LOG(llevDebug, " -- %4d refs '%s' %c\n", (ss->refcount&~TOPBIT), ss->string, (ss->refcount&TOPBIT ? '*' : ' '));
390  }
391  }
392  }
393 
394  if (what&SS_DUMP_TOTALS) {
395  snprintf(buf, size, "\n%d entries, %d refs, %d links.", entries, refs, links);
396  return buf;
397  }
398  return NULL;
399 }
400 
412 int buf_overflow(const char *buf1, const char *buf2, size_t bufsize) {
413  size_t len1 = 0, len2 = 0;
414 
415  if (buf1)
416  len1 = strlen(buf1);
417  if (buf2)
418  len2 = strlen(buf2);
419  if (len2 >= bufsize)
420  return 1;
421  if (len1 >= (bufsize-len2))
422  return 1;
423  return 0;
424 }
global.h
LOG
void LOG(LogLevel logLevel, const char *format,...)
Logs a message to stderr, or to file.
Definition: logger.cpp:58
TABLESIZE
#define TABLESIZE
The size of the shared strings hashtable.
Definition: shstr.h:13
ss_dump_statistics
void ss_dump_statistics(char *buf, size_t size)
A call to this function will cause the statistics to be dumped into specified buffer.
Definition: shstr.cpp:337
win32.h
logger.h
hashstr
static unsigned long hashstr(const char *str)
Hashing-function used by the shared string library.
Definition: shstr.cpp:84
shared_string::previous
shared_string * previous
Definition: shstr.h:73
shared_string::refcount
unsigned REFCOUNT_TYPE refcount
Definition: shstr.h:79
buf
StringBuffer * buf
Definition: readable.cpp:1565
shstr.h
is_valid_types_gen.line
line
Definition: is_valid_types_gen.py:34
add_refcount
sstring add_refcount(sstring str)
Like add_string(), but the string is already a shared string.
Definition: shstr.cpp:224
SS_DUMP_TABLE
#define SS_DUMP_TABLE
Definition: shstr.h:46
shared_string::array
shared_string ** array
Definition: shstr.h:72
add_string
sstring add_string(const char *str)
Share a string.
Definition: shstr.cpp:137
find_string
sstring find_string(const char *str)
Searches a string in the shared strings.
Definition: shstr.cpp:250
SS
#define SS(x)
SS(string) will return the address of the shared_string struct which contains "string".
Definition: shstr.h:44
MAXSTRING
#define MAXSTRING
Definition: config.h:528
ss_dump_table
char * ss_dump_table(int what, char *buf, size_t size)
Dump the contents of the share string tables.
Definition: shstr.cpp:368
query_refcount
int query_refcount(sstring str)
This will return the refcount of the string str.
Definition: shstr.cpp:238
hash_table
static shared_string * hash_table[TABLESIZE]
Hash table to store our string.
Definition: shstr.cpp:64
fatal
void fatal(enum fatal_error err)
fatal() is meant to be called whenever a fatal signal is intercepted.
Definition: utils.cpp:590
shared_string::next
shared_string * next
Definition: shstr.h:75
TOPBIT
#define TOPBIT
Definition: shstr.h:63
free_string
void free_string(sstring str)
This will reduce the refcount, and if it has reached 0, str will be freed.
Definition: shstr.cpp:294
shared_string::string
char string[PADDING]
Definition: shstr.h:84
init_hash_table
void init_hash_table(void)
Initialises the hash-table used by the shared string library.
Definition: shstr.cpp:69
sstring
const typedef char * sstring
Definition: sstring.h:2
shared_string::u
union shared_string::@7 u
PADDING
#define PADDING
Definition: shstr.h:65
shared_string
One actual shared string.
Definition: shstr.h:70
SS_DUMP_TOTALS
#define SS_DUMP_TOTALS
Definition: shstr.h:47
GATHER
#define GATHER(n)
Definition: shstr.h:60
buf_overflow
int buf_overflow(const char *buf1, const char *buf2, size_t bufsize)
We don't want to exceed the buffer size of buf1 by adding on buf2!
Definition: shstr.cpp:412
new_shared_string
static shared_string * new_shared_string(const char *str)
Allocates and initialises a new shared_string structure, containing the string str.
Definition: shstr.cpp:112
OUT_OF_MEMORY
@ OUT_OF_MEMORY
Definition: define.h:48
libproto.h
llevDebug
@ llevDebug
Only for debugging purposes.
Definition: logger.h:13
autoconf.h