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