server/include/util.h

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 *
 * Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
 * Copyright (©) 2005,2006,2007,2008,2009,2010,2011,2012,2013,2014,2015,2016 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 *
 * Deliantra is free software: you can redistribute it and/or modify it under
 * the terms of the Affero 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 Affero GNU General Public License
 * and 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 <support@deliantra.net>
 */

#ifndef UTIL_H__
#define UTIL_H__

#define DEBUG_POISON 0x00 // poison memory before freeing it if != 0
#define DEBUG_SALLOC  0   // add a debug wrapper around all sallocs

#include <pthread.h>

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

#include <glib.h>

#include <flat_hash_map.hpp>

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

#include "ecb.h"

#define REAL_ALLOC(size) malloc (size)
#define REAL_ALLOC0(size) calloc (1, size)
#define REAL_FREE(ptr,size) free (ptr)

#if DEBUG_SALLOC
void *deliantra_alloc (size_t size);
void *deliantra_alloc0 (size_t size);
void deliantra_free (void *ptr, size_t size);
#else
#define deliantra_alloc(size)    REAL_ALLOC  (size)
#define deliantra_alloc0(size)   REAL_ALLOC0 (size)
#define deliantra_free(ptr,size) REAL_FREE   (ptr, size)
#endif

// very ugly macro that basically 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))

ecb_cold void cleanup (const char *cause, bool make_core = false);
ecb_cold 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 a < (T)b ? a : (T)b; }
template<typename T, typename U> static inline T max (T a, U b) { return a > (T)b ? a : (T)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 min_it (T &v, U m) { v = min (v, (T)m); }
template<typename T, typename U> static inline void max_it (T &v, U m) { v = max (v, (T)m); }
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); }

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, typename U, typename V> static inline T min (T a, U b, V c) { return min (a, min (b, c)); }
template<typename T, typename U, typename V> static inline T max (T a, U b, V c) { return max (a, max (b, c)); }

// sign returns -1 or +1
template<typename T>
static inline T sign (T v) { return v < 0 ? -1 : +1; }
// relies on 2c representation
template<>
inline sint8  sign (sint8  v) { return 1 - (sint8  (uint8  (v) >>  7) * 2); }
template<>
inline sint16 sign (sint16 v) { return 1 - (sint16 (uint16 (v) >> 15) * 2); }
template<>
inline sint32 sign (sint32 v) { return 1 - (sint32 (uint32 (v) >> 31) * 2); }

// sign0 returns -1, 0 or +1
template<typename T>
static inline T sign0 (T v) { return v ? sign (v) : 0; }

//clashes with C++0x
template<typename T, typename U>
static inline T copysign (T a, U b) { return a > 0 ? b : -b; }

// div* only work correctly for div > 0
// div, with correct rounding (< 0.5 downwards, >=0.5 upwards)
template<typename T> static inline T div    (T val, T div)
{
  return ecb_expect_false (val < 0) ? - ((-val + (div - 1) / 2) / div) : (val + div / 2) / div;
}

template<> inline float  div (float  val, float  div) { return val / div; }
template<> inline double div (double val, double div) { return val / div; }

// div, round-up
template<typename T> static inline T div_ru (T val, T div)
{
  return ecb_expect_false (val < 0) ? - ((-val                ) / div) : (val + div - 1) / div;
}
// div, round-down
template<typename T> static inline T div_rd (T val, T div)
{
  return ecb_expect_false (val < 0) ? - ((-val + (div - 1)    ) / div) : (val          ) / div;
}

// lerp* only work correctly for min_in < max_in
// Linear intERPolate, scales val from min_in..max_in to min_out..max_out
template<typename T>
static inline T
lerp (T val, T min_in, T max_in, T min_out, T max_out)
{
  return min_out + div   <T> ((val - min_in) * (max_out - min_out), max_in  - min_in);
}

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

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

// 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 crossfire's original algorithm
// on modern cpus
inline int
isqrt (int n)
{
  return (int)sqrtf ((float)n);
}

// this is kind of like the ^^ operator, if it would exist, without sequence point.
// more handy than it looks like, due to the implicit !! done on its arguments
inline bool
logical_xor (bool a, bool b)
{
  return a != b;
}

inline bool
logical_implies (bool a, bool b)
{
  return a <= b;
}

// 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
}

// can be substantially faster than floor, if your value range allows for it
template<typename T>
inline T
fastfloor (T x)
{
   return std::floor (x);
}

inline float
fastfloor (float x)
{
  return sint32(x) - (x < 0);
}

