server/include/util.h

/*
 * This file is part of Crossfire TRT, the Roguelike Realtime MORPG.
 * 
 * Copyright (©) 2005,2006,2007 Marc Alexander Lehmann / Robin Redeker / the Crossfire TRT team
 * 
 * Crossfire TRT 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 <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <crossfire@schmorp.de>
 */

#ifndef UTIL_H__
#define UTIL_H__

//#define PREFER_MALLOC

#if __GNUC__ >= 3
# define is_constant(c)             __builtin_constant_p (c)
# define expect(expr,value)         __builtin_expect ((expr),(value))
# define prefetch(addr,rw,locality) __builtin_prefetch (addr, rw, locality)
#else
# define is_constant(c)             0
# define expect(expr,value)         (expr)
# define prefetch(addr,rw,locality)
#endif

#if __GNUC__ < 4 || (__GNUC__ == 4 || __GNUC_MINOR__ < 4)
# define decltype(x) typeof(x)
#endif

// put into ifs if you are very sure that the expression
// is mostly true or mosty false. note that these return
// booleans, not the expression.
#define expect_false(expr) expect ((expr) != 0, 0)
#define expect_true(expr)  expect ((expr) != 0, 1)

#include <cstddef>
#include <cmath>
#include <new>
#include <vector>

#include <glib.h>

#include <shstr.h>
#include <traits.h>

// use C0X decltype for auto declarations until ISO C++ sanctifies them (if ever)
#define auto(var,expr) decltype(expr) var = (expr)

// very ugly macro that basicaly declares and initialises a variable
// that is in scope for the next statement only
// works only for stuff that can be assigned 0 and converts to false
// (note: works great for pointers)
// most ugly macro I ever wrote
#define statementvar(type, name, value) if (type name = 0) { } else if (((name) = (value)), 1)

// in range including end
#define IN_RANGE_INC(val,beg,end) \
  ((unsigned int)(val) - (unsigned int)(beg) <= (unsigned int)(end) - (unsigned int)(beg))

// in range excluding end
#define IN_RANGE_EXC(val,beg,end) \
  ((unsigned int)(val) - (unsigned int)(beg) <  (unsigned int)(end) - (unsigned int)(beg))

void fork_abort (const char *msg);

// rationale for using (U) not (T) is to reduce signed/unsigned issues,
// as a is often a constant while b is the variable. it is still a bug, though.
template<typename T, typename U> static inline T min (T a, U b) { return (U)a < b ? (U)a : b; }
template<typename T, typename U> static inline T max (T a, U b) { return (U)a > b ? (U)a : b; }
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; }

template<typename T, typename U> static inline void swap (T& a, U& b) { T t=a; a=(T)b; b=(U)t; }

template<typename T>
static inline T
lerp (T val, T min_in, T max_in, T min_out, T max_out)
{
  return (val - min_in) * (max_out - min_out) / (max_in - min_in) + min_out;
}

// lots of stuff taken from FXT

/* Rotate right. This is used in various places for checksumming */
//TODO: that sucks, use a better checksum algo
static inline uint32_t
rotate_right (uint32_t c, uint32_t count = 1)
{
  return (c << (32 - count)) | (c >> count);
}

static inline uint32_t
rotate_left (uint32_t c, uint32_t count = 1)
{
  return (c >> (32 - count)) | (c << count);
}

// Return abs(a-b)
// Both a and b must not have the most significant bit set
static inline uint32_t
upos_abs_diff (uint32_t a, uint32_t b)
{
  long d1 = b - a;
  long d2 = (d1 & (d1 >> 31)) << 1;

  return d1 - d2;               // == (b - d) - (a + d);
}

// Both a and b must not have the most significant bit set
static inline uint32_t
upos_min (uint32_t a, uint32_t b)
{
  int32_t d = b - a;
  d &= d >> 31;
  return a + d;
}

