1 #ifndef JEMALLOC_INTERNAL_BIT_UTIL_H
2 #define JEMALLOC_INTERNAL_BIT_UTIL_H
4 #include "jemalloc/internal/assert.h"
6 #define BIT_UTIL_INLINE static inline
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
15 BIT_UTIL_INLINE unsigned
16 ffs_llu(unsigned long long bitmap) {
17 return JEMALLOC_INTERNAL_FFSLL(bitmap);
20 BIT_UTIL_INLINE unsigned
21 ffs_lu(unsigned long bitmap) {
22 return JEMALLOC_INTERNAL_FFSL(bitmap);
25 BIT_UTIL_INLINE unsigned
26 ffs_u(unsigned bitmap) {
27 return JEMALLOC_INTERNAL_FFS(bitmap);
30 BIT_UTIL_INLINE unsigned
31 ffs_zu(size_t bitmap) {
32 #if LG_SIZEOF_PTR == LG_SIZEOF_INT
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);
39 #error No implementation for size_t ffs()
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);
50 #error No implementation for 64-bit ffs()
54 BIT_UTIL_INLINE unsigned
55 ffs_u32(uint32_t bitmap) {
56 #if LG_SIZEOF_INT == 2
59 #error No implementation for 32-bit ffs()
64 BIT_UTIL_INLINE uint64_t
65 pow2_ceil_u64(uint64_t x) {
77 BIT_UTIL_INLINE uint32_t
78 pow2_ceil_u32(uint32_t x) {
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);
95 return pow2_ceil_u32(x);
99 #if (defined(__i386__) || defined(__amd64__) || defined(__x86_64__))
100 BIT_UTIL_INLINE unsigned
106 : "=r"(ret) // Outputs.
109 assert(ret < UINT_MAX);
110 return (unsigned)ret;
112 #elif (defined(_MSC_VER))
113 BIT_UTIL_INLINE unsigned
119 #if (LG_SIZEOF_PTR == 3)
120 _BitScanReverse64(&ret, x);
121 #elif (LG_SIZEOF_PTR == 2)
122 _BitScanReverse(&ret, x);
124 # error "Unsupported type size for lg_floor()"
126 assert(ret < UINT_MAX);
127 return (unsigned)ret;
129 #elif (defined(JEMALLOC_HAVE_BUILTIN_CLZ))
130 BIT_UTIL_INLINE unsigned
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);
139 # error "Unsupported type size for lg_floor()"
143 BIT_UTIL_INLINE unsigned
152 #if (LG_SIZEOF_PTR == 3)
155 if (x == SIZE_T_MAX) {
156 return (8 << LG_SIZEOF_PTR) - 1;
159 return ffs_zu(x) - 2;
163 #undef BIT_UTIL_INLINE
165 #endif /* JEMALLOC_INTERNAL_BIT_UTIL_H */