Crossfire Server, Branch 1.12
R12190
|
00001 /* 00002 * static char *rcsid_shstr_c = 00003 * "$Id: shstr.c 11578 2009-02-23 22:02:27Z lalo $"; 00004 */ 00005 00013 #include <stdio.h> 00014 #include <stddef.h> 00015 #include <stdlib.h> 00016 #include <sys/types.h> 00017 #include <limits.h> 00018 #include <string.h> 00019 #include <global.h> 00020 #include <libproto.h> /* For LOG */ 00021 00022 #if defined(__sun__) && defined(StupidSunHeaders) 00023 #include <sys/time.h> 00024 #include "sunos.h" 00025 #endif 00026 00027 #include <logger.h> 00028 00029 #define SS_STATISTICS 00030 #include "shstr.h" 00031 00032 #ifdef WIN32 00033 #include <win32.h> 00034 #else 00035 #include <autoconf.h> 00036 #endif 00037 #ifdef HAVE_LIBDMALLOC 00038 #include <dmalloc.h> 00039 #endif 00040 00042 static shared_string *hash_table[TABLESIZE]; 00043 00047 void init_hash_table(void) { 00048 /* A static object should be zeroed out always */ 00049 #if !defined(__STDC__) 00050 (void)memset((void *)hash_table, 0, TABLESIZE*sizeof(shared_string *)); 00051 #endif 00052 } 00053 00062 static unsigned long hashstr(const char *str) { 00063 unsigned long hash = 0; 00064 int i = 0; 00065 unsigned rot = 0; 00066 const char *p; 00067 00068 GATHER(hash_stats.calls); 00069 00070 for (p = str; i < MAXSTRING && *p; p++, i++) { 00071 hash ^= (unsigned long)*p<<rot; 00072 rot += 2; 00073 if (rot >= (sizeof(unsigned long)-sizeof(char))*CHAR_BIT) 00074 rot = 0; 00075 } 00076 return (hash%TABLESIZE); 00077 } 00078 00090 static shared_string *new_shared_string(const char *str) { 00091 shared_string *ss; 00092 00093 /* Allocate room for a struct which can hold str. Note 00094 * that some bytes for the string are already allocated in the 00095 * shared_string struct. 00096 */ 00097 ss = (shared_string *)malloc(sizeof(shared_string)-PADDING+strlen(str)+1); 00098 if (ss == NULL) 00099 fatal(OUT_OF_MEMORY); 00100 ss->u.previous = NULL; 00101 ss->next = NULL; 00102 ss->refcount = 1; 00103 strcpy(ss->string, str); 00104 return ss; 00105 } 00106 00116 sstring add_string(const char *str) { 00117 shared_string *ss; 00118 unsigned long ind; 00119 00120 GATHER(add_stats.calls); 00121 00122 /* Should really core dump here, since functions should not be calling 00123 * add_string with a null parameter. But this will prevent a few 00124 * core dumps. 00125 */ 00126 if (str == NULL) { 00127 #ifdef MANY_CORES 00128 abort(); 00129 #else 00130 return NULL; 00131 #endif 00132 } 00133 00134 ind = hashstr(str); 00135 ss = hash_table[ind]; 00136 00137 /* Is there an entry for that hash? 00138 */ 00139 if (ss) { 00140 /* Simple case first: See if the first pointer matches. */ 00141 if (str != ss->string) { 00142 GATHER(add_stats.strcmps); 00143 if (strcmp(ss->string, str)) { 00144 /* Apparantly, a string with the same hash value has this 00145 * slot. We must see in the list if "str" has been 00146 * registered earlier. 00147 */ 00148 while (ss->next) { 00149 GATHER(add_stats.search); 00150 ss = ss->next; 00151 if (ss->string != str) { 00152 GATHER(add_stats.strcmps); 00153 if (strcmp(ss->string, str)) { 00154 /* This wasn't the right string... */ 00155 continue; 00156 } 00157 } 00158 /* We found an entry for this string. Fix the 00159 * refcount and exit. 00160 */ 00161 GATHER(add_stats.linked); 00162 ++(ss->refcount); 00163 00164 return ss->string; 00165 } 00166 /* There are no occurences of this string in the hash table. */ 00167 { 00168 shared_string *new_ss; 00169 00170 GATHER(add_stats.linked); 00171 new_ss = new_shared_string(str); 00172 ss->next = new_ss; 00173 new_ss->u.previous = ss; 00174 return new_ss->string; 00175 } 00176 } 00177 /* Fall through. */ 00178 } 00179 GATHER(add_stats.hashed); 00180 ++(ss->refcount); 00181 return ss->string; 00182 } else { 00183 /* The string isn't registered, and the slot is empty. */ 00184 GATHER(add_stats.hashed); 00185 hash_table[ind] = new_shared_string(str); 00186 00187 /* One bit in refcount is used to keep track of the union. */ 00188 hash_table[ind]->refcount |= TOPBIT; 00189 hash_table[ind]->u.array = &(hash_table[ind]); 00190 00191 return hash_table[ind]->string; 00192 } 00193 } 00194 00202 sstring add_refcount(sstring str) { 00203 GATHER(add_ref_stats.calls); 00204 ++(SS(str)->refcount); 00205 return str; 00206 } 00207 00216 int query_refcount(sstring str) { 00217 return (SS(str)->refcount)&~TOPBIT; 00218 } 00219 00228 sstring find_string(const char *str) { 00229 shared_string *ss; 00230 unsigned long ind; 00231 00232 GATHER(find_stats.calls); 00233 00234 ind = hashstr(str); 00235 ss = hash_table[ind]; 00236 00237 /* Is there an entry for that hash? 00238 */ 00239 if (ss) { 00240 /* Simple case first: Is the first string the right one? */ 00241 GATHER(find_stats.strcmps); 00242 if (!strcmp(ss->string, str)) { 00243 GATHER(find_stats.hashed); 00244 return ss->string; 00245 } else { 00246 /* Recurse through the linked list, if there's one. */ 00247 while (ss->next) { 00248 GATHER(find_stats.search); 00249 GATHER(find_stats.strcmps); 00250 ss = ss->next; 00251 if (!strcmp(ss->string, str)) { 00252 GATHER(find_stats.linked); 00253 return ss->string; 00254 } 00255 } 00256 /* No match. Fall through. */ 00257 } 00258 } 00259 return NULL; 00260 } 00261 00272 void free_string(sstring str) { 00273 shared_string *ss; 00274 00275 GATHER(free_stats.calls); 00276 00277 ss = SS(str); 00278 00279 if ((--ss->refcount&~TOPBIT) == 0) { 00280 /* Remove this entry. */ 00281 if (ss->refcount&TOPBIT) { 00282 /* We must put a new value into the hash_table[]. 00283 */ 00284 if (ss->next) { 00285 *(ss->u.array) = ss->next; 00286 ss->next->u.array = ss->u.array; 00287 ss->next->refcount |= TOPBIT; 00288 } else { 00289 *(ss->u.array) = NULL; 00290 } 00291 free(ss); 00292 } else { 00293 /* Relink and free this struct. */ 00294 if (ss->next) 00295 ss->next->u.previous = ss->u.previous; 00296 ss->u.previous->next = ss->next; 00297 free(ss); 00298 } 00299 } 00300 } 00301 00302 #ifdef SS_STATISTICS 00303 00315 void ss_dump_statistics(char *buf, size_t size) { 00316 static char line[80]; 00317 00318 snprintf(buf, size, "%-13s %6s %6s %6s %6s %6s\n", "", "calls", "hashed", "strcmp", "search", "linked"); 00319 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); 00320 snprintf(buf+strlen(buf), size-strlen(buf), "%s", line); 00321 snprintf(line, sizeof(line), "%-13s %6d\n", "add_refcount:", add_ref_stats.calls); 00322 snprintf(buf+strlen(buf), size-strlen(buf), "%s", line); 00323 snprintf(line, sizeof(line), "%-13s %6d\n", "free_string:", free_stats.calls); 00324 snprintf(buf+strlen(buf), size-strlen(buf), "%s", line); 00325 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); 00326 snprintf(buf+strlen(buf), size-strlen(buf), "%s", line); 00327 snprintf(line, sizeof(line), "%-13s %6d\n", "hashstr:", hash_stats.calls); 00328 snprintf(buf+strlen(buf), size-strlen(buf), "%s", line); 00329 } 00330 #endif /* SS_STATISTICS */ 00331 00346 char *ss_dump_table(int what, char *buf, size_t size) { 00347 int entries = 0, refs = 0, links = 0; 00348 int i; 00349 00350 for (i = 0; i < TABLESIZE; i++) { 00351 shared_string *ss; 00352 00353 if ((ss = hash_table[i]) != NULL) { 00354 ++entries; 00355 refs += (ss->refcount&~TOPBIT); 00356 /* Can't use stderr any longer, need to include global.h and 00357 if (what&SS_DUMP_TABLE) 00358 * use logfile. */ 00359 LOG(llevDebug, "%4d -- %4d refs '%s' %c\n", i, (ss->refcount&~TOPBIT), ss->string, (ss->refcount&TOPBIT ? ' ' : '#')); 00360 00361 while (ss->next) { 00362 ss = ss->next; 00363 ++links; 00364 refs += (ss->refcount&~TOPBIT); 00365 00366 if (what&SS_DUMP_TABLE) 00367 LOG(llevDebug, " -- %4d refs '%s' %c\n", (ss->refcount&~TOPBIT), ss->string, (ss->refcount&TOPBIT ? '*' : ' ')); 00368 } 00369 } 00370 } 00371 00372 if (what&SS_DUMP_TOTALS) { 00373 snprintf(buf, size, "\n%d entries, %d refs, %d links.", entries, refs, links); 00374 return buf; 00375 } 00376 return NULL; 00377 } 00378 00393 int buf_overflow(const char *buf1, const char *buf2, size_t bufsize) { 00394 size_t len1 = 0, len2 = 0; 00395 00396 if (buf1) 00397 len1 = strlen(buf1); 00398 if (buf2) 00399 len2 = strlen(buf2); 00400 if ((len1+len2) >= bufsize) 00401 return 1; 00402 return 0; 00403 }