Changeset c5396c1 in mainline for kernel/generic/src/adt/bitmap.c
- Timestamp:
- 2013-09-12T10:27:17Z (11 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 6e75f2d
- Parents:
- 4a5f2b0
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
r4a5f2b0 rc5396c1 37 37 * setting and clearing ranges of bits and for finding ranges 38 38 * of unset bits. 39 *40 * The bitmap ADT can optionally implement a two-level hierarchy41 * for faster range searches. The second level bitmap (of blocks)42 * is not precise, but conservative. This means that if the block43 * 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 the45 * bits in the block.46 *47 39 */ 48 40 … … 56 48 #define ALL_ZEROES 0x00 57 49 58 /** Compute the size of a bitmap59 *60 * Compute the size of a bitmap that can store given number61 * 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 blocks79 *80 * Compute the number of 2nd level blocks for a given number81 * 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 50 /** Unchecked version of bitmap_get() 104 51 * … … 113 60 static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element) 114 61 { 115 return !!((bitmap->bits)[element / BITMAP_ELEMENT] & 116 (1 << (element & BITMAP_REMAINER))); 62 size_t byte = element / BITMAP_ELEMENT; 63 uint8_t mask = 1 << (element & BITMAP_REMAINER); 64 65 return !!((bitmap->bits)[byte] & mask); 117 66 } 118 67 … … 122 71 * 123 72 * @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 73 * 127 74 * @return Size (in bytes) required for the bitmap. 128 75 * 129 76 */ 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)); 77 size_t bitmap_size(size_t elements) 78 { 79 size_t size = elements / BITMAP_ELEMENT; 80 81 if ((elements % BITMAP_ELEMENT) != 0) 82 size++; 83 84 return size; 135 85 } 136 86 … … 141 91 * @param bitmap Bitmap structure. 142 92 * @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 93 * @param data Address of the memory used to hold the map. 146 94 * The optional 2nd level bitmap follows the 1st … … 148 96 * 149 97 */ 150 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, 151 void *data) 98 void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data) 152 99 { 153 100 bitmap->elements = elements; 154 101 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)169 return;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) {183 /* Set bits in the middle of byte. */184 bits[start / BITMAP_ELEMENT] |=185 ((1 << lub) - 1) << (start & BITMAP_REMAINER);186 return;187 }188 189 if (lub) {190 /* Make sure to set any leading unaligned bits. */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++) {198 /* The middle bits can be set byte by byte. */199 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES;200 }201 202 if (tab) {203 /* Make sure to set any trailing aligned bits. */204 bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1;205 }206 102 } 207 103 … … 217 113 ASSERT(start + count <= bitmap->elements); 218 114 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 115 if (count == 0) 241 116 return; … … 253 128 254 129 if (start + count < aligned_start) { 255 /* Set bits in the middle of byte */256 bit s[start / BITMAP_ELEMENT] &=257 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));130 /* Set bits in the middle of byte. */ 131 bitmap->bits[start / BITMAP_ELEMENT] |= 132 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 258 133 return; 259 134 } 260 135 261 136 if (lub) { 262 /* Make sure to clearany leading unaligned bits. */263 bit s[start / BITMAP_ELEMENT] &=264 (1 << (BITMAP_ELEMENT - lub)) - 1;137 /* Make sure to set any leading unaligned bits. */ 138 bitmap->bits[start / BITMAP_ELEMENT] |= 139 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 265 140 } 266 141 … … 268 143 269 144 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 270 /* The middle bits can be cleared byte by byte. */ 271 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES; 145 /* The middle bits can be set byte by byte. */ 146 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 147 ALL_ONES; 272 148 } 273 149 274 150 if (tab) { 275 /* Make sure to clear any trailing aligned bits. */ 276 bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1); 151 /* Make sure to set any trailing aligned bits. */ 152 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |= 153 (1 << tab) - 1; 277 154 } 278 155 } … … 289 166 ASSERT(start + count <= bitmap->elements); 290 167 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); 168 if (count == 0) 169 return; 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) { 183 /* Set bits in the middle of byte */ 184 bitmap->bits[start / BITMAP_ELEMENT] &= 185 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); 186 return; 187 } 188 189 if (lub) { 190 /* Make sure to clear any leading unaligned bits. */ 191 bitmap->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++) { 198 /* The middle bits can be cleared byte by byte. */ 199 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 200 ALL_ZEROES; 201 } 202 203 if (tab) { 204 /* Make sure to clear any trailing aligned bits. */ 205 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &= 206 ~((1 << tab) - 1); 305 207 } 306 208 } … … 367 269 return false; 368 270 369 size_t bytes = bitmap_ bytes(bitmap->elements);271 size_t bytes = bitmap_size(bitmap->elements); 370 272 371 273 for (size_t byte = 0; byte < bytes; byte++) {
Note:
See TracChangeset
for help on using the changeset viewer.