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
#define PREFER_MALLOC 0   // use malloc and not the slice allocator

#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"

#if DEBUG_SALLOC
# define g_slice_alloc0(s) debug_slice_alloc0(s)
# define g_slice_alloc(s) debug_slice_alloc(s)
# define g_slice_free1(s,p) debug_slice_free1(s,p)
void *g_slice_alloc (unsigned long size);
void *g_slice_alloc0 (unsigned long size);
void g_slice_free1 (unsigned long size, void *ptr);
#elif PREFER_MALLOC
# define g_slice_alloc0(s) calloc (1, (s))
# define g_slice_alloc(s) malloc ((s))
# define g_slice_free1(s,p) free ((p))
#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 slice_alloc; // statistics

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

// strictly the same as 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))
    {
      slice_alloc -= n * sizeof (T);
      if (DEBUG_POISON) memset (ptr, DEBUG_POISON, n * sizeof (T));
      g_slice_free1 (n * sizeof (T), (void *)ptr);
    }
}

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

// makes dynamically allocated objects zero-initialised
struct slice_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 g_slice
// boy, this is much less verbose in newer C++ versions
template<typename Tp>
struct slice_allocator
{
  using value_type = Tp;

  slice_allocator () noexcept { }
  template<class U> slice_allocator (const slice_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 slice_allocator<T> &, const slice_allocator<U> &) noexcept
{
    return true;
}

template<class T, class U>
bool operator != (const slice_allocator<T> &x, const slice_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, 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
// 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 push_back (T *obj)
  {
    std::vector<T *, slice_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.133
Committed:	Sat Oct 8 21:54:05 2022 UTC (19 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.132:	+2 -2 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	#define PREFER_MALLOC 0 // use malloc and not the slice allocator
30
31	#include <pthread.h>
32
33	#include <cstddef>
34	#include <cmath>
35	#include <new>
36	#include <vector>
37
38	#include <glib.h>
39
40	#include <flat_hash_map.hpp>
41
42	#include <shstr.h>
43	#include <traits.h>
44
45	#include "ecb.h"
46
47	#if DEBUG_SALLOC
48	# define g_slice_alloc0(s) debug_slice_alloc0(s)
49	# define g_slice_alloc(s) debug_slice_alloc(s)
50	# define g_slice_free1(s,p) debug_slice_free1(s,p)
51	void *g_slice_alloc (unsigned long size);
52	void *g_slice_alloc0 (unsigned long size);
53	void g_slice_free1 (unsigned long size, void *ptr);
54	#elif PREFER_MALLOC
55	# define g_slice_alloc0(s) calloc (1, (s))
56	# define g_slice_alloc(s) malloc ((s))
57	# define g_slice_free1(s,p) free ((p))
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 slice_alloc; // statistics
282
283	void *salloc_ (int n) noexcept;
284	void salloc_ (int n, void src) noexcept;
285
286	// strictly the same as 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	slice_alloc -= n * sizeof (T);
306	if (DEBUG_POISON) memset (ptr, DEBUG_POISON, n * sizeof (T));
307	g_slice_free1 (n * sizeof (T), (void *)ptr);
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	// makes dynamically allocated objects zero-initialised
350	struct slice_allocated
351	{
352	void operator new (size_t s, void p)
353	{
354	return p;
355	}
356
357	void *operator new (size_t s)
358	{
359	return salloc<char> (s);
360	}
361
362	void *operator new[] (size_t s)
363	{
364	return salloc<char> (s);
365	}
366
367	void operator delete (void *p, size_t s)
368	{
369	sfree ((char *)p, s);
370	}
371
372	void operator delete[] (void *p, size_t s)
373	{
374	sfree ((char *)p, s);
375	}
376	};
377
378	// a STL-compatible allocator that uses g_slice
379	// boy, this is much less verbose in newer C++ versions
380	template<typename Tp>
381	struct slice_allocator
382	{
383	using value_type = Tp;
384
385	slice_allocator () noexcept { }
386	template<class U> slice_allocator (const slice_allocator<U> &) noexcept {}
387
388	value_type *allocate (std::size_t n)
389	{
390	return salloc<Tp> (n);
391	}
392
393	void deallocate (value_type *p, std::size_t n)
394	{
395	sfree<Tp> (p, n);
396	}
397	};
398
399	template<class T, class U>
400	bool operator == (const slice_allocator<T> &, const slice_allocator<U> &) noexcept
401	{
402	return true;
403	}
404
405	template<class T, class U>
406	bool operator != (const slice_allocator<T> &x, const slice_allocator<U> &y) noexcept
407	{
408	return !(x == y);
409	}
410
411	// basically a memory area, but refcounted
412	struct refcnt_buf
413	{
414	char *data;
415
416	refcnt_buf (size_t size = 0);
417	refcnt_buf (void *data, size_t size);
418
419	refcnt_buf (const refcnt_buf &src)
420	{
421	data = src.data;
422	inc ();
423	}
424
425	~refcnt_buf ();
426
427	refcnt_buf &operator =(const refcnt_buf &src);
428
429	operator char *()
430	{
431	return data;
432	}
433
434	size_t size () const
435	{
436	return _size ();
437	}
438
439	protected:
440	enum {
441	overhead = sizeof (uint32_t) * 2
442	};
443
444	uint32_t &_size () const
445	{
446	return ((unsigned int *)data)[-2];
447	}
448
449	uint32_t &_refcnt () const
450	{
451	return ((unsigned int *)data)[-1];
452	}
453
454	void _alloc (uint32_t size)
455	{
456	data = ((char *)salloc<char> (size + overhead)) + overhead;
457	_size () = size;
458	_refcnt () = 1;
459	}
460
461	void _dealloc ();
462
463	void inc ()
464	{
465	++_refcnt ();
466	}
467
468	void dec ()
469	{
470	if (!--_refcnt ())
471	_dealloc ();
472	}
473	};
474
475	INTERFACE_CLASS (attachable)
476	struct refcnt_base
477	{
478	typedef int refcnt_t;
479	mutable refcnt_t ACC (RW, refcnt);
480
481	MTH void refcnt_inc () const { ++refcnt; }
482	MTH void refcnt_dec () const { --refcnt; }
483
484	refcnt_base () : refcnt (0) { }
485	};
486
487	// to avoid branches with more advanced compilers
488	extern refcnt_base::refcnt_t refcnt_dummy;
489
490	template<class T>
491	struct refptr
492	{
493	// p if not null
494	refcnt_base::refcnt_t *refcnt_ref () { return p ? &p->refcnt : &refcnt_dummy; }
495
496	void refcnt_dec ()
497	{
498	if (!ecb_is_constant (p))
499	--*refcnt_ref ();
500	else if (p)
501	--p->refcnt;
502	}
503
504	void refcnt_inc ()
505	{
506	if (!ecb_is_constant (p))
507	++*refcnt_ref ();
508	else if (p)
509	++p->refcnt;
510	}
511
512	T *p;
513
514	refptr () : p(0) { }
515	refptr (const refptr<T> &p) : p(p.p) { refcnt_inc (); }
516	refptr (T *p) : p(p) { refcnt_inc (); }
517	~refptr () { refcnt_dec (); }
518
519	const refptr<T> &operator =(T *o)
520	{
521	// if decrementing ever destroys we need to reverse the order here
522	refcnt_dec ();
523	p = o;
524	refcnt_inc ();
525	return *this;
526	}
527
528	const refptr<T> &operator =(const refptr<T> &o)
529	{
530	*this = o.p;
531	return *this;
532	}
533
534	T &operator * () const { return *p; }
535	T *operator ->() const { return p; }
536
537	operator T *() const { return p; }
538	};
539
540	typedef refptr<maptile> maptile_ptr;
541	typedef refptr<object> object_ptr;
542	typedef refptr<archetype> arch_ptr;
543	typedef refptr<client> client_ptr;
544	typedef refptr<player> player_ptr;
545	typedef refptr<region> region_ptr;
546
547	#define STRHSH_NULL 2166136261
548
549	static inline uint32_t
550	strhsh (const char *s)
551	{
552	// use FNV-1a hash (http://isthe.com/chongo/tech/comp/fnv/)
553	// it is about twice as fast as the one-at-a-time one,
554	// with good distribution.
555	// FNV-1a is faster on many cpus because the multiplication
556	// runs concurrently with the looping logic.
557	// we modify the hash a bit to improve its distribution
558	uint32_t hash = STRHSH_NULL;
559
560	while (*s)
561	hash = (hash ^ s++) 16777619U;
562
563	return hash ^ (hash >> 16);
564	}
565
566	static inline uint32_t
567	memhsh (const char *s, size_t len)
568	{
569	uint32_t hash = STRHSH_NULL;
570
571	while (len--)
572	hash = (hash ^ s++) 16777619U;
573
574	return hash;
575	}
576
577	struct str_hash
578	{
579	std::size_t operator ()(const char *s) const
580	{
581	return strhsh (s);
582	}
583
584	std::size_t operator ()(const shstr &s) const
585	{
586	return strhsh (s);
587	}
588
589	typedef ska::power_of_two_hash_policy hash_policy;
590	};
591
592	struct str_equal
593	{
594	bool operator ()(const char a, const char b) const
595	{
596	return !strcmp (a, b);
597	}
598	};
599
600	// Mostly the same as std::vector, but insert/erase can reorder
601	// the elements, making append(=insert)/remove O(1) instead of O(n).
602	//
603	// NOTE: only some forms of erase are available
604	template<class T>
605	struct unordered_vector : std::vector<T, slice_allocator<T> >
606	{
607	typedef typename unordered_vector::iterator iterator;
608
609	void erase (unsigned int pos)
610	{
611	if (pos < this->size () - 1)
612	(this)[pos] = (this)[this->size () - 1];
613
614	this->pop_back ();
615	}
616
617	void erase (iterator i)
618	{
619	erase ((unsigned int )(i - this->begin ()));
620	}
621	};
622
623	// This container blends advantages of linked lists
624	// (efficiency) with vectors (random access) by
625	// using an unordered vector and storing the vector
626	// index inside the object.
627	//
628	// + memory-efficient on most 64 bit archs
629	// + O(1) insert/remove
630	// + free unique (but varying) id for inserted objects
631	// + cache-friendly iteration
632	// - only works for pointers to structs
633	//
634	// NOTE: only some forms of erase/insert are available
635	typedef int object_vector_index;
636
637	template<class T, object_vector_index T::*indexmember>
638	struct object_vector : std::vector<T , slice_allocator<T > >
639	{
640	typedef typename object_vector::iterator iterator;
641
642	bool contains (const T *obj) const
643	{
644	return obj->*indexmember;
645	}
646
647	iterator find (const T *obj)
648	{
649	return obj->*indexmember
650	? this->begin () + obj->*indexmember - 1
651	: this->end ();
652	}
653
654	void push_back (T *obj)
655	{
656	std::vector<T , slice_allocator<T > >::push_back (obj);
657	obj->*indexmember = this->size ();
658	}
659
660	void insert (T *obj)
661	{
662	push_back (obj);
663	}
664
665	void insert (T &obj)
666	{
667	insert (&obj);
668	}
669
670	void erase (T *obj)
671	{
672	object_vector_index pos = obj->*indexmember;
673	obj->*indexmember = 0;
674
675	if (pos < this->size ())
676	{
677	(this)[pos - 1] = (this)[this->size () - 1];
678	(this)[pos - 1]->indexmember = pos;
679	}
680
681	this->pop_back ();
682	}
683
684	void erase (T &obj)
685	{
686	erase (&obj);
687	}
688	};
689
690	/////////////////////////////////////////////////////////////////////////////
691
692	// something like a vector or stack, but without
693	// out of bounds checking
694	template<typename T>
695	struct fixed_stack
696	{
697	T *data;
698	int size;
699	int max;
700
701	fixed_stack ()
702	: size (0), data (0)
703	{
704	}
705
706	fixed_stack (int max)
707	: size (0), max (max)
708	{
709	data = salloc<T> (max);
710	}
711
712	void reset (int new_max)
713	{
714	sfree (data, max);
715	size = 0;
716	max = new_max;
717	data = salloc<T> (max);
718	}
719
720	void free ()
721	{
722	sfree (data, max);
723	data = 0;
724	}
725
726	~fixed_stack ()
727	{
728	sfree (data, max);
729	}
730
731	T &operator[](int idx)
732	{
733	return data [idx];
734	}
735
736	void push (T v)
737	{
738	data [size++] = v;
739	}
740
741	T &pop ()
742	{
743	return data [--size];
744	}
745
746	T remove (int idx)
747	{
748	T v = data [idx];
749
750	data [idx] = data [--size];
751
752	return v;
753	}
754	};
755
756	/////////////////////////////////////////////////////////////////////////////
757
758	// basically does what strncpy should do, but appends "..." to strings exceeding length
759	// returns the number of bytes actually used (including \0)
760	int assign (char dst, const char src, int maxsize);
761
762	// type-safe version of assign
763	template<int N>
764	inline int assign (char (&dst)[N], const char *src)
765	{
766	return assign ((char *)&dst, src, N);
767	}
768
769	typedef double tstamp;
770
771	// return current time as timestamp
772	tstamp now ();
773
774	int similar_direction (int a, int b);
775
776	// like v?sprintf, but returns a "static" buffer
777	char vformat (const char format, va_list ap);
778	char format (const char format, ...) ecb_attribute ((format (printf, 1, 2)));
779
780	// safety-check player input which will become object->msg
781	bool msg_is_safe (const char *msg);
782
783	/////////////////////////////////////////////////////////////////////////////
784	// threads, very very thin wrappers around pthreads
785
786	struct thread
787	{
788	pthread_t id;
789
790	void start (void (start_routine)(void ), void arg = 0);
791
792	void cancel ()
793	{
794	pthread_cancel (id);
795	}
796
797	void *join ()
798	{
799	void *ret;
800
801	if (pthread_join (id, &ret))
802	cleanup ("pthread_join failed", 1);
803
804	return ret;
805	}
806	};
807
808	// note that mutexes are not classes
809	typedef pthread_mutex_t smutex;
810
811	#if __linux && defined (PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP)
812	#define SMUTEX_INITIALISER PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP
813	#else
814	#define SMUTEX_INITIALISER PTHREAD_MUTEX_INITIALIZER
815	#endif
816
817	#define SMUTEX(name) smutex name = SMUTEX_INITIALISER
818	#define SMUTEX_LOCK(name) pthread_mutex_lock (&(name))
819	#define SMUTEX_UNLOCK(name) pthread_mutex_unlock (&(name))
820
821	typedef pthread_cond_t scond;
822
823	#define SCOND(name) scond name = PTHREAD_COND_INITIALIZER
824	#define SCOND_SIGNAL(name) pthread_cond_signal (&(name))
825	#define SCOND_BROADCAST(name) pthread_cond_broadcast (&(name))
826	#define SCOND_WAIT(name,mutex) pthread_cond_wait (&(name), &(mutex))
827
828	#endif
829