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

Comparing deliantra/server/common/shstr.C (file contents):
Revision 1.6 by root, Sun Sep 3 11:37:25 2006 UTC vs.
Revision 1.32 by root, Wed Dec 31 17:35:37 2008 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
		45	shstr_alloc += sizeof (unsigned int) * 2 + len + 1;
		46	const char v = (const char ) (2 + (int )g_slice_alloc (sizeof (unsigned int) 2 + len + 1));
		47
		48	shstr::length (v) = len;
		49	shstr::refcnt (v) = 1;
		50
		51	memcpy ((char *) v, s, len + 1);
		52
		53	return v;
		54	}
		55
		56	static const char *
		57	makenull ()
		58	{
		59	const char *s = makevec ("(null)");
		60	shstr_tmp::length (s) = 0;
		61	//shstr ::refcnt (s) = 0xffffffff; // useful for debugging
		62	return s;
		63	}
		64
		65	const char *shstr_tmp::null = makenull ();
53		66
54	const char *	67	const char *
55	shstr::find (const char *s)	68	shstr::find (const char *s)
56	{	69	{
57	if (!s)	70	if (!s)
58	return s;	71	return s;
59		72
60	HT::iterator i = ht.find (s);	73	auto (i, ht.find (s));
61		74
62	return i != ht.end ()	75	return i != ht.end ()? *i : 0;
63	? *i
64	: 0;
65	}	76	}
66		77
67	const char *	78	const char *
68	shstr::intern (const char *s)	79	shstr::intern (const char *s)
69	{	80	{
70	if (!s)	81	if (!s)
71	return s;	82	return null;
72		83
73	if (const char *found = find (s))	84	if (const char *found = find (s))
74	{	85	{
75	++refcnt (found);	86	++refcnt (found);
76	return found;	87	return found;
77	}	88	}
78		89
79	int len = strlen (s);	90	--next_gc;
80		91	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);	92	ht.insert (s);
89
90	return v;	93	return s;
91	}	94	}
92		95
93	// periodically test refcounts == 0 for a few strings	96	// periodically test refcounts == 0 for a few strings
94	// this is the ONLY thing that erases stuff from ht. keep it that way.	97	// this is the ONLY thing that erases stuff from ht. keep it that way.
95	void	98	void
96	shstr::gc ()	99	shstr::gc ()
97	{	100	{
		101	if (expect_true (next_gc > 0))
		102	return;
		103
98	static const char *curpos;	104	static const char *curpos;
99		105
100	HT::iterator i = curpos ? ht.find (curpos) : ht.begin ();	106	auto (i, curpos ? ht.find (curpos) : ht.begin ());
101		107
102	if (i == ht.end ())	108	if (i == ht.end ())
103	i = ht.begin ();	109	i = ht.begin ();
104		110
105	// go through all strings roughly once every 4 minutes
106	int n = ht.size () / 256 + 16;	111	int n = ht.size () / 256 + 16;
		112	next_gc += n >> 1;
107		113
108	for (;;)	114	for (;;)
109	{	115	{
110	if (i == ht.end ())	116	if (i == ht.end ())
111	{	117	{
114	}	120	}
115	else if (!--n)	121	else if (!--n)
116	break;	122	break;
117	else if (!refcnt (*i))	123	else if (!refcnt (*i))
118	{	124	{
119	HT::iterator o = i++;	125	auto (o, i++);
120	const char s = o;	126	const char s = o;
		127
121	ht.erase (o);	128	ht.erase (o);
122		129
123	//printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s));	130	//printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s));
124	free (-2 + (int *)s);	131	shstr_alloc -= sizeof (unsigned int) * 2 + length (s) + 1;
		132	g_slice_free1 (sizeof (unsigned int) * 2 + length (s) + 1, -2 + (int *) s);
125	}	133	}
126	else	134	else
127	++i;	135	++i;
128	}	136	}
129		137
130	curpos = *i;	138	curpos = *i;
131	}	139	}
132		140
		141	const shstr shstr_null;
		142
		143	// declare these here to get correct initialisation order
		144	#define def(str) const shstr shstr_ ## str (# str);
		145	# include "shstrinc.h"
		146	#undef def
		147
		148	shstr skill_names[NUM_SKILLS];
		149
133	//TODO: this should of course not be here	150	//TODO: this should of course not be here
		151
134	/* buf_overflow() - we don't want to exceed the buffer size of	152	/* buf_overflow() - we don't want to exceed the buffer size of
135	* buf1 by adding on buf2! Returns true if overflow will occur.	153	* buf1 by adding on buf2! Returns true if overflow will occur.
136	*/	154	*/
137
138	int	155	int
139	buf_overflow (const char buf1, const char buf2, int bufsize)	156	buf_overflow (const char buf1, const char buf2, int bufsize)
140	{	157	{
141	int len1 = 0, len2 = 0;	158	int len1 = 0, len2 = 0;
142		159
143	if (buf1)	160	if (buf1)
144	len1 = strlen (buf1);	161	len1 = strlen (buf1);
		162
145	if (buf2)	163	if (buf2)
146	len2 = strlen (buf2);	164	len2 = strlen (buf2);
		165
147	if ((len1 + len2) >= bufsize)	166	if ((len1 + len2) >= bufsize)
148	return 1;
149	return 0;	167	return 1;
		168
		169	return 0;
150	}	170	}
151

Diff Legend

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

Comparing deliantra/server/common/shstr.C (file contents): Revision 1.6 by root, Sun Sep 3 11:37:25 2006 UTC vs. Revision 1.32 by root, Wed Dec 31 17:35:37 2008 UTC

Diff Legend

Comparing deliantra/server/common/shstr.C (file contents):
Revision 1.6 by root, Sun Sep 3 11:37:25 2006 UTC vs.
Revision 1.32 by root, Wed Dec 31 17:35:37 2008 UTC