--- deliantra/server/common/shstr.C 2006/09/03 08:05:39 1.4 +++ deliantra/server/common/shstr.C 2011/06/03 08:36:45 1.47 @@ -1,52 +1,74 @@ /* + * This file is part of Deliantra, the Roguelike Realtime MMORPG. + * + * Copyright (©) 2005,2006,2007,2008,2009,2010,2011 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 Affero 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 Affero GNU General Public License + * and the GNU General Public License along with this program. If not, see + * . + * + * The authors can be reached via e-mail to + */ + +/* * shstr.C */ #include #include - +#include #include -#include "shstr.h" +#include "global.h" -struct hash -{ - std::size_t operator ()(const char *s) const - { - unsigned long hash = 0; - unsigned int i = 0; - - /* use the one-at-a-time hash function, which supposedly is - * better than the djb2-like one used by perl5.005, but - * certainly is better then the bug used here before. - * see http://burtleburtle.net/bob/hash/doobs.html - */ - while (*s) - { - hash += *s++; - hash += hash << 10; - hash ^= hash >> 6; - } - - hash += hash << 3; - hash ^= hash >> 11; - hash += hash << 15; - - return hash; - } -}; +size_t shstr_alloc; + +typedef std::tr1::unordered_set > HT; + +static HT ht; +static int next_gc; + +#define NUM_INT 3 -struct equal +static const char * +makevec (const char *s) { - bool operator ()(const char *a, const char *b) const - { - return !strcmp (a, b); - } -}; + int len = strlen (s); + int alloc = sizeof (uint32_t) * NUM_INT + len + 1; -typedef std::tr1::unordered_set HT; + shstr_alloc += alloc; + char *v = (char *)g_slice_alloc (alloc); + v += sizeof (uint32_t) * NUM_INT; + + shstr::hash (v) = strhsh (s); + shstr::length (v) = len; + shstr::refcnt (v) = 1; -static HT ht; + memcpy (v, s, len + 1); + + return v; +} + +shstr_vec shstr_tmp::nullvec = { STRHSH_NULL, 0, 0xffffffff, "(null)" }; + +bool +shstr_tmp::contains (const char *substring) const +{ + //TODO: this is supposed to check for comma-seperation... + return s != null () + && substring + && strstr (s, substring); +} const char * shstr::find (const char *s) @@ -54,60 +76,82 @@ if (!s) return s; - HT::iterator i = ht.find (s); + auto (i, ht.find (s)); - return i != ht.end () - ? (char *)*i - : 0; + return i != ht.end ()? *i : 0; } const char * shstr::intern (const char *s) { if (!s) - return s; + return null (); if (const char *found = find (s)) - return found; - - int len = strlen (s); - - int *v = (int *)malloc (sizeof (int) * 2 + len + 1); - - v [0] = len; - v [1] = 0; - - v += 2; - - memcpy (v, s, len + 1); - - ht.insert ((char *)v); - - return (char *)v; + { + ++refcnt (found); + return found; + } + + --next_gc; + s = makevec (s); + ht.insert (s); + return s; } -// TODO: periodically test refcounts == 0 for a few strings (e.g. one hash bucket, -// exploiting the fatc that iterators stay valid for unordered_set). +// periodically test refcounts == 0 for a few strings +// this is the ONLY thing that erases stuff from ht. keep it that way. void shstr::gc () { -} + if (expect_true (next_gc > 0)) + return; -/* buf_overflow() - we don't want to exceed the buffer size of - * buf1 by adding on buf2! Returns true if overflow will occur. - */ + static const char *curpos; -int -buf_overflow (const char *buf1, const char *buf2, int bufsize) -{ - int len1 = 0, len2 = 0; + auto (i, curpos ? ht.find (curpos) : ht.begin ()); + + if (i == ht.end ()) + i = ht.begin (); + + int n = ht.size () / 256 + 16; + next_gc += n >> 1; + + for (;;) + { + if (i == ht.end ()) + { + curpos = 0; + return; + } + else if (!--n) + break; + else if (!refcnt (*i)) + { + auto (o, i++); + const char *s = *o; + + ht.erase (o); + + //printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s)); + int alloc = sizeof (uint32_t) * NUM_INT + length (s) + 1; + shstr_alloc -= alloc; + g_slice_free1 (alloc, (void *)(s - sizeof (uint32_t) * NUM_INT)); + } + else + ++i; + } - if (buf1) - len1 = strlen (buf1); - if (buf2) - len2 = strlen (buf2); - if ((len1 + len2) >= bufsize) - return 1; - return 0; + curpos = *i; } +// declare these here to get correct initialisation order +#define def2(id,str) const shstr id (str); +#define def(id) def2(shstr_ ## id, # id) +# include "shstrinc.h" +#undef def +#undef def2 + +materialtype_t material_null; + +struct freed_map freed_map;