AUTHORS: Add Valient Gough.
[openvswitch] / lib / bitmap.h
1 /*
2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 #ifndef BITMAP_H
18 #define BITMAP_H 1
19
20 #include <limits.h>
21 #include <stdlib.h>
22 #include "util.h"
23
24 #define BITMAP_ULONG_BITS (sizeof(unsigned long) * CHAR_BIT)
25
26 static inline unsigned long *
27 bitmap_unit__(const unsigned long *bitmap, size_t offset)
28 {
29     return (unsigned long *) &bitmap[offset / BITMAP_ULONG_BITS];
30 }
31
32 static inline unsigned long
33 bitmap_bit__(size_t offset)
34 {
35     return 1UL << (offset % BITMAP_ULONG_BITS);
36 }
37
38 static inline size_t
39 bitmap_n_longs(size_t n_bits)
40 {
41     return DIV_ROUND_UP(n_bits, BITMAP_ULONG_BITS);
42 }
43
44 static inline size_t
45 bitmap_n_bytes(size_t n_bits)
46 {
47     return bitmap_n_longs(n_bits) * sizeof(unsigned long int);
48 }
49
50 static inline unsigned long *
51 bitmap_allocate(size_t n_bits)
52 {
53     return xzalloc(bitmap_n_bytes(n_bits));
54 }
55
56 static inline void
57 bitmap_free(unsigned long *bitmap)
58 {
59     free(bitmap);
60 }
61
62 static inline bool
63 bitmap_is_set(const unsigned long *bitmap, size_t offset)
64 {
65     return (*bitmap_unit__(bitmap, offset) & bitmap_bit__(offset)) != 0;
66 }
67
68 static inline void
69 bitmap_set1(unsigned long *bitmap, size_t offset)
70 {
71     *bitmap_unit__(bitmap, offset) |= bitmap_bit__(offset);
72 }
73
74 static inline void
75 bitmap_set0(unsigned long *bitmap, size_t offset)
76 {
77     *bitmap_unit__(bitmap, offset) &= ~bitmap_bit__(offset);
78 }
79
80 static inline void
81 bitmap_set(unsigned long *bitmap, size_t offset, bool value)
82 {
83     if (value) {
84         bitmap_set1(bitmap, offset);
85     } else {
86         bitmap_set0(bitmap, offset);
87     }
88 }
89
90 void bitmap_set_multiple(unsigned long *, size_t start, size_t count,
91                          bool value);
92 bool bitmap_equal(const unsigned long *, const unsigned long *, size_t n);
93 size_t bitmap_scan(const unsigned long int *, size_t start, size_t end);
94
95 #define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \
96     for ((IDX) = bitmap_scan(BITMAP, 0, SIZE); (IDX) < (SIZE); \
97          (IDX) = bitmap_scan(BITMAP, (IDX) + 1, SIZE))
98
99 #endif /* bitmap.h */