]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
e0edde6f | 2 | * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
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 | ||
17d18afb BP |
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 | ||
064af421 BP |
50 | static inline unsigned long * |
51 | bitmap_allocate(size_t n_bits) | |
52 | { | |
17d18afb | 53 | return xzalloc(bitmap_n_bytes(n_bits)); |
064af421 BP |
54 | } |
55 | ||
77d895d6 BP |
56 | unsigned long *bitmap_allocate1(size_t n_bits); |
57 | ||
2a4ae635 BP |
58 | static inline unsigned long * |
59 | bitmap_clone(const unsigned long *bitmap, size_t n_bits) | |
60 | { | |
61 | return xmemdup(bitmap, bitmap_n_bytes(n_bits)); | |
62 | } | |
63 | ||
064af421 BP |
64 | static inline void |
65 | bitmap_free(unsigned long *bitmap) | |
66 | { | |
67 | free(bitmap); | |
68 | } | |
69 | ||
70 | static inline bool | |
71 | bitmap_is_set(const unsigned long *bitmap, size_t offset) | |
72 | { | |
73 | return (*bitmap_unit__(bitmap, offset) & bitmap_bit__(offset)) != 0; | |
74 | } | |
75 | ||
76 | static inline void | |
77 | bitmap_set1(unsigned long *bitmap, size_t offset) | |
78 | { | |
79 | *bitmap_unit__(bitmap, offset) |= bitmap_bit__(offset); | |
80 | } | |
81 | ||
82 | static inline void | |
83 | bitmap_set0(unsigned long *bitmap, size_t offset) | |
84 | { | |
85 | *bitmap_unit__(bitmap, offset) &= ~bitmap_bit__(offset); | |
86 | } | |
87 | ||
88 | static inline void | |
89 | bitmap_set(unsigned long *bitmap, size_t offset, bool value) | |
90 | { | |
91 | if (value) { | |
92 | bitmap_set1(bitmap, offset); | |
93 | } else { | |
94 | bitmap_set0(bitmap, offset); | |
95 | } | |
96 | } | |
97 | ||
98 | void bitmap_set_multiple(unsigned long *, size_t start, size_t count, | |
99 | bool value); | |
100 | bool bitmap_equal(const unsigned long *, const unsigned long *, size_t n); | |
7cc48aed BP |
101 | size_t bitmap_scan(const unsigned long int *, size_t start, size_t end); |
102 | ||
103 | #define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \ | |
104 | for ((IDX) = bitmap_scan(BITMAP, 0, SIZE); (IDX) < (SIZE); \ | |
105 | (IDX) = bitmap_scan(BITMAP, (IDX) + 1, SIZE)) | |
064af421 BP |
106 | |
107 | #endif /* bitmap.h */ |