Changeset 3a0a4d8 in mainline for kernel/generic/src/adt/bitmap.c
- Timestamp:
- 2013-09-12T07:54:05Z (11 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 95027b5
- Parents:
- 47f5a77 (diff), 64f3d3b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
r47f5a77 r3a0a4d8 35 35 * 36 36 * This file implements bitmap ADT and provides functions for 37 * setting and clearing ranges of bits. 37 * setting and clearing ranges of bits and for finding ranges 38 * of unset bits. 39 * 40 * The bitmap ADT can optionally implement a two-level hierarchy 41 * for faster range searches. The second level bitmap (of blocks) 42 * is not precise, but conservative. This means that if the block 43 * bit is set, it guarantees that all bits in the block are set. 44 * But if the block bit is unset, nothing can be said about the 45 * bits in the block. 46 * 38 47 */ 39 48 … … 44 53 #include <macros.h> 45 54 46 #define ALL_ONES 0xff 47 #define ALL_ZEROES 0x00 55 #define ALL_ONES 0xff 56 #define ALL_ZEROES 0x00 57 58 /** Compute the size of a bitmap 59 * 60 * Compute the size of a bitmap that can store given number 61 * of elements. 62 * 63 * @param elements Number of elements to store. 64 * 65 * @return Size of the bitmap (in units of BITMAP_ELEMENT bits). 66 * 67 */ 68 static size_t bitmap_bytes(size_t elements) 69 { 70 size_t bytes = elements / BITMAP_ELEMENT; 71 72 if ((elements % BITMAP_ELEMENT) != 0) 73 bytes++; 74 75 return bytes; 76 } 77 78 /** Compute the number of 2nd level blocks 79 * 80 * Compute the number of 2nd level blocks for a given number 81 * of elements. 82 * 83 * @param elements Number of elements. 84 * @param block_size Number of elements in one block. 85 * 86 * @return Number of 2nd level blocks. 87 * @return Zero if block_size is zero. 88 * 89 */ 90 static size_t bitmap_blocks(size_t elements, size_t block_size) 91 { 92 if (block_size == 0) 93 return 0; 94 95 size_t blocks = elements / block_size; 96 97 if ((elements % block_size) != 0) 98 blocks++; 99 100 return blocks; 101 } 102 103 /** Unchecked version of bitmap_get() 104 * 105 * This version of bitmap_get() does not do any boundary checks. 106 * 107 * @param bitmap Bitmap to access. 108 * @param element Element to access. 109 * 110 * @return Bit value of the element in the bitmap. 111 * 112 */ 113 static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element) 114 { 115 return !!((bitmap->bits)[element / BITMAP_ELEMENT] & 116 (1 << (element & BITMAP_REMAINER))); 117 } 118 119 /** Get bitmap size 120 * 121 * Return the size (in bytes) required for the bitmap. 122 * 123 * @param elements Number bits stored in bitmap. 124 * @param block_size Block size of the 2nd level bitmap. 125 * If set to zero, no 2nd level is used. 126 * 127 * @return Size (in bytes) required for the bitmap. 128 * 129 */ 130 size_t bitmap_size(size_t elements, size_t block_size) 131 { 132 size_t blocks = bitmap_blocks(elements, block_size); 133 134 return (bitmap_bytes(elements) + bitmap_bytes(blocks)); 135 } 48 136 49 137 /** Initialize bitmap. … … 51 139 * No portion of the bitmap is set or cleared by this function. 52 140 * 53 * @param bitmap Bitmap structure. 54 * @param map Address of the memory used to hold the map. 55 * @param bits Number of bits stored in bitmap. 56 */ 57 void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits) 58 { 59 bitmap->map = map; 60 bitmap->bits = bits; 61 } 62 63 /** Set range of bits. 64 * 65 * @param bitmap Bitmap structure. 66 * @param start Starting bit. 67 * @param bits Number of bits to set. 68 */ 69 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits) 70 { 71 size_t i = 0; 72 size_t aligned_start; 73 size_t lub; /* leading unaligned bits */ 74 size_t amb; /* aligned middle bits */ 75 size_t tab; /* trailing aligned bits */ 76 77 ASSERT(start + bits <= bitmap->bits); 78 79 aligned_start = ALIGN_UP(start, 8); 80 lub = min(aligned_start - start, bits); 81 amb = bits > lub ? bits - lub : 0; 82 tab = amb % 8; 83 84 if (!bits) 141 * @param bitmap Bitmap structure. 142 * @param elements Number of bits stored in bitmap. 143 * @param block_size Block size of the 2nd level bitmap. 144 * If set to zero, no 2nd level is used. 145 * @param data Address of the memory used to hold the map. 146 * The optional 2nd level bitmap follows the 1st 147 * level bitmap. 148 * 149 */ 150 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, 151 void *data) 152 { 153 bitmap->elements = elements; 154 bitmap->bits = (uint8_t *) data; 155 156 if (block_size > 0) { 157 bitmap->block_size = block_size; 158 bitmap->blocks = bitmap->bits + 159 bitmap_size(elements, 0); 160 } else { 161 bitmap->block_size = 0; 162 bitmap->blocks = NULL; 163 } 164 } 165 166 static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count) 167 { 168 if (count == 0) 85 169 return; 86 87 if (start + bits < aligned_start) { 170 171 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 172 173 /* Leading unaligned bits */ 174 size_t lub = min(aligned_start - start, count); 175 176 /* Aligned middle bits */ 177 size_t amb = (count > lub) ? (count - lub) : 0; 178 179 /* Trailing aligned bits */ 180 size_t tab = amb % BITMAP_ELEMENT; 181 182 if (start + count < aligned_start) { 88 183 /* Set bits in the middle of byte. */ 89 bitmap->map[start / 8] |= ((1 << lub) - 1) << (start & 7); 184 bits[start / BITMAP_ELEMENT] |= 185 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 90 186 return; 91 187 } … … 93 189 if (lub) { 94 190 /* Make sure to set any leading unaligned bits. */ 95 bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1); 96 } 97 for (i = 0; i < amb / 8; i++) { 191 bits[start / BITMAP_ELEMENT] |= 192 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 193 } 194 195 size_t i; 196 197 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 98 198 /* The middle bits can be set byte by byte. */ 99 bitmap->map[aligned_start / 8 + i] = ALL_ONES; 100 } 199 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES; 200 } 201 101 202 if (tab) { 102 203 /* Make sure to set any trailing aligned bits. */ 103 bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1; 104 } 105 106 } 107 108 /** Clear range of bits. 109 * 110 * @param bitmap Bitmap structure. 111 * @param start Starting bit. 112 * @param bits Number of bits to clear. 113 */ 114 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits) 115 { 116 size_t i = 0; 117 size_t aligned_start; 118 size_t lub; /* leading unaligned bits */ 119 size_t amb; /* aligned middle bits */ 120 size_t tab; /* trailing aligned bits */ 121 122 ASSERT(start + bits <= bitmap->bits); 123 124 aligned_start = ALIGN_UP(start, 8); 125 lub = min(aligned_start - start, bits); 126 amb = bits > lub ? bits - lub : 0; 127 tab = amb % 8; 128 129 if (!bits) 204 bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1; 205 } 206 } 207 208 /** Set range of bits. 209 * 210 * @param bitmap Bitmap structure. 211 * @param start Starting bit. 212 * @param count Number of bits to set. 213 * 214 */ 215 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count) 216 { 217 ASSERT(start + count <= bitmap->elements); 218 219 bitmap_set_range_internal(bitmap->bits, start, count); 220 221 if (bitmap->block_size > 0) { 222 size_t aligned_start = ALIGN_UP(start, bitmap->block_size); 223 224 /* Leading unaligned bits */ 225 size_t lub = min(aligned_start - start, count); 226 227 /* Aligned middle bits */ 228 size_t amb = (count > lub) ? (count - lub) : 0; 229 230 size_t aligned_size = amb / bitmap->block_size; 231 232 bitmap_set_range_internal(bitmap->blocks, aligned_start, 233 aligned_size); 234 } 235 } 236 237 static void bitmap_clear_range_internal(uint8_t *bits, size_t start, 238 size_t count) 239 { 240 if (count == 0) 130 241 return; 131 132 if (start + bits < aligned_start) { 242 243 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 244 245 /* Leading unaligned bits */ 246 size_t lub = min(aligned_start - start, count); 247 248 /* Aligned middle bits */ 249 size_t amb = (count > lub) ? (count - lub) : 0; 250 251 /* Trailing aligned bits */ 252 size_t tab = amb % BITMAP_ELEMENT; 253 254 if (start + count < aligned_start) { 133 255 /* Set bits in the middle of byte */ 134 bitmap->map[start / 8] &= ~(((1 << lub) - 1) << (start & 7)); 256 bits[start / BITMAP_ELEMENT] &= 257 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); 135 258 return; 136 259 } 137 260 138 261 if (lub) { 139 262 /* Make sure to clear any leading unaligned bits. */ 140 bitmap->map[start / 8] &= (1 << (8 - lub)) - 1; 141 } 142 for (i = 0; i < amb / 8; i++) { 263 bits[start / BITMAP_ELEMENT] &= 264 (1 << (BITMAP_ELEMENT - lub)) - 1; 265 } 266 267 size_t i; 268 269 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 143 270 /* The middle bits can be cleared byte by byte. */ 144 bitmap->map[aligned_start / 8 + i] = ALL_ZEROES; 145 } 271 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES; 272 } 273 146 274 if (tab) { 147 275 /* Make sure to clear any trailing aligned bits. */ 148 bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1); 149 } 150 276 bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1); 277 } 278 } 279 280 /** Clear range of bits. 281 * 282 * @param bitmap Bitmap structure. 283 * @param start Starting bit. 284 * @param count Number of bits to clear. 285 * 286 */ 287 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count) 288 { 289 ASSERT(start + count <= bitmap->elements); 290 291 bitmap_clear_range_internal(bitmap->bits, start, count); 292 293 if (bitmap->block_size > 0) { 294 size_t aligned_start = start / bitmap->block_size; 295 296 size_t aligned_end = (start + count) / bitmap->block_size; 297 298 if (((start + count) % bitmap->block_size) != 0) 299 aligned_end++; 300 301 size_t aligned_size = aligned_end - aligned_start; 302 303 bitmap_clear_range_internal(bitmap->blocks, aligned_start, 304 aligned_size); 305 } 151 306 } 152 307 153 308 /** Copy portion of one bitmap into another bitmap. 154 309 * 155 * @param dst Destination bitmap. 156 * @param src Source bitmap. 157 * @param bits Number of bits to copy. 158 */ 159 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits) 160 { 310 * @param dst Destination bitmap. 311 * @param src Source bitmap. 312 * @param count Number of bits to copy. 313 * 314 */ 315 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count) 316 { 317 ASSERT(count <= dst->elements); 318 ASSERT(count <= src->elements); 319 161 320 size_t i; 162 321 163 ASSERT(bits <= dst->bits); 164 ASSERT(bits <= src->bits); 165 166 for (i = 0; i < bits / 8; i++) 167 dst->map[i] = src->map[i]; 168 169 if (bits % 8) { 170 bitmap_clear_range(dst, i * 8, bits % 8); 171 dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1); 172 } 322 for (i = 0; i < count / BITMAP_ELEMENT; i++) 323 dst->bits[i] = src->bits[i]; 324 325 if (count % BITMAP_ELEMENT) { 326 bitmap_clear_range(dst, i * BITMAP_ELEMENT, 327 count % BITMAP_ELEMENT); 328 dst->bits[i] |= src->bits[i] & 329 ((1 << (count % BITMAP_ELEMENT)) - 1); 330 } 331 } 332 333 static int constraint_satisfy(size_t index, size_t base, size_t constraint) 334 { 335 return (((base + index) & constraint) == 0); 336 } 337 338 /** Find a continuous zero bit range 339 * 340 * Find a continuous zero bit range in the bitmap. The address 341 * computed as the sum of the index of the first zero bit and 342 * the base argument needs to be compliant with the constraint 343 * (those bits that are set in the constraint cannot be set in 344 * the address). 345 * 346 * If the index argument is non-NULL, the continuous zero range 347 * is set and the index of the first bit is stored to index. 348 * Otherwise the bitmap stays untouched. 349 * 350 * @param bitmap Bitmap structure. 351 * @param count Number of continuous zero bits to find. 352 * @param base Address of the first bit in the bitmap. 353 * @param constraint Constraint for the address of the first zero bit. 354 * @param index Place to store the index of the first zero 355 * bit. Can be NULL (in which case the bitmap 356 * is not modified). 357 * 358 * @return Non-zero if a continuous range of zero bits satisfying 359 * the constraint has been found. 360 * @return Zero otherwise. 361 * 362 */ 363 int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base, 364 size_t constraint, size_t *index) 365 { 366 if (count == 0) 367 return false; 368 369 size_t bytes = bitmap_bytes(bitmap->elements); 370 371 for (size_t byte = 0; byte < bytes; byte++) { 372 /* Skip if the current byte has all bits set */ 373 if (bitmap->bits[byte] == ALL_ONES) 374 continue; 375 376 size_t byte_bit = byte * BITMAP_ELEMENT; 377 378 for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) { 379 size_t i = byte_bit + bit; 380 381 if (i >= bitmap->elements) 382 break; 383 384 if (!constraint_satisfy(i, base, constraint)) 385 continue; 386 387 if (!bitmap_get_fast(bitmap, i)) { 388 bool continuous = true; 389 390 for (size_t j = 1; j < count; j++) { 391 if ((i + j >= bitmap->elements) || 392 (bitmap_get_fast(bitmap, i + j))) { 393 continuous = false; 394 break; 395 } 396 } 397 398 if (continuous) { 399 if (index != NULL) { 400 bitmap_set_range(bitmap, i, count); 401 *index = i; 402 } 403 404 return true; 405 } 406 } 407 } 408 } 409 410 return false; 173 411 } 174 412
Note:
See TracChangeset
for help on using the changeset viewer.