// Both a and b must not have the most significant bit set
static inline uint32_t
upos_max (uint32_t a, uint32_t b)
{
  int32_t d = b - a;
  d &= d >> 31;
  return b - d;
}

// this is much faster than crossfires original algorithm
// on modern cpus
inline int
isqrt (int n)
{
  return (int)sqrtf ((float)n);
}

// this is only twice as fast as naive sqrtf (dx*dy+dy*dy)
#if 0
// and has a max. error of 6 in the range -100..+100.
#else
// and has a max. error of 9 in the range -100..+100.
#endif
inline int 
idistance (int dx, int dy)
{ 
  unsigned int dx_ = abs (dx);
  unsigned int dy_ = abs (dy);

#if 0
  return dx_ > dy_
      ? (dx_ * 61685 + dy_ * 26870) >> 16
      : (dy_ * 61685 + dx_ * 26870) >> 16;
#else
  return dx_ + dy_ - min (dx_, dy_) * 5 / 8;
#endif
}

/*
 * absdir(int): Returns a number between 1 and 8, which represent
 * the "absolute" direction of a number (it actually takes care of
 * "overflow" in previous calculations of a direction).
 */
inline int
absdir (int d)
{
  return ((d - 1) & 7) + 1;
}

// makes dynamically allocated objects zero-initialised
struct zero_initialised
{
  void *operator new (size_t s, void *p)
  {
    memset (p, 0, s);
    return p;
  }

  void *operator new (size_t s)
  {
    return g_slice_alloc0 (s);
  }

  void *operator new[] (size_t s)
  {
    return g_slice_alloc0 (s);
  }

  void operator delete (void *p, size_t s)
  {
    g_slice_free1 (s, p);
  }

  void operator delete[] (void *p, size_t s)
  {
    g_slice_free1 (s, p);
  }
};

void *salloc_ (int n)            throw (std::bad_alloc);
void *salloc_ (int n, void *src) throw (std::bad_alloc);

// strictly the same as g_slice_alloc, but never returns 0
template<typename T>
inline T *salloc (int n = 1)     throw (std::bad_alloc) { return (T *)salloc_ (n * sizeof (T));              }

// also copies src into the new area, like "memdup"
// if src is 0, clears the memory
template<typename T>
inline T *salloc (int n, T *src) throw (std::bad_alloc) { return (T *)salloc_ (n * sizeof (T), (void *)src); }

// clears the memory
template<typename T>
inline T *salloc0(int n = 1)     throw (std::bad_alloc) { return (T *)salloc_ (n * sizeof (T), 0);           }

// for symmetry
template<typename T>
inline void sfree (T *ptr, int n = 1) throw ()
{
#ifdef PREFER_MALLOC
  free (ptr);
#else
  g_slice_free1 (n * sizeof (T), (void *)ptr);
#endif
}

// a STL-compatible allocator that uses g_slice
// boy, this is verbose
template<typename Tp>
struct slice_allocator
{
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef Tp *pointer;
  typedef const Tp *const_pointer;
  typedef Tp &reference;
  typedef const Tp &const_reference;
  typedef Tp value_type;

  template <class U> 
  struct rebind
  {
    typedef slice_allocator<U> other;
  };

  slice_allocator () throw () { }
  slice_allocator (const slice_allocator &o) throw () { }
  template<typename Tp2>
  slice_allocator (const slice_allocator<Tp2> &) throw () { }

  ~slice_allocator () { }

  pointer address (reference x) const { return &x; }
  const_pointer address (const_reference x) const { return &x; }

  pointer allocate (size_type n, const_pointer = 0)
  {
    return salloc<Tp> (n);
  }

  void deallocate (pointer p, size_type n)
  {
    sfree<Tp> (p, n);
  }

  size_type max_size ()const throw ()
  {
    return size_t (-1) / sizeof (Tp);
  }

  void construct (pointer p, const Tp &val)
  {
    ::new (p) Tp (val);
  }

