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