[ViewVC] Diff of: cvs/deliantra/server/include/util.h

Comparing deliantra/server/include/util.h (file contents):
Revision 1.20 by root, Sun Dec 17 23:10:35 2006 UTC vs.
Revision 1.96 by root, Wed Nov 11 03:52:44 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 it under
		7	* the terms of the Affero GNU General Public License as published by the
		8	* Free Software Foundation, either version 3 of the License, or (at your
		9	* 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 Affero GNU General Public License
		17	* and the GNU General Public License along with this program. If not, see
		18	* <http://www.gnu.org/licenses/>.
		19	*
		20	* The authors can be reached via e-mail to <support@deliantra.net>
		21	*/
		22
1	#ifndef UTIL_H__	23	#ifndef UTIL_H__
2	#define UTIL_H__	24	#define UTIL_H__
3		25
4	#if __GNUC__ >= 3	26	#include <compiler.h>
5	# define is_constant(c) __builtin_constant_p (c)	27
		28	#define DEBUG_POISON 0x00 // poison memory before freeing it if != 0
		29	#define DEBUG_SALLOC 0 // add a debug wrapper around all sallocs
		30	#define PREFER_MALLOC 0 // use malloc and not the slice allocator
		31
		32	#include <pthread.h>
		33
		34	#include <cstddef>
		35	#include <cmath>
		36	#include <new>
		37	#include <vector>
		38
		39	#include <glib.h>
		40
		41	#include <shstr.h>
		42	#include <traits.h>
		43
		44	#if DEBUG_SALLOC
		45	# define g_slice_alloc0(s) debug_slice_alloc0(s)
		46	# define g_slice_alloc(s) debug_slice_alloc(s)
		47	# define g_slice_free1(s,p) debug_slice_free1(s,p)
		48	void *g_slice_alloc (unsigned long size);
		49	void *g_slice_alloc0 (unsigned long size);
		50	void g_slice_free1 (unsigned long size, void *ptr);
		51	#elif PREFER_MALLOC
		52	# define g_slice_alloc0(s) calloc (1, (s))
		53	# define g_slice_alloc(s) malloc ((s))
		54	# define g_slice_free1(s,p) free ((p))
		55	#endif
		56
		57	// use C0X decltype for auto declarations until ISO C++ sanctifies them (if ever)
		58	#define auto(var,expr) decltype(expr) var = (expr)
		59
		60	// very ugly macro that basically declares and initialises a variable
		61	// that is in scope for the next statement only
		62	// works only for stuff that can be assigned 0 and converts to false
		63	// (note: works great for pointers)
		64	// most ugly macro I ever wrote
		65	#define statementvar(type, name, value) if (type name = 0) { } else if (((name) = (value)), 1)
		66
		67	// in range including end
		68	#define IN_RANGE_INC(val,beg,end) \
		69	((unsigned int)(val) - (unsigned int)(beg) <= (unsigned int)(end) - (unsigned int)(beg))
		70
		71	// in range excluding end
		72	#define IN_RANGE_EXC(val,beg,end) \
		73	((unsigned int)(val) - (unsigned int)(beg) < (unsigned int)(end) - (unsigned int)(beg))
		74
		75	void cleanup (const char *cause, bool make_core = false);
		76	void fork_abort (const char *msg);
		77
		78	// rationale for using (U) not (T) is to reduce signed/unsigned issues,
		79	// as a is often a constant while b is the variable. it is still a bug, though.
		80	template<typename T, typename U> static inline T min (T a, U b) { return (U)a < b ? (U)a : b; }
		81	template<typename T, typename U> static inline T max (T a, U b) { return (U)a > b ? (U)a : b; }
		82	template<typename T, typename U, typename V> static inline T clamp (T v, U a, V b) { return v < (T)a ? (T)a : v >(T)b ? (T)b : v; }
		83
		84	template<typename T, typename U> static inline void min_it (T &v, U m) { v = min (v, (T)m); }
		85	template<typename T, typename U> static inline void max_it (T &v, U m) { v = max (v, (T)m); }
		86	template<typename T, typename U, typename V> static inline void clamp_it (T &v, U a, V b) { v = clamp (v, (T)a, (T)b); }
		87
		88	template<typename T, typename U> static inline void swap (T& a, U& b) { T t=a; a=(T)b; b=(U)t; }
		89
		90	template<typename T, typename U, typename V> static inline T min (T a, U b, V c) { return min (a, min (b, c)); }
		91	template<typename T, typename U, typename V> static inline T max (T a, U b, V c) { return max (a, max (b, c)); }
		92
		93	// sign returns -1 or +1
		94	template<typename T>
		95	static inline T sign (T v) { return v < 0 ? -1 : +1; }
		96	// relies on 2c representation
		97	template<>
		98	inline sint8 sign (sint8 v) { return 1 - (sint8 (uint8 (v) >> 7) * 2); }
		99
		100	// sign0 returns -1, 0 or +1
		101	template<typename T>
		102	static inline T sign0 (T v) { return v ? sign (v) : 0; }
		103
		104	// div* only work correctly for div > 0
		105	// div, with correct rounding (< 0.5 downwards, >=0.5 upwards)
		106	template<typename T> static inline T div (T val, T div)
		107	{
		108	return expect_false (val < 0) ? - ((-val + (div - 1) / 2) / div) : (val + div / 2) / div;
		109	}
		110	// div, round-up
		111	template<typename T> static inline T div_ru (T val, T div)
		112	{
		113	return expect_false (val < 0) ? - ((-val ) / div) : (val + div - 1) / div;
		114	}
		115	// div, round-down
		116	template<typename T> static inline T div_rd (T val, T div)
		117	{
		118	return expect_false (val < 0) ? - ((-val + (div - 1) ) / div) : (val ) / div;
		119	}
		120
		121	// lerp* only work correctly for min_in < max_in
		122	// Linear intERPolate, scales val from min_in..max_in to min_out..max_out
		123	template<typename T>
		124	static inline T
		125	lerp (T val, T min_in, T max_in, T min_out, T max_out)
		126	{
		127	return min_out + div <T> ((val - min_in) * (max_out - min_out), max_in - min_in);
		128	}
		129
		130	// lerp, round-down
		131	template<typename T>
		132	static inline T
		133	lerp_rd (T val, T min_in, T max_in, T min_out, T max_out)
		134	{
		135	return min_out + div_rd<T> ((val - min_in) * (max_out - min_out), max_in - min_in);
		136	}
		137
		138	// lerp, round-up
		139	template<typename T>
		140	static inline T
		141	lerp_ru (T val, T min_in, T max_in, T min_out, T max_out)
		142	{
		143	return min_out + div_ru<T> ((val - min_in) * (max_out - min_out), max_in - min_in);
		144	}
		145
		146	// lots of stuff taken from FXT
		147
		148	/* Rotate right. This is used in various places for checksumming */
		149	//TODO: that sucks, use a better checksum algo
		150	static inline uint32_t
		151	rotate_right (uint32_t c, uint32_t count = 1)
		152	{
		153	return (c << (32 - count)) \| (c >> count);
		154	}
		155
		156	static inline uint32_t
		157	rotate_left (uint32_t c, uint32_t count = 1)
		158	{
		159	return (c >> (32 - count)) \| (c << count);
		160	}
		161
		162	// Return abs(a-b)
		163	// Both a and b must not have the most significant bit set
		164	static inline uint32_t
		165	upos_abs_diff (uint32_t a, uint32_t b)
		166	{
		167	long d1 = b - a;
		168	long d2 = (d1 & (d1 >> 31)) << 1;
		169
		170	return d1 - d2; // == (b - d) - (a + d);
		171	}
		172
		173	// Both a and b must not have the most significant bit set
		174	static inline uint32_t
		175	upos_min (uint32_t a, uint32_t b)
		176	{
		177	int32_t d = b - a;
		178	d &= d >> 31;
		179	return a + d;
		180	}
		181
		182	// Both a and b must not have the most significant bit set
		183	static inline uint32_t
		184	upos_max (uint32_t a, uint32_t b)
		185	{
		186	int32_t d = b - a;
		187	d &= d >> 31;
		188	return b - d;
		189	}
		190
		191	// this is much faster than crossfire's original algorithm
		192	// on modern cpus
		193	inline int
		194	isqrt (int n)
		195	{
		196	return (int)sqrtf ((float)n);
		197	}
		198
		199	// this is kind of like the ^^ operator, if it would exist, without sequence point.
		200	// more handy than it looks like, due to the implicit !! done on its arguments
		201	inline bool
		202	logical_xor (bool a, bool b)
		203	{
		204	return a != b;
		205	}
		206
		207	inline bool
		208	logical_implies (bool a, bool b)
		209	{
		210	return a <= b;
		211	}
		212
		213	// this is only twice as fast as naive sqrtf (dxdy+dydy)
		214	#if 0
		215	// and has a max. error of 6 in the range -100..+100.
6	#else	216	#else
7	# define is_constant(c) 0	217	// and has a max. error of 9 in the range -100..+100.
8	#endif	218	#endif
		219	inline int
		220	idistance (int dx, int dy)
		221	{
		222	unsigned int dx_ = abs (dx);
		223	unsigned int dy_ = abs (dy);
9		224
10	#include <cstddef>	225	#if 0
		226	return dx_ > dy_
		227	? (dx_ * 61685 + dy_ * 26870) >> 16
		228	: (dy_ * 61685 + dx_ * 26870) >> 16;
		229	#else
		230	return dx_ + dy_ - min (dx_, dy_) * 5 / 8;
		231	#endif
		232	}
11		233
12	#include <glib.h>	234	/*
		235	* absdir(int): Returns a number between 1 and 8, which represent
		236	* the "absolute" direction of a number (it actually takes care of
		237	* "overflow" in previous calculations of a direction).
		238	*/
		239	inline int
		240	absdir (int d)
		241	{
		242	return ((d - 1) & 7) + 1;
		243	}
13		244
14	// use a gcc extension for auto declarations until ISO C++ sanctifies them	245	// avoid ctz name because netbsd or freebsd spams it's namespace with it
15	#define AUTODECL(var,expr) typeof(expr) var = (expr)	246	#if GCC_VERSION(3,4)
		247	static inline int least_significant_bit (uint32_t x)
		248	{
		249	return __builtin_ctz (x);
		250	}
		251	#else
		252	int least_significant_bit (uint32_t x);
		253	#endif
		254
		255	#define for_all_bits_sparse_32(mask, idxvar) \
		256	for (uint32_t idxvar, mask_ = mask; \
		257	mask_ && ((idxvar = least_significant_bit (mask_)), mask_ &= ~(1 << idxvar), 1);)
		258
		259	extern ssize_t slice_alloc; // statistics
		260
		261	void *salloc_ (int n) throw (std::bad_alloc);
		262	void salloc_ (int n, void src) throw (std::bad_alloc);
		263
		264	// strictly the same as g_slice_alloc, but never returns 0
		265	template<typename T>
		266	inline T salloc (int n = 1) throw (std::bad_alloc) { return (T )salloc_ (n * sizeof (T)); }
		267
		268	// also copies src into the new area, like "memdup"
		269	// if src is 0, clears the memory
		270	template<typename T>
		271	inline T salloc (int n, T src) throw (std::bad_alloc) { return (T )salloc_ (n sizeof (T), (void *)src); }
		272
		273	// clears the memory
		274	template<typename T>
		275	inline T salloc0(int n = 1) throw (std::bad_alloc) { return (T )salloc_ (n * sizeof (T), 0); }
		276
		277	// for symmetry
		278	template<typename T>
		279	inline void sfree (T *ptr, int n = 1) throw ()
		280	{
		281	if (expect_true (ptr))
		282	{
		283	slice_alloc -= n * sizeof (T);
		284	if (DEBUG_POISON) memset (ptr, DEBUG_POISON, n * sizeof (T));
		285	g_slice_free1 (n * sizeof (T), (void *)ptr);
		286	assert (slice_alloc >= 0);//D
		287	}
		288	}
		289
		290	// nulls the pointer
		291	template<typename T>
		292	inline void sfree0 (T *&ptr, int n = 1) throw ()
		293	{
		294	sfree<T> (ptr, n);
		295	ptr = 0;
		296	}
16		297
17	// makes dynamically allocated objects zero-initialised	298	// makes dynamically allocated objects zero-initialised
18	struct zero_initialised	299	struct zero_initialised
19	{	300	{
20	void operator new (size_t s, void p)	301	void operator new (size_t s, void p)
23	return p;	304	return p;
24	}	305	}
25		306
26	void *operator new (size_t s)	307	void *operator new (size_t s)
27	{	308	{
28	return g_slice_alloc0 (s);	309	return salloc0<char> (s);
29	}	310	}
30		311
31	void *operator new[] (size_t s)	312	void *operator new[] (size_t s)
32	{	313	{
33	return g_slice_alloc0 (s);	314	return salloc0<char> (s);
34	}	315	}
35		316
36	void operator delete (void *p, size_t s)	317	void operator delete (void *p, size_t s)
37	{	318	{
38	g_slice_free1 (s, p);	319	sfree ((char *)p, s);
39	}	320	}
40		321
41	void operator delete[] (void *p, size_t s)	322	void operator delete[] (void *p, size_t s)
42	{	323	{
43	g_slice_free1 (s, p);	324	sfree ((char *)p, s);
44	}	325	}
45	};	326	};
46		327
47	void *salloc_ (int n) throw (std::bad_alloc);	328	// makes dynamically allocated objects zero-initialised
48	void salloc_ (int n, void src) throw (std::bad_alloc);	329	struct slice_allocated
49
50	// strictly the same as g_slice_alloc, but never returns 0
51	template<typename T>
52	inline T salloc (int n = 1) throw (std::bad_alloc) { return (T )salloc_ (n * sizeof (T)); }
53
54	// also copies src into the new area, like "memdup"
55	// if src is 0, clears the memory
56	template<typename T>
57	inline T salloc (int n, T src) throw (std::bad_alloc) { return (T )salloc_ (n sizeof (T), (void *)src); }
58
59	// for symmetry
60	template<typename T>
61	inline void sfree (T *ptr, int n = 1) throw ()
62	{	330	{
63	g_slice_free1 (n * sizeof (T), (void *)ptr);	331	void operator new (size_t s, void p)
64	}	332	{
		333	return p;
		334	}
		335
		336	void *operator new (size_t s)
		337	{
		338	return salloc<char> (s);
		339	}
		340
		341	void *operator new[] (size_t s)
		342	{
		343	return salloc<char> (s);
		344	}
		345
		346	void operator delete (void *p, size_t s)
		347	{
		348	sfree ((char *)p, s);
		349	}
		350
		351	void operator delete[] (void *p, size_t s)
		352	{
		353	sfree ((char *)p, s);
		354	}
		355	};
