1 /************************************************************************** 2 * 3 * Copyright 2009 VMware, Inc. 4 * All Rights Reserved. 5 * 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: 13 * 14 * The above copyright notice and this permission notice (including the 15 * next paragraph) shall be included in all copies or substantial portions 16 * of the Software. 17 * 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. 25 * 26 **************************************************************************/ 27 28 /** 29 * @file 30 * Generic bitmask implementation. 31 * 32 * @author Jose Fonseca <jfonseca (at) vmware.com> 33 */ 34 35 36 #include "pipe/p_compiler.h" 37 #include "util/u_debug.h" 38 39 #include "util/u_memory.h" 40 #include "util/u_bitmask.h" 41 42 43 typedef uint32_t util_bitmask_word; 44 45 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) 49 50 51 struct util_bitmask 52 { 53 util_bitmask_word *words; 54 55 /** Number of bits we can currently hold */ 56 unsigned size; 57 58 /** Number of consecutive bits set at the start of the bitmask */ 59 unsigned filled; 60 }; 61 62 63 struct util_bitmask * 64 util_bitmask_create(void) 65 { 66 struct util_bitmask *bm; 67 68 bm = MALLOC_STRUCT(util_bitmask); 69 if (!bm) 70 return NULL; 71 72 bm->words = (util_bitmask_word *)CALLOC(UTIL_BITMASK_INITIAL_WORDS, sizeof(util_bitmask_word)); 73 if(!bm->words) { 74 FREE(bm); 75 return NULL; 76 } 77 78 bm->size = UTIL_BITMASK_INITIAL_WORDS * UTIL_BITMASK_BITS_PER_WORD; 79 bm->filled = 0; 80 81 return bm; 82 } 83 84 85 /** 86 * Resize the bitmask if necessary 87 */ 88 static inline boolean 89 util_bitmask_resize(struct util_bitmask *bm, 90 unsigned minimum_index) 91 { 92 unsigned minimum_size = minimum_index + 1; 93 unsigned new_size; 94 util_bitmask_word *new_words; 95 96 /* Check integer overflow */ 97 if(!minimum_size) 98 return FALSE; 99 100 if(bm->size >= minimum_size) 101 return TRUE; 102 103 assert(bm->size % UTIL_BITMASK_BITS_PER_WORD == 0); 104 new_size = bm->size; 105 while(new_size < minimum_size) { 106 new_size *= 2; 107 /* Check integer overflow */ 108 if(new_size < bm->size) 109 return FALSE; 110 } 111 assert(new_size); 112 assert(new_size % UTIL_BITMASK_BITS_PER_WORD == 0); 113 114 new_words = (util_bitmask_word *)REALLOC((void *)bm->words, 115 bm->size / UTIL_BITMASK_BITS_PER_BYTE, 116 new_size / UTIL_BITMASK_BITS_PER_BYTE); 117 if (!new_words) 118 return FALSE; 119 120 memset(new_words + bm->size/UTIL_BITMASK_BITS_PER_WORD, 121 0, 122 (new_size - bm->size)/UTIL_BITMASK_BITS_PER_BYTE); 123 124 bm->size = new_size; 125 bm->words = new_words; 126 127 return TRUE; 128 } 129 130 131 /** 132 * Lazily update the filled. 133 */ 134 static inline void 135 util_bitmask_filled_set(struct util_bitmask *bm, 136 unsigned index) 137 { 138 assert(bm->filled <= bm->size); 139 assert(index < bm->size); 140 141 if(index == bm->filled) { 142 ++bm->filled; 143 assert(bm->filled <= bm->size); 144 } 145 } 146 147 static inline void 148 util_bitmask_filled_unset(struct util_bitmask *bm, 149 unsigned index) 150 { 151 assert(bm->filled <= bm->size); 152 assert(index < bm->size); 153 154 if(index < bm->filled) 155 bm->filled = index; 156 } 157 158 159 unsigned 160 util_bitmask_add(struct util_bitmask *bm) 161 { 162 unsigned word; 163 unsigned bit; 164 util_bitmask_word mask; 165 166 assert(bm); 167 168 /* linear search for an empty index */ 169 word = bm->filled / UTIL_BITMASK_BITS_PER_WORD; 170 bit = bm->filled % UTIL_BITMASK_BITS_PER_WORD; 171 mask = 1 << bit; 172 while(word < bm->size / UTIL_BITMASK_BITS_PER_WORD) { 173 while(bit < UTIL_BITMASK_BITS_PER_WORD) { 174 if(!(bm->words[word] & mask)) 175 goto found; 176 ++bm->filled; 177 ++bit; 178 mask <<= 1; 179 } 180 ++word; 181 bit = 0; 182 mask = 1; 183 } 184 found: 185 186 /* grow the bitmask if necessary */ 187 if(!util_bitmask_resize(bm, bm->filled)) 188 return UTIL_BITMASK_INVALID_INDEX; 189 190 assert(!(bm->words[word] & mask)); 191 bm->words[word] |= mask; 192 193 return bm->filled++; 194 } 195 196 197 unsigned 198 util_bitmask_set(struct util_bitmask *bm, 199 unsigned index) 200 { 201 unsigned word; 202 unsigned bit; 203 util_bitmask_word mask; 204 205 assert(bm); 206 207 /* grow the bitmask if necessary */ 208 if(!util_bitmask_resize(bm, index)) 209 return UTIL_BITMASK_INVALID_INDEX; 210 211 word = index / UTIL_BITMASK_BITS_PER_WORD; 212 bit = index % UTIL_BITMASK_BITS_PER_WORD; 213 mask = 1 << bit; 214 215 bm->words[word] |= mask; 216 217 util_bitmask_filled_set(bm, index); 218 219 return index; 220 } 221 222 223 void 224 util_bitmask_clear(struct util_bitmask *bm, 225 unsigned index) 226 { 227 unsigned word; 228 unsigned bit; 229 util_bitmask_word mask; 230 231 assert(bm); 232 233 if(index >= bm->size) 234 return; 235 236 word = index / UTIL_BITMASK_BITS_PER_WORD; 237 bit = index % UTIL_BITMASK_BITS_PER_WORD; 238 mask = 1 << bit; 239 240 bm->words[word] &= ~mask; 241 242 util_bitmask_filled_unset(bm, index); 243 } 244 245 246 boolean 247 util_bitmask_get(struct util_bitmask *bm, 248 unsigned index) 249 { 250 unsigned word = index / UTIL_BITMASK_BITS_PER_WORD; 251 unsigned bit = index % UTIL_BITMASK_BITS_PER_WORD; 252 util_bitmask_word mask = 1 << bit; 253 254 assert(bm); 255 256 if(index < bm->filled) { 257 assert(bm->words[word] & mask); 258 return TRUE; 259 } 260 261 if(index >= bm->size) 262 return FALSE; 263 264 if(bm->words[word] & mask) { 265 util_bitmask_filled_set(bm, index); 266 return TRUE; 267 } 268 else 269 return FALSE; 270 } 271 272 273 unsigned 274 util_bitmask_get_next_index(struct util_bitmask *bm, 275 unsigned index) 276 { 277 unsigned word = index / UTIL_BITMASK_BITS_PER_WORD; 278 unsigned bit = index % UTIL_BITMASK_BITS_PER_WORD; 279 util_bitmask_word mask = 1 << bit; 280 281 if(index < bm->filled) { 282 assert(bm->words[word] & mask); 283 return index; 284 } 285 286 if(index >= bm->size) { 287 return UTIL_BITMASK_INVALID_INDEX; 288 } 289 290 /* Do a linear search */ 291 while(word < bm->size / UTIL_BITMASK_BITS_PER_WORD) { 292 while(bit < UTIL_BITMASK_BITS_PER_WORD) { 293 if(bm->words[word] & mask) { 294 if(index == bm->filled) { 295 ++bm->filled; 296 assert(bm->filled <= bm->size); 297 } 298 return index; 299 } 300 ++index; 301 ++bit; 302 mask <<= 1; 303 } 304 ++word; 305 bit = 0; 306 mask = 1; 307 } 308 309 return UTIL_BITMASK_INVALID_INDEX; 310 } 311 312 313 unsigned 314 util_bitmask_get_first_index(struct util_bitmask *bm) 315 { 316 return util_bitmask_get_next_index(bm, 0); 317 } 318 319 320 void 321 util_bitmask_destroy(struct util_bitmask *bm) 322 { 323 if (bm) { 324 FREE(bm->words); 325 FREE(bm); 326 } 327 } 328 329