inline double
fastfloor (double x)
{
  return sint64(x) - (x < 0);
}

/*
 * 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;
}

#define for_all_bits_sparse_32(mask, idxvar)      \
  for (uint32_t idxvar, mask_ = mask;   \
       mask_ && ((idxvar = ecb_ctz32 (mask_)), mask_ &= ~(1 << idxvar), 1);)

extern ssize_t deliantra_alloc; // statistics

void *salloc_ (int n)            noexcept;
void *salloc_ (int n, void *src) noexcept;

// similar to glib's g_slice_alloc, but never returns 0
template<typename T>
inline T *salloc (int n = 1)     { 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) { return (T *)salloc_ (n * sizeof (T), (void *)src); }

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

// for symmetry
template<typename T>
inline void sfree (T *ptr, int n = 1) noexcept
{
  if (ecb_expect_true (ptr))
    {
      deliantra_alloc -= n * sizeof (T);
      if (DEBUG_POISON) memset (ptr, DEBUG_POISON, n * sizeof (T));
      deliantra_free (ptr, n * sizeof (T));
    }
}

// nulls the pointer
template<typename T>
inline void sfree0 (T *&ptr, int n = 1) noexcept
{
  sfree<T> (ptr, n);
  ptr = 0;
}

// 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 salloc0<char> (s);
  }

  void *operator new[] (size_t s)
  {
    return salloc0<char> (s);
  }

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

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

struct deliantra_allocated
{
  void *operator new (size_t s, void *p)
  {
    return p;
  }

  void *operator new (size_t s)
  {
    return salloc<char> (s);
  }

  void *operator new[] (size_t s)
  {
    return salloc<char> (s);
  }

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

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

// a STL-compatible allocator that uses salloc
// boy, this is much less verbose in newer C++ versions
template<typename Tp>
struct deliantra_allocator
{
  using value_type = Tp;

  deliantra_allocator () noexcept { }
  template<class U> deliantra_allocator (const deliantra_allocator<U> &) noexcept {}

  value_type *allocate (std::size_t n)
  {
    return salloc<Tp> (n);
  }

  void deallocate (value_type *p, std::size_t n)
  {
    sfree<Tp> (p, n);
  }
};

template<class T, class U>
bool operator == (const deliantra_allocator<T> &, const deliantra_allocator<U> &) noexcept
{
    return true;
}

template<class T, class U>
bool operator != (const deliantra_allocator<T> &x, const deliantra_allocator<U> &y) noexcept
{
    return !(x == y);
}

// basically a memory area, but refcounted
struct refcnt_buf
{
  char *data;

  refcnt_buf (size_t size = 0);
  refcnt_buf (void *data, size_t size);

  refcnt_buf (const refcnt_buf &src)
  {
    data = src.data;
    inc ();
  }

  ~refcnt_buf ();

  refcnt_buf &operator =(const refcnt_buf &src);

  operator char *()
  {
    return data;
  }

  size_t size () const
  {
    return _size ();
  }

protected:
  enum {
    overhead = sizeof (uint32_t) * 2
  };

  uint32_t &_size () const
  {
    return ((unsigned int *)data)[-2];
  }

  uint32_t &_refcnt () const
  {
    return ((unsigned int *)data)[-1];
  }

  void _alloc (uint32_t size)
  {
    data = ((char *)salloc<char> (size + overhead)) + overhead;
    _size   () = size;
    _refcnt () = 1;
  }

  void _dealloc ();

  void inc ()
  {
    ++_refcnt ();
  }

  void dec ()
  {
    if (!--_refcnt ())
      _dealloc ();
  }
};

INTERFACE_CLASS (attachable)
struct refcnt_base
{
  typedef int refcnt_t;
  mutable refcnt_t ACC (RW, refcnt);

  MTH void refcnt_inc () const { ++refcnt; }
  MTH void refcnt_dec () const { --refcnt; }

  refcnt_base () : refcnt (0) { }
};

// to avoid branches with more advanced compilers
extern refcnt_base::refcnt_t refcnt_dummy;

template<class T>
struct refptr
{
  // p if not null
  refcnt_base::refcnt_t *refcnt_ref () { return p ? &p->refcnt : &refcnt_dummy; }

  void refcnt_dec ()
  {
    if (!ecb_is_constant (p))
      --*refcnt_ref ();
    else if (p)
      --p->refcnt;
  }

  void refcnt_inc ()
  {
    if (!ecb_is_constant (p))
      ++*refcnt_ref ();
    else if (p)
      ++p->refcnt;
  }

  T *p;

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

  const refptr<T> &operator =(T *o)
  {
    // if decrementing ever destroys we need to reverse the order here
    refcnt_dec ();
    p = o;
    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;
typedef refptr<region>    region_ptr;

#define STRHSH_NULL 2166136261

static inline uint32_t
strhsh (const char *s)
{
  // use FNV-1a hash (http://isthe.com/chongo/tech/comp/fnv/)
  // it is about twice as fast as the one-at-a-time one,
  // with good distribution.
  // FNV-1a is faster on many cpus because the multiplication
  // runs concurrently with the looping logic.
  // we modify the hash a bit to improve its distribution
  uint32_t hash = STRHSH_NULL;

  while (*s)
    hash = (hash ^ *s++) * 16777619U;

  return hash ^ (hash >> 16);
}

static inline uint32_t
memhsh (const char *s, size_t len)
{
  uint32_t hash = STRHSH_NULL;

  while (len--)
    hash = (hash ^ *s++) * 16777619U;

  return hash;
}

struct str_hash
{
  std::size_t operator ()(const char *s) const
  {
    return strhsh (s);
  }

  std::size_t operator ()(const shstr &s) const
  {
    return strhsh (s);
  }

  typedef ska::power_of_two_hash_policy hash_policy;
};

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 append(=insert)/remove O(1) instead of O(n).
//
// NOTE: only some forms of erase are available
template<class T>
struct unordered_vector : std::vector<T, deliantra_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
// 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 *, deliantra_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 push_back (T *obj)
  {
    std::vector<T *, deliantra_allocator<T *> >::push_back (obj);
    obj->*indexmember = this->size ();
  }

  void insert (T *obj)
  {
    push_back (obj);
  }

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

  void erase (T *obj)
  {
    object_vector_index 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);
  }
};

/////////////////////////////////////////////////////////////////////////////

// something like a vector or stack, but without
// out of bounds checking
template<typename T>
struct fixed_stack
{
  T *data;
  int size;
  int max;

  fixed_stack ()
  : size (0), data (0)
  {
  }

  fixed_stack (int max)
  : size (0), max (max)
  {
    data = salloc<T> (max);
  }

  void reset (int new_max)
  {
    sfree (data, max);
    size = 0;
    max = new_max;
    data = salloc<T> (max);
  }

  void free ()
  {
    sfree (data, max);
    data = 0;
  }

  ~fixed_stack ()
  {
    sfree (data, max);
  }

  T &operator[](int idx)
  {
    return data [idx];
  }

  void push (T v)
  {
    data [size++] = v;
  }

  T &pop ()
  {
    return data [--size];
  }

  T remove (int idx)
  {
    T v = data [idx];

    data [idx] = data [--size];

    return v;
  }
};

/////////////////////////////////////////////////////////////////////////////

// basically does what strncpy should do, but appends "..." to strings exceeding length
// returns the number of bytes actually used (including \0)
int assign (char *dst, const char *src, int maxsize);

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

typedef double tstamp;

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

int similar_direction (int a, int b);

// like v?sprintf, but returns a "static" buffer
char *vformat (const char *format, va_list ap);
char *format (const char *format, ...) ecb_attribute ((format (printf, 1, 2)));

// safety-check player input which will become object->msg
bool msg_is_safe (const char *msg);

/////////////////////////////////////////////////////////////////////////////
// threads, very very thin wrappers around pthreads

struct thread
{
  pthread_t id;

  void start (void *(*start_routine)(void *), void *arg = 0);

  void cancel ()
  {
    pthread_cancel (id);
  }

  void *join ()
  {
    void *ret;

    if (pthread_join (id, &ret))
      cleanup ("pthread_join failed", 1);

    return ret;
  }
};

// note that mutexes are not classes
typedef pthread_mutex_t smutex;

#if __linux && defined (PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP)
 #define SMUTEX_INITIALISER PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP
#else
 #define SMUTEX_INITIALISER PTHREAD_MUTEX_INITIALIZER
#endif

#define SMUTEX(name) smutex name = SMUTEX_INITIALISER
#define SMUTEX_LOCK(name)   pthread_mutex_lock   (&(name))
#define SMUTEX_UNLOCK(name) pthread_mutex_unlock (&(name))

typedef pthread_cond_t scond;

#define SCOND(name) scond name = PTHREAD_COND_INITIALIZER
#define SCOND_SIGNAL(name)     pthread_cond_signal    (&(name))
#define SCOND_BROADCAST(name)  pthread_cond_broadcast (&(name))
#define SCOND_WAIT(name,mutex) pthread_cond_wait      (&(name), &(mutex))

#endif

Revision:	1.134
Committed:	Fri Sep 19 13:03:53 2025 UTC (12 months, 3 weeks ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.133:	+25 -26 lines
Log Message:	* empty log message *
#	Content
1	/*
2	* This file is part of Deliantra, the Roguelike Realtime MMORPG.
3	*
4	* Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
5	* Copyright (©) 2005,2006,2007,2008,2009,2010,2011,2012,2013,2014,2015,2016 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
6	*
7	* Deliantra is free software: you can redistribute it and/or modify it under
8	* the terms of the Affero GNU General Public License as published by the
9	* Free Software Foundation, either version 3 of the License, or (at your
10	* option) any later version.
11	*
12	* This program is distributed in the hope that it will be useful,
13	* but WITHOUT ANY WARRANTY; without even the implied warranty of
14	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15	* GNU General Public License for more details.
16	*
17	* You should have received a copy of the Affero GNU General Public License
18	* and the GNU General Public License along with this program. If not, see
19	* <http://www.gnu.org/licenses/>.
20	*
21	* The authors can be reached via e-mail to <support@deliantra.net>
22	*/
23
24	#ifndef UTIL_H__
25	#define UTIL_H__
26
27	#define DEBUG_POISON 0x00 // poison memory before freeing it if != 0
28	#define DEBUG_SALLOC 0 // add a debug wrapper around all sallocs
29
30	#include <pthread.h>
31
32	#include <cstddef>
33	#include <cmath>
34	#include <new>
35	#include <vector>
36
37	#include <glib.h>
38
39	#include <flat_hash_map.hpp>
40
41	#include <shstr.h>
42	#include <traits.h>
43
44	#include "ecb.h"
45
46	#define REAL_ALLOC(size) malloc (size)
47	#define REAL_ALLOC0(size) calloc (1, size)
48	#define REAL_FREE(ptr,size) free (ptr)
49
50	#if DEBUG_SALLOC
51	void *deliantra_alloc (size_t size);
52	void *deliantra_alloc0 (size_t size);
53	void deliantra_free (void *ptr, size_t size);
54	#else
55	#define deliantra_alloc(size) REAL_ALLOC (size)
56	#define deliantra_alloc0(size) REAL_ALLOC0 (size)
57	#define deliantra_free(ptr,size) REAL_FREE (ptr, size)
58	#endif
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	ecb_cold void cleanup (const char *cause, bool make_core = false);
76	ecb_cold 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 a < (T)b ? a : (T)b; }
81	template<typename T, typename U> static inline T max (T a, U b) { return a > (T)b ? a : (T)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	template<>
100	inline sint16 sign (sint16 v) { return 1 - (sint16 (uint16 (v) >> 15) * 2); }
101	template<>
102	inline sint32 sign (sint32 v) { return 1 - (sint32 (uint32 (v) >> 31) * 2); }
103
104	// sign0 returns -1, 0 or +1
105	template<typename T>
106	static inline T sign0 (T v) { return v ? sign (v) : 0; }
107
108	//clashes with C++0x
109	template<typename T, typename U>
110	static inline T copysign (T a, U b) { return a > 0 ? b : -b; }
111
112	// div* only work correctly for div > 0
113	// div, with correct rounding (< 0.5 downwards, >=0.5 upwards)
114	template<typename T> static inline T div (T val, T div)
115	{
116	return ecb_expect_false (val < 0) ? - ((-val + (div - 1) / 2) / div) : (val + div / 2) / div;
117	}
118
119	template<> inline float div (float val, float div) { return val / div; }
120	template<> inline double div (double val, double div) { return val / div; }
121
122	// div, round-up
123	template<typename T> static inline T div_ru (T val, T div)
124	{
125	return ecb_expect_false (val < 0) ? - ((-val ) / div) : (val + div - 1) / div;
126	}
127	// div, round-down
128	template<typename T> static inline T div_rd (T val, T div)
129	{
130	return ecb_expect_false (val < 0) ? - ((-val + (div - 1) ) / div) : (val ) / div;
131	}
132
133	// lerp* only work correctly for min_in < max_in
134	// Linear intERPolate, scales val from min_in..max_in to min_out..max_out
135	template<typename T>
136	static inline T
137	lerp (T val, T min_in, T max_in, T min_out, T max_out)
138	{
139	return min_out + div <T> ((val - min_in) * (max_out - min_out), max_in - min_in);
140	}
141
142	// lerp, round-down
143	template<typename T>
144	static inline T
145	lerp_rd (T val, T min_in, T max_in, T min_out, T max_out)
146	{
147	return min_out + div_rd<T> ((val - min_in) * (max_out - min_out), max_in - min_in);
148	}
149
150	// lerp, round-up
151	template<typename T>
152	static inline T
153	lerp_ru (T val, T min_in, T max_in, T min_out, T max_out)
154	{
155	return min_out + div_ru<T> ((val - min_in) * (max_out - min_out), max_in - min_in);
156	}
157
158	// lots of stuff taken from FXT
159
160	/* Rotate right. This is used in various places for checksumming */
161	//TODO: that sucks, use a better checksum algo
162	static inline uint32_t
163	rotate_right (uint32_t c, uint32_t count = 1)
164	{
165	return (c << (32 - count)) \| (c >> count);
166	}
167
168	static inline uint32_t
169	rotate_left (uint32_t c, uint32_t count = 1)
170	{
171	return (c >> (32 - count)) \| (c << count);
172	}
173
174	// Return abs(a-b)
175	// Both a and b must not have the most significant bit set
176	static inline uint32_t
177	upos_abs_diff (uint32_t a, uint32_t b)
178	{
179	long d1 = b - a;
180	long d2 = (d1 & (d1 >> 31)) << 1;
181
182	return d1 - d2; // == (b - d) - (a + d);
183	}
184
185	// Both a and b must not have the most significant bit set
186	static inline uint32_t
187	upos_min (uint32_t a, uint32_t b)
188	{
189	int32_t d = b - a;
190	d &= d >> 31;
191	return a + d;
192	}
193
194	// Both a and b must not have the most significant bit set
195	static inline uint32_t
196	upos_max (uint32_t a, uint32_t b)
197	{
198	int32_t d = b - a;
199	d &= d >> 31;
200	return b - d;
201	}
202
203	// this is much faster than crossfire's original algorithm
204	// on modern cpus
205	inline int
206	isqrt (int n)
207	{
208	return (int)sqrtf ((float)n);
209	}
210
211	// this is kind of like the ^^ operator, if it would exist, without sequence point.
212	// more handy than it looks like, due to the implicit !! done on its arguments
213	inline bool
214	logical_xor (bool a, bool b)
215	{
216	return a != b;
217	}
218
219	inline bool
220	logical_implies (bool a, bool b)
221	{
222	return a <= b;
223	}
224
225	// this is only twice as fast as naive sqrtf (dxdy+dydy)
226	#if 0
227	// and has a max. error of 6 in the range -100..+100.
228	#else
229	// and has a max. error of 9 in the range -100..+100.
230	#endif
231	inline int
232	idistance (int dx, int dy)
233	{
234	unsigned int dx_ = abs (dx);
235	unsigned int dy_ = abs (dy);
236
237	#if 0
238	return dx_ > dy_
239	? (dx_ * 61685 + dy_ * 26870) >> 16
240	: (dy_ * 61685 + dx_ * 26870) >> 16;
241	#else
242	return dx_ + dy_ - min (dx_, dy_) * 5 / 8;
243	#endif
244	}
245
246	// can be substantially faster than floor, if your value range allows for it
247	template<typename T>
248	inline T
249	fastfloor (T x)
250	{
251	return std::floor (x);
252	}
253
254	inline float
255	fastfloor (float x)
256	{
257	return sint32(x) - (x < 0);
258	}
259
260	inline double
261	fastfloor (double x)
262	{
263	return sint64(x) - (x < 0);
264	}
265
266	/*
267	* absdir(int): Returns a number between 1 and 8, which represent
268	* the "absolute" direction of a number (it actually takes care of
269	* "overflow" in previous calculations of a direction).
270	*/
271	inline int
272	absdir (int d)
273	{
274	return ((d - 1) & 7) + 1;
275	}
276
277	#define for_all_bits_sparse_32(mask, idxvar) \
278	for (uint32_t idxvar, mask_ = mask; \
279	mask_ && ((idxvar = ecb_ctz32 (mask_)), mask_ &= ~(1 << idxvar), 1);)
280
281	extern ssize_t deliantra_alloc; // statistics
282
283	void *salloc_ (int n) noexcept;
284	void salloc_ (int n, void src) noexcept;
285
286	// similar to glib's g_slice_alloc, but never returns 0
287	template<typename T>
288	inline T salloc (int n = 1) { return (T )salloc_ (n * sizeof (T)); }
289
290	// also copies src into the new area, like "memdup"
291	// if src is 0, clears the memory
292	template<typename T>
293	inline T salloc (int n, T src) { return (T )salloc_ (n sizeof (T), (void *)src); }
294
295	// clears the memory
296	template<typename T>
297	inline T salloc0(int n = 1) { return (T )salloc_ (n * sizeof (T), 0); }
298
299	// for symmetry
300	template<typename T>
301	inline void sfree (T *ptr, int n = 1) noexcept
302	{
303	if (ecb_expect_true (ptr))
304	{
305	deliantra_alloc -= n * sizeof (T);
306	if (DEBUG_POISON) memset (ptr, DEBUG_POISON, n * sizeof (T));
307	deliantra_free (ptr, n * sizeof (T));
308	}
309	}
310
311	// nulls the pointer
312	template<typename T>
313	inline void sfree0 (T *&ptr, int n = 1) noexcept
314	{
315	sfree<T> (ptr, n);
316	ptr = 0;
317	}
318
319	// makes dynamically allocated objects zero-initialised
320	struct zero_initialised
321	{
322	void operator new (size_t s, void p)
323	{
324	memset (p, 0, s);
325	return p;
326	}
327
328	void *operator new (size_t s)
329	{
330	return salloc0<char> (s);
331	}
332
333	void *operator new[] (size_t s)
334	{
335	return salloc0<char> (s);
336	}
337
338	void operator delete (void *p, size_t s)
339	{
340	sfree ((char *)p, s);
341	}
342
343	void operator delete[] (void *p, size_t s)
344	{
345	sfree ((char *)p, s);
346	}
347	};
348
349	struct deliantra_allocated
350	{
351	void operator new (size_t s, void p)
352	{
353	return p;
354	}
355
356	void *operator new (size_t s)
357	{
358	return salloc<char> (s);
359	}
360
361	void *operator new[] (size_t s)
362	{
363	return salloc<char> (s);
364	}
365
366	void operator delete (void *p, size_t s)
367	{
368	sfree ((char *)p, s);
369	}
370
371	void operator delete[] (void *p, size_t s)
372	{
373	sfree ((char *)p, s);
374	}
375	};
376
377	// a STL-compatible allocator that uses salloc
378	// boy, this is much less verbose in newer C++ versions
379	template<typename Tp>
380	struct deliantra_allocator
381	{
382	using value_type = Tp;
383
384	deliantra_allocator () noexcept { }
385	template<class U> deliantra_allocator (const deliantra_allocator<U> &) noexcept {}
386
387	value_type *allocate (std::size_t n)
388	{
389	return salloc<Tp> (n);
390	}
391
392	void deallocate (value_type *p, std::size_t n)
393	{
394	sfree<Tp> (p, n);
395	}
396	};
397
398	template<class T, class U>
399	bool operator == (const deliantra_allocator<T> &, const deliantra_allocator<U> &) noexcept
400	{
401	return true;
402	}
403
404	template<class T, class U>
405	bool operator != (const deliantra_allocator<T> &x, const deliantra_allocator<U> &y) noexcept
406	{
407	return !(x == y);
408	}
409
410	// basically a memory area, but refcounted
411	struct refcnt_buf
412	{
413	char *data;
414
415	refcnt_buf (size_t size = 0);
416	refcnt_buf (void *data, size_t size);
417
418	refcnt_buf (const refcnt_buf &src)
419	{
420	data = src.data;
421	inc ();
422	}
423
424	~refcnt_buf ();
425
426	refcnt_buf &operator =(const refcnt_buf &src);
427
428	operator char *()
429	{
430	return data;
431	}
432
433	size_t size () const
434	{
435	return _size ();
436	}
437
438	protected:
439	enum {
440	overhead = sizeof (uint32_t) * 2
441	};
442
443	uint32_t &_size () const
444	{
445	return ((unsigned int *)data)[-2];
446	}
447
448	uint32_t &_refcnt () const
449	{
450	return ((unsigned int *)data)[-1];
451	}
452
453	void _alloc (uint32_t size)
454	{
455	data = ((char *)salloc<char> (size + overhead)) + overhead;
456	_size () = size;
457	_refcnt () = 1;
458	}
459
460	void _dealloc ();
461
462	void inc ()
463	{
464	++_refcnt ();
465	}
466
467	void dec ()
468	{
469	if (!--_refcnt ())
470	_dealloc ();
471	}
472	};
473
474	INTERFACE_CLASS (attachable)
475	struct refcnt_base
476	{
477	typedef int refcnt_t;
478	mutable refcnt_t ACC (RW, refcnt);
479
480	MTH void refcnt_inc () const { ++refcnt; }
481	MTH void refcnt_dec () const { --refcnt; }
482
483	refcnt_base () : refcnt (0) { }
484	};
485
486	// to avoid branches with more advanced compilers
487	extern refcnt_base::refcnt_t refcnt_dummy;
488
489	template<class T>
490	struct refptr
491	{
492	// p if not null
493	refcnt_base::refcnt_t *refcnt_ref () { return p ? &p->refcnt : &refcnt_dummy; }
494
495	void refcnt_dec ()
496	{
497	if (!ecb_is_constant (p))
498	--*refcnt_ref ();
499	else if (p)
500	--p->refcnt;
501	}
502
503	void refcnt_inc ()
504	{
505	if (!ecb_is_constant (p))
506	++*refcnt_ref ();
507	else if (p)
508	++p->refcnt;
509	}
510
511	T *p;
512
513	refptr () : p(0) { }
514	refptr (const refptr<T> &p) : p(p.p) { refcnt_inc (); }
515	refptr (T *p) : p(p) { refcnt_inc (); }
516	~refptr () { refcnt_dec (); }
517
518	const refptr<T> &operator =(T *o)
519	{
520	// if decrementing ever destroys we need to reverse the order here
521	refcnt_dec ();
522	p = o;
523	refcnt_inc ();
524	return *this;
525	}
526
527	const refptr<T> &operator =(const refptr<T> &o)
528	{
529	*this = o.p;
530	return *this;
531	}
532
533	T &operator * () const { return *p; }
534	T *operator ->() const { return p; }
535
536	operator T *() const { return p; }
537	};
538
539	typedef refptr<maptile> maptile_ptr;
540	typedef refptr<object> object_ptr;
541	typedef refptr<archetype> arch_ptr;
542	typedef refptr<client> client_ptr;
543	typedef refptr<player> player_ptr;
544	typedef refptr<region> region_ptr;
545
546	#define STRHSH_NULL 2166136261
547
548	static inline uint32_t
549	strhsh (const char *s)
550	{
551	// use FNV-1a hash (http://isthe.com/chongo/tech/comp/fnv/)
552	// it is about twice as fast as the one-at-a-time one,
553	// with good distribution.
554	// FNV-1a is faster on many cpus because the multiplication
555	// runs concurrently with the looping logic.
556	// we modify the hash a bit to improve its distribution
557	uint32_t hash = STRHSH_NULL;
558
559	while (*s)
560	hash = (hash ^ s++) 16777619U;
561
562	return hash ^ (hash >> 16);
563	}
564
565	static inline uint32_t
566	memhsh (const char *s, size_t len)
567	{
568	uint32_t hash = STRHSH_NULL;
569
570	while (len--)
571	hash = (hash ^ s++) 16777619U;
572
573	return hash;
574	}
575
576	struct str_hash
577	{
578	std::size_t operator ()(const char *s) const
579	{
580	return strhsh (s);
581	}
582
583	std::size_t operator ()(const shstr &s) const
584	{
585	return strhsh (s);
586	}
587
588	typedef ska::power_of_two_hash_policy hash_policy;
589	};
590
591	struct str_equal
592	{
593	bool operator ()(const char a, const char b) const
594	{
595	return !strcmp (a, b);
596	}
597	};
598
599	// Mostly the same as std::vector, but insert/erase can reorder
600	// the elements, making append(=insert)/remove O(1) instead of O(n).
601	//
602	// NOTE: only some forms of erase are available
603	template<class T>
604	struct unordered_vector : std::vector<T, deliantra_allocator<T> >
605	{
606	typedef typename unordered_vector::iterator iterator;
607
608	void erase (unsigned int pos)
609	{
610	if (pos < this->size () - 1)
611	(this)[pos] = (this)[this->size () - 1];
612
613	this->pop_back ();
614	}
615
616	void erase (iterator i)
617	{
618	erase ((unsigned int )(i - this->begin ()));
619	}
620	};
621
622	// This container blends advantages of linked lists
623	// (efficiency) with vectors (random access) by
624	// using an unordered vector and storing the vector
625	// index inside the object.
626	//
627	// + memory-efficient on most 64 bit archs
628	// + O(1) insert/remove
629	// + free unique (but varying) id for inserted objects
630	// + cache-friendly iteration
631	// - only works for pointers to structs
632	//
633	// NOTE: only some forms of erase/insert are available
634	typedef int object_vector_index;
635
636	template<class T, object_vector_index T::*indexmember>
637	struct object_vector : std::vector<T , deliantra_allocator<T > >
638	{
639	typedef typename object_vector::iterator iterator;
640
641	bool contains (const T *obj) const
642	{
643	return obj->*indexmember;
644	}
645
646	iterator find (const T *obj)
647	{
648	return obj->*indexmember
649	? this->begin () + obj->*indexmember - 1
650	: this->end ();
651	}
652
653	void push_back (T *obj)
654	{
655	std::vector<T , deliantra_allocator<T > >::push_back (obj);
656	obj->*indexmember = this->size ();
657	}
658
659	void insert (T *obj)
660	{
661	push_back (obj);
662	}
663
664	void insert (T &obj)
665	{
666	insert (&obj);
667	}
668
669	void erase (T *obj)
670	{
671	object_vector_index pos = obj->*indexmember;
672	obj->*indexmember = 0;
673
674	if (pos < this->size ())
675	{
676	(this)[pos - 1] = (this)[this->size () - 1];
677	(this)[pos - 1]->indexmember = pos;
678	}
679
680	this->pop_back ();
681	}
682
683	void erase (T &obj)
684	{
685	erase (&obj);
686	}
687	};
688
689	/////////////////////////////////////////////////////////////////////////////
690
691	// something like a vector or stack, but without
692	// out of bounds checking
693	template<typename T>
694	struct fixed_stack
695	{
696	T *data;
697	int size;
698	int max;
699
700	fixed_stack ()
701	: size (0), data (0)
702	{
703	}
704
705	fixed_stack (int max)
706	: size (0), max (max)
707	{
708	data = salloc<T> (max);
709	}
710
711	void reset (int new_max)
712	{
713	sfree (data, max);
714	size = 0;
715	max = new_max;
716	data = salloc<T> (max);
717	}
718
719	void free ()
720	{
721	sfree (data, max);
722	data = 0;
723	}
724
725	~fixed_stack ()
726	{
727	sfree (data, max);
728	}
729
730	T &operator[](int idx)
731	{
732	return data [idx];
733	}
734
735	void push (T v)
736	{
737	data [size++] = v;
738	}
739
740	T &pop ()
741	{
742	return data [--size];
743	}
744
745	T remove (int idx)
746	{
747	T v = data [idx];
748
749	data [idx] = data [--size];
750
751	return v;
752	}
753	};
754
755	/////////////////////////////////////////////////////////////////////////////
756
757	// basically does what strncpy should do, but appends "..." to strings exceeding length
758	// returns the number of bytes actually used (including \0)
759	int assign (char dst, const char src, int maxsize);
760
761	// type-safe version of assign
762	template<int N>
763	inline int assign (char (&dst)[N], const char *src)
764	{
765	return assign ((char *)&dst, src, N);
766	}
767
768	typedef double tstamp;
769
770	// return current time as timestamp
771	tstamp now ();
772
773	int similar_direction (int a, int b);
774
775	// like v?sprintf, but returns a "static" buffer
776	char vformat (const char format, va_list ap);
777	char format (const char format, ...) ecb_attribute ((format (printf, 1, 2)));
778
779	// safety-check player input which will become object->msg
780	bool msg_is_safe (const char *msg);
781
782	/////////////////////////////////////////////////////////////////////////////
783	// threads, very very thin wrappers around pthreads
784
785	struct thread
786	{
787	pthread_t id;
788
789	void start (void (start_routine)(void ), void arg = 0);
790
791	void cancel ()
792	{
793	pthread_cancel (id);
794	}
795
796	void *join ()
797	{
798	void *ret;
799
800	if (pthread_join (id, &ret))
801	cleanup ("pthread_join failed", 1);
802
803	return ret;
804	}
805	};
806
807	// note that mutexes are not classes
808	typedef pthread_mutex_t smutex;
809
810	#if __linux && defined (PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP)
811	#define SMUTEX_INITIALISER PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP
812	#else
813	#define SMUTEX_INITIALISER PTHREAD_MUTEX_INITIALIZER
814	#endif
815
816	#define SMUTEX(name) smutex name = SMUTEX_INITIALISER
817	#define SMUTEX_LOCK(name) pthread_mutex_lock (&(name))
818	#define SMUTEX_UNLOCK(name) pthread_mutex_unlock (&(name))
819
820	typedef pthread_cond_t scond;
821
822	#define SCOND(name) scond name = PTHREAD_COND_INITIALIZER
823	#define SCOND_SIGNAL(name) pthread_cond_signal (&(name))
824	#define SCOND_BROADCAST(name) pthread_cond_broadcast (&(name))
825	#define SCOND_WAIT(name,mutex) pthread_cond_wait (&(name), &(mutex))
826
827	#endif
828