65		356
66	// a STL-compatible allocator that uses g_slice	357	// a STL-compatible allocator that uses g_slice
67	// boy, this is verbose	358	// boy, this is verbose
68	template<typename Tp>	359	template<typename Tp>
69	struct slice_allocator	360	struct slice_allocator
…		…
81	{	372	{
82	typedef slice_allocator<U> other;	373	typedef slice_allocator<U> other;
83	};	374	};
84		375
85	slice_allocator () throw () { }	376	slice_allocator () throw () { }
86	slice_allocator (const slice_allocator &o) throw () { }	377	slice_allocator (const slice_allocator &) throw () { }
87	template<typename Tp2>	378	template<typename Tp2>
88	slice_allocator (const slice_allocator<Tp2> &) throw () { }	379	slice_allocator (const slice_allocator<Tp2> &) throw () { }
89		380
90	~slice_allocator () { }	381	~slice_allocator () { }
91		382
…		…
100	void deallocate (pointer p, size_type n)	391	void deallocate (pointer p, size_type n)
101	{	392	{
102	sfree<Tp> (p, n);	393	sfree<Tp> (p, n);
103	}	394	}
104		395
105	size_type max_size ()const throw ()	396	size_type max_size () const throw ()
106	{	397	{
107	return size_t (-1) / sizeof (Tp);	398	return size_t (-1) / sizeof (Tp);
108	}	399	}
109		400
110	void construct (pointer p, const Tp &val)	401	void construct (pointer p, const Tp &val)
…		…
116	{	407	{
117	p->~Tp ();	408	p->~Tp ();
118	}	409	}
119	};	410	};
120		411
		412	// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
		413	// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
		414	// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
		415	struct tausworthe_random_generator
		416	{
		417	uint32_t state [4];
		418
		419	void operator =(const tausworthe_random_generator &src)
		420	{
		421	state [0] = src.state [0];
		422	state [1] = src.state [1];
		423	state [2] = src.state [2];
		424	state [3] = src.state [3];
		425	}
		426
		427	void seed (uint32_t seed);
		428	uint32_t next ();
		429	};
		430
		431	// Xorshift RNGs, George Marsaglia
		432	// http://www.jstatsoft.org/v08/i14/paper
		433	// this one is about 40% faster than the tausworthe one above (i.e. not much),
		434	// despite the inlining, and has the issue of only creating 2**32-1 numbers.
		435	// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
		436	struct xorshift_random_generator
		437	{
		438	uint32_t x, y;
		439
		440	void operator =(const xorshift_random_generator &src)
		441	{
		442	x = src.x;
		443	y = src.y;
		444	}
		445
		446	void seed (uint32_t seed)
		447	{
		448	x = seed;
		449	y = seed * 69069U;
		450	}
		451
		452	uint32_t next ()
		453	{
		454	uint32_t t = x ^ (x << 10);
		455	x = y;
		456	y = y ^ (y >> 13) ^ t ^ (t >> 10);
		457	return y;
		458	}
		459	};
		460
		461	template<class generator>
		462	struct random_number_generator : generator
		463	{
		464	// uniform distribution, 0 .. max (0, num - 1)
		465	uint32_t operator ()(uint32_t num)
		466	{
		467	return !is_constant (num) ? get_range (num) // non-constant
		468	: num & (num - 1) ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two
		469	: this->next () & (num - 1); // constant, power-of-two
		470	}
		471
		472	// return a number within (min .. max)
		473	int operator () (int r_min, int r_max)
		474	{
		475	return is_constant (r_min) && is_constant (r_max) && r_min <= r_max
		476	? r_min + operator ()(r_max - r_min + 1)
		477	: get_range (r_min, r_max);
		478	}
		479
		480	double operator ()()
		481	{
		482	return this->next () / (double)0xFFFFFFFFU;
		483	}
		484
		485	protected:
		486	uint32_t get_range (uint32_t r_max);
		487	int get_range (int r_min, int r_max);
		488	};
		489
		490	typedef random_number_generator<tausworthe_random_generator> rand_gen;
		491
		492	extern rand_gen rndm, rmg_rndm;
		493
		494	INTERFACE_CLASS (attachable)
