Changes in kernel/generic/src/adt/bitmap.c [f72906c:9d58539] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/adt/bitmap.c (modified) (4 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
rf72906c r9d58539 35 35 * 36 36 * This file implements bitmap ADT and provides functions for 37 * setting and clearing ranges of bits and for finding ranges 38 * of unset bits. 37 * setting and clearing ranges of bits. 39 38 */ 40 39 … … 45 44 #include <macros.h> 46 45 47 #define ALL_ONES 0xff 48 #define ALL_ZEROES 0x00 49 50 /** Unchecked version of bitmap_get() 51 * 52 * This version of bitmap_get() does not do any boundary checks. 53 * 54 * @param bitmap Bitmap to access. 55 * @param element Element to access. 56 * 57 * @return Bit value of the element in the bitmap. 58 * 59 */ 60 static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element) 61 { 62 size_t byte = element / BITMAP_ELEMENT; 63 uint8_t mask = 1 << (element & BITMAP_REMAINER); 64 65 return !!((bitmap->bits)[byte] & mask); 66 } 67 68 /** Get bitmap size 69 * 70 * Return the size (in bytes) required for the bitmap. 71 * 72 * @param elements Number bits stored in bitmap. 73 * 74 * @return Size (in bytes) required for the bitmap. 75 * 76 */ 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; 85 } 46 #define ALL_ONES 0xff 47 #define ALL_ZEROES 0x00 86 48 87 49 /** Initialize bitmap. … … 89 51 * No portion of the bitmap is set or cleared by this function. 90 52 * 91 * @param bitmap Bitmap structure. 92 * @param elements Number of bits stored in bitmap. 93 * @param data Address of the memory used to hold the map. 94 * The optional 2nd level bitmap follows the 1st 95 * level bitmap. 96 * 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. 97 56 */ 98 void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data)57 void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits) 99 58 { 100 bitmap->elements = elements; 101 bitmap->bits = (uint8_t *) data; 102 bitmap->next_fit = 0; 59 bitmap->map = map; 60 bitmap->bits = bits; 103 61 } 104 62 105 63 /** Set range of bits. 106 64 * 107 * @param bitmap Bitmap structure. 108 * @param start Starting bit. 109 * @param count Number of bits to set. 110 * 65 * @param bitmap Bitmap structure. 66 * @param start Starting bit. 67 * @param bits Number of bits to set. 111 68 */ 112 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)69 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits) 113 70 { 114 ASSERT(start + count <= bitmap->elements); 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 */ 115 76 116 if (count == 0) 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) 117 85 return; 118 119 size_t start_byte = start / BITMAP_ELEMENT; 120 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 121 122 /* Leading unaligned bits */ 123 size_t lub = min(aligned_start - start, count); 124 125 /* Aligned middle bits */ 126 size_t amb = (count > lub) ? (count - lub) : 0; 127 128 /* Trailing aligned bits */ 129 size_t tab = amb % BITMAP_ELEMENT; 130 131 if (start + count < aligned_start) { 86 87 if (start + bits < aligned_start) { 132 88 /* Set bits in the middle of byte. */ 133 bitmap->bits[start_byte] |= 134 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 89 bitmap->map[start / 8] |= ((1 << lub) - 1) << (start & 7); 135 90 return; 136 91 } … … 138 93 if (lub) { 139 94 /* Make sure to set any leading unaligned bits. */ 140 bitmap->bits[start_byte] |= 141 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 95 bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1); 96 } 97 for (i = 0; i < amb / 8; i++) { 98 /* The middle bits can be set byte by byte. */ 99 bitmap->map[aligned_start / 8 + i] = ALL_ONES; 100 } 101 if (tab) { 102 /* Make sure to set any trailing aligned bits. */ 103 bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1; 142 104 } 143 105 144 size_t i;145 146 for (i = 0; i < amb / BITMAP_ELEMENT; i++) {147 /* The middle bits can be set byte by byte. */148 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] =149 ALL_ONES;150 }151 152 if (tab) {153 /* Make sure to set any trailing aligned bits. */154 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |=155 (1 << tab) - 1;156 }157 106 } 158 107 159 108 /** Clear range of bits. 160 109 * 161 * @param bitmap Bitmap structure. 162 * @param start Starting bit. 163 * @param count Number of bits to clear. 164 * 110 * @param bitmap Bitmap structure. 111 * @param start Starting bit. 112 * @param bits Number of bits to clear. 165 113 */ 166 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)114 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits) 167 115 { 168 ASSERT(start + count <= bitmap->elements); 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 */ 169 121 170 if (count == 0) 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) 171 130 return; 172 173 size_t start_byte = start / BITMAP_ELEMENT; 174 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 175 176 /* Leading unaligned bits */ 177 size_t lub = min(aligned_start - start, count); 178 179 /* Aligned middle bits */ 180 size_t amb = (count > lub) ? (count - lub) : 0; 181 182 /* Trailing aligned bits */ 183 size_t tab = amb % BITMAP_ELEMENT; 184 185 if (start + count < aligned_start) { 131 132 if (start + bits < aligned_start) { 186 133 /* Set bits in the middle of byte */ 187 bitmap->bits[start_byte] &= 188 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); 134 bitmap->map[start / 8] &= ~(((1 << lub) - 1) << (start & 7)); 189 135 return; 190 136 } 191 137 192 138 if (lub) { 193 139 /* Make sure to clear any leading unaligned bits. */ 194 bitmap->bits[start_byte] &= 195 (1 << (BITMAP_ELEMENT - lub)) - 1; 140 bitmap->map[start / 8] &= (1 << (8 - lub)) - 1; 196 141 } 197 198 size_t i; 199 200 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 142 for (i = 0; i < amb / 8; i++) { 201 143 /* The middle bits can be cleared byte by byte. */ 202 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 203 ALL_ZEROES; 144 bitmap->map[aligned_start / 8 + i] = ALL_ZEROES; 204 145 } 205 206 146 if (tab) { 207 147 /* Make sure to clear any trailing aligned bits. */ 208 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &= 209 ~((1 << tab) - 1); 148 bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1); 210 149 } 211 212 bitmap->next_fit = start_byte; 150 213 151 } 214 152 215 153 /** Copy portion of one bitmap into another bitmap. 216 154 * 217 * @param dst Destination bitmap. 218 * @param src Source bitmap. 219 * @param count Number of bits to copy. 220 * 155 * @param dst Destination bitmap. 156 * @param src Source bitmap. 157 * @param bits Number of bits to copy. 221 158 */ 222 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count)159 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits) 223 160 { 224 ASSERT(count <= dst->elements);225 ASSERT(count <= src->elements);226 227 161 size_t i; 228 162 229 for (i = 0; i < count / BITMAP_ELEMENT; i++)230 dst->bits[i] = src->bits[i];163 ASSERT(bits <= dst->bits); 164 ASSERT(bits <= src->bits); 231 165 232 if (count % BITMAP_ELEMENT) { 233 bitmap_clear_range(dst, i * BITMAP_ELEMENT, 234 count % BITMAP_ELEMENT); 235 dst->bits[i] |= src->bits[i] & 236 ((1 << (count % BITMAP_ELEMENT)) - 1); 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); 237 172 } 238 }239 240 static int constraint_satisfy(size_t index, size_t base, size_t constraint)241 {242 return (((base + index) & constraint) == 0);243 }244 245 /** Find a continuous zero bit range246 *247 * Find a continuous zero bit range in the bitmap. The address248 * computed as the sum of the index of the first zero bit and249 * the base argument needs to be compliant with the constraint250 * (those bits that are set in the constraint cannot be set in251 * the address).252 *253 * If the index argument is non-NULL, the continuous zero range254 * is set and the index of the first bit is stored to index.255 * Otherwise the bitmap stays untouched.256 *257 * @param bitmap Bitmap structure.258 * @param count Number of continuous zero bits to find.259 * @param base Address of the first bit in the bitmap.260 * @param prefered Prefered address to start searching from.261 * @param constraint Constraint for the address of the first zero bit.262 * @param index Place to store the index of the first zero263 * bit. Can be NULL (in which case the bitmap264 * is not modified).265 *266 * @return Non-zero if a continuous range of zero bits satisfying267 * the constraint has been found.268 * @return Zero otherwise.269 *270 */271 int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base,272 size_t prefered, size_t constraint, size_t *index)273 {274 if (count == 0)275 return false;276 277 size_t size = bitmap_size(bitmap->elements);278 size_t next_fit = bitmap->next_fit;279 280 /*281 * Adjust the next-fit value according to the address282 * the caller prefers to start the search at.283 */284 if ((prefered > base) && (prefered < base + bitmap->elements)) {285 size_t prefered_fit = (prefered - base) / BITMAP_ELEMENT;286 287 if (prefered_fit > next_fit)288 next_fit = prefered_fit;289 }290 291 for (size_t pos = 0; pos < size; pos++) {292 size_t byte = (next_fit + pos) % size;293 294 /* Skip if the current byte has all bits set */295 if (bitmap->bits[byte] == ALL_ONES)296 continue;297 298 size_t byte_bit = byte * BITMAP_ELEMENT;299 300 for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) {301 size_t i = byte_bit + bit;302 303 if (i >= bitmap->elements)304 break;305 306 if (!constraint_satisfy(i, base, constraint))307 continue;308 309 if (!bitmap_get_fast(bitmap, i)) {310 size_t continuous = 1;311 312 for (size_t j = 1; j < count; j++) {313 if ((i + j < bitmap->elements) &&314 (!bitmap_get_fast(bitmap, i + j)))315 continuous++;316 else317 break;318 }319 320 if (continuous == count) {321 if (index != NULL) {322 bitmap_set_range(bitmap, i, count);323 bitmap->next_fit = i / BITMAP_ELEMENT;324 *index = i;325 }326 327 return true;328 } else329 i += continuous;330 }331 }332 }333 334 return false;335 173 } 336 174
Note:
See TracChangeset
for help on using the changeset viewer.
