contrib/jemalloc/include/jemalloc/internal/bit_util.h

   1 #ifndef JEMALLOC_INTERNAL_BIT_UTIL_H
   2 #define JEMALLOC_INTERNAL_BIT_UTIL_H
   3
   4 #include "jemalloc/internal/assert.h"
   5
   6 #define BIT_UTIL_INLINE static inline
   7
   8 /* Sanity check. */
   9 #if !defined(JEMALLOC_INTERNAL_FFSLL) || !defined(JEMALLOC_INTERNAL_FFSL) \
  10     || !defined(JEMALLOC_INTERNAL_FFS)
  11 #  error JEMALLOC_INTERNAL_FFS{,L,LL} should have been defined by configure
  12 #endif
  13
  14
  15 BIT_UTIL_INLINE unsigned
  16 ffs_llu(unsigned long long bitmap) {
  17         return JEMALLOC_INTERNAL_FFSLL(bitmap);
  18 }
  19
  20 BIT_UTIL_INLINE unsigned
  21 ffs_lu(unsigned long bitmap) {
  22         return JEMALLOC_INTERNAL_FFSL(bitmap);
  23 }
  24
  25 BIT_UTIL_INLINE unsigned
  26 ffs_u(unsigned bitmap) {
  27         return JEMALLOC_INTERNAL_FFS(bitmap);
  28 }
  29
  30 BIT_UTIL_INLINE unsigned
  31 ffs_zu(size_t bitmap) {
  32 #if LG_SIZEOF_PTR == LG_SIZEOF_INT
  33         return ffs_u(bitmap);
  34 #elif LG_SIZEOF_PTR == LG_SIZEOF_LONG
  35         return ffs_lu(bitmap);
  36 #elif LG_SIZEOF_PTR == LG_SIZEOF_LONG_LONG
  37         return ffs_llu(bitmap);
  38 #else
  39 #error No implementation for size_t ffs()
  40 #endif
  41 }
  42
  43 BIT_UTIL_INLINE unsigned
  44 ffs_u64(uint64_t bitmap) {
  45 #if LG_SIZEOF_LONG == 3
  46         return ffs_lu(bitmap);
  47 #elif LG_SIZEOF_LONG_LONG == 3
  48         return ffs_llu(bitmap);
  49 #else
  50 #error No implementation for 64-bit ffs()
  51 #endif
  52 }
  53
  54 BIT_UTIL_INLINE unsigned
  55 ffs_u32(uint32_t bitmap) {
  56 #if LG_SIZEOF_INT == 2
  57         return ffs_u(bitmap);
  58 #else
  59 #error No implementation for 32-bit ffs()
  60 #endif
  61         return ffs_u(bitmap);
  62 }
  63
  64 BIT_UTIL_INLINE uint64_t
  65 pow2_ceil_u64(uint64_t x) {
  66         x--;
  67         x |= x >> 1;
  68         x |= x >> 2;
  69         x |= x >> 4;
  70         x |= x >> 8;
  71         x |= x >> 16;
  72         x |= x >> 32;
  73         x++;
  74         return x;
  75 }
  76
  77 BIT_UTIL_INLINE uint32_t
  78 pow2_ceil_u32(uint32_t x) {
  79         x--;
  80         x |= x >> 1;
  81         x |= x >> 2;
  82         x |= x >> 4;
  83         x |= x >> 8;
  84         x |= x >> 16;
  85         x++;
  86         return x;
  87 }
  88
  89 /* Compute the smallest power of 2 that is >= x. */
  90 BIT_UTIL_INLINE size_t
  91 pow2_ceil_zu(size_t x) {
  92 #if (LG_SIZEOF_PTR == 3)
  93         return pow2_ceil_u64(x);
  94 #else
  95         return pow2_ceil_u32(x);
  96 #endif
  97 }
  98
  99 #if (defined(__i386__) || defined(__amd64__) || defined(__x86_64__))
 100 BIT_UTIL_INLINE unsigned
 101 lg_floor(size_t x) {
 102         size_t ret;
 103         assert(x != 0);
 104
 105         asm ("bsr %1, %0"
 106             : "=r"(ret) // Outputs.
 107             : "r"(x)    // Inputs.
 108             );
 109         assert(ret < UINT_MAX);
 110         return (unsigned)ret;
 111 }
 112 #elif (defined(_MSC_VER))
 113 BIT_UTIL_INLINE unsigned
 114 lg_floor(size_t x) {
 115         unsigned long ret;
 116
 117         assert(x != 0);
 118
 119 #if (LG_SIZEOF_PTR == 3)
 120         _BitScanReverse64(&ret, x);
 121 #elif (LG_SIZEOF_PTR == 2)
 122         _BitScanReverse(&ret, x);
 123 #else
 124 #  error "Unsupported type size for lg_floor()"
 125 #endif
 126         assert(ret < UINT_MAX);
 127         return (unsigned)ret;
 128 }
 129 #elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
 130 BIT_UTIL_INLINE unsigned
 131 lg_floor(size_t x) {
 132         assert(x != 0);
 133
 134 #if (LG_SIZEOF_PTR == LG_SIZEOF_INT)
 135         return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clz(x);
 136 #elif (LG_SIZEOF_PTR == LG_SIZEOF_LONG)
 137         return ((8 << LG_SIZEOF_PTR) - 1) - __builtin_clzl(x);
 138 #else
 139 #  error "Unsupported type size for lg_floor()"
 140 #endif
 141 }
 142 #else
 143 BIT_UTIL_INLINE unsigned
 144 lg_floor(size_t x) {
 145         assert(x != 0);
 146
 147         x |= (x >> 1);
 148         x |= (x >> 2);
 149         x |= (x >> 4);
 150         x |= (x >> 8);
 151         x |= (x >> 16);
 152 #if (LG_SIZEOF_PTR == 3)
 153         x |= (x >> 32);
 154 #endif
 155         if (x == SIZE_T_MAX) {
 156                 return (8 << LG_SIZEOF_PTR) - 1;
 157         }
 158         x++;
 159         return ffs_zu(x) - 2;
 160 }
 161 #endif
 162
 163 #undef BIT_UTIL_INLINE
 164
 165 #endif /* JEMALLOC_INTERNAL_BIT_UTIL_H */