Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : /** \file
29 : * Generic types.
30 : */
31 :
32 : #ifndef __TOMMYTYPES_H
33 : #define __TOMMYTYPES_H
34 :
35 : /******************************************************************************/
36 : /* types */
37 :
38 : #include <stddef.h>
39 :
40 : #if defined(_MSC_VER)
41 : typedef unsigned tommy_uint32_t; /**< Generic uint32_t type. */
42 : typedef unsigned _int64 tommy_uint64_t; /**< Generic uint64_t type. */
43 : typedef size_t tommy_uintptr_t; /**< Generic uintptr_t type. */
44 : #else
45 : #include <stdint.h>
46 : typedef uint32_t tommy_uint32_t; /**< Generic uint32_t type. */
47 : typedef uint64_t tommy_uint64_t; /**< Generic uint64_t type. */
48 : typedef uintptr_t tommy_uintptr_t; /**< Generic uintptr_t type. */
49 : #endif
50 : typedef size_t tommy_size_t; /**< Generic size_t type. */
51 : typedef ptrdiff_t tommy_ptrdiff_t; /**< Generic ptrdiff_t type. */
52 : typedef int tommy_bool_t; /**< Generic boolean type. */
53 :
54 : /**
55 : * Generic unsigned integer type.
56 : *
57 : * It has no specific size, as is used to store only small values.
58 : * To make the code more efficient, a full 32 bit integer is used.
59 : */
60 : typedef tommy_uint32_t tommy_uint_t;
61 :
62 : /**
63 : * Generic unsigned integer for counting objects.
64 : *
65 : * TommyDS doesn't support more than 2^32-1 objects.
66 : */
67 : typedef tommy_uint32_t tommy_count_t;
68 :
69 : /** \internal
70 : * Type cast required for the C++ compilation.
71 : * When compiling in C++ we cannot convert a void* pointer to another pointer.
72 : * In such case we need an explicit cast.
73 : */
74 : #ifdef __cplusplus
75 : #define tommy_cast(type, value) static_cast<type>(value)
76 : #else
77 : #define tommy_cast(type, value) (value)
78 : #endif
79 :
80 : /******************************************************************************/
81 : /* heap */
82 :
83 : /* by default uses malloc/calloc/realloc/free */
84 :
85 : /**
86 : * Generic malloc(), calloc(), realloc() and free() functions.
87 : * Redefine them to what you need. By default they map to the C malloc(), calloc(), realloc() and free().
88 : */
89 : #if !defined(tommy_malloc) || !defined(tommy_calloc) || !defined(tommy_realloc) || !defined(tommy_free)
90 : #include <stdlib.h>
91 : #endif
92 : #if !defined(tommy_malloc)
93 : #define tommy_malloc malloc
94 : #endif
95 : #if !defined(tommy_calloc)
96 : #define tommy_calloc calloc
97 : #endif
98 : #if !defined(tommy_realloc)
99 : #define tommy_realloc realloc
100 : #endif
101 : #if !defined(tommy_free)
102 : #define tommy_free free
103 : #endif
104 :
105 : /******************************************************************************/
106 : /* modificators */
107 :
108 : /** \internal
109 : * Definition of the inline keyword if available.
110 : */
111 : #if !defined(tommy_inline)
112 : #if defined(_MSC_VER) || defined(__GNUC__)
113 : #define tommy_inline static __inline
114 : #else
115 : #define tommy_inline static
116 : #endif
117 : #endif
118 :
119 : /** \internal
120 : * Definition of the restrict keyword if available.
121 : */
122 : #if !defined(tommy_restrict)
123 : #if __STDC_VERSION__ >= 199901L
124 : #define tommy_restrict restrict
125 : #elif defined(_MSC_VER) || defined(__GNUC__)
126 : #define tommy_restrict __restrict
127 : #else
128 : #define tommy_restrict
129 : #endif
130 : #endif
131 :
132 : /** \internal
133 : * Hints the compiler that a condition is likely true.
134 : */
135 : #if !defined(tommy_likely)
136 : #if defined(__GNUC__)
137 : #define tommy_likely(x) __builtin_expect(!!(x), 1)
138 : #else
139 : #define tommy_likely(x) (x)
140 : #endif
141 : #endif
142 :
143 : /** \internal
144 : * Hints the compiler that a condition is likely false.
145 : */
146 : #if !defined(tommy_unlikely)
147 : #if defined(__GNUC__)
148 : #define tommy_unlikely(x) __builtin_expect(!!(x), 0)
149 : #else
150 : #define tommy_unlikely(x) (x)
151 : #endif
152 : #endif
153 :
154 : /******************************************************************************/
155 : /* key */
156 :
157 : /**
158 : * Key type used in indexed data structures to store the key or the hash value.
159 : */
160 : typedef tommy_uint32_t tommy_key_t;
161 :
162 : /**
163 : * Bits into the ::tommy_key_t type.
164 : */
165 : #define TOMMY_KEY_BIT (sizeof(tommy_key_t) * 8)
166 :
167 : /******************************************************************************/
168 : /* node */
169 :
170 : /**
171 : * Data structure node.
172 : * This node type is shared between all the data structures and used to store some
173 : * info directly into the objects you want to store.
174 : *
175 : * A typical declaration is:
176 : * \code
177 : * struct object {
178 : * tommy_node node;
179 : * // other fields
180 : * };
181 : * \endcode
182 : */
183 : typedef struct tommy_node_struct {
184 : /**
185 : * Next node.
186 : * The tail node has it at 0, like a 0 terminated list.
187 : */
188 : struct tommy_node_struct* next;
189 :
190 : /**
191 : * Previous node.
192 : * The head node points to the tail node, like a circular list.
193 : */
194 : struct tommy_node_struct* prev;
195 :
196 : /**
197 : * Pointer to the object containing the node.
198 : * This field is initialized when inserting nodes into a data structure.
199 : */
200 : void* data;
201 :
202 : /**
203 : * Key used to store the node.
204 : * With hashtables this field is used to store the hash value.
205 : * With lists this field is not used.
206 : */
207 : tommy_key_t key;
208 : } tommy_node;
209 :
210 : /******************************************************************************/
211 : /* compare */
212 :
213 : /**
214 : * Compare function for elements.
215 : * \param obj_a Pointer to the first object to compare.
216 : * \param obj_b Pointer to the second object to compare.
217 : * \return <0 if the first element is less than the second, ==0 equal, >0 if greather.
218 : *
219 : * This function is like the C strcmp().
220 : *
221 : * \code
222 : * struct object {
223 : * tommy_node node;
224 : * int value;
225 : * };
226 : *
227 : * int compare(const void* obj_a, const void* obj_b)
228 : * {
229 : * if (((const struct object*)obj_a)->value < ((const struct object*)obj_b)->value)
230 : * return -1;
231 : * if (((const struct object*)obj_a)->value > ((const struct object*)obj_b)->value)
232 : * return 1;
233 : * return 0;
234 : * }
235 : *
236 : * tommy_list_sort(&list, compare);
237 : * \endcode
238 : *
239 : */
240 : typedef int tommy_compare_func(const void* obj_a, const void* obj_b);
241 :
242 : /**
243 : * Search function for elements.
244 : * \param arg Pointer to the value to search as passed at the search function.
245 : * \param obj Pointer to the object to compare to.
246 : * \return ==0 if the value matches the element. !=0 if different.
247 : *
248 : * The first argument is a pointer to the value to search exactly
249 : * as it's passed at the search function called.
250 : * The second argument is a pointer to the object inside the hashtable to compare.
251 : *
252 : * The return value has to be 0 if the values are equal. != 0 if they are different.
253 : *
254 : * \code
255 : * struct object {
256 : * tommy_node node;
257 : * int value;
258 : * };
259 : *
260 : * int compare(const void* arg, const void* obj)
261 : * {
262 : * const int* value_to_find = arg;
263 : * const struct object* object_to_compare = obj;
264 : *
265 : * return *value_to_find != object_to_compare->value;
266 : * }
267 : *
268 : * int value_to_find = 1;
269 : * struct object* obj = tommy_hashtable_search(&hashtable, compare, &value_to_find, tommy_inthash_u32(value_to_find));
270 : * if (!obj) {
271 : * // not found
272 : * } else {
273 : * // found
274 : * }
275 : * \endcode
276 : *
277 : */
278 : typedef int tommy_search_func(const void* arg, const void* obj);
279 :
280 : /**
281 : * Foreach function.
282 : * \param obj Pointer to the object to iterate.
283 : *
284 : * A typical example is to use free() to deallocate all the objects in a list.
285 : * \code
286 : * tommy_list_foreach(&list, (tommy_foreach_func*)free);
287 : * \endcode
288 : */
289 : typedef void tommy_foreach_func(void* obj);
290 :
291 : /**
292 : * Foreach function with an argument.
293 : * \param arg Pointer to a generic argument.
294 : * \param obj Pointer to the object to iterate.
295 : */
296 : typedef void tommy_foreach_arg_func(void* arg, void* obj);
297 :
298 : /******************************************************************************/
299 : /* bit hacks */
300 :
301 : #if defined(_MSC_VER) && !defined(__cplusplus)
302 : #include <intrin.h>
303 : #pragma intrinsic(_BitScanReverse)
304 : #pragma intrinsic(_BitScanForward)
305 : #endif
306 :
307 : /** \internal
308 : * Integer log2 for constants.
309 : * You can use it only for exact power of 2 up to 256.
310 : */
311 : #define TOMMY_ILOG2(value) ((value) == 256 ? 8 : (value) == 128 ? 7 : (value) == 64 ? 6 : (value) == 32 ? 5 : (value) == 16 ? 4 : (value) == 8 ? 3 : (value) == 4 ? 2 : (value) == 2 ? 1 : 0)
312 :
313 : /**
314 : * Bit scan reverse or integer log2.
315 : * Return the bit index of the most significant 1 bit.
316 : *
317 : * If no bit is set, the result is undefined.
318 : * To force a return 0 in this case, you can use tommy_ilog2_u32(value | 1).
319 : *
320 : * Other interesting ways for bitscan are at:
321 : *
322 : * Bit Twiddling Hacks
323 : * http://graphics.stanford.edu/~seander/bithacks.html
324 : *
325 : * Chess Programming BitScan
326 : * http://chessprogramming.wikispaces.com/BitScan
327 : *
328 : * \param value Value to scan. 0 is not allowed.
329 : * \return The index of the most significant bit set.
330 : */
331 10268423 : tommy_inline tommy_uint_t tommy_ilog2_u32(tommy_uint32_t value)
332 : {
333 : #if defined(_MSC_VER)
334 : unsigned long count;
335 : _BitScanReverse(&count, value);
336 : return count;
337 : #elif defined(__GNUC__)
338 : /*
339 : * GCC implements __builtin_clz(x) as "__builtin_clz(x) = bsr(x) ^ 31"
340 : *
341 : * Where "x ^ 31 = 31 - x", but gcc does not optimize "31 - __builtin_clz(x)" to bsr(x),
342 : * but generates 31 - (bsr(x) xor 31).
343 : *
344 : * So we write "__builtin_clz(x) ^ 31" instead of "31 - __builtin_clz(x)",
345 : * to allow the double xor to be optimized out.
346 : */
347 10268423 : return __builtin_clz(value) ^ 31;
348 : #else
349 : /* Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup */
350 : /* from http://graphics.stanford.edu/~seander/bithacks.html */
351 : static unsigned char TOMMY_DE_BRUIJN_INDEX_ILOG2[32] = {
352 : 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
353 : 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
354 : };
355 :
356 : value |= value >> 1;
357 : value |= value >> 2;
358 : value |= value >> 4;
359 : value |= value >> 8;
360 : value |= value >> 16;
361 :
362 : return TOMMY_DE_BRUIJN_INDEX_ILOG2[(tommy_uint32_t)(value * 0x07C4ACDDU) >> 27];
363 : #endif
364 : }
365 :
366 : /**
367 : * Bit scan forward or trailing zero count.
368 : * Return the bit index of the least significant 1 bit.
369 : *
370 : * If no bit is set, the result is undefined.
371 : * \param value Value to scan. 0 is not allowed.
372 : * \return The index of the least significant bit set.
373 : */
374 1693 : tommy_inline tommy_uint_t tommy_ctz_u32(tommy_uint32_t value)
375 : {
376 : #if defined(_MSC_VER)
377 : unsigned long count;
378 : _BitScanForward(&count, value);
379 : return count;
380 : #elif defined(__GNUC__)
381 1693 : return __builtin_ctz(value);
382 : #else
383 : /* Count the consecutive zero bits (trailing) on the right with multiply and lookup */
384 : /* from http://graphics.stanford.edu/~seander/bithacks.html */
385 : static const unsigned char TOMMY_DE_BRUIJN_INDEX_CTZ[32] = {
386 : 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
387 : 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
388 : };
389 :
390 : return TOMMY_DE_BRUIJN_INDEX_CTZ[(tommy_uint32_t)(((value & - value) * 0x077CB531U)) >> 27];
391 : #endif
392 : }
393 :
394 : /**
395 : * Rounds up to the next power of 2.
396 : * For the value 0, the result is undefined.
397 : * \return The smallest power of 2 not less than the specified value.
398 : */
399 : tommy_inline tommy_uint32_t tommy_roundup_pow2_u32(tommy_uint32_t value)
400 : {
401 : /* Round up to the next highest power of 2 */
402 : /* from http://graphics.stanford.edu/~seander/bithacks.html */
403 :
404 : --value;
405 : value |= value >> 1;
406 : value |= value >> 2;
407 : value |= value >> 4;
408 : value |= value >> 8;
409 : value |= value >> 16;
410 : ++value;
411 :
412 : return value;
413 : }
414 :
415 : /**
416 : * Check if the specified word has a byte at 0.
417 : * \return 0 or 1.
418 : */
419 85 : tommy_inline int tommy_haszero_u32(tommy_uint32_t value)
420 : {
421 85 : return ((value - 0x01010101) & ~value & 0x80808080) != 0;
422 : }
423 : #endif
424 :
|