121	struct refcounted	495	struct refcnt_base
122	{	496	{
123	refcounted () : refcnt (0) { }	497	typedef int refcnt_t;
124	// virtual ~refcounted ();	498	mutable refcnt_t ACC (RW, refcnt);
		499
125	void refcnt_inc () { ++refcnt; }	500	MTH void refcnt_inc () const { ++refcnt; }
126	void refcnt_dec () { --refcnt; }	501	MTH void refcnt_dec () const { --refcnt; }
127	bool dead () { return refcnt == 0; }	502
128	mutable int refcnt;	503	refcnt_base () : refcnt (0) { }
129	#if 0
130	private:
131	static refcounted *rc_first;
132	refcounted *rc_next;
133	#endif
134	};	504	};
		505
		506	// to avoid branches with more advanced compilers
		507	extern refcnt_base::refcnt_t refcnt_dummy;
135		508
136	template<class T>	509	template<class T>
137	struct refptr	510	struct refptr
138	{	511	{
		512	// p if not null
		513	refcnt_base::refcnt_t *refcnt_ref () { return p ? &p->refcnt : &refcnt_dummy; }
		514
		515	void refcnt_dec ()
		516	{
		517	if (!is_constant (p))
		518	--*refcnt_ref ();
		519	else if (p)
		520	--p->refcnt;
		521	}
		522
		523	void refcnt_inc ()
		524	{
		525	if (!is_constant (p))
		526	++*refcnt_ref ();
		527	else if (p)
		528	++p->refcnt;
		529	}
		530
139	T *p;	531	T *p;
140		532
141	refptr () : p(0) { }	533	refptr () : p(0) { }
142	refptr (const refptr<T> &p) : p(p.p) { if (p) p->refcnt_inc (); }	534	refptr (const refptr<T> &p) : p(p.p) { refcnt_inc (); }
143	refptr (T *p) : p(p) { if (p) p->refcnt_inc (); }	535	refptr (T *p) : p(p) { refcnt_inc (); }
144	~refptr () { if (p) p->refcnt_dec (); }	536	~refptr () { refcnt_dec (); }
145		537
146	const refptr<T> &operator =(T *o)	538	const refptr<T> &operator =(T *o)
147	{	539	{
		540	// if decrementing ever destroys we need to reverse the order here
148	if (p) p->refcnt_dec ();	541	refcnt_dec ();
149	p = o;	542	p = o;
150	if (p) p->refcnt_inc ();	543	refcnt_inc ();
151
152	return *this;	544	return *this;
153	}	545	}
154		546
155	const refptr<T> &operator =(const refptr<T> o)	547	const refptr<T> &operator =(const refptr<T> &o)
156	{	548	{
157	*this = o.p;	549	*this = o.p;
158	return *this;	550	return *this;
159	}	551	}
160		552
161	T &operator * () const { return *p; }	553	T &operator * () const { return *p; }
162	T *operator ->() const { return p; }	554	T *operator ->() const { return p; }
163		555
164	operator T *() const { return p; }	556	operator T *() const { return p; }
165	};	557	};
166		558
		559	typedef refptr<maptile> maptile_ptr;
		560	typedef refptr<object> object_ptr;
		561	typedef refptr<archetype> arch_ptr;
		562	typedef refptr<client> client_ptr;
		563	typedef refptr<player> player_ptr;
		564
		565	#define STRHSH_NULL 2166136261
		566
		567	static inline uint32_t
		568	strhsh (const char *s)
		569	{
		570	// use FNV-1a hash (http://isthe.com/chongo/tech/comp/fnv/)
		571	// it is about twice as fast as the one-at-a-time one,
		572	// with good distribution.
		573	// FNV-1a is faster on many cpus because the multiplication
		574	// runs concurrently with the looping logic.
		575	uint32_t hash = STRHSH_NULL;
		576
		577	while (*s)
		578	hash = (hash ^ s++) 16777619;
		579
		580	return hash;
		581	}
		582
		583	static inline uint32_t
		584	memhsh (const char *s, size_t len)
		585	{
		586	uint32_t hash = STRHSH_NULL;
		587
		588	while (len--)
		589	hash = (hash ^ s++) 16777619;
		590
		591	return hash;
		592	}
		593
