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