include/common/util.h

/*
 * Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
 * Rights to this code are as documented in doc/pod/gplicense.pod.
 *
 * Various utility functions.
 *
 * $Id: account.h,v 1.2 2007-07-21 01:29:07 pippijn Exp $
 */

#ifndef UTIL_H
#define UTIL_H

#include <climits>
#include <cstddef>
#include <vector>

#include "exception.h"

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

  void *operator new[] (size_t s)
  {
    void *p = malloc (s);
    memset (p, 0, s);
    return p;
  }

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

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

/**
 * Mostly the same as std::vector, but erase can reorder
 * the elements, making insert/remove O(1) instead of O(n).
 *
 * NOTE: only some forms of erase are available
 * (Taken from Crossfire TRT http://cf.schmorp.de/)
 */
template<typename T, typename Alloc = std::allocator<T> >
struct unordered_vector : std::vector<T, Alloc>
{
  typedef typename unordered_vector::iterator iterator;

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

    this->pop_back ();
  }

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

  void insert (T const &val)
  {
    push_back (val);
  }
};

/**
 * The following templates find a sufficiently large integer type to contain
 * the given number of bits.
 *
 * Usage:
 *
 * unsigned_type<16>::type a; // 16-bit unsigned if available (probably unsigned short)
 * signed_type<8>::type a; // 8-bit signed if available (probably char)
 */

// Empty class if everything failed
struct empty_base
{
};

// To allow inheritance from this and get the integer type out
template<typename T>
struct identity
{
  typedef T type;
};

/**
 * The following two templates are a compile-time if-statement.
 */
template<bool Cond, class Then, class Else>
struct If
{
  typedef Then ret;
};

template<class Then, class Else>
struct If<false, Then, Else>
{
  typedef Else ret;
};

// Looks whether the desired type exists
template<typename T, std::size_t bits, typename Else>
struct type_if_size
: If<sizeof (T) * CHAR_BIT >= bits, identity<T>, Else>::ret
{
};

template<std::size_t bits>
struct unsigned_type
: type_if_size<unsigned char, bits,
    type_if_size<unsigned short, bits,
      type_if_size<unsigned int, bits,
        type_if_size<unsigned long, bits,
          empty_base // No such type
        >
      >
    >
  >
{
};

template<std::size_t bits>
struct signed_type
: type_if_size<signed char, bits
  , type_if_size<signed short, bits
    , type_if_size<signed int, bits
      , type_if_size<signed long, bits
        , empty_base // No such type
        >
      >
    >
  >
{
};

template<class T, int T::*index = &T::index, class Alloc = std::allocator<T *> >
struct indexing_vector : std::vector<T *, Alloc>
{
  typedef typename indexing_vector::size_type size_type;
  typedef typename indexing_vector::iterator iterator;
  
