LCOV - code coverage report
Current view: top level - tommyds - tommytypes.h (source / functions) Hit Total Coverage
Test: lcov.info Lines: 6 6 100.0 %
Date: 2017-11-06 22:14:04 Functions: 3 3 100.0 %

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

Generated by: LCOV version 1.13