COMBINATORIAL_BLAS  1.6
tommytypes.h
Go to the documentation of this file.
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 
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;
42 typedef unsigned _int64 tommy_uint64_t;
43 typedef size_t tommy_uintptr_t;
44 #else
45 #include <stdint.h>
46 typedef uint32_t tommy_uint32_t;
47 typedef uint64_t tommy_uint64_t;
48 typedef uintptr_t tommy_uintptr_t;
49 #endif
50 typedef size_t tommy_size_t;
51 typedef ptrdiff_t tommy_ptrdiff_t;
52 typedef int tommy_bool_t;
61 
68 
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 
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 
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 
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 
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 
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 
161 
165 #define TOMMY_KEY_BIT (sizeof(tommy_key_t) * 8)
166 
167 /******************************************************************************/
168 /* node */
169 
183 typedef struct tommy_node_struct {
189 
195 
200  void* data;
201 
208 } tommy_node;
209 
210 /******************************************************************************/
211 /* compare */
212 
240 typedef int tommy_compare_func(const void* obj_a, const void* obj_b);
241 
273 typedef int tommy_search_func(const void* arg, const void* obj);
274 
284 typedef void tommy_foreach_func(void* obj);
285 
291 typedef void tommy_foreach_arg_func(void* arg, void* obj);
292 
293 /******************************************************************************/
294 /* bit hacks */
295 
296 #if defined(_MSC_VER) && !defined(__cplusplus)
297 #include <intrin.h>
298 #pragma intrinsic(_BitScanReverse)
299 #pragma intrinsic(_BitScanForward)
300 #endif
301 
306 #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)
307 
327 {
328 #if defined(_MSC_VER)
329  unsigned long count;
330  _BitScanReverse(&count, value);
331  return count;
332 #elif defined(__GNUC__)
333  /*
334  * GCC implements __builtin_clz(x) as "__builtin_clz(x) = bsr(x) ^ 31"
335  *
336  * Where "x ^ 31 = 31 - x", but gcc does not optimize "31 - __builtin_clz(x)" to bsr(x),
337  * but generates 31 - (bsr(x) xor 31).
338  *
339  * So we write "__builtin_clz(x) ^ 31" instead of "31 - __builtin_clz(x)",
340  * to allow the double xor to be optimized out.
341  */
342  return __builtin_clz(value) ^ 31;
343 #else
344  /* Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup */
345  /* from http://graphics.stanford.edu/~seander/bithacks.html */
346  static unsigned char TOMMY_DE_BRUIJN_INDEX_ILOG2[32] = {
347  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
348  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
349  };
350 
351  value |= value >> 1;
352  value |= value >> 2;
353  value |= value >> 4;
354  value |= value >> 8;
355  value |= value >> 16;
356 
357  return TOMMY_DE_BRUIJN_INDEX_ILOG2[(tommy_uint32_t)(value * 0x07C4ACDDU) >> 27];
358 #endif
359 }
360 
370 {
371 #if defined(_MSC_VER)
372  unsigned long count;
373  _BitScanForward(&count, value);
374  return count;
375 #elif defined(__GNUC__)
376  return __builtin_ctz(value);
377 #else
378  /* Count the consecutive zero bits (trailing) on the right with multiply and lookup */
379  /* from http://graphics.stanford.edu/~seander/bithacks.html */
380  static const unsigned char TOMMY_DE_BRUIJN_INDEX_CTZ[32] = {
381  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
382  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
383  };
384 
385  return TOMMY_DE_BRUIJN_INDEX_CTZ[(tommy_uint32_t)(((value & - value) * 0x077CB531U)) >> 27];
386 #endif
387 }
388 
395 {
396  /* Round up to the next highest power of 2 */
397  /* from http://www-graphics.stanford.edu/~seander/bithacks.html */
398 
399  --value;
400  value |= value >> 1;
401  value |= value >> 2;
402  value |= value >> 4;
403  value |= value >> 8;
404  value |= value >> 16;
405  ++value;
406 
407  return value;
408 }
409 #endif
410 
struct tommy_node_struct tommy_node
tommy_uint32_t tommy_key_t
Definition: tommytypes.h:160
tommy_uint32_t tommy_count_t
Definition: tommytypes.h:67
uint32_t tommy_uint32_t
Definition: tommytypes.h:46
ptrdiff_t tommy_ptrdiff_t
Definition: tommytypes.h:51
struct tommy_node_struct * next
Definition: tommytypes.h:188
struct tommy_node_struct * prev
Definition: tommytypes.h:194
tommy_inline tommy_uint_t tommy_ctz_u32(tommy_uint32_t value)
Definition: tommytypes.h:369
uintptr_t tommy_uintptr_t
Definition: tommytypes.h:48
int tommy_search_func(const void *arg, const void *obj)
Definition: tommytypes.h:273
int tommy_compare_func(const void *obj_a, const void *obj_b)
Definition: tommytypes.h:240
tommy_inline tommy_uint32_t tommy_roundup_pow2_u32(tommy_uint32_t value)
Definition: tommytypes.h:394
#define tommy_inline
Definition: tommytypes.h:115
tommy_uint32_t tommy_uint_t
Definition: tommytypes.h:60
void tommy_foreach_func(void *obj)
Definition: tommytypes.h:284
size_t tommy_size_t
Definition: tommytypes.h:50
tommy_inline tommy_uint_t tommy_ilog2_u32(tommy_uint32_t value)
Definition: tommytypes.h:326
uint64_t tommy_uint64_t
Definition: tommytypes.h:47
int tommy_bool_t
Definition: tommytypes.h:52
tommy_key_t key
Definition: tommytypes.h:207
void tommy_foreach_arg_func(void *arg, void *obj)
Definition: tommytypes.h:291