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 : /** \file
28 : * Generic types.
29 : */
30 :
31 : #ifndef __TOMMYTYPES_H
32 : #define __TOMMYTYPES_H
33 :
34 : /******************************************************************************/
35 : /* types */
36 :
37 : #include <stddef.h>
38 :
39 : #ifdef _MSC_VER
40 : typedef unsigned tommy_uint32_t; /**< Generic uint32_t type. */
41 : typedef unsigned _int64 tommy_uint64_t; /**< Generic uint64_t type. */
42 : typedef size_t tommy_uintptr_t; /**< Generic uintptr_t type. */
43 : #ifdef _WIN64
44 : #define TOMMY_SIZE_BIT 64
45 : typedef unsigned _int64_t tommy_size_t; /**< Generic size_t type. */
46 : typedef _int64_t tommy_ssize_t; /**< Generic ssize_t type. */
47 : #else
48 : #define TOMMY_SIZE_BIT 32
49 : typedef unsigned tommy_size_t; /**< Generic size_t type. */
50 : typedef int tommy_ssize_t; /**< Generic ssize_t type. */
51 : #endif
52 : #else
53 : #include <stdint.h>
54 : typedef uint32_t tommy_uint32_t; /**< Generic uint32_t type. */
55 : typedef uint64_t tommy_uint64_t; /**< Generic uint64_t type. */
56 : typedef uintptr_t tommy_uintptr_t; /**< Generic uintptr_t type. */
57 : #if SIZE_MAX == UINT64_MAX
58 : #define TOMMY_SIZE_BIT 64
59 : typedef uint64_t tommy_size_t; /**< Generic size_t type. */
60 : typedef int64_t tommy_ssize_t; /**< Generic ssize_t type. */
61 : #elif SIZE_MAX == UINT32_MAX
62 : #define TOMMY_SIZE_BIT 32
63 : typedef uint32_t tommy_size_t; /**< Generic size_t type. */
64 : typedef int32_t tommy_ssize_t; /**< Generic ssize_t type. */
65 : #else
66 : #error Unsupported SIZE_MAX
67 : #endif
68 : #endif
69 :
70 : typedef ptrdiff_t tommy_ptrdiff_t; /**< Generic ptrdiff_t type. */
71 : typedef int tommy_bool_t; /**< Generic boolean type. */
72 :
73 : /**
74 : * Generic unsigned integer type.
75 : *
76 : * It has no specific size, as is used to store only small values.
77 : * To make the code more efficient, a full 32 bit integer is used.
78 : */
79 : typedef tommy_uint32_t tommy_uint_t;
80 :
81 : /** \internal
82 : * Type cast required for the C++ compilation.
83 : * When compiling in C++ we cannot convert a void* pointer to another pointer.
84 : * In such case we need an explicit cast.
85 : */
86 : #ifdef __cplusplus
87 : #define tommy_cast(type, value) static_cast<type>(value)
88 : #else
89 : #define tommy_cast(type, value) (value)
90 : #endif
91 :
92 : /******************************************************************************/
93 : /* heap */
94 :
95 : /* by default uses malloc/calloc/realloc/free */
96 :
97 : /**
98 : * Generic malloc(), calloc(), realloc() and free() functions.
99 : * Redefine them to what you need. By default they map to the C malloc(), calloc(), realloc() and free().
100 : */
101 : #if !defined(tommy_malloc) || !defined(tommy_calloc) || !defined(tommy_realloc) || !defined(tommy_free)
102 : #include <stdlib.h>
103 : #endif
104 : #if !defined(tommy_malloc)
105 : #define tommy_malloc malloc
106 : #endif
107 : #if !defined(tommy_calloc)
108 : #define tommy_calloc calloc
109 : #endif
110 : #if !defined(tommy_realloc)
111 : #define tommy_realloc realloc
112 : #endif
113 : #if !defined(tommy_free)
114 : #define tommy_free free
115 : #endif
116 :
117 : /******************************************************************************/
118 : /* modificators */
119 :
120 : /** \internal
121 : * Definition of the inline keyword if available.
122 : */
123 : #if !defined(tommy_inline)
124 : #if defined(_MSC_VER) || defined(__GNUC__)
125 : #define tommy_inline static __inline
126 : #else
127 : #define tommy_inline static
128 : #endif
129 : #endif
130 :
131 : /** \internal
132 : * Definition of the restrict keyword if available.
133 : */
134 : #if !defined(tommy_restrict)
135 : #if __STDC_VERSION__ >= 199901L
136 : #define tommy_restrict restrict
137 : #elif defined(_MSC_VER) || defined(__GNUC__)
138 : #define tommy_restrict __restrict
139 : #else
140 : #define tommy_restrict
141 : #endif
142 : #endif
143 :
144 : /** \internal
145 : * Hints the compiler that a condition is likely true.
146 : */
147 : #if !defined(tommy_likely)
148 : #if defined(__GNUC__)
149 : #define tommy_likely(x) __builtin_expect(!!(x), 1)
150 : #else
151 : #define tommy_likely(x) (x)
152 : #endif
153 : #endif
154 :
155 : /** \internal
156 : * Hints the compiler that a condition is likely false.
157 : */
158 : #if !defined(tommy_unlikely)
159 : #if defined(__GNUC__)
160 : #define tommy_unlikely(x) __builtin_expect(!!(x), 0)
161 : #else
162 : #define tommy_unlikely(x) (x)
163 : #endif
164 : #endif
165 :
166 : /******************************************************************************/
167 : /* key/hash */
168 :
169 : /**
170 : * Type used in indexed data structures to store the key of a object.
171 : */
172 : typedef tommy_size_t tommy_key_t;
173 :
174 : /**
175 : * Type used in hashtables to store the hash of a object.
176 : */
177 : typedef tommy_size_t tommy_hash_t;
178 :
179 : /******************************************************************************/
180 : /* node */
181 :
182 : /**
183 : * Data structure node.
184 : * This node type is shared between all the data structures and used to store some
185 : * info directly into the objects you want to store.
186 : *
187 : * A typical declaration is:
188 : * \code
189 : * struct object {
190 : * tommy_node node;
191 : * // other fields
192 : * };
193 : * \endcode
194 : */
195 : typedef struct tommy_node_struct {
196 : /**
197 : * Next node.
198 : * The tail node has it at 0, like a 0 terminated list.
199 : */
200 : struct tommy_node_struct* next;
201 :
202 : /**
203 : * Previous node.
204 : * The head node points to the tail node, like a circular list.
205 : */
206 : struct tommy_node_struct* prev;
207 :
208 : /**
209 : * Pointer to the object containing the node.
210 : * This field is initialized when inserting nodes into a data structure.
211 : */
212 : void* data;
213 :
214 : /**
215 : * Index of the node.
216 : * With tries this field is used to store the key.
217 : * With hashtables this field is used to store the hash value.
218 : * With lists this field is not used.
219 : */
220 : tommy_size_t index;
221 : } tommy_node;
222 :
223 : /******************************************************************************/
224 : /* compare */
225 :
226 : /**
227 : * Compare function for elements.
228 : * \param obj_a Pointer to the first object to compare.
229 : * \param obj_b Pointer to the second object to compare.
230 : * \return <0 if the first element is less than the second, ==0 equal, >0 if greather.
231 : *
232 : * This function is like the C strcmp().
233 : *
234 : * \code
235 : * struct object {
236 : * tommy_node node;
237 : * int value;
238 : * };
239 : *
240 : * int compare(const void* obj_a, const void* obj_b)
241 : * {
242 : * if (((const struct object*)obj_a)->value < ((const struct object*)obj_b)->value)
243 : * return -1;
244 : * if (((const struct object*)obj_a)->value > ((const struct object*)obj_b)->value)
245 : * return 1;
246 : * return 0;
247 : * }
248 : *
249 : * tommy_list_sort(&list, compare);
250 : * \endcode
251 : *
252 : */
253 : typedef int tommy_compare_func(const void* obj_a, const void* obj_b);
254 :
255 : /**
256 : * Search function for elements.
257 : * \param arg Pointer to the value to search as passed at the search function.
258 : * \param obj Pointer to the object to compare to.
259 : * \return ==0 if the value matches the element. !=0 if different.
260 : *
261 : * The first argument is a pointer to the value to search exactly
262 : * as it's passed at the search function called.
263 : * The second argument is a pointer to the object inside the hashtable to compare.
264 : *
265 : * The return value has to be 0 if the values are equal. != 0 if they are different.
266 : *
267 : * \code
268 : * struct object {
269 : * tommy_node node;
270 : * int value;
271 : * };
272 : *
273 : * int compare(const void* arg, const void* obj)
274 : * {
275 : * const int* value_to_find = arg;
276 : * const struct object* object_to_compare = obj;
277 : *
278 : * return *value_to_find != object_to_compare->value;
279 : * }
280 : *
281 : * int value_to_find = 1;
282 : * struct object* obj = tommy_hashtable_search(&hashtable, compare, &value_to_find, tommy_inthash_u32(value_to_find));
283 : * if (!obj) {
284 : * // not found
285 : * } else {
286 : * // found
287 : * }
288 : * \endcode
289 : *
290 : */
291 : typedef int tommy_search_func(const void* arg, const void* obj);
292 :
293 : /**
294 : * Foreach function.
295 : * \param obj Pointer to the object to iterate.
296 : *
297 : * A typical example is to use free() to deallocate all the objects in a list.
298 : * \code
299 : * tommy_list_foreach(&list, (tommy_foreach_func*)free);
300 : * \endcode
301 : */
302 : typedef void tommy_foreach_func(void* obj);
303 :
304 : /**
305 : * Foreach function with an argument.
306 : * \param arg Pointer to a generic argument.
307 : * \param obj Pointer to the object to iterate.
308 : */
309 : typedef void tommy_foreach_arg_func(void* arg, void* obj);
310 :
311 : /******************************************************************************/
312 : /* bit hacks */
313 :
314 : #if defined(_MSC_VER) && !defined(__cplusplus)
315 : #include <intrin.h>
316 : #pragma intrinsic(_BitScanReverse)
317 : #pragma intrinsic(_BitScanForward)
318 : #if TOMMY_SIZE_BIT == 64
319 : #pragma intrinsic(_BitScanReverse64)
320 : #pragma intrinsic(_BitScanForward64)
321 : #endif
322 : #endif
323 :
324 : /** \internal
325 : * Integer log2 for constants.
326 : * You can use it only for exact power of 2 up to 256.
327 : */
328 : #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)
329 :
330 : /**
331 : * Bit scan reverse or integer log2.
332 : * Return the bit index of the most significant 1 bit.
333 : *
334 : * If no bit is set, the result is undefined.
335 : * To force a return 0 in this case, you can use tommy_ilog2_u32(value | 1).
336 : *
337 : * Other interesting ways for bitscan are at:
338 : *
339 : * Bit Twiddling Hacks
340 : * http://graphics.stanford.edu/~seander/bithacks.html
341 : *
342 : * Chess Programming BitScan
343 : * http://chessprogramming.wikispaces.com/BitScan
344 : *
345 : * \param value Value to scan. 0 is not allowed.
346 : * \return The index of the most significant bit set.
347 : */
348 : tommy_inline tommy_uint_t tommy_ilog2_u32(tommy_uint32_t value)
349 : {
350 : #if defined(_MSC_VER)
351 : unsigned long count;
352 : _BitScanReverse(&count, value);
353 : return count;
354 : #elif defined(__GNUC__)
355 : /*
356 : * GCC implements __builtin_clz(x) as "__builtin_clz(x) = bsr(x) ^ 31"
357 : *
358 : * Where "x ^ 31 = 31 - x", but gcc does not optimize "31 - __builtin_clz(x)" to bsr(x),
359 : * but generates 31 - (bsr(x) xor 31).
360 : *
361 : * So we write "__builtin_clz(x) ^ 31" instead of "31 - __builtin_clz(x)",
362 : * to allow the double xor to be optimized out.
363 : */
364 : return __builtin_clz(value) ^ 31;
365 : #else
366 : /* Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup */
367 : /* from http://graphics.stanford.edu/~seander/bithacks.html */
368 : static unsigned char TOMMY_DE_BRUIJN_INDEX_ILOG2[32] = {
369 : 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
370 : 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
371 : };
372 :
373 : value |= value >> 1;
374 : value |= value >> 2;
375 : value |= value >> 4;
376 : value |= value >> 8;
377 : value |= value >> 16;
378 :
379 : return TOMMY_DE_BRUIJN_INDEX_ILOG2[(tommy_uint32_t)(value * 0x07C4ACDDU) >> 27];
380 : #endif
381 : }
382 :
383 : #if TOMMY_SIZE_BIT == 64
384 : /**
385 : * Bit scan reverse or integer log2 for 64 bits.
386 : */
387 908497031 : tommy_inline tommy_uint_t tommy_ilog2_u64(tommy_uint64_t value)
388 : {
389 : #if defined(_MSC_VER)
390 : unsigned long count;
391 : _BitScanReverse64(&count, value);
392 : return count;
393 : #elif defined(__GNUC__)
394 908497031 : return __builtin_clzll(value) ^ 63;
395 : #else
396 : uint32_t l = value & 0xFFFFFFFFU;
397 : uint32_t h = value >> 32;
398 : if (h)
399 : return tommy_ilog2_u32(h) + 32;
400 : else
401 : return tommy_ilog2_u32(l);
402 : #endif
403 : }
404 : #endif
405 :
406 : /**
407 : * Bit scan forward or trailing zero count.
408 : * Return the bit index of the least significant 1 bit.
409 : *
410 : * If no bit is set, the result is undefined.
411 : * \param value Value to scan. 0 is not allowed.
412 : * \return The index of the least significant bit set.
413 : */
414 : tommy_inline tommy_uint_t tommy_ctz_u32(tommy_uint32_t value)
415 : {
416 : #if defined(_MSC_VER)
417 : unsigned long count;
418 : _BitScanForward(&count, value);
419 : return count;
420 : #elif defined(__GNUC__)
421 : return __builtin_ctz(value);
422 : #else
423 : /* Count the consecutive zero bits (trailing) on the right with multiply and lookup */
424 : /* from http://graphics.stanford.edu/~seander/bithacks.html */
425 : static const unsigned char TOMMY_DE_BRUIJN_INDEX_CTZ[32] = {
426 : 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
427 : 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
428 : };
429 :
430 : return TOMMY_DE_BRUIJN_INDEX_CTZ[(tommy_uint32_t)(((value & - value) * 0x077CB531U)) >> 27];
431 : #endif
432 : }
433 :
434 : #if TOMMY_SIZE_BIT == 64
435 : /**
436 : * Bit scan forward or trailing zero count for 64 bits.
437 : */
438 5 : tommy_inline tommy_uint_t tommy_ctz_u64(tommy_uint64_t value)
439 : {
440 : #if defined(_MSC_VER)
441 : unsigned long count;
442 : _BitScanForward64(&count, value);
443 : return count;
444 : #elif defined(__GNUC__)
445 5 : return __builtin_ctzll(value);
446 : #else
447 : uint32_t l = value & 0xFFFFFFFFU;
448 : uint32_t h = value >> 32;
449 : if (l)
450 : return tommy_ctz_u32(l);
451 : else
452 : return tommy_ctz_u32(h) + 32;
453 : #endif
454 : }
455 : #endif
456 :
457 : /**
458 : * Rounds up to the next power of 2.
459 : * For the value 0, the result is undefined.
460 : * \return The smallest power of 2 not less than the specified value.
461 : */
462 : tommy_inline tommy_uint32_t tommy_roundup_pow2_u32(tommy_uint32_t value)
463 : {
464 : /* Round up to the next highest power of 2 */
465 : /* from http://graphics.stanford.edu/~seander/bithacks.html */
466 :
467 : --value;
468 : value |= value >> 1;
469 : value |= value >> 2;
470 : value |= value >> 4;
471 : value |= value >> 8;
472 : value |= value >> 16;
473 : ++value;
474 :
475 : return value;
476 : }
477 :
478 : /**
479 : * Rounds up to the next power of 2 for 64 bits.
480 : */
481 5064 : tommy_inline tommy_uint64_t tommy_roundup_pow2_u64(tommy_uint64_t value)
482 : {
483 5064 : --value;
484 5064 : value |= value >> 1;
485 5064 : value |= value >> 2;
486 5064 : value |= value >> 4;
487 5064 : value |= value >> 8;
488 5064 : value |= value >> 16;
489 5064 : value |= value >> 32;
490 5064 : ++value;
491 :
492 5064 : return value;
493 : }
494 :
495 : /**
496 : * Check if the specified word has a byte at 0.
497 : * \return 0 or 1.
498 : */
499 67108949 : tommy_inline int tommy_haszero_u32(tommy_uint32_t value)
500 : {
501 67108949 : return ((value - 0x01010101) & ~value & 0x80808080) != 0;
502 : }
503 :
504 : /*
505 : * Bit depth mapping.
506 : */
507 : #if TOMMY_SIZE_BIT == 64
508 : #define tommy_ilog2 tommy_ilog2_u64
509 : #define tommy_ctz tommy_ctz_u64
510 : #define tommy_roundup_pow2 tommy_roundup_pow2_u64
511 : #else
512 : #define tommy_ilog2 tommy_ilog2_u32
513 : #define tommy_ctz tommy_ctz_u32
514 : #define tommy_roundup_pow2 tommy_roundup_pow2_u32
515 : #endif
516 :
517 : #endif
518 :
|
