Crossfire Server, Trunk
shstr.c
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 
21 #include <stdio.h>
22 #include <stddef.h>
23 #include <stdlib.h>
24 #include <sys/types.h>
25 #include <limits.h>
26 #include <string.h>
27 #include <global.h>
28 #include <libproto.h> /* For LOG */
29 
30 #if defined(__sun__) && defined(StupidSunHeaders)
31 #include <sys/time.h>
32 #include "sunos.h"
33 #endif
34 
35 #include <logger.h>
36 
37 #define SS_STATISTICS
38 #include "shstr.h"
39 
40 #ifdef WIN32
41 #include <win32.h>
42 #else
43 #include <autoconf.h>
44 #endif
45 #ifdef HAVE_LIBDMALLOC
46 #include <dmalloc.h>
47 #endif
48 
51 
55 void init_hash_table(void) {
56  /* A static object should be zeroed out always */
57 #if !defined(__STDC__)
58  (void)memset((void *)hash_table, 0, TABLESIZE*sizeof(shared_string *));
59 #endif
60 }
61 
70 static unsigned long hashstr(const char *str) {
71  unsigned long hash = 0;
72  int i = 0;
73  unsigned rot = 0;
74  const char *p;
75 
76  GATHER(hash_stats.calls);
77 
78  for (p = str; i < MAXSTRING && *p; p++, i++) {
79  hash ^= (unsigned long)*p<<rot;
80  rot += 2;
81  if (rot >= (sizeof(unsigned long)-sizeof(char))*CHAR_BIT)
82  rot = 0;
83  }
84  return (hash%TABLESIZE);
85 }
86 
98 static shared_string *new_shared_string(const char *str) {
99  shared_string *ss;
100 
101  /* Allocate room for a struct which can hold str. Note
102  * that some bytes for the string are already allocated in the
103  * shared_string struct.
104  */
105  ss = (shared_string *)malloc(sizeof(shared_string)-PADDING+strlen(str)+1);
106  if (ss == NULL)
108  ss->u.previous = NULL;
109  ss->next = NULL;
110  ss->refcount = 1;
111  strcpy(ss->string, str);
112  return ss;
113 }
114 
124 sstring add_string(const char *str) {
125  shared_string *ss;
126  unsigned long ind;
127 
128  GATHER(add_stats.calls);
129 
130  /* Should really core dump here, since functions should not be calling
131  * add_string with a null parameter. But this will prevent a few
132  * core dumps.
133  */
134  if (str == NULL) {
135 #ifdef MANY_CORES
136  abort();
137 #else
138  return NULL;
139 #endif
140  }
141 
142  ind = hashstr(str);
143  ss = hash_table[ind];
144 
145  /* Is there an entry for that hash?
146  */
147  if (ss) {
148  /* Simple case first: See if the first pointer matches. */
149  if (str != ss->string) {
150  GATHER(add_stats.strcmps);
151  if (strcmp(ss->string, str)) {
152  /* Apparantly, a string with the same hash value has this
153  * slot. We must see in the list if "str" has been
154  * registered earlier.
155  */
156  while (ss->next) {
157  GATHER(add_stats.search);
158  ss = ss->next;
159  if (ss->string != str) {
160  GATHER(add_stats.strcmps);
161  if (strcmp(ss->string, str)) {
162  /* This wasn't the right string... */
163  continue;
164  }
165  }
166  /* We found an entry for this string. Fix the
167  * refcount and exit.
168  */
169  GATHER(add_stats.linked);
170  ++(ss->refcount);
171 
172  return ss->string;
173  }
174  /* There are no occurences of this string in the hash table. */
175  {
176  shared_string *new_ss;
177 
178  GATHER(add_stats.linked);
179  new_ss = new_shared_string(str);
180  ss->next = new_ss;
181  new_ss->u.previous = ss;
182  return new_ss->string;
183  }
184  }
185  /* Fall through. */
186  }
187  GATHER(add_stats.hashed);
188  ++(ss->refcount);
189  return ss->string;
190  } else {
191  /* The string isn't registered, and the slot is empty. */
192  GATHER(add_stats.hashed);
194 
195  /* One bit in refcount is used to keep track of the union. */
196  hash_table[ind]->refcount |= TOPBIT;
197  hash_table[ind]->u.array = &(hash_table[ind]);
198 
199  return hash_table[ind]->string;
200  }
201 }
202 
211  GATHER(add_ref_stats.calls);
212  ++(SS(str)->refcount);
213  return str;
214 }
215 
225  return (SS(str)->refcount)&~TOPBIT;
226 }
227 
236 sstring find_string(const char *str) {
237  shared_string *ss;
238  unsigned long ind;
239 
240  GATHER(find_stats.calls);
241 
242  ind = hashstr(str);
243  ss = hash_table[ind];
244 
245  /* Is there an entry for that hash?
246  */
247  if (ss) {
248  /* Simple case first: Is the first string the right one? */
249  GATHER(find_stats.strcmps);
250  if (!strcmp(ss->string, str)) {
251  GATHER(find_stats.hashed);
252  return ss->string;
253  } else {
254  /* Recurse through the linked list, if there's one. */
255  while (ss->next) {
256  GATHER(find_stats.search);
257  GATHER(find_stats.strcmps);
258  ss = ss->next;
259  if (!strcmp(ss->string, str)) {
260  GATHER(find_stats.linked);
261  return ss->string;
262  }
263  }
264  /* No match. Fall through. */
265  }
266  }
267  return NULL;
268 }
269 
281  shared_string *ss;
282 
283  GATHER(free_stats.calls);
284 
285  ss = SS(str);
286 
287  if ((--ss->refcount&~TOPBIT) == 0) {
288  /* Remove this entry. */
289  if (ss->refcount&TOPBIT) {
290  /* We must put a new value into the hash_table[].
291  */
292  if (ss->next) {
293  *(ss->u.array) = ss->next;
294  ss->next->u.array = ss->u.array;
295  ss->next->refcount |= TOPBIT;
296  } else {
297  *(ss->u.array) = NULL;
298  }
299  free(ss);
300  } else {
301  /* Relink and free this struct. */
302  if (ss->next)
303  ss->next->u.previous = ss->u.previous;
304  ss->u.previous->next = ss->next;
305  free(ss);
306  }
307  }
308 }
309 
310 #ifdef SS_STATISTICS
311 
323 void ss_dump_statistics(char *buf, size_t size) {
324  static char line[80];
325 
326  snprintf(buf, size, "%-13s %6s %6s %6s %6s %6s\n", "", "calls", "hashed", "strcmp", "search", "linked");
327  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);
328  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
329  snprintf(line, sizeof(line), "%-13s %6d\n", "add_refcount:", add_ref_stats.calls);
330  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
331  snprintf(line, sizeof(line), "%-13s %6d\n", "free_string:", free_stats.calls);
332  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
333  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);
334  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
335  snprintf(line, sizeof(line), "%-13s %6d\n", "hashstr:", hash_stats.calls);
336  snprintf(buf+strlen(buf), size-strlen(buf), "%s", line);
337 }
338 #endif /* SS_STATISTICS */
339 
354 char *ss_dump_table(int what, char *buf, size_t size) {
355  int entries = 0, refs = 0, links = 0;
356  int i;
357 
358  for (i = 0; i < TABLESIZE; i++) {
359  shared_string *ss;
360 
361  if ((ss = hash_table[i]) != NULL) {
362  ++entries;
363  refs += (ss->refcount&~TOPBIT);
364  /* Can't use stderr any longer, need to include global.h and
365  if (what&SS_DUMP_TABLE)
366  * use logfile. */
367  LOG(llevDebug, "%4d -- %4d refs '%s' %c\n", i, (ss->refcount&~TOPBIT), ss->string, (ss->refcount&TOPBIT ? ' ' : '#'));
368 
369  while (ss->next) {
370  ss = ss->next;
371  ++links;
372  refs += (ss->refcount&~TOPBIT);
373 
374  if (what&SS_DUMP_TABLE)
375  LOG(llevDebug, " -- %4d refs '%s' %c\n", (ss->refcount&~TOPBIT), ss->string, (ss->refcount&TOPBIT ? '*' : ' '));
376  }
377  }
378  }
379 
380  if (what&SS_DUMP_TOTALS) {
381  snprintf(buf, size, "\n%d entries, %d refs, %d links.", entries, refs, links);
382  return buf;
383  }
384  return NULL;
385 }
386 
398 int buf_overflow(const char *buf1, const char *buf2, size_t bufsize) {
399  size_t len1 = 0, len2 = 0;
400 
401  if (buf1)
402  len1 = strlen(buf1);
403  if (buf2)
404  len2 = strlen(buf2);
405  if (len2 >= bufsize)
406  return 1;
407  if (len1 >= (bufsize-len2))
408  return 1;
409  return 0;
410 }
init_hash_table
void init_hash_table(void)
Definition: shstr.c:55
global.h
add_refcount
sstring add_refcount(sstring str)
Definition: shstr.c:210
nlohmann::detail::hash
std::size_t hash(const BasicJsonType &j)
hash a JSON value
Definition: json.hpp:5197
add_string
sstring add_string(const char *str)
Definition: shstr.c:124
_shared_string
Definition: shstr.h:70
TABLESIZE
#define TABLESIZE
Definition: shstr.h:13
win32.h
logger.h
hash_table
static shared_string * hash_table[TABLESIZE]
Definition: shstr.c:50
shstr.h
_shared_string::u
union _shared_string::@7 u
free_string
void free_string(sstring str)
Definition: shstr.c:280
hashstr
static unsigned long hashstr(const char *str)
Definition: shstr.c:70
is_valid_types_gen.line
line
Definition: is_valid_types_gen.py:34
SS_DUMP_TABLE
#define SS_DUMP_TABLE
Definition: shstr.h:46
_shared_string::refcount
unsigned REFCOUNT_TYPE refcount
Definition: shstr.h:79
fatal
void fatal(enum fatal_error err)
Definition: utils.c:580
_shared_string::previous
struct _shared_string * previous
Definition: shstr.h:73
make_face_from_files.str
str
Definition: make_face_from_files.py:24
find_string
sstring find_string(const char *str)
Definition: shstr.c:236
ss_dump_statistics
void ss_dump_statistics(char *buf, size_t size)
Definition: shstr.c:323
_shared_string::next
struct _shared_string * next
Definition: shstr.h:75
ss_dump_table
char * ss_dump_table(int what, char *buf, size_t size)
Definition: shstr.c:354
SS
#define SS(x)
Definition: shstr.h:44
MAXSTRING
#define MAXSTRING
Definition: config.h:520
buf_overflow
int buf_overflow(const char *buf1, const char *buf2, size_t bufsize)
Definition: shstr.c:398
sstring
const typedef char * sstring
Definition: global.h:40
_shared_string::array
struct _shared_string ** array
Definition: shstr.h:72
nlohmann::detail::void
j template void())
Definition: json.hpp:4099
TOPBIT
#define TOPBIT
Definition: shstr.h:63
new_shared_string
static shared_string * new_shared_string(const char *str)
Definition: shstr.c:98
LOG
void LOG(LogLevel logLevel, const char *format,...)
Definition: logger.c:51
_shared_string::string
char string[PADDING]
Definition: shstr.h:84
buf
StringBuffer * buf
Definition: readable.c:1610
query_refcount
int query_refcount(sstring str)
Definition: shstr.c:224
PADDING
#define PADDING
Definition: shstr.h:65
SS_DUMP_TOTALS
#define SS_DUMP_TOTALS
Definition: shstr.h:47
GATHER
#define GATHER(n)
Definition: shstr.h:60
OUT_OF_MEMORY
@ OUT_OF_MEMORY
Definition: define.h:48
libproto.h
llevDebug
@ llevDebug
Definition: logger.h:13
autoconf.h