  void destroy (pointer p)
  {
    p->~Tp ();
  }
};

// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
struct tausworthe_random_generator
{
  // generator
  uint32_t state [4];

  void operator =(const tausworthe_random_generator &src)
  {
    state [0] = src.state [0];
    state [1] = src.state [1];
    state [2] = src.state [2];
    state [3] = src.state [3];
  }

  void seed (uint32_t seed);
  uint32_t next ();

  // uniform distribution
  uint32_t operator ()(uint32_t num)
  {
    return is_constant (num)
             ? (next () * (uint64_t)num) >> 32U
             : get_range (num);
  }

  // return a number within (min .. max)
  int operator () (int r_min, int r_max)
  {
    return is_constant (r_min) && is_constant (r_max) && r_min <= r_max
              ? r_min + operator ()(r_max - r_min + 1)
              : get_range (r_min, r_max);
  }

  double operator ()()
  {
    return this->next () / (double)0xFFFFFFFFU;
  }

protected:
  uint32_t get_range (uint32_t r_max);
  int get_range (int r_min, int r_max);
};

typedef tausworthe_random_generator rand_gen;

extern rand_gen rndm;

template<class T>
struct refptr
{
  T *p;

  refptr () : p(0) { }
  refptr (const refptr<T> &p) : p(p.p) { if (p) p->refcnt_inc (); }
  refptr (T *p) : p(p) { if (p) p->refcnt_inc (); }
  ~refptr () { if (p) p->refcnt_dec (); }

  const refptr<T> &operator =(T *o)
  {
    if (p) p->refcnt_dec ();
    p = o;
    if (p) p->refcnt_inc ();

    return *this;
  }

  const refptr<T> &operator =(const refptr<T> o)
  {
    *this = o.p;
    return *this;
  }

  T &operator * () const { return *p; }
  T *operator ->() const { return p; }

  operator T *() const { return p; }
};

typedef refptr<maptile>   maptile_ptr;
typedef refptr<object>    object_ptr;
typedef refptr<archetype> arch_ptr;
typedef refptr<client>    client_ptr;
typedef refptr<player>    player_ptr;

struct str_hash
{
  std::size_t operator ()(const char *s) const
  {
    unsigned long hash = 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;
  }
};

struct str_equal
{
  bool operator ()(const char *a, const char *b) const
  {
    return !strcmp (a, b);
  }
};

// Mostly the same as std::vector, but insert/erase can reorder
// the elements, making insret/remove O(1) instead of O(n).
//
// NOTE: only some forms of erase/insert are available
template<class T>
struct unordered_vector : std::vector<T, slice_allocator<T> >
{
  typedef typename unordered_vector::iterator iterator;

  void erase (unsigned int pos)
  {
    if (pos < this->size () - 1)
      (*this)[pos] = (*this)[this->size () - 1];

    this->pop_back ();
  }

  void erase (iterator i)
  {
    erase ((unsigned int )(i - this->begin ()));
  }
};

// This container blends advantages of linked lists
// (efficiency) with vectors (random access) by
// by using an unordered vector and storing the vector
// index inside the object.
//
// + memory-efficient on most 64 bit archs
// + O(1) insert/remove
// + free unique (but varying) id for inserted objects
// + cache-friendly iteration
// - only works for pointers to structs
//
// NOTE: only some forms of erase/insert are available
typedef int object_vector_index;

template<class T, object_vector_index T::*indexmember>
struct object_vector : std::vector<T *, slice_allocator<T *> >
{
  typedef typename object_vector::iterator iterator;

  bool contains (const T *obj) const
  {
    return obj->*indexmember;
  }

  iterator find (const T *obj)
  {
    return obj->*indexmember
      ? this->begin () + obj->*indexmember - 1
      : this->end ();
  }

  void insert (T *obj)
  {
    push_back (obj);
    obj->*indexmember = this->size ();
  }

