[ViewVC] Diff of: cvs/deliantra/server/common/shstr.C

Comparing deliantra/server/common/shstr.C (file contents):
Revision 1.5 by root, Sun Sep 3 09:00:05 2006 UTC vs.
Revision 1.38 by root, Thu Jan 1 21:15:12 2009 UTC

		1	/*
		2	* This file is part of Deliantra, the Roguelike Realtime MMORPG.
		3	*
		4	* Copyright (©) 2005,2006,2007,2008 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
		5	*
		6	* Deliantra is free software: you can redistribute it and/or modify
		7	* it under the terms of the GNU General Public License as published by
		8	* the Free Software Foundation, either version 3 of the License, or
		9	* (at your option) any later version.
		10	*
		11	* This program is distributed in the hope that it will be useful,
		12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
		13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		14	* GNU General Public License for more details.
		15	*
		16	* You should have received a copy of the GNU General Public License
		17	* along with this program. If not, see <http://www.gnu.org/licenses/>.
		18	*
		19	* The authors can be reached via e-mail to <support@deliantra.net>
		20	*/
		21
1	/*	22	/*
2	* shstr.C	23	* shstr.C
3	*/	24	*/
4		25
5	#include <cstring>	26	#include <cstring>
6	#include <cstdlib>	27	#include <cstdlib>
7		28	#include <glib.h>
8	#include <tr1/unordered_set>	29	#include <tr1/unordered_set>
9		30
10	#include "shstr.h"	31	#include "global.h"
11		32
12	// NOTE: even with lots of stuff loaded, we do not usually have >>20000 strings.	33	size_t shstr_alloc;
13	// maybe refcounting is just overhead?
14		34
15	struct hash
16	{
17	std::size_t operator ()(const char *s) const
18	{
19	unsigned long hash = 0;
20	unsigned int i = 0;
21
22	/* use the one-at-a-time hash function, which supposedly is
23	* better than the djb2-like one used by perl5.005, but
24	* certainly is better then the bug used here before.
25	* see http://burtleburtle.net/bob/hash/doobs.html
26	*/
27	while (*s)
28	{
29	hash += *s++;
30	hash += hash << 10;
31	hash ^= hash >> 6;
32	}
33
34	hash += hash << 3;
35	hash ^= hash >> 11;
36	hash += hash << 15;
37
38	return hash;
39	}
40	};
41
42	struct equal
43	{
44	bool operator ()(const char a, const char b) const
45	{
46	return !strcmp (a, b);
47	}
48	};
49
50	typedef std::tr1::unordered_set<const char *, hash, equal> HT;	35	typedef std::tr1::unordered_set <const char , str_hash, str_equal, slice_allocator<const char > > HT;
51		36
52	static HT ht;	37	static HT ht;
		38	static int next_gc;
		39
		40	static const char *
		41	makevec (const char *s)
		42	{
		43	int len = strlen (s);
		44	int alloc = sizeof (uint32_t) * 2 + len + 1;
		45
		46	shstr_alloc += alloc;
		47	char v = (char )g_slice_alloc (alloc);
		48	v += sizeof (uint32_t) * 2;
		49
		50	shstr::length (v) = len;
		51	shstr::refcnt (v) = 1;
		52
		53	memcpy (v, s, len + 1);
		54
		55	return v;
		56	}
		57
		58	shstr_vec<sizeof "(null)"> shstr_tmp::nullvec = { 0, 0xffffffff, "(null)" };