167	struct str_hash	594	struct str_hash
168	{	595	{
169	std::size_t operator ()(const char *s) const	596	std::size_t operator ()(const char *s) const
170	{	597	{
171	unsigned long hash = 0;
172
173	/* use the one-at-a-time hash function, which supposedly is
174	* better than the djb2-like one used by perl5.005, but
175	* certainly is better then the bug used here before.
176	* see http://burtleburtle.net/bob/hash/doobs.html
177	*/
178	while (*s)
179	{
180	hash += *s++;
181	hash += hash << 10;
182	hash ^= hash >> 6;
183	}
184
185	hash += hash << 3;
186	hash ^= hash >> 11;
187	hash += hash << 15;
188
189	return hash;	598	return strhsh (s);
		599	}
		600
		601	std::size_t operator ()(const shstr &s) const
		602	{
		603	return strhsh (s);
190	}	604	}
191	};	605	};
192		606
193	struct str_equal	607	struct str_equal
194	{	608	{
…		…
196	{	610	{
197	return !strcmp (a, b);	611	return !strcmp (a, b);
198	}	612	}
199	};	613	};
200		614
201	#include <vector>	615	// Mostly the same as std::vector, but insert/erase can reorder
202		616	// the elements, making append(=insert)/remove O(1) instead of O(n).
		617	//
		618	// NOTE: only some forms of erase are available
