--- deliantra/server/common/shstr.C 2006/08/13 17:16:01 1.1 +++ deliantra/server/common/shstr.C 2007/05/28 21:21:40 1.23 @@ -1,421 +1,155 @@ /* - * static char *rcsid_shstr_c = - * "$Id: shstr.C,v 1.1 2006/08/13 17:16:01 elmex Exp $"; - * - * shstr.c - * - * This is a simple shared strings package with a simple interface. - * - * char *find_string(const char *str) - * char *add_string(const char *str) - * char *add_refcount(char *str) - * void free_string(char *str) - * char *ss_dump_table(int what) - * void ss_dump_statistics() - * - * Author: Kjetil T. Homme, Oslo 1992. + * This file is part of Crossfire TRT, the Multiplayer Online Role Playing Game. + * + * Copyright (©) 2005,2006,2007 Marc Alexander Lehmann / Robin Redeker / the Crossfire TRT team + * + * Crossfire TRT is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * for more details. + * + * You should have received a copy of the GNU General Public License along + * with Crossfire TRT; if not, write to the Free Software Foundation, Inc. 51 + * Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * The authors can be reached via e-mail to */ -#include -#include -#include -#include -#include -#include - -#if defined (__sun__) && defined (StupidSunHeaders) -#include -#include "sunos.h" -#endif - -#include "shstr.h" - -#ifndef WIN32 -#include -#endif -#ifdef HAVE_LIBDMALLOC -#include -#endif - -static shared_string *hash_table[TABLESIZE]; - -/* - * Initialises the hash-table used by the shared string library. - */ - -void -init_hash_table(void) { - /* A static object should be zeroed out always */ -#if !defined(__STDC__) - (void) memset((void *)hash_table, 0, TABLESIZE * sizeof(shared_string *)); -#endif -} - /* - * Hashing-function used by the shared string library. - */ + * shstr.C + */ + +#include +#include +#include +#include -static int -hashstr(const char *str) { - unsigned long hash = 0; - int i = 0; - unsigned rot = 0; - const char *p; - - GATHER(hash_stats.calls); - - for (p = str; i < MAXSTRING && *p; p++, i++) { - hash ^= (unsigned long) *p << rot; - rot += 2; - if (rot >= (sizeof(long) - sizeof(char)) * CHAR_BIT) - rot = 0; - } - return (hash % TABLESIZE); -} +#include "global.h" -/* - * Allocates and initialises a new shared_string structure, containing - * the string str. - */ +typedef std::tr1::unordered_set , true> HT; -static shared_string * -new_shared_string(const char *str) { - shared_string *ss; - - /* Allocate room for a struct which can hold str. Note - * that some bytes for the string are already allocated in the - * shared_string struct. - */ - ss = (shared_string *) malloc(sizeof(shared_string) - PADDING + - strlen(str) + 1); - ss->u.previous = NULL; - ss->next = NULL; - ss->refcount = 1; - strcpy(ss->string, str); +static HT ht; - return ss; -} +static const char * +makevec (const char *s) +{ + int len = strlen (s); -/* - * Description: - * This will add 'str' to the hash table. If there's no entry for this - * string, a copy will be allocated, and a pointer to that is returned. - * Return values: - * - pointer to string identical to str - */ + const char *v = (const char *) (2 + (int *)g_slice_alloc (sizeof (int) * 2 + len + 1)); -const char * -add_string(const char *str) { - shared_string *ss; - int ind; - - GATHER(add_stats.calls); - - /* Should really core dump here, since functions should not be calling - * add_string with a null parameter. But this will prevent a few - * core dumps. - */ - if (str==NULL) { -#ifdef MANY_CORES - abort(); -#else - return NULL; -#endif - } + shstr::length (v) = len; + shstr::refcnt (v) = 1; - ind = hashstr(str); - ss = hash_table[ind]; + memcpy ((char *) v, s, len + 1); - /* Is there an entry for that hash? - */ - if (ss) { - /* Simple case first: See if the first pointer matches. - */ - if (str != ss->string) { - GATHER(add_stats.strcmps); - if (strcmp(ss->string, str)) { - /* Apparantly, a string with the same hash value has this - * slot. We must see in the list if "str" has been - * registered earlier. - */ - while (ss->next) { - GATHER(add_stats.search); - ss = ss->next; - if (ss->string != str) { - GATHER(add_stats.strcmps); - if (strcmp(ss->string, str)) { - /* This wasn't the right string... - */ - continue; - } - } - /* We found an entry for this string. Fix the - * refcount and exit. - */ - GATHER(add_stats.linked); - ++(ss->refcount); - - return ss->string; - } - /* There are no occurences of this string in the hash table. - */ - { - shared_string *new_ss; - - GATHER(add_stats.linked); - new_ss = new_shared_string(str); - ss->next = new_ss; - new_ss->u.previous = ss; - return new_ss->string; - } - } - /* Fall through. - */ - } - GATHER(add_stats.hashed); - ++(ss->refcount); - return ss->string; - } else { - /* The string isn't registered, and the slot is empty. - */ - GATHER(add_stats.hashed); - hash_table[ind] = new_shared_string(str); - - /* One bit in refcount is used to keep track of the union. - */ - hash_table[ind]->refcount |= TOPBIT; - hash_table[ind]->u.array = &(hash_table[ind]); + return v; +} - return hash_table[ind]->string; - } +static const char * +makenull () +{ + const char *s = makevec ("(null)"); + shstr::length (s) = 0; + return s; } -/* - * Description: - * This will increase the refcount of the string str, which *must* - * have been returned from a previous add_string(). - * Return values: - * - str - */ +const char *shstr::null = makenull (); const char * -add_refcount(const char *str) { - GATHER(add_ref_stats.calls); - ++(SS(str)->refcount); - /* This function should be declared - * const char *add_refcount(const char *) - * Unfortunately, that would require changing a lot of structs - * - * Yup, many changes, but may have make some bugs more visible :) - * -- Ryo 2005-08-12 - */ - return (char*)str; -} +shstr::find (const char *s) +{ + if (!s) + return s; -/* - * Description: - * This will return the refcount of the string str, which *must* - * have been returned from a previous add_string(). - * Return values: - * - length - */ + auto (i, ht.find (s)); -int -query_refcount(const char *str) { - return (SS(str)->refcount) & ~TOPBIT; + return i != ht.end ()? *i : 0; } -/* - * Description: - * This will see if str is in the hash table, and return the address - * of that string if it exists. - * Return values: - * - pointer to identical string or NULL - */ - const char * -find_string(const char *str) { - shared_string *ss; - int ind; - - GATHER(find_stats.calls); - - ind = hashstr(str); - ss = hash_table[ind]; - - /* Is there an entry for that hash? - */ - if (ss) { - /* Simple case first: Is the first string the right one? - */ - GATHER(find_stats.strcmps); - if (!strcmp(ss->string, str)) { - GATHER(find_stats.hashed); - return ss->string; - } else { - /* Recurse through the linked list, if there's one. - */ - while (ss->next) { - GATHER(find_stats.search); - GATHER(find_stats.strcmps); - ss = ss->next; - if (!strcmp(ss->string, str)) { - GATHER(find_stats.linked); - return ss->string; - } - } - /* No match. Fall through. - */ - } +shstr::intern (const char *s) +{ + if (!s) + return null; + + if (const char *found = find (s)) + { + ++refcnt (found); + return found; } - return NULL; -} -/* - * Description: - * This will reduce the refcount, and if it has reached 0, str will - * be freed. - * Return values: - * None - */ + s = makevec (s); + ht.insert (s); + return s; +} +// periodically test refcounts == 0 for a few strings +// this is the ONLY thing that erases stuff from ht. keep it that way. void -free_string(const char *str) { - shared_string *ss; - - GATHER(free_stats.calls); +shstr::gc () +{ + static const char *curpos; - ss = SS(str); + auto (i, curpos ? ht.find (curpos) : ht.begin ()); - if ((--ss->refcount & ~TOPBIT) == 0) { - /* Remove this entry. - */ - if (ss->refcount & TOPBIT) { - /* We must put a new value into the hash_table[]. - */ - if (ss->next) { - *(ss->u.array) = ss->next; - ss->next->u.array = ss->u.array; - ss->next->refcount |= TOPBIT; - } else { - *(ss->u.array) = NULL; - } - free(ss); - } else { - /* Relink and free this struct. - */ - if (ss->next) - ss->next->u.previous = ss->u.previous; - ss->u.previous->next = ss->next; - free(ss); - } - } -} + if (i == ht.end ()) + i = ht.begin (); -#ifdef SS_STATISTICS + // go through all strings roughly once every 4 minutes + int n = ht.size () / 256 + 16; -extern char errmsg[]; + for (;;) + { + if (i == ht.end ()) + { + curpos = 0; + return; + } + else if (!--n) + break; + else if (!refcnt (*i)) + { + auto (o, i++); + const char *s = *o; -/* - * Description: - * The routines will gather statistics if SS_STATISTICS is defined. - * A call to this function will cause the statistics to be dumped - * into an external string errmsg, which must be large. - * Return values: - * None - */ + ht.erase (o); -void -ss_dump_statistics(void) { - static char line[80]; + //printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s)); + g_slice_free1 (sizeof (int) * 2 + length (s) + 1, -2 + (int *) s); + } + else + ++i; + } - sprintf(errmsg, "%-13s %6s %6s %6s %6s %6s\n", - "", "calls", "hashed", "strcmp", "search", "linked"); - sprintf(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); - strcat(errmsg, line); - sprintf(line, "%-13s %6d\n", - "add_refcount:", add_ref_stats.calls); - strcat(errmsg, line); - sprintf(line, "%-13s %6d\n", - "free_string:", free_stats.calls); - strcat(errmsg, line); - sprintf(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); - strcat(errmsg, line); - sprintf(line, "%-13s %6d\n", - "hashstr:", hash_stats.calls); - strcat(errmsg, line); + curpos = *i; } -#endif /* SS_STATISTICS */ -/* - * Description: - * If (what & SS_DUMP_TABLE) dump the contents of the hash table to - * stderr. If (what & SS_DUMP_TOTALS) return a string which - * says how many entries etc. there are in the table. - * Return values: - * - a string or NULL - */ +shstr skill_names[NUM_SKILLS]; -const char * -ss_dump_table(int what) { - static char totals[80]; - int entries = 0, refs = 0, links = 0; - int i; - - for (i = 0; i < TABLESIZE; i++) { - shared_string *ss; - - if ((ss = hash_table[i])!=NULL) { - ++entries; - refs += (ss->refcount & ~TOPBIT); -#if 1 /* Can't use stderr any longer, need to include global.h and - if (what & SS_DUMP_TABLE) - * use logfile. */ - fprintf(stderr, "%4d -- %4d refs '%s' %c\n", - i, (ss->refcount & ~TOPBIT), ss->string, - (ss->refcount & TOPBIT ? ' ' : '#')); -#endif - while (ss->next) { - ss = ss->next; - ++links; - refs += (ss->refcount & ~TOPBIT); -#if 1 - if (what & SS_DUMP_TABLE) - fprintf(stderr, " -- %4d refs '%s' %c\n", - (ss->refcount & ~TOPBIT), ss->string, - (ss->refcount & TOPBIT ? '*' : ' ')); -#endif - } - } - } +// what weird misoptimisation is this again? +const shstr undead_name ("undead"); - if (what & SS_DUMP_TOTALS) { - sprintf(totals, "\n%d entries, %d refs, %d links.", - entries, refs, links); - return totals; - } - return NULL; -} +//TODO: this should of course not be here /* buf_overflow() - we don't want to exceed the buffer size of * buf1 by adding on buf2! Returns true if overflow will occur. */ - -int +int buf_overflow (const char *buf1, const char *buf2, int bufsize) { - int len1 = 0, len2 = 0; + int len1 = 0, len2 = 0; - if (buf1) - len1 = strlen (buf1); - if (buf2) - len2 = strlen (buf2); - if ((len1 + len2) >= bufsize) - return 1; - return 0; -} + if (buf1) + len1 = strlen (buf1); + if (buf2) + len2 = strlen (buf2); + if ((len1 + len2) >= bufsize) + return 1; + return 0; +}