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.
#	User	Rev	Content
1	root	1.46	/*
2	root	1.51	* This file is part of Crossfire TRT, the Roguelike Realtime MORPG.
3	root	1.46	*
4			* Copyright (©) 2005,2006,2007 Marc Alexander Lehmann / Robin Redeker / the Crossfire TRT team
5			*
6	root	1.51	* 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	root	1.46	*
11	root	1.51	* 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	root	1.46	*
16	root	1.51	* 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	root	1.46	*
19			* The authors can be reached via e-mail to <crossfire@schmorp.de>
20			*/
21
22	root	1.1	#ifndef UTIL_H__
23			#define UTIL_H__
24
25	root	1.36	//#define PREFER_MALLOC
26
27	root	1.2	#if __GNUC__ >= 3
28	root	1.45	# 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	root	1.2	#else
32	root	1.45	# define is_constant(c) 0
33			# define expect(expr,value) (expr)
34			# define prefetch(addr,rw,locality)
35	root	1.2	#endif
36
37	root	1.47	#if __GNUC__ < 4 \|\| (__GNUC__ == 4 \|\| __GNUC_MINOR__ < 4)
38			# define decltype(x) typeof(x)
39			#endif
40
41	root	1.45	// 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	root	1.11	#include <cstddef>
48	root	1.28	#include <cmath>
49	root	1.25	#include <new>
50			#include <vector>
51	root	1.11
52			#include <glib.h>
53
54	root	1.25	#include <shstr.h>
55			#include <traits.h>
56
57	root	1.49	// use C0X decltype for auto declarations until ISO C++ sanctifies them (if ever)
58	root	1.47	#define auto(var,expr) decltype(expr) var = (expr)
59	root	1.14
60	root	1.26	// 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	root	1.48	#define statementvar(type, name, value) if (type name = 0) { } else if (((name) = (value)), 1)
66	root	1.26
67	root	1.27	// 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	root	1.31	void fork_abort (const char *msg);
76
77	root	1.35	// 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	root	1.32
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	root	1.44	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	root	1.37	// lots of stuff taken from FXT
93
94			/* Rotate right. This is used in various places for checksumming */
95	root	1.38	//TODO: that sucks, use a better checksum algo
96	root	1.37	static inline uint32_t
97	root	1.38	rotate_right (uint32_t c, uint32_t count = 1)
98	root	1.37	{
99	root	1.38	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	root	1.37	}
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	root	1.28	// 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	root	1.30	return dx_ + dy_ - min (dx_, dy_) * 5 / 8;
163	root	1.28	#endif
164			}
165
166	root	1.29	/*
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	root	1.28
177	root	1.1	// makes dynamically allocated objects zero-initialised
178			struct zero_initialised
179			{
180	root	1.11	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	root	1.20	void *salloc_ (int n) throw (std::bad_alloc);
208			void salloc_ (int n, void src) throw (std::bad_alloc);
209
210	root	1.12	// strictly the same as g_slice_alloc, but never returns 0
211	root	1.20	template<typename T>
212			inline T salloc (int n = 1) throw (std::bad_alloc) { return (T )salloc_ (n * sizeof (T)); }
213
214	root	1.17	// also copies src into the new area, like "memdup"
215	root	1.18	// if src is 0, clears the memory
216			template<typename T>
217	root	1.20	inline T salloc (int n, T src) throw (std::bad_alloc) { return (T )salloc_ (n sizeof (T), (void *)src); }
218	root	1.18
219	root	1.21	// 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	root	1.12	// for symmetry
224	root	1.18	template<typename T>
225	root	1.20	inline void sfree (T *ptr, int n = 1) throw ()
226	root	1.12	{
227	root	1.36	#ifdef PREFER_MALLOC
228			free (ptr);
229			#else
230	root	1.20	g_slice_free1 (n * sizeof (T), (void *)ptr);
231	root	1.36	#endif
232	root	1.12	}
233	root	1.11
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	root	1.18	return salloc<Tp> (n);
266	root	1.11	}
267
268			void deallocate (pointer p, size_type n)
269			{
270	root	1.19	sfree<Tp> (p, n);
271	root	1.11	}
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	root	1.1	};
288
289	root	1.32	// 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	root	1.34	// generator
295	root	1.32	uint32_t state [4];
296
297	root	1.34	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	root	1.32	uint32_t next ();
307
308	root	1.34	// uniform distribution
309	root	1.42	uint32_t operator ()(uint32_t num)
310	root	1.32	{
311	root	1.42	return is_constant (num)
312			? (next () * (uint64_t)num) >> 32U
313			: get_range (num);
314	root	1.32	}
315
316			// return a number within (min .. max)
317			int operator () (int r_min, int r_max)
318			{
319	root	1.42	return is_constant (r_min) && is_constant (r_max) && r_min <= r_max
320			? r_min + operator ()(r_max - r_min + 1)
321	root	1.34	: get_range (r_min, r_max);
322	root	1.32	}
323
324			double operator ()()
325			{
326	root	1.34	return this->next () / (double)0xFFFFFFFFU;
327	root	1.32	}
328	root	1.34
329			protected:
330			uint32_t get_range (uint32_t r_max);
331			int get_range (int r_min, int r_max);
332	root	1.32	};
333
334			typedef tausworthe_random_generator rand_gen;
335
336			extern rand_gen rndm;
337
338	root	1.7	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	root	1.24	typedef refptr<maptile> maptile_ptr;
370	root	1.22	typedef refptr<object> object_ptr;
371			typedef refptr<archetype> arch_ptr;
372	root	1.24	typedef refptr<client> client_ptr;
373			typedef refptr<player> player_ptr;
374	root	1.22
375	root	1.4	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	root	1.49	// 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	root	1.26	template<class T>
414			struct unordered_vector : std::vector<T, slice_allocator<T> >
415	root	1.6	{
416	root	1.11	typedef typename unordered_vector::iterator iterator;
417	root	1.6
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	root	1.49	// 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	root	1.50	typedef int object_vector_index;
445
446			template<class T, object_vector_index T::*indexmember>
447	root	1.26	struct object_vector : std::vector<T , slice_allocator<T > >
448			{
449	root	1.48	typedef typename object_vector::iterator iterator;
450
451			bool contains (const T *obj) const
452			{
453	root	1.50	return obj->*indexmember;
454	root	1.48	}
455
456			iterator find (const T *obj)
457			{
458	root	1.50	return obj->*indexmember
459			? this->begin () + obj->*indexmember - 1
460	root	1.48	: this->end ();
461			}
462
463	root	1.26	void insert (T *obj)
464			{
465			push_back (obj);
466	root	1.50	obj->*indexmember = this->size ();
467	root	1.26	}
468
469			void insert (T &obj)
470			{
471			insert (&obj);
472			}
473
474			void erase (T *obj)
475			{
476	root	1.50	unsigned int pos = obj->*indexmember;
477			obj->*indexmember = 0;
478	root	1.26
479			if (pos < this->size ())
480			{
481			(this)[pos - 1] = (this)[this->size () - 1];
482	root	1.50	(this)[pos - 1]->indexmember = pos;
483	root	1.26	}
484
485			this->pop_back ();
486			}
487
488			void erase (T &obj)
489			{
490	root	1.50	erase (&obj);
491	root	1.26	}
492			};
493
494	root	1.10	// 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	root	1.9	template<int N>
499			inline void assign (char (&dst)[N], const char *src)
500			{
501	root	1.10	assign ((char *)&dst, src, N);
502	root	1.9	}
503
504	root	1.17	typedef double tstamp;
505
506			// return current time as timestampe
507			tstamp now ();
508
509	root	1.25	int similar_direction (int a, int b);
510
511	root	1.43	// like printf, but returns a std::string
512			const std::string format (const char *format, ...);
513
514	root	1.1	#endif
515