--- deliantra/server/common/shstr.C 2006/08/13 17:16:01 1.1
+++ deliantra/server/common/shstr.C 2007/11/08 19:43:23 1.28
@@ -1,421 +1,161 @@
/*
- * 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 Deliantra, the Roguelike Realtime MMORPG.
+ *
+ * Copyright (©) 2005,2006,2007 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
+ *
+ * Deliantra 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 3 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 this program. If not, see .
+ *
+ * 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.
+ * shstr.C
*/
-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
-}
+#include
+#include
+#include
+#include
-/*
- * Hashing-function used by the shared string library.
- */
+#include "global.h"
-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);
-}
+size_t shstr_alloc;
-/*
- * 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
- */
+ shstr_alloc += sizeof (int) * 2 + len + 1;
+ 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;
+shstr::gc ()
+{
+ static const char *curpos;
- GATHER(free_stats.calls);
+ auto (i, curpos ? ht.find (curpos) : ht.begin ());
- ss = SS(str);
+ if (i == ht.end ())
+ i = 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);
- }
- }
-}
+ int n = ht.size () / 256 + 16;
-#ifdef SS_STATISTICS
+ for (;;)
+ {
+ if (i == ht.end ())
+ {
+ curpos = 0;
+ return;
+ }
+ else if (!--n)
+ break;
+ else if (!refcnt (*i))
+ {
+ auto (o, i++);
+ const char *s = *o;
-extern char errmsg[];
+ ht.erase (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
- */
-
-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));
+ shstr_alloc -= sizeof (int) * 2 + length (s) + 1;
+ 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
- */
+// declare these here to get correct initialisation order
+#define def(str) const shstr shstr_ ## str (# str);
+# include "shstrinc.h"
+#undef def
-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
- }
- }
- }
+shstr skill_names[NUM_SKILLS];
- 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;
+}