include/common/util.h

/**
 * util.h: Various utility functions.
 *
 * Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
 * Rights to this code are as documented in doc/pod/gplicense.pod.
 *
 * $Id: util.h,v 1.7 2007-09-16 18:54:42 pippijn Exp $
 */

#ifndef UTIL_H
#define UTIL_H

#include <sysconf.h>

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

#include <ermyth/exception.h>

#include <sys/time.h>

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

// This is a vector that stores each element's index in the object.
// This only works for pointers to objects.
template<class T, unsigned 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;
  
  iterator find (const T *obj)
  {
    return obj->*index
      ? this->begin () + obj->*index - 1
      : this->end ();
  }

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

    if (pos < this->size ())
      {
        (*this)[pos - 1] = (*this)[this->size () - 1];
        (*this)[pos - 1]->*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;
  }
};

E int irccasecmp (char const * const s1, char const * const s2);
E int ircncasecmp (char const * const s1, char const * const s2, int maxlen);

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

typedef double tstamp;

inline tstamp
now ()
{
#ifdef HAVE_GETTIMEOFDAY
  struct timeval tv;

  gettimeofday (&tv, 0);
  return tstamp (tv.tv_sec) + tstamp (tv.tv_usec) * tstamp (1e-6);
#else
  return tstamp (time (NULL));
#endif
}

#if 0
/**
 * Comma delimited output to std::cout
 */

namespace impl
{
  struct C
  {
    template<typename T>
    C operator << (T const &t) const
    {
      std::cout << ", " << t;
      return C();
    }
    
    C operator << (std::ostream &(* const f) (std::ostream &)) const
    {
      std::cout << f;
      return C();
    }
    
    C operator << (std::ios_base &(* const f) (std::ios_base &)) const
    {
      std::cout << f;
      return C();
    }
  };

  enum Del
  {
    del
  };
  
  template<typename T>
  C operator << (Del, T const &t)
  {
    std::cout << t;
    return C();
  }
  
  inline Del
  operator << (Del, std::ostream &(* const f) (std::ostream &))
  {
    std::cout << f;
    return del;
  }
  
  inline Del
  operator << (Del, std::ios_base &(* const f) (std::ios_base &))
  {
    std::cout << f;
    return del;
  }

  // The <<'s taking std::ios_base&(std::ios_base&)'s are for things like std::hex.
  // The <<'s taking std::ostream&(std::ostream&)'s are for things like std::endl.

  inline Del
  operator << (std::ostream &, Del)
  {
    return del;
  }
  // To allow: std::cout << del << 2 << 4
}

using impl::del;
#endif

// Allow pasting things, even if one of the arguments is a macro itself
#define PASTE(A, B)              DOPASTE (A, B)
#define DOPASTE(A, B)            DODOPASTE (A, B)
#define DODOPASTE(A, B)          A ## B

#define PASTE3(A, B, C)          PASTE (PASTE (A, B), C)
#define PASTE4(A, B, C, D)       PASTE (PASTE3 (A, B, C), D)
#define PASTE5(A, B, C, D, E)    PASTE (PASTE4 (A, B, C, D), E)
#define PASTE6(A, B, C, D, E, F) PASTE (PASTE5 (A, B, C, D, E), F)

namespace impl
{
  template<bool>
  struct static_assert;

  template<>
  struct static_assert<true>
  {
  };
}

#define static_assert(cond) ::impl::static_assert<(cond)> PASTE (static_assert_, __LINE__)

E int itoa (uint32_t n, char *buf, int buflen);
E int itoa (uint64_t n, char *buf, int buflen);

inline int
itoa (int32_t n, char *buf, int buflen)
{
  *buf = '-';
  buf += (n < 0);
  uint32_t u = n < 0 ? -n : n;
  return itoa (u, buf, buflen - 1);
}

inline int
itoa (int64_t n, char *buf, int buflen)
{
  *buf = '-';
  buf += (n < 0);
  uint64_t u = n < 0 ? -n : n;
  return itoa (u, buf, buflen - 1);
}

template<typename IntType, int N>
inline int
itoa (IntType n, char (&buf)[N])
{
  return itoa (n, buf, N);
}

