htable: fix type of htable_type _pick return.
[ccan] / ccan / bitmap / bitmap.h
1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #ifndef CCAN_BITMAP_H_
3 #define CCAN_BITMAP_H_
4
5 #include <stdbool.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <limits.h>
9
10 #include <ccan/endian/endian.h>
11
12 typedef unsigned long bitmap_word;
13
14 #define BITMAP_WORD_BITS        (sizeof(bitmap_word) * CHAR_BIT)
15 #define BITMAP_NWORDS(_n)       \
16         (((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
17
18 #define BITMAP_WORD_0           (0)
19 #define BITMAP_WORD_1           ((bitmap_word)-1UL)
20
21 /*
22  * We wrap each word in a structure for type checking.
23  */
24 typedef struct bitmap {
25         bitmap_word w;
26 } bitmap;
27
28 #define BITMAP_DECLARE(_name, _nbits) \
29         bitmap (_name)[BITMAP_NWORDS(_nbits)]
30
31 static inline size_t bitmap_sizeof(unsigned long nbits)
32 {
33         return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
34 }
35
36 static inline bitmap_word bitmap_bswap(bitmap_word w)
37 {
38         if (BITMAP_WORD_BITS == 32)
39                 return (ENDIAN_CAST bitmap_word)cpu_to_be32(w);
40         else if (BITMAP_WORD_BITS == 64)
41                 return (ENDIAN_CAST bitmap_word)cpu_to_be64(w);
42 }
43
44 #define BITMAP_WORD(_bm, _n)    ((_bm)[(_n) / BITMAP_WORD_BITS].w)
45 #define BITMAP_WORDBIT(_n)      \
46         (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
47
48 #define BITMAP_HEADWORDS(_nbits) \
49         ((_nbits) / BITMAP_WORD_BITS)
50 #define BITMAP_HEADBYTES(_nbits) \
51         (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
52
53 #define BITMAP_TAILWORD(_bm, _nbits) \
54         ((_bm)[BITMAP_HEADWORDS(_nbits)].w)
55 #define BITMAP_HASTAIL(_nbits)  (((_nbits) % BITMAP_WORD_BITS) != 0)
56 #define BITMAP_TAILBITS(_nbits) \
57         (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
58 #define BITMAP_TAIL(_bm, _nbits) \
59         (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
60
61 static inline void bitmap_set_bit(bitmap *bitmap, unsigned long n)
62 {
63         BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n);
64 }
65
66 static inline void bitmap_clear_bit(bitmap *bitmap, unsigned long n)
67 {
68         BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n);
69 }
70
71 static inline void bitmap_change_bit(bitmap *bitmap, unsigned long n)
72 {
73         BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n);
74 }
75
76 static inline bool bitmap_test_bit(const bitmap *bitmap, unsigned long n)
77 {
78         return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
79 }
80
81 void bitmap_zero_range(bitmap *bitmap, unsigned long n, unsigned long m);
82 void bitmap_fill_range(bitmap *bitmap, unsigned long n, unsigned long m);
83
84 static inline void bitmap_zero(bitmap *bitmap, unsigned long nbits)
85 {
86         memset(bitmap, 0, bitmap_sizeof(nbits));
87 }
88
89 static inline void bitmap_fill(bitmap *bitmap, unsigned long nbits)
90 {
91         memset(bitmap, 0xff, bitmap_sizeof(nbits));
92 }
93
94 static inline void bitmap_copy(bitmap *dst, const bitmap *src,
95                                unsigned long nbits)
96 {
97         memcpy(dst, src, bitmap_sizeof(nbits));
98 }
99
100 #define BITMAP_DEF_BINOP(_name, _op) \
101         static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
102                                           unsigned long nbits)          \
103         { \
104                 unsigned long i = 0; \
105                 for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
106                         dst[i].w = src1[i].w _op src2[i].w; \
107                 } \
108         }
109
110 BITMAP_DEF_BINOP(and, &)
111 BITMAP_DEF_BINOP(or, |)
112 BITMAP_DEF_BINOP(xor, ^)
113 BITMAP_DEF_BINOP(andnot, & ~)
114
115 #undef BITMAP_DEF_BINOP
116
117 static inline void bitmap_complement(bitmap *dst, const bitmap *src,
118                                      unsigned long nbits)
119 {
120         unsigned long i;
121
122         for (i = 0; i < BITMAP_NWORDS(nbits); i++)
123                 dst[i].w = ~src[i].w;
124 }
125
126 static inline bool bitmap_equal(const bitmap *src1, const bitmap *src2,
127                                 unsigned long nbits)
128 {
129         return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
130                 && (!BITMAP_HASTAIL(nbits)
131                     || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
132 }
133
134 static inline bool bitmap_intersects(const bitmap *src1, const bitmap *src2,
135                                      unsigned long nbits)
136 {
137         unsigned long i;
138
139         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
140                 if (src1[i].w & src2[i].w)
141                         return true;
142         }
143         if (BITMAP_HASTAIL(nbits) &&
144             (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
145                 return true;
146         return false;
147 }
148
149 static inline bool bitmap_subset(const bitmap *src1, const bitmap *src2,
150                                  unsigned long nbits)
151 {
152         unsigned long i;
153
154         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
155                 if (src1[i].w  & ~src2[i].w)
156                         return false;
157         }
158         if (BITMAP_HASTAIL(nbits) &&
159             (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
160                 return false;
161         return true;
162 }
163
164 static inline bool bitmap_full(const bitmap *bitmap, unsigned long nbits)
165 {
166         unsigned long i;
167
168         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
169                 if (bitmap[i].w != -1UL)
170                         return false;
171         }
172         if (BITMAP_HASTAIL(nbits) &&
173             (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits)))
174                 return false;
175
176         return true;
177 }
178
179 static inline bool bitmap_empty(const bitmap *bitmap, unsigned long nbits)
180 {
181         unsigned long i;
182
183         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
184                 if (bitmap[i].w != 0)
185                         return false;
186         }
187         if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0))
188                 return false;
189
190         return true;
191 }
192
193 unsigned long bitmap_ffs(const bitmap *bitmap,
194                          unsigned long n, unsigned long m);
195
196 /*
197  * Allocation functions
198  */
199 static inline bitmap *bitmap_alloc(unsigned long nbits)
200 {
201         return malloc(bitmap_sizeof(nbits));
202 }
203
204 static inline bitmap *bitmap_alloc0(unsigned long nbits)
205 {
206         bitmap *bitmap;
207
208         bitmap = bitmap_alloc(nbits);
209         if (bitmap)
210                 bitmap_zero(bitmap, nbits);
211         return bitmap;
212 }
213
214 static inline bitmap *bitmap_alloc1(unsigned long nbits)
215 {
216         bitmap *bitmap;
217
218         bitmap = bitmap_alloc(nbits);
219         if (bitmap)
220                 bitmap_fill(bitmap, nbits);
221         return bitmap;
222 }
223
224 static inline bitmap *bitmap_realloc0(bitmap *bitmap,
225                                       unsigned long obits, unsigned long nbits)
226 {
227         bitmap = realloc(bitmap, bitmap_sizeof(nbits));
228
229         if ((nbits > obits) && bitmap)
230                 bitmap_zero_range(bitmap, obits, nbits);
231
232         return bitmap;
233 }
234
235 static inline bitmap *bitmap_realloc1(bitmap *bitmap,
236                                       unsigned long obits, unsigned long nbits)
237 {
238         bitmap = realloc(bitmap, bitmap_sizeof(nbits));
239
240         if ((nbits > obits) && bitmap)
241                 bitmap_fill_range(bitmap, obits, nbits);
242
243         return bitmap;
244 }
245
246 #endif /* CCAN_BITMAP_H_ */