  void erase (T *obj)
  {
    size_type pos = obj->*index - 1;
    obj->*index = 0;

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

    this->pop_back ();
  }

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

struct str_hash
{
  std::size_t operator () (char const *s) const
  {
    unsigned long hash = 0;

    // use the one-at-a-time hash function.
    // 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_eq
{
  bool operator () (char const * const s1, char const * const s2) const
  {
    if (s1 == NULL || s2 == NULL)
      throw nullpointer_exception ();
    return !strcmp (s1, s2);
  }
};

struct str_lt
{
  bool operator () (char const * const s1, char const * const s2) const
  {
    if (s1 == NULL || s2 == NULL)
      throw nullpointer_exception ();
    return strcmp (s1, s2) < 0;
  }
};

#endif
Revision:	1.2
Committed:	Wed Jul 25 01:05:17 2007 UTC (19 years, 3 months ago) by pippijn
Content type:	text/plain
Branch:	MAIN
Changes since 1.1:	+9 -0 lines
Log Message:	- moved to GPL - added license information to files
#	User	Rev	Content
1	pippijn	1.2	/*
2			* Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
3			* Rights to this code are as documented in doc/pod/gplicense.pod.
4			*
5			* Various utility functions.
6			*
7			* $Id: account.h,v 1.2 2007-07-21 01:29:07 pippijn Exp $
8			*/
9
10	pippijn	1.1	#ifndef UTIL_H
11			#define UTIL_H
12
13			#include <climits>
14			#include <cstddef>
15			#include <vector>
16
17			#include "exception.h"
18
19			// makes dynamically allocated objects zero-initialised
20			struct zero_initialised
21			{
22			void *operator new (size_t s)
23			{
24			void *p = malloc (s);
25			memset (p, 0, s);
26			return p;
27			}
28
29			void *operator new[] (size_t s)
30			{
31			void *p = malloc (s);
32			memset (p, 0, s);
33			return p;
34			}
35
36			void operator delete (void *p, size_t s)
37			{
38			free (p);
39			}
40
41			void operator delete[] (void *p, size_t s)
42			{
43			free (p);
44			}
45			};
46
47			/**
48			* Mostly the same as std::vector, but erase can reorder
49			* the elements, making insert/remove O(1) instead of O(n).
50			*
51			* NOTE: only some forms of erase are available
52			* (Taken from Crossfire TRT http://cf.schmorp.de/)
53			*/
54			template<typename T, typename Alloc = std::allocator<T> >
55			struct unordered_vector : std::vector<T, Alloc>
56			{
57			typedef typename unordered_vector::iterator iterator;
58
59			void erase (unsigned pos)
60			{
61			if (pos < this->size () - 1)
62			(this)[pos] = (this)[this->size () - 1];
63
64			this->pop_back ();
65			}
66
67			void erase (iterator pos)
68			{
69			erase ((unsigned)(pos - this->begin ()));
70			}
71
72			void insert (T const &val)
73			{
74			push_back (val);
75			}
76			};
77
78			/**
79			* The following templates find a sufficiently large integer type to contain
80			* the given number of bits.
81			*
82			* Usage:
83			*
84			* unsigned_type<16>::type a; // 16-bit unsigned if available (probably unsigned short)
85			* signed_type<8>::type a; // 8-bit signed if available (probably char)
86			*/
87
88			// Empty class if everything failed
89			struct empty_base
90			{
91			};
92
93			// To allow inheritance from this and get the integer type out
94			template<typename T>
95			struct identity
96			{
97			typedef T type;
98			};
99
100			/**
101			* The following two templates are a compile-time if-statement.
102			*/
103			template<bool Cond, class Then, class Else>
104			struct If
105			{
106			typedef Then ret;
107			};
108
109			template<class Then, class Else>
110			struct If<false, Then, Else>
111			{
112			typedef Else ret;
113			};
114
115			// Looks whether the desired type exists
116			template<typename T, std::size_t bits, typename Else>
117			struct type_if_size
118			: If<sizeof (T) * CHAR_BIT >= bits, identity<T>, Else>::ret
119			{
120			};
121
122			template<std::size_t bits>
123			struct unsigned_type
124			: type_if_size<unsigned char, bits,
125			type_if_size<unsigned short, bits,
126			type_if_size<unsigned int, bits,
127			type_if_size<unsigned long, bits,
128			empty_base // No such type
129			>
130			>
131			>
132			>
133			{
134			};
135
136			template<std::size_t bits>
137			struct signed_type
138			: type_if_size<signed char, bits
139			, type_if_size<signed short, bits
140			, type_if_size<signed int, bits
141			, type_if_size<signed long, bits
142			, empty_base // No such type
143			>
144			>
145			>
146			>
147			{
148			};
149
150			template<class T, int T::index = &T::index, class Alloc = std::allocator<T > >
151			struct indexing_vector : std::vector<T *, Alloc>
152			{
153			typedef typename indexing_vector::size_type size_type;
154			typedef typename indexing_vector::iterator iterator;
155
156			void erase (T *obj)
157			{
158			size_type pos = obj->*index - 1;
159			obj->*index = 0;
160
161			if (pos <= this->size ())
162			{
163			(this)[pos] = (this)[this->size () - 1];
164			(this)[pos]->index = pos;
165			}
166
167			this->pop_back ();
168			}
169
170			void insert (T *obj)
171			{
172			this->push_back (obj);
173			obj->*index = this->size ();
174			}
175			};
176
177			struct str_hash
178			{
179			std::size_t operator () (char const *s) const
180			{
181			unsigned long hash = 0;
182
183			// use the one-at-a-time hash function.
184			// see http://burtleburtle.net/bob/hash/doobs.html
185			while (*s)
186			{
187			hash += *s++;
188			hash += hash << 10;
189			hash ^= hash >> 6;
190			}
191
192			hash += hash << 3;
193			hash ^= hash >> 11;
194			hash += hash << 15;
195
196			return hash;
197			}
198			};
199
200			struct str_eq
201			{
202			bool operator () (char const * const s1, char const * const s2) const
203			{
204			if (s1 == NULL \|\| s2 == NULL)
205			throw nullpointer_exception ();
206			return !strcmp (s1, s2);
207			}
208			};
209
210			struct str_lt
211			{
212			bool operator () (char const * const s1, char const * const s2) const
213			{
214			if (s1 == NULL \|\| s2 == NULL)
215			throw nullpointer_exception ();
216			return strcmp (s1, s2) < 0;
217			}
218			};
219
220			#endif