#endif
Revision:	1.8
Committed:	Sat Sep 22 14:27:26 2007 UTC (19 years ago) by pippijn
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.7:	+1 -1 lines
State:	*FILE REMOVED*
Log Message:	split up ermyth into ermyth-modules, libermyth (currently just ermyth-util) and ermyth-core
#	User	Rev	Content
1	pippijn	1.7	/**
2			* util.h: Various utility functions.
3			*
4	pippijn	1.2	* Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
5	pippijn	1.7	* Rights to this code are as documented in doc/pod/gplicense.pod.
6	pippijn	1.2	*
7	pippijn	1.8	* $Id: util.h,v 1.7 2007-09-16 18:54:42 pippijn Exp $
8	pippijn	1.2	*/
9
10	pippijn	1.1	#ifndef UTIL_H
11			#define UTIL_H
12
13	pippijn	1.6	#include <sysconf.h>
14
15	pippijn	1.1	#include <climits>
16			#include <cstddef>
17			#include <vector>
18
19	pippijn	1.3	#include <ermyth/exception.h>
20	pippijn	1.1
21	pippijn	1.6	#include <sys/time.h>
22
23	pippijn	1.1	/**
24			* Mostly the same as std::vector, but erase can reorder
25			* the elements, making insert/remove O(1) instead of O(n).
26			*
27			* NOTE: only some forms of erase are available
28			* (Taken from Crossfire TRT http://cf.schmorp.de/)
29			*/
30			template<typename T, typename Alloc = std::allocator<T> >
31			struct unordered_vector : std::vector<T, Alloc>
32			{
33			typedef typename unordered_vector::iterator iterator;
34
35			void erase (unsigned pos)
36			{
37			if (pos < this->size () - 1)
38			(this)[pos] = (this)[this->size () - 1];
39
40			this->pop_back ();
41			}
42
43			void erase (iterator pos)
44			{
45			erase ((unsigned)(pos - this->begin ()));
46			}
47
48			void insert (T const &val)
49			{
50			push_back (val);
51			}
52			};
53
54			/**
55			* The following templates find a sufficiently large integer type to contain
56			* the given number of bits.
57			*
58			* Usage:
59			*
60			* unsigned_type<16>::type a; // 16-bit unsigned if available (probably unsigned short)
61			* signed_type<8>::type a; // 8-bit signed if available (probably char)
62			*/
63
64			// Empty class if everything failed
65			struct empty_base
66			{
67			};
68
69			// To allow inheritance from this and get the integer type out
70			template<typename T>
71			struct identity
72			{
73			typedef T type;
74			};
75
76			/**
77			* The following two templates are a compile-time if-statement.
78			*/
79			template<bool Cond, class Then, class Else>
80			struct If
81			{
82			typedef Then ret;
83			};
84
85			template<class Then, class Else>
86			struct If<false, Then, Else>
87			{
88			typedef Else ret;
89			};
90
91			// Looks whether the desired type exists
92			template<typename T, std::size_t bits, typename Else>
93			struct type_if_size
94			: If<sizeof (T) * CHAR_BIT >= bits, identity<T>, Else>::ret
95			{
96			};
97
98			template<std::size_t bits>
99			struct unsigned_type
100			: type_if_size<unsigned char, bits,
101			type_if_size<unsigned short, bits,
102			type_if_size<unsigned int, bits,
103			type_if_size<unsigned long, bits,
104			empty_base // No such type
105			>
106			>
107			>
108			>
109			{
110			};
111
112			template<std::size_t bits>
113			struct signed_type
114			: type_if_size<signed char, bits
115			, type_if_size<signed short, bits
116			, type_if_size<signed int, bits
117			, type_if_size<signed long, bits
118			, empty_base // No such type
119			>
120			>
121			>
122			>
123			{
124			};
125
126	pippijn	1.3	// This is a vector that stores each element's index in the object.
127			// This only works for pointers to objects.
128	pippijn	1.6	template<class T, unsigned T::index = &T::index, class Alloc = std::allocator<T > >
129	pippijn	1.1	struct indexing_vector : std::vector<T *, Alloc>
130			{
131			typedef typename indexing_vector::size_type size_type;
132			typedef typename indexing_vector::iterator iterator;
133
134	pippijn	1.3	iterator find (const T *obj)
135			{
136			return obj->*index
137			? this->begin () + obj->*index - 1
138			: this->end ();
139			}
140
141	pippijn	1.1	void erase (T *obj)
142			{
143	pippijn	1.6	unsigned pos = obj->*index;
144	pippijn	1.1	obj->*index = 0;
145
146	pippijn	1.3	if (pos < this->size ())
147	pippijn	1.1	{
148	pippijn	1.3	(this)[pos - 1] = (this)[this->size () - 1];
149			(this)[pos - 1]->index = pos;
150	pippijn	1.1	}
151
152			this->pop_back ();
153			}
154
155			void insert (T *obj)
156			{
157			this->push_back (obj);
158			obj->*index = this->size ();
159			}
160			};
161
162			struct str_hash
163			{
164			std::size_t operator () (char const *s) const
165			{
166			unsigned long hash = 0;
167
168			// use the one-at-a-time hash function.
169			// see http://burtleburtle.net/bob/hash/doobs.html
170			while (*s)
171			{
172			hash += *s++;
173			hash += hash << 10;
174			hash ^= hash >> 6;
175			}
176
177			hash += hash << 3;
178			hash ^= hash >> 11;
179			hash += hash << 15;
180
181			return hash;
182			}
183			};
184
185			struct str_eq
186			{
187			bool operator () (char const * const s1, char const * const s2) const
188			{
189			if (s1 == NULL \|\| s2 == NULL)
190			throw nullpointer_exception ();
191			return !strcmp (s1, s2);
192			}
193			};
194
195			struct str_lt
196			{
197			bool operator () (char const * const s1, char const * const s2) const
198			{
199			if (s1 == NULL \|\| s2 == NULL)
200			throw nullpointer_exception ();
201			return strcmp (s1, s2) < 0;
202			}
203			};
204
205	pippijn	1.3	E int irccasecmp (char const * const s1, char const * const s2);
206			E int ircncasecmp (char const * const s1, char const * const s2, int maxlen);
207
208			struct irccase_lt
209			{
210			bool operator () (char const * const s1, char const * const s2) const
211			{
212			if (s1 == NULL \|\| s2 == NULL)
213			throw nullpointer_exception ();
214			return irccasecmp (s1, s2) < 0;
215			}
216			};
217
218	pippijn	1.5	typedef double tstamp;
219
220			inline tstamp
221	pippijn	1.3	now ()
222			{
223			#ifdef HAVE_GETTIMEOFDAY
224			struct timeval tv;
225
226			gettimeofday (&tv, 0);
227	pippijn	1.5	return tstamp (tv.tv_sec) + tstamp (tv.tv_usec) * tstamp (1e-6);
228	pippijn	1.3	#else
229	pippijn	1.5	return tstamp (time (NULL));
230	pippijn	1.3	#endif
231			}
232
233	pippijn	1.4	#if 0
234			/**
235			* Comma delimited output to std::cout
236			*/
237
238			namespace impl
239			{
240			struct C
241			{
242			template<typename T>
243			C operator << (T const &t) const
244			{
245			std::cout << ", " << t;
246			return C();
247			}
248
249			C operator << (std::ostream &(* const f) (std::ostream &)) const
250			{
251			std::cout << f;
252			return C();
253			}
254
255			C operator << (std::ios_base &(* const f) (std::ios_base &)) const
256			{
257			std::cout << f;
258			return C();
259			}
260			};
261
262			enum Del
263			{
264			del
265			};
266
267			template<typename T>
268			C operator << (Del, T const &t)
269			{
270			std::cout << t;
271			return C();
272			}
273
274			inline Del
275			operator << (Del, std::ostream &(* const f) (std::ostream &))
276			{
277			std::cout << f;
278			return del;
279			}
280
281			inline Del
282			operator << (Del, std::ios_base &(* const f) (std::ios_base &))
283			{
284			std::cout << f;
285			return del;
286			}
287
288			// The <<'s taking std::ios_base&(std::ios_base&)'s are for things like std::hex.
289			// The <<'s taking std::ostream&(std::ostream&)'s are for things like std::endl.
290
291			inline Del
292			operator << (std::ostream &, Del)
293			{
294			return del;
295			}
296			// To allow: std::cout << del << 2 << 4
297			}
298
299			using impl::del;
300			#endif
301
302			// Allow pasting things, even if one of the arguments is a macro itself
303			#define PASTE(A, B) DOPASTE (A, B)
304			#define DOPASTE(A, B) DODOPASTE (A, B)
305			#define DODOPASTE(A, B) A ## B
306
307			#define PASTE3(A, B, C) PASTE (PASTE (A, B), C)
308			#define PASTE4(A, B, C, D) PASTE (PASTE3 (A, B, C), D)
309			#define PASTE5(A, B, C, D, E) PASTE (PASTE4 (A, B, C, D), E)
310			#define PASTE6(A, B, C, D, E, F) PASTE (PASTE5 (A, B, C, D, E), F)
311
312			namespace impl
313			{
314			template<bool>
315			struct static_assert;
316
317			template<>
318			struct static_assert<true>
319			{
320			};
321			}
322
323			#define static_assert(cond) ::impl::static_assert<(cond)> PASTE (static_assert_, __LINE__)
324	pippijn	1.3
325	pippijn	1.6	E int itoa (uint32_t n, char *buf, int buflen);
326			E int itoa (uint64_t n, char *buf, int buflen);
327
328			inline int
329			itoa (int32_t n, char *buf, int buflen)
330			{
331			*buf = '-';
332			buf += (n < 0);
333			uint32_t u = n < 0 ? -n : n;
334			return itoa (u, buf, buflen - 1);
335			}
336
337			inline int
338			itoa (int64_t n, char *buf, int buflen)
339			{
340			*buf = '-';
341			buf += (n < 0);
342			uint64_t u = n < 0 ? -n : n;
343			return itoa (u, buf, buflen - 1);
344			}
345
346			template<typename IntType, int N>
347			inline int
348			itoa (IntType n, char (&buf)[N])
349			{
350			return itoa (n, buf, N);
351			}
352
353	pippijn	1.1	#endif