Crossfire Server, Branch 1.12  R12190
shstr.c
Go to the documentation of this file.
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 }