53		59
54	const char *	60	const char *
55	shstr::find (const char *s)	61	shstr::find (const char *s)
56	{	62	{
57	if (!s)	63	if (!s)
58	return s;	64	return s;
59		65
60	HT::iterator i = ht.find (s);	66	auto (i, ht.find (s));
61		67
62	return i != ht.end ()	68	return i != ht.end ()? *i : 0;
63	? *i
64	: 0;
65	}	69	}
66		70
67	const char *	71	const char *
68	shstr::intern (const char *s)	72	shstr::intern (const char *s)
69	{	73	{
70	if (!s)	74	if (!s)
71	return s;	75	return null ();
72		76
73	if (const char *found = find (s))	77	if (const char *found = find (s))
74	{	78	{
75	++refcnt (found);	79	++refcnt (found);
76	return found;	80	return found;
77	}	81	}
78		82
79	int len = strlen (s);	83	--next_gc;
80		84	s = makevec (s);
81	const char v = (const char )(2 + (int )malloc (sizeof (int) 2 + len + 1));
82
83	length (v) = len;
84	refcnt (v) = 1;
85
86	memcpy ((char *)v, s, len + 1);
87
88	ht.insert (v);	85	ht.insert (s);
89
90	return v;	86	return s;
91	}	87	}
92		88
93	// periodically test refcounts == 0 for a few strings	89	// periodically test refcounts == 0 for a few strings
94	// this is the ONLY thing that erases stuff from ht. keep it that way.	90	// this is the ONLY thing that erases stuff from ht. keep it that way.
95	void	91	void
96	shstr::gc ()	92	shstr::gc ()
97	{	93	{
		94	if (expect_true (next_gc > 0))
		95	return;
		96
98	static const char *curpos;	97	static const char *curpos;
99		98
100	HT::iterator i = curpos ? ht.find (curpos) : ht.begin ();	99	auto (i, curpos ? ht.find (curpos) : ht.begin ());
101		100
102	if (i == ht.end ())	101	if (i == ht.end ())
103	i = ht.begin ();	102	i = ht.begin ();
104		103
105	// go through all strings roughly once every 4 minutes
106	for (int n = ht.size () / 256 + 16; --n; )	104	int n = ht.size () / 256 + 16;
		105	next_gc += n >> 1;
		106
		107	for (;;)
107	{	108	{
108	if (i == ht.end ())	109	if (i == ht.end ())
109	{	110	{
110	curpos = 0;	111	curpos = 0;
111	return;	112	return;
112	}	113	}
		114	else if (!--n)
		115	break;
		116	else if (!refcnt (*i))
		117	{
		118	auto (o, i++);
		119	const char s = o;
113		120
114	if (!refcnt (*i))
115	{
116	HT::iterator o = i++;
117	const char s = o;
118	ht.erase (o);	121	ht.erase (o);
119		122
120	//printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s));	123	//printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s));
121	free (-2 + (int *)s);	124	int alloc = sizeof (uint32_t) * 2 + length (s) + 1;
		125	shstr_alloc -= alloc;
		126	g_slice_free1 (alloc, (void )(s - sizeof (uint32_t) 2));
122	}	127	}
123	else	128	else
124	++i;	129	++i;
125	}	130	}
126		131
127	curpos = *i;	132	curpos = *i;
128	}	133	}
129		134
		135	// declare these here to get correct initialisation order
		136	#define def2(id,str) const shstr id (str);
		137	#define def(id) def2(shstr_ ## id, # id)
		138	# include "shstrinc.h"
		139	#undef def
		140	#undef def2
		141
		142	shstr skill_names[NUM_SKILLS];
		143
130	//TODO: this should of course not be here	144	//TODO: this should of course not be here
		145
131	/* buf_overflow() - we don't want to exceed the buffer size of	146	/* buf_overflow() - we don't want to exceed the buffer size of
132	* buf1 by adding on buf2! Returns true if overflow will occur.	147	* buf1 by adding on buf2! Returns true if overflow will occur.
133	*/	148	*/
134
135	int	149	int
136	buf_overflow (const char buf1, const char buf2, int bufsize)	150	buf_overflow (const char buf1, const char buf2, int bufsize)
137	{	151	{
138	int len1 = 0, len2 = 0;	152	int len1 = 0, len2 = 0;
139		153
140	if (buf1)	154	if (buf1)
141	len1 = strlen (buf1);	155	len1 = strlen (buf1);
		156
142	if (buf2)	157	if (buf2)
143	len2 = strlen (buf2);	158	len2 = strlen (buf2);
		159
144	if ((len1 + len2) >= bufsize)	160	if ((len1 + len2) >= bufsize)
145	return 1;
146	return 0;	161	return 1;
		162
		163	return 0;
147	}	164	}
148

Diff Legend

-–
+Removed lines
-+
+Added lines
-<
+Changed lines
->
+Changed lines

Comparing deliantra/server/common/shstr.C (file contents): Revision 1.5 by root, Sun Sep 3 09:00:05 2006 UTC vs. Revision 1.38 by root, Thu Jan 1 21:15:12 2009 UTC

Diff Legend

Comparing deliantra/server/common/shstr.C (file contents):
Revision 1.5 by root, Sun Sep 3 09:00:05 2006 UTC vs.
Revision 1.38 by root, Thu Jan 1 21:15:12 2009 UTC