tdb2: allow transaction to nest.
[ccan] / ccan / ilog / ilog.h
1 #if !defined(_ilog_H)
2 # define _ilog_H (1)
3 # include "config.h"
4 # include <stdint.h>
5 # include <limits.h>
6 # include <ccan/compiler/compiler.h>
7
8 /**
9  * ilog32 - Integer binary logarithm of a 32-bit value.
10  * @_v: A 32-bit value.
11  * Returns floor(log2(_v))+1, or 0 if _v==0.
12  * This is the number of bits that would be required to represent _v in two's
13  *  complement notation with all of the leading zeros stripped.
14  * Note that many uses will resolve to the fast macro version instead.
15  *
16  * See Also:
17  *      ilog32_nz(), ilog64()
18  *
19  * Example:
20  *      // Rounds up to next power of 2 (if not a power of 2).
21  *      static uint32_t round_up32(uint32_t i)
22  *      {
23  *              assert(i != 0);
24  *              return 1U << ilog32(i-1);
25  *      }
26  */
27 int ilog32(uint32_t _v) IDEMPOTENT;
28
29 /**
30  * ilog32_nz - Integer binary logarithm of a non-zero 32-bit value.
31  * @_v: A 32-bit value.
32  * Returns floor(log2(_v))+1, or undefined if _v==0.
33  * This is the number of bits that would be required to represent _v in two's
34  *  complement notation with all of the leading zeros stripped.
35  * Note that many uses will resolve to the fast macro version instead.
36  * See Also:
37  *      ilog32(), ilog64_nz()
38  * Example:
39  *      // Find Last Set (ie. highest bit set, 0 to 31).
40  *      static uint32_t fls32(uint32_t i)
41  *      {
42  *              assert(i != 0);
43  *              return ilog32_nz(i) - 1;
44  *      }
45  */
46 int ilog32_nz(uint32_t _v) IDEMPOTENT;
47
48 /**
49  * ilog64 - Integer binary logarithm of a 64-bit value.
50  * @_v: A 64-bit value.
51  * Returns floor(log2(_v))+1, or 0 if _v==0.
52  * This is the number of bits that would be required to represent _v in two's
53  *  complement notation with all of the leading zeros stripped.
54  * Note that many uses will resolve to the fast macro version instead.
55  * See Also:
56  *      ilog64_nz(), ilog32()
57  */
58 int ilog64(uint64_t _v) IDEMPOTENT;
59
60 /**
61  * ilog64_nz - Integer binary logarithm of a non-zero 64-bit value.
62  * @_v: A 64-bit value.
63  * Returns floor(log2(_v))+1, or undefined if _v==0.
64  * This is the number of bits that would be required to represent _v in two's
65  *  complement notation with all of the leading zeros stripped.
66  * Note that many uses will resolve to the fast macro version instead.
67  * See Also:
68  *      ilog64(), ilog32_nz()
69  */
70 int ilog64_nz(uint64_t _v) IDEMPOTENT;
71
72 /**
73  * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
74  * @_v: A non-negative 32-bit constant.
75  * Returns floor(log2(_v))+1, or 0 if _v==0.
76  * This is the number of bits that would be required to represent _v in two's
77  *  complement notation with all of the leading zeros stripped.
78  * This macro should only be used when you need a compile-time constant,
79  * otherwise ilog32 or ilog32_nz are just as fast and more flexible.
80  *
81  * Example:
82  *      #define MY_PAGE_SIZE    4096
83  *      #define MY_PAGE_BITS    (STATIC_ILOG_32(PAGE_SIZE) - 1)
84  */
85 #define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
86
87 /**
88  * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
89  * @_v: A non-negative 64-bit constant.
90  * Returns floor(log2(_v))+1, or 0 if _v==0.
91  * This is the number of bits that would be required to represent _v in two's
92  *  complement notation with all of the leading zeros stripped.
93  * This macro should only be used when you need a compile-time constant,
94  * otherwise ilog64 or ilog64_nz are just as fast and more flexible.
95  */
96 #define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
97
98 /* Private implementation details */
99
100 /*Note the casts to (int) below: this prevents "upgrading"
101    the type of an entire expression to an (unsigned) size_t.*/
102 #if INT_MAX>=2147483647 && HAVE_BUILTIN_CLZ
103 #define builtin_ilog32_nz(v) \
104         (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
105 #elif LONG_MAX>=2147483647L && HAVE_BUILTIN_CLZL
106 #define builtin_ilog32_nz(v) \
107         (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clzl(v))
108 #endif
109
110 #if INT_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZ
111 #define builtin_ilog64_nz(v) \
112         (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
113 #elif LONG_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZL
114 #define builtin_ilog64_nz(v) \
115         (((int)sizeof(unsigned long)*CHAR_BIT) - __builtin_clzl(v))
116 #elif HAVE_BUILTIN_CLZLL
117 #define builtin_ilog64_nz(v) \
118         (((int)sizeof(unsigned long long)*CHAR_BIT) - __builtin_clzll(v))
119 #endif
120
121 #ifdef builtin_ilog32_nz
122 #define ilog32(_v) (builtin_ilog32_nz(_v)&-!!(_v))
123 #define ilog32_nz(_v) builtin_ilog32_nz(_v)
124 #else
125 #define ilog32_nz(_v) ilog32(_v)
126 #define ilog32(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_32(_v) : ilog32(_v))
127 #endif /* builtin_ilog32_nz */
128
129 #ifdef builtin_ilog64_nz
130 #define ilog64(_v) (builtin_ilog64_nz(_v)&-!!(_v))
131 #define ilog64_nz(_v) builtin_ilog64_nz(_v)
132 #else
133 #define ilog64_nz(_v) ilog64(_v)
134 #define ilog64(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_64(_v) : ilog64(_v))
135 #endif /* builtin_ilog64_nz */
136
137 /* Macros for evaluating compile-time constant ilog. */
138 # define STATIC_ILOG0(_v) (!!(_v))
139 # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v))
140 # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v))
141 # define STATIC_ILOG3(_v) \
142  (((_v)&0xF0)?4+STATIC_ILOG2((_v)>>4):STATIC_ILOG2(_v))
143 # define STATIC_ILOG4(_v) \
144  (((_v)&0xFF00)?8+STATIC_ILOG3((_v)>>8):STATIC_ILOG3(_v))
145 # define STATIC_ILOG5(_v) \
146  (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v))
147 # define STATIC_ILOG6(_v) \
148  (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v))
149
150 #endif /* _ilog_H */