203	template<class obj>	619	template<class T>
204	struct unordered_vector : std::vector<obj, slice_allocator<obj> >	620	struct unordered_vector : std::vector<T, slice_allocator<T> >
205	{	621	{
206	typedef typename unordered_vector::iterator iterator;	622	typedef typename unordered_vector::iterator iterator;
207		623
208	void erase (unsigned int pos)	624	void erase (unsigned int pos)
209	{	625	{
…		…
217	{	633	{
218	erase ((unsigned int )(i - this->begin ()));	634	erase ((unsigned int )(i - this->begin ()));
219	}	635	}
220	};	636	};
221		637
222	template<typename T, typename U> static inline T min (T a, U b) { return a < (T)b ? a : (T)b; }	638	// This container blends advantages of linked lists
223	template<typename T, typename U> static inline T max (T a, U b) { return a > (T)b ? a : (T)b; }	639	// (efficiency) with vectors (random access) by
224	template<typename T, typename U, typename V> static inline T clamp (T v, U a, V b) { return v < (T)a ? a : v >(T)b ? b : v; }	640	// by using an unordered vector and storing the vector
		641	// index inside the object.
		642	//
		643	// + memory-efficient on most 64 bit archs
		644	// + O(1) insert/remove
		645	// + free unique (but varying) id for inserted objects
		646	// + cache-friendly iteration
		647	// - only works for pointers to structs
		648	//
		649	// NOTE: only some forms of erase/insert are available
		650	typedef int object_vector_index;
225		651
226	template<typename T, typename U> static inline void swap (T& a, U& b) { T t=a; a=(T)b; b=(U)t; }	652	template<class T, object_vector_index T::*indexmember>
		653	struct object_vector : std::vector<T , slice_allocator<T > >
		654	{
		655	typedef typename object_vector::iterator iterator;
		656
		657	bool contains (const T *obj) const
		658	{
		659	return obj->*indexmember;
		660	}
		661
		662	iterator find (const T *obj)
		663	{
		664	return obj->*indexmember
		665	? this->begin () + obj->*indexmember - 1
		666	: this->end ();
		667	}
		668
		669	void push_back (T *obj)
		670	{
		671	std::vector<T , slice_allocator<T > >::push_back (obj);
		672	obj->*indexmember = this->size ();
		673	}
		674
		675	void insert (T *obj)
		676	{
		677	push_back (obj);
		678	}
		679
		680	void insert (T &obj)
		681	{
		682	insert (&obj);
		683	}
		684
		685	void erase (T *obj)
		686	{
		687	unsigned int pos = obj->*indexmember;
		688	obj->*indexmember = 0;
		689
		690	if (pos < this->size ())
		691	{
		692	(this)[pos - 1] = (this)[this->size () - 1];
		693	(this)[pos - 1]->indexmember = pos;
		694	}
		695
		696	this->pop_back ();
		697	}
		698
		699	void erase (T &obj)
		700	{
		701	erase (&obj);
		702	}
		703	};
227		704
228	// basically does what strncpy should do, but appends "..." to strings exceeding length	705	// basically does what strncpy should do, but appends "..." to strings exceeding length
		706	// returns the number of bytes actually used (including \0)
229	void assign (char dst, const char src, int maxlen);	707	int assign (char dst, const char src, int maxsize);
230		708
231	// type-safe version of assign	709	// type-safe version of assign
232	template<int N>	710	template<int N>
233	inline void assign (char (&dst)[N], const char *src)	711	inline int assign (char (&dst)[N], const char *src)
234	{	712	{
235	assign ((char *)&dst, src, N);	713	return assign ((char *)&dst, src, N);
236	}	714	}
237		715
238	typedef double tstamp;	716	typedef double tstamp;
239		717
240	// return current time as timestampe	718	// return current time as timestamp
241	tstamp now ();	719	tstamp now ();
242		720
		721	int similar_direction (int a, int b);
		722
		723	// like v?sprintf, but returns a "static" buffer
		724	char vformat (const char format, va_list ap);
		725	char format (const char format, ...) attribute ((format (printf, 1, 2)));
		726
		727	// safety-check player input which will become object->msg
		728	bool msg_is_safe (const char *msg);
		729
		730	/////////////////////////////////////////////////////////////////////////////
		731	// threads, very very thin wrappers around pthreads
		732
		733	struct thread
		734	{
		735	pthread_t id;
		736
		737	void start (void (start_routine)(void ), void arg = 0);
		738
		739	void cancel ()
		740	{
		741	pthread_cancel (id);
		742	}
		743
		744	void *join ()
		745	{
		746	void *ret;
		747
		748	if (pthread_join (id, &ret))
		749	cleanup ("pthread_join failed", 1);
		750
		751	return ret;
		752	}
		753	};
		754
		755	// note that mutexes are not classes
		756	typedef pthread_mutex_t smutex;
		757
		758	#if __linux && defined (PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP)
		759	#define SMUTEX_INITIALISER PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP
		760	#else
		761	#define SMUTEX_INITIALISER PTHREAD_MUTEX_INITIALIZER
243	#endif	762	#endif
244		763
		764	#define SMUTEX(name) smutex name = SMUTEX_INITIALISER
		765	#define SMUTEX_LOCK(name) pthread_mutex_lock (&(name))
		766	#define SMUTEX_UNLOCK(name) pthread_mutex_unlock (&(name))
		767
		768	typedef pthread_cond_t scond;
		769
		770	#define SCOND(name) scond name = PTHREAD_COND_INITIALIZER
		771	#define SCOND_SIGNAL(name) pthread_cond_signal (&(name))
		772	#define SCOND_BROADCAST(name) pthread_cond_broadcast (&(name))
		773	#define SCOND_WAIT(name,mutex) pthread_cond_wait (&(name), &(mutex))
		774
		775	#endif
		776

Diff Legend

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

Comparing deliantra/server/include/util.h (file contents): Revision 1.20 by root, Sun Dec 17 23:10:35 2006 UTC vs. Revision 1.96 by root, Wed Nov 11 03:52:44 2009 UTC

Diff Legend

Comparing deliantra/server/include/util.h (file contents):
Revision 1.20 by root, Sun Dec 17 23:10:35 2006 UTC vs.
Revision 1.96 by root, Wed Nov 11 03:52:44 2009 UTC