tommyDS_hashlin/tommytypes.h

   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 at 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 at the first object to compare.
 216  * \param obj_b Pointer at 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 at the value to search.
 245  * \param obj Pointer at the object to compare to.
 246  * \return ==0 if the value matches the element. !=0 if different.
 247  *
 248  * Note that the first argument is a pointer to the value to search and
 249  * the second one is a pointer to the object to compare.
 250  * They are pointers of two different types.
 251  *
 252  * \code
 253  * struct object {
 254  *     tommy_node node;
 255  *     int value;
 256  * };
 257  *
 258  * int compare(const void* arg, const void* obj)
 259  * {
 260  *     return *(const int*)arg != ((const struct object*)obj)->value;
 261  * }
 262  *
 263  * int value_to_find = 1;
 264  * struct object* obj = tommy_hashtable_search(&hashtable, compare, &value_to_find, tommy_inthash_u32(value_to_find));
 265  * if (!obj) {
 266  *     // not found
 267  * } else {
 268  *     // found
 269  * }
 270  * \endcode
 271  *
 272  */
 273 typedef int tommy_search_func(const void* arg, const void* obj);
 274
 275 /**
 276  * Foreach function.
 277  * \param obj Pointer at the object to iterate.
 278  *
 279  * A typical example is to use free() to deallocate all the objects in a list.
 280  * \code
 281  * tommy_list_foreach(&list, (tommy_foreach_func*)free);
 282  * \endcode
 283  */
 284 typedef void tommy_foreach_func(void* obj);
 285
 286 /**
 287  * Foreach function with an argument.
 288  * \param arg Pointer at a generic argument.
 289  * \param obj Pointer at the object to iterate.
 290  */
 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
 302 /** \internal
 303  * Integer log2 for constants.
 304  * You can use it only for exact power of 2 up to 256.
 305  */
 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
 308 /**
 309  * Bit scan reverse or integer log2.
 310  * Return the bit index of the most significant 1 bit.
 311  *
 312  * If no bit is set, the result is undefined.
 313  * To force a return 0 in this case, you can use tommy_ilog2_u32(value | 1).
 314  *
 315  * Other interesting ways for bitscan are at:
 316  *
 317  * Bit Twiddling Hacks
 318  * http://graphics.stanford.edu/~seander/bithacks.html
 319  *
 320  * Chess Programming BitScan
 321  * http://chessprogramming.wikispaces.com/BitScan
 322  *
 323  * \param value Value to scan. 0 is not allowed.
 324  * \return The index of the most significant bit set.
 325  */
 326 tommy_inline tommy_uint_t tommy_ilog2_u32(tommy_uint32_t value)
 327 {
 328 #if defined(_MSC_VER)
 329         unsigned long count;
 330         _BitScanReverse(&count, value);
 331         return count;
 332 /* Removed since current toolchain used for crosscompiling for Fritzbox 73XX and 74XX cant handle this!
 333 #elif defined(__GNUC__)
 334
 335          * GCC implements __builtin_clz(x) as "__builtin_clz(x) = bsr(x) ^ 31"
 336          *
 337          * Where "x ^ 31 = 31 - x", but gcc does not optimize "31 - __builtin_clz(x)" to bsr(x),
 338          * but generates 31 - (bsr(x) xor 31).
 339          *
 340          * So we write "__builtin_clz(x) ^ 31" instead of "31 - __builtin_clz(x)",
 341          * to allow the double xor to be optimized out.
 342         return __builtin_clz(value) ^ 31;
 343 */
 344 #else
 345         /* Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup */
 346         /* from http://graphics.stanford.edu/~seander/bithacks.html */
 347         static unsigned char TOMMY_DE_BRUIJN_INDEX_ILOG2[32] = {
 348                 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
 349                 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
 350         };
 351
 352         value |= value >> 1;
 353         value |= value >> 2;
 354         value |= value >> 4;
 355         value |= value >> 8;
 356         value |= value >> 16;
 357
 358         return TOMMY_DE_BRUIJN_INDEX_ILOG2[(tommy_uint32_t)(value * 0x07C4ACDDU) >> 27];
 359 #endif
 360 }
 361
 362 /**
 363  * Bit scan forward or trailing zero count.
 364  * Return the bit index of the least significant 1 bit.
 365  *
 366  * If no bit is set, the result is undefined.
 367  * \param value Value to scan. 0 is not allowed.
 368  * \return The index of the least significant bit set.
 369  */
 370 tommy_inline tommy_uint_t tommy_ctz_u32(tommy_uint32_t value)
 371 {
 372 #if defined(_MSC_VER)
 373         unsigned long count;
 374         _BitScanForward(&count, value);
 375         return count;
 376 #elif defined(__GNUC__)
 377         return __builtin_ctz(value);
 378 #else
 379         /* Count the consecutive zero bits (trailing) on the right with multiply and lookup */
 380         /* from http://graphics.stanford.edu/~seander/bithacks.html */
 381         static const unsigned char TOMMY_DE_BRUIJN_INDEX_CTZ[32] = {
 382                 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
 383                 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
 384         };
 385
 386         return TOMMY_DE_BRUIJN_INDEX_CTZ[(tommy_uint32_t)(((value & - value) * 0x077CB531U)) >> 27];
 387 #endif
 388 }
 389
 390 /**
 391  * Rounds up to the next power of 2.
 392  * For the value 0, the result is undefined.
 393  * \return The smallest power of 2 not less than the specified value.
 394  */
 395 tommy_inline tommy_uint32_t tommy_roundup_pow2_u32(tommy_uint32_t value)
 396 {
 397         /* Round up to the next highest power of 2 */
 398         /* from http://graphics.stanford.edu/~seander/bithacks.html */
 399
 400         --value;
 401         value |= value >> 1;
 402         value |= value >> 2;
 403         value |= value >> 4;
 404         value |= value >> 8;
 405         value |= value >> 16;
 406         ++value;
 407
 408         return value;
 409 }
 410 #endif
 411