1 /**************************************************************************
3 * Copyright 2009 VMware, Inc.
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 **************************************************************************/
30 * Generic bitmask implementation.
32 * @author Jose Fonseca <jfonseca@vmware.com>
36 #include "pipe/p_compiler.h"
37 #include "util/u_debug.h"
39 #include "util/u_memory.h"
40 #include "util/u_bitmask.h"
43 typedef uint32_t util_bitmask_word
;
46 #define UTIL_BITMASK_INITIAL_WORDS 16
47 #define UTIL_BITMASK_BITS_PER_BYTE 8
48 #define UTIL_BITMASK_BITS_PER_WORD (sizeof(util_bitmask_word) * UTIL_BITMASK_BITS_PER_BYTE)
53 util_bitmask_word
*words
;
55 /** Number of bits we can currently hold */
58 /** Number of consecutive bits set at the start of the bitmask */
64 util_bitmask_create(void)
66 struct util_bitmask
*bm
;
68 bm
= MALLOC_STRUCT(util_bitmask
);
72 bm
->words
= (util_bitmask_word
*)
73 CALLOC(UTIL_BITMASK_INITIAL_WORDS
, sizeof(util_bitmask_word
));
79 bm
->size
= UTIL_BITMASK_INITIAL_WORDS
* UTIL_BITMASK_BITS_PER_WORD
;
87 * Resize the bitmask if necessary
90 util_bitmask_resize(struct util_bitmask
*bm
,
91 unsigned minimum_index
)
93 const unsigned minimum_size
= minimum_index
+ 1;
95 util_bitmask_word
*new_words
;
97 /* Check integer overflow */
101 if (bm
->size
>= minimum_size
)
104 assert(bm
->size
% UTIL_BITMASK_BITS_PER_WORD
== 0);
106 while (new_size
< minimum_size
) {
108 /* Check integer overflow */
109 if (new_size
< bm
->size
)
113 assert(new_size
% UTIL_BITMASK_BITS_PER_WORD
== 0);
115 new_words
= (util_bitmask_word
*)
116 REALLOC((void *)bm
->words
,
117 bm
->size
/ UTIL_BITMASK_BITS_PER_BYTE
,
118 new_size
/ UTIL_BITMASK_BITS_PER_BYTE
);
122 memset(new_words
+ bm
->size
/UTIL_BITMASK_BITS_PER_WORD
,
124 (new_size
- bm
->size
)/UTIL_BITMASK_BITS_PER_BYTE
);
127 bm
->words
= new_words
;
134 * Check if we can increment the filled counter.
137 util_bitmask_filled_set(struct util_bitmask
*bm
,
140 assert(bm
->filled
<= bm
->size
);
141 assert(index
< bm
->size
);
143 if (index
== bm
->filled
) {
145 assert(bm
->filled
<= bm
->size
);
151 * Check if we need to decrement the filled counter.
154 util_bitmask_filled_unset(struct util_bitmask
*bm
,
157 assert(bm
->filled
<= bm
->size
);
158 assert(index
< bm
->size
);
160 if (index
< bm
->filled
)
166 util_bitmask_add(struct util_bitmask
*bm
)
170 util_bitmask_word mask
;
174 /* linear search for an empty index, starting at filled position */
175 word
= bm
->filled
/ UTIL_BITMASK_BITS_PER_WORD
;
176 bit
= bm
->filled
% UTIL_BITMASK_BITS_PER_WORD
;
178 while (word
< bm
->size
/ UTIL_BITMASK_BITS_PER_WORD
) {
179 while (bit
< UTIL_BITMASK_BITS_PER_WORD
) {
180 if (!(bm
->words
[word
] & mask
))
192 /* grow the bitmask if necessary */
193 if (!util_bitmask_resize(bm
, bm
->filled
))
194 return UTIL_BITMASK_INVALID_INDEX
;
196 assert(!(bm
->words
[word
] & mask
));
197 bm
->words
[word
] |= mask
;
204 util_bitmask_set(struct util_bitmask
*bm
,
209 util_bitmask_word mask
;
213 /* grow the bitmask if necessary */
214 if (!util_bitmask_resize(bm
, index
))
215 return UTIL_BITMASK_INVALID_INDEX
;
217 word
= index
/ UTIL_BITMASK_BITS_PER_WORD
;
218 bit
= index
% UTIL_BITMASK_BITS_PER_WORD
;
221 bm
->words
[word
] |= mask
;
223 util_bitmask_filled_set(bm
, index
);
230 util_bitmask_clear(struct util_bitmask
*bm
,
235 util_bitmask_word mask
;
239 if (index
>= bm
->size
)
242 word
= index
/ UTIL_BITMASK_BITS_PER_WORD
;
243 bit
= index
% UTIL_BITMASK_BITS_PER_WORD
;
246 bm
->words
[word
] &= ~mask
;
248 util_bitmask_filled_unset(bm
, index
);
253 util_bitmask_get(struct util_bitmask
*bm
,
256 const unsigned word
= index
/ UTIL_BITMASK_BITS_PER_WORD
;
257 const unsigned bit
= index
% UTIL_BITMASK_BITS_PER_WORD
;
258 const util_bitmask_word mask
= 1 << bit
;
262 if (index
< bm
->filled
) {
263 assert(bm
->words
[word
] & mask
);
267 if (index
>= bm
->size
)
270 if (bm
->words
[word
] & mask
) {
271 util_bitmask_filled_set(bm
, index
);
280 util_bitmask_get_next_index(struct util_bitmask
*bm
,
283 unsigned word
= index
/ UTIL_BITMASK_BITS_PER_WORD
;
284 unsigned bit
= index
% UTIL_BITMASK_BITS_PER_WORD
;
285 util_bitmask_word mask
= 1 << bit
;
287 if (index
< bm
->filled
) {
288 assert(bm
->words
[word
] & mask
);
292 if (index
>= bm
->size
) {
293 return UTIL_BITMASK_INVALID_INDEX
;
296 /* Do a linear search */
297 while (word
< bm
->size
/ UTIL_BITMASK_BITS_PER_WORD
) {
298 while (bit
< UTIL_BITMASK_BITS_PER_WORD
) {
299 if (bm
->words
[word
] & mask
) {
300 if (index
== bm
->filled
) {
302 assert(bm
->filled
<= bm
->size
);
315 return UTIL_BITMASK_INVALID_INDEX
;
320 util_bitmask_get_first_index(struct util_bitmask
*bm
)
322 return util_bitmask_get_next_index(bm
, 0);
327 util_bitmask_destroy(struct util_bitmask
*bm
)