  void insert (T &obj)
  {
    insert (&obj);
  }

  void erase (T *obj)
  {
    unsigned int pos = obj->*indexmember;
    obj->*indexmember = 0;

    if (pos < this->size ())
      {
        (*this)[pos - 1] = (*this)[this->size () - 1];
        (*this)[pos - 1]->*indexmember = pos;
      }

    this->pop_back ();
  }

  void erase (T &obj)
  {
    erase (&obj);
  }
};

// basically does what strncpy should do, but appends "..." to strings exceeding length
void assign (char *dst, const char *src, int maxlen);

// type-safe version of assign
template<int N>
inline void assign (char (&dst)[N], const char *src)
{
  assign ((char *)&dst, src, N);
}

typedef double tstamp;

// return current time as timestampe
tstamp now ();

int similar_direction (int a, int b);

// like printf, but returns a std::string
const std::string format (const char *format, ...);

#endif

Revision:	1.51
Committed:	Sun Jul 1 05:00:18 2007 UTC (16 years, 11 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.50:	+11 -12 lines
Log Message:	- upgrade crossfire trt to the GPL version 3 (hopefully correctly). - add a single file covered by the GNU Affero General Public License (which is not yet released, so I used the current draft, which is legally a bit wavy, but its likely better than nothing as it expresses direct intent by the authors, and we can upgrade as soon as it has been released). * this should ensure availability of source code for the server at least and hopefully also archetypes and maps even when modified versions are not being distributed, in accordance of section 13 of the agplv3.
#	Content
1	/*
2	* This file is part of Crossfire TRT, the Roguelike Realtime MORPG.
3	*
4	* Copyright (©) 2005,2006,2007 Marc Alexander Lehmann / Robin Redeker / the Crossfire TRT team
5	*
6	* Crossfire TRT 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 <crossfire@schmorp.de>
20	*/
21
22	#ifndef UTIL_H__
23	#define UTIL_H__
24
25	//#define PREFER_MALLOC
26
27	#if __GNUC__ >= 3
28	# define is_constant(c) __builtin_constant_p (c)
29	# define expect(expr,value) __builtin_expect ((expr),(value))
30	# define prefetch(addr,rw,locality) __builtin_prefetch (addr, rw, locality)
31	#else
32	# define is_constant(c) 0
33	# define expect(expr,value) (expr)
34	# define prefetch(addr,rw,locality)
35	#endif
36
37	#if __GNUC__ < 4 \|\| (__GNUC__ == 4 \|\| __GNUC_MINOR__ < 4)
38	# define decltype(x) typeof(x)
39	#endif
40
41	// put into ifs if you are very sure that the expression
42	// is mostly true or mosty false. note that these return
43	// booleans, not the expression.
44	#define expect_false(expr) expect ((expr) != 0, 0)
45	#define expect_true(expr) expect ((expr) != 0, 1)
46
47	#include <cstddef>
48	#include <cmath>
49	#include <new>
50	#include <vector>
51
52	#include <glib.h>
53
54	#include <shstr.h>
55	#include <traits.h>
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 basicaly 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 fork_abort (const char *msg);
76
77	// rationale for using (U) not (T) is to reduce signed/unsigned issues,
78	// as a is often a constant while b is the variable. it is still a bug, though.
79	template<typename T, typename U> static inline T min (T a, U b) { return (U)a < b ? (U)a : b; }
80	template<typename T, typename U> static inline T max (T a, U b) { return (U)a > b ? (U)a : b; }
81	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; }
82
83	template<typename T, typename U> static inline void swap (T& a, U& b) { T t=a; a=(T)b; b=(U)t; }
84
85	template<typename T>
86	static inline T
87	lerp (T val, T min_in, T max_in, T min_out, T max_out)
88	{
89	return (val - min_in) * (max_out - min_out) / (max_in - min_in) + min_out;
90	}
91
92	// lots of stuff taken from FXT
93
94	/* Rotate right. This is used in various places for checksumming */
95	//TODO: that sucks, use a better checksum algo
96	static inline uint32_t
97	rotate_right (uint32_t c, uint32_t count = 1)
98	{
99	return (c << (32 - count)) \| (c >> count);
100	}
101
102	static inline uint32_t
103	rotate_left (uint32_t c, uint32_t count = 1)
104	{
105	return (c >> (32 - count)) \| (c << count);
106	}
107
108	// Return abs(a-b)
109	// Both a and b must not have the most significant bit set
110	static inline uint32_t
111	upos_abs_diff (uint32_t a, uint32_t b)
112	{
113	long d1 = b - a;
114	long d2 = (d1 & (d1 >> 31)) << 1;
115
116	return d1 - d2; // == (b - d) - (a + d);
117	}
118
119	// Both a and b must not have the most significant bit set
120	static inline uint32_t
121	upos_min (uint32_t a, uint32_t b)
122	{
123	int32_t d = b - a;
124	d &= d >> 31;
125	return a + d;
126	}
127
128	// Both a and b must not have the most significant bit set
129	static inline uint32_t
130	upos_max (uint32_t a, uint32_t b)
131	{
132	int32_t d = b - a;
133	d &= d >> 31;
134	return b - d;
135	}
136
137	// this is much faster than crossfires original algorithm
138	// on modern cpus
139	inline int
140	isqrt (int n)
141	{
142	return (int)sqrtf ((float)n);
143	}
144
145	// this is only twice as fast as naive sqrtf (dxdy+dydy)
146	#if 0
147	// and has a max. error of 6 in the range -100..+100.
148	#else
149	// and has a max. error of 9 in the range -100..+100.
150	#endif
151	inline int
152	idistance (int dx, int dy)
153	{
154	unsigned int dx_ = abs (dx);
155	unsigned int dy_ = abs (dy);
156
157	#if 0
158	return dx_ > dy_
159	? (dx_ * 61685 + dy_ * 26870) >> 16
160	: (dy_ * 61685 + dx_ * 26870) >> 16;
161	#else
162	return dx_ + dy_ - min (dx_, dy_) * 5 / 8;
163	#endif
164	}
165
166	/*
167	* absdir(int): Returns a number between 1 and 8, which represent
168	* the "absolute" direction of a number (it actually takes care of
169	* "overflow" in previous calculations of a direction).
170	*/
171	inline int
172	absdir (int d)
173	{
174	return ((d - 1) & 7) + 1;
175	}
176
177	// makes dynamically allocated objects zero-initialised
178	struct zero_initialised
179	{
180	void operator new (size_t s, void p)
181	{
182	memset (p, 0, s);
183	return p;
184	}
185
186	void *operator new (size_t s)
187	{
188	return g_slice_alloc0 (s);
189	}
190
191	void *operator new[] (size_t s)
192	{
193	return g_slice_alloc0 (s);
194	}
195
196	void operator delete (void *p, size_t s)
197	{
198	g_slice_free1 (s, p);
199	}
200
201	void operator delete[] (void *p, size_t s)
202	{
203	g_slice_free1 (s, p);
204	}
205	};
206
207	void *salloc_ (int n) throw (std::bad_alloc);
208	void salloc_ (int n, void src) throw (std::bad_alloc);
209
210	// strictly the same as g_slice_alloc, but never returns 0
211	template<typename T>
212	inline T salloc (int n = 1) throw (std::bad_alloc) { return (T )salloc_ (n * sizeof (T)); }
213
214	// also copies src into the new area, like "memdup"
215	// if src is 0, clears the memory
216	template<typename T>
217	inline T salloc (int n, T src) throw (std::bad_alloc) { return (T )salloc_ (n sizeof (T), (void *)src); }
218
219	// clears the memory
220	template<typename T>
221	inline T salloc0(int n = 1) throw (std::bad_alloc) { return (T )salloc_ (n * sizeof (T), 0); }
222
223	// for symmetry
224	template<typename T>
225	inline void sfree (T *ptr, int n = 1) throw ()
226	{
227	#ifdef PREFER_MALLOC
228	free (ptr);
229	#else
230	g_slice_free1 (n * sizeof (T), (void *)ptr);
231	#endif
232	}
233
234	// a STL-compatible allocator that uses g_slice
235	// boy, this is verbose
236	template<typename Tp>
237	struct slice_allocator
238	{
239	typedef size_t size_type;
240	typedef ptrdiff_t difference_type;
241	typedef Tp *pointer;
242	typedef const Tp *const_pointer;
243	typedef Tp &reference;
244	typedef const Tp &const_reference;
245	typedef Tp value_type;
246
247	template <class U>
248	struct rebind
249	{
250	typedef slice_allocator<U> other;
251	};
252
253	slice_allocator () throw () { }
254	slice_allocator (const slice_allocator &o) throw () { }
255	template<typename Tp2>
256	slice_allocator (const slice_allocator<Tp2> &) throw () { }
257
258	~slice_allocator () { }
259
260	pointer address (reference x) const { return &x; }
261	const_pointer address (const_reference x) const { return &x; }
262
263	pointer allocate (size_type n, const_pointer = 0)
264	{
265	return salloc<Tp> (n);
266	}
267
268	void deallocate (pointer p, size_type n)
269	{
270	sfree<Tp> (p, n);
271	}
272
273	size_type max_size ()const throw ()
274	{
275	return size_t (-1) / sizeof (Tp);
276	}
277
278	void construct (pointer p, const Tp &val)
279	{
280	::new (p) Tp (val);
281	}
282
283	void destroy (pointer p)
284	{
285	p->~Tp ();
286	}
287	};
288
289	// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
290	// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
291	// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
292	struct tausworthe_random_generator
293	{
294	// generator
295	uint32_t state [4];
296
297	void operator =(const tausworthe_random_generator &src)
298	{
299	state [0] = src.state [0];
300	state [1] = src.state [1];
301	state [2] = src.state [2];
302	state [3] = src.state [3];
303	}
304
305	void seed (uint32_t seed);
306	uint32_t next ();
307
308	// uniform distribution
309	uint32_t operator ()(uint32_t num)
310	{
311	return is_constant (num)
312	? (next () * (uint64_t)num) >> 32U
313	: get_range (num);
314	}
315
316	// return a number within (min .. max)
317	int operator () (int r_min, int r_max)
318	{
319	return is_constant (r_min) && is_constant (r_max) && r_min <= r_max
320	? r_min + operator ()(r_max - r_min + 1)
321	: get_range (r_min, r_max);
322	}
323
324	double operator ()()
325	{
326	return this->next () / (double)0xFFFFFFFFU;
327	}
328
329	protected:
330	uint32_t get_range (uint32_t r_max);
331	int get_range (int r_min, int r_max);
332	};
333
334	typedef tausworthe_random_generator rand_gen;
335
336	extern rand_gen rndm;
337
338	template<class T>
339	struct refptr
340	{
341	T *p;
342
343	refptr () : p(0) { }
344	refptr (const refptr<T> &p) : p(p.p) { if (p) p->refcnt_inc (); }
345	refptr (T *p) : p(p) { if (p) p->refcnt_inc (); }
346	~refptr () { if (p) p->refcnt_dec (); }
347
348	const refptr<T> &operator =(T *o)
349	{
350	if (p) p->refcnt_dec ();
351	p = o;
352	if (p) p->refcnt_inc ();
353
354	return *this;
355	}
356
357	const refptr<T> &operator =(const refptr<T> o)
358	{
359	*this = o.p;
360	return *this;
361	}
362
363	T &operator * () const { return *p; }
364	T *operator ->() const { return p; }
365
366	operator T *() const { return p; }
367	};
368
369	typedef refptr<maptile> maptile_ptr;
370	typedef refptr<object> object_ptr;
371	typedef refptr<archetype> arch_ptr;
372	typedef refptr<client> client_ptr;
373	typedef refptr<player> player_ptr;
374
375	struct str_hash
376	{
377	std::size_t operator ()(const char *s) const
378	{
379	unsigned long hash = 0;
380
381	/* use the one-at-a-time hash function, which supposedly is
382	* better than the djb2-like one used by perl5.005, but
383	* certainly is better then the bug used here before.
384	* see http://burtleburtle.net/bob/hash/doobs.html
385	*/
386	while (*s)
387	{
388	hash += *s++;
389	hash += hash << 10;
390	hash ^= hash >> 6;
391	}
392
393	hash += hash << 3;
394	hash ^= hash >> 11;
395	hash += hash << 15;
396
397	return hash;
398	}
399	};
400
401	struct str_equal
402	{
403	bool operator ()(const char a, const char b) const
404	{
405	return !strcmp (a, b);
406	}
407	};
408
409	// Mostly the same as std::vector, but insert/erase can reorder
410	// the elements, making insret/remove O(1) instead of O(n).
411	//
412	// NOTE: only some forms of erase/insert are available
413	template<class T>
414	struct unordered_vector : std::vector<T, slice_allocator<T> >
415	{
416	typedef typename unordered_vector::iterator iterator;
417
418	void erase (unsigned int pos)
419	{
420	if (pos < this->size () - 1)
421	(this)[pos] = (this)[this->size () - 1];
422
423	this->pop_back ();
424	}
425
426	void erase (iterator i)
427	{
428	erase ((unsigned int )(i - this->begin ()));
429	}
430	};
431
432	// This container blends advantages of linked lists
433	// (efficiency) with vectors (random access) by
434	// by using an unordered vector and storing the vector
435	// index inside the object.
436	//
437	// + memory-efficient on most 64 bit archs
438	// + O(1) insert/remove
439	// + free unique (but varying) id for inserted objects
440	// + cache-friendly iteration
441	// - only works for pointers to structs
442	//
443	// NOTE: only some forms of erase/insert are available
444	typedef int object_vector_index;
445
446	template<class T, object_vector_index T::*indexmember>
447	struct object_vector : std::vector<T , slice_allocator<T > >
448	{
449	typedef typename object_vector::iterator iterator;
450
451	bool contains (const T *obj) const
452	{
453	return obj->*indexmember;
454	}
455
456	iterator find (const T *obj)
457	{
458	return obj->*indexmember
459	? this->begin () + obj->*indexmember - 1
460	: this->end ();
461	}
462
463	void insert (T *obj)
464	{
465	push_back (obj);
466	obj->*indexmember = this->size ();
467	}
468
469	void insert (T &obj)
470	{
471	insert (&obj);
472	}
473
474	void erase (T *obj)
475	{
476	unsigned int pos = obj->*indexmember;
477	obj->*indexmember = 0;
478
479	if (pos < this->size ())
480	{
481	(this)[pos - 1] = (this)[this->size () - 1];
482	(this)[pos - 1]->indexmember = pos;
483	}
484
485	this->pop_back ();
486	}
487
488	void erase (T &obj)
489	{
490	erase (&obj);
491	}
492	};
493
494	// basically does what strncpy should do, but appends "..." to strings exceeding length
495	void assign (char dst, const char src, int maxlen);
496
497	// type-safe version of assign
498	template<int N>
499	inline void assign (char (&dst)[N], const char *src)
500	{
501	assign ((char *)&dst, src, N);
502	}
503
504	typedef double tstamp;
505
506	// return current time as timestampe
507	tstamp now ();
508
509	int similar_direction (int a, int b);
510
511	// like printf, but returns a std::string
512	const std::string format (const char *format, ...);
513
514	#endif
515