1 | /** |
---|
2 | * @file |
---|
3 | * |
---|
4 | * @ingroup rtems_rfs |
---|
5 | * |
---|
6 | * @brief RTEMS File Systems Bitmap Routines |
---|
7 | * |
---|
8 | * These functions manage bit maps. A bit map consists of the map of bit |
---|
9 | * allocated in a block and a search map where a bit represents 32 actual |
---|
10 | * bits. The search map allows for a faster search for an available bit as 32 |
---|
11 | * search bits can checked in a test. |
---|
12 | */ |
---|
13 | |
---|
14 | /* |
---|
15 | * COPYRIGHT (c) 2010 Chris Johns <chrisj@rtems.org> |
---|
16 | * |
---|
17 | * The license and distribution terms for this file may be |
---|
18 | * found in the file LICENSE in this distribution or at |
---|
19 | * http://www.rtems.org/license/LICENSE. |
---|
20 | */ |
---|
21 | |
---|
22 | #ifdef HAVE_CONFIG_H |
---|
23 | #include "config.h" |
---|
24 | #endif |
---|
25 | |
---|
26 | /** |
---|
27 | * Set to 1 to enable warnings when developing. |
---|
28 | */ |
---|
29 | #define RTEMS_RFS_BITMAP_WARNINGS 0 |
---|
30 | |
---|
31 | #if RTEMS_RFS_BITMAP_WARNINGS |
---|
32 | #include <stdio.h> |
---|
33 | #endif |
---|
34 | #include <stdlib.h> |
---|
35 | #include <rtems/rfs/rtems-rfs-bitmaps.h> |
---|
36 | |
---|
37 | #define rtems_rfs_bitmap_check(_c, _sm) \ |
---|
38 | _Assert(_sm >= _c->search_bits && \ |
---|
39 | _sm < (_c->search_bits + \ |
---|
40 | rtems_rfs_bitmap_elements(rtems_rfs_bitmap_elements(_c->size)))) |
---|
41 | |
---|
42 | |
---|
43 | /** |
---|
44 | * Test a bit in an element. If set return true else return false. |
---|
45 | * |
---|
46 | * @param target The target to test the bit in. |
---|
47 | * @param bit The bit to test. |
---|
48 | * @retval true The bit is set. |
---|
49 | * @retval false The bit is clear. |
---|
50 | */ |
---|
51 | static bool |
---|
52 | rtems_rfs_bitmap_test (rtems_rfs_bitmap_element target, |
---|
53 | rtems_rfs_bitmap_bit bit) |
---|
54 | { |
---|
55 | return RTEMS_RFS_BITMAP_TEST_BIT (target, bit); |
---|
56 | } |
---|
57 | |
---|
58 | /** |
---|
59 | * Set the bits in the element. Bits not set in the bit argument are left |
---|
60 | * unchanged. |
---|
61 | * |
---|
62 | * @param target The target element bits are set. |
---|
63 | * @param bits The bits in the target to set. A 1 in the bits will set the |
---|
64 | * same bit in the target. |
---|
65 | */ |
---|
66 | static rtems_rfs_bitmap_element |
---|
67 | rtems_rfs_bitmap_set (rtems_rfs_bitmap_element target, |
---|
68 | rtems_rfs_bitmap_element bits) |
---|
69 | { |
---|
70 | return RTEMS_RFS_BITMAP_SET_BITS (target, bits); |
---|
71 | } |
---|
72 | |
---|
73 | /** |
---|
74 | * Clear the bits in the element. Bits not set in the bit argument are left |
---|
75 | * unchanged. |
---|
76 | * |
---|
77 | * @param target The target element to clear the bits in. |
---|
78 | * @param bits The bits in the target to clear. A 1 in the bits will clear the |
---|
79 | * bit in the target. |
---|
80 | */ |
---|
81 | static rtems_rfs_bitmap_element |
---|
82 | rtems_rfs_bitmap_clear (rtems_rfs_bitmap_element target, |
---|
83 | rtems_rfs_bitmap_element bits) |
---|
84 | { |
---|
85 | return RTEMS_RFS_BITMAP_CLEAR_BITS (target, bits); |
---|
86 | } |
---|
87 | |
---|
88 | /** |
---|
89 | * Merge the bits in 2 variables based on the mask. A set bit in the mask will |
---|
90 | * merge the bits from bits1 and a clear bit will merge the bits from bits2. |
---|
91 | * The mask is always defined as 1 being set and 0 being clear. |
---|
92 | */ |
---|
93 | static rtems_rfs_bitmap_element |
---|
94 | rtems_rfs_bitmap_merge (rtems_rfs_bitmap_element bits1, |
---|
95 | rtems_rfs_bitmap_element bits2, |
---|
96 | rtems_rfs_bitmap_element mask) |
---|
97 | { |
---|
98 | /* |
---|
99 | * Use the normal bit operators because we do not change the bits just merge |
---|
100 | * the 2 separate parts. |
---|
101 | */ |
---|
102 | bits1 &= mask; |
---|
103 | bits2 &= RTEMS_RFS_BITMAP_INVERT_MASK (mask); |
---|
104 | return bits1 | bits2; |
---|
105 | } |
---|
106 | |
---|
107 | /** |
---|
108 | * Match the bits of 2 elements and return true if they match else return |
---|
109 | * false. |
---|
110 | * |
---|
111 | * @param bits1 One set of bits to match. |
---|
112 | * @param bits2 The second set of bits to match. |
---|
113 | * @retval true The bits match. |
---|
114 | * @retval false The bits do not match. |
---|
115 | */ |
---|
116 | static bool |
---|
117 | rtems_rfs_bitmap_match (rtems_rfs_bitmap_element bits1, |
---|
118 | rtems_rfs_bitmap_element bits2) |
---|
119 | { |
---|
120 | return bits1 ^ bits2 ? false : true; |
---|
121 | } |
---|
122 | |
---|
123 | #if RTEMS_NOT_USED_BUT_KEPT |
---|
124 | /** |
---|
125 | * Match the bits of 2 elements within the mask and return true if they match |
---|
126 | * else return false. |
---|
127 | * |
---|
128 | * @param mask The mask over which the match occurs. A 1 is a valid mask bit. |
---|
129 | * @param bits1 One set of bits to match. |
---|
130 | * @param bits2 The second set of bits to match. |
---|
131 | * @retval true The bits match. |
---|
132 | * @retval false The bits do not match. |
---|
133 | */ |
---|
134 | static bool |
---|
135 | rtems_rfs_bitmap_match_masked (rtems_rfs_bitmap_element mask, |
---|
136 | rtems_rfs_bitmap_element bits1, |
---|
137 | rtems_rfs_bitmap_element bits2) |
---|
138 | { |
---|
139 | return (bits1 ^ bits2) & mask ? false : true; |
---|
140 | } |
---|
141 | #endif |
---|
142 | |
---|
143 | /** |
---|
144 | * Return the map after loading from disk if not already loaded. |
---|
145 | * |
---|
146 | * @param control The bitmap control. |
---|
147 | * @param rtems_rfs_bitmap_map* Pointer to the bitmap map data if no error. |
---|
148 | * @return int The error number (errno). No error if 0. |
---|
149 | */ |
---|
150 | static int |
---|
151 | rtems_rfs_bitmap_load_map (rtems_rfs_bitmap_control* control, |
---|
152 | rtems_rfs_bitmap_map* map) |
---|
153 | { |
---|
154 | int rc; |
---|
155 | |
---|
156 | if (!control->buffer) |
---|
157 | return ENXIO; |
---|
158 | |
---|
159 | *map = NULL; |
---|
160 | |
---|
161 | rc = rtems_rfs_buffer_handle_request (control->fs, |
---|
162 | control->buffer, |
---|
163 | control->block, |
---|
164 | true); |
---|
165 | if (rc) |
---|
166 | return rc; |
---|
167 | |
---|
168 | *map = rtems_rfs_buffer_data (control->buffer); |
---|
169 | return 0; |
---|
170 | } |
---|
171 | |
---|
172 | rtems_rfs_bitmap_element |
---|
173 | rtems_rfs_bitmap_mask (unsigned int size) |
---|
174 | { |
---|
175 | rtems_rfs_bitmap_element mask = RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK; |
---|
176 | mask >>= (rtems_rfs_bitmap_element_bits () - size); |
---|
177 | return mask; |
---|
178 | } |
---|
179 | |
---|
180 | rtems_rfs_bitmap_element |
---|
181 | rtems_rfs_bitmap_mask_section (unsigned int start, unsigned int end) |
---|
182 | { |
---|
183 | rtems_rfs_bitmap_element mask = 0; |
---|
184 | if (end > start) |
---|
185 | mask = rtems_rfs_bitmap_mask (end - start) << start; |
---|
186 | return mask; |
---|
187 | } |
---|
188 | |
---|
189 | int |
---|
190 | rtems_rfs_bitmap_map_set (rtems_rfs_bitmap_control* control, |
---|
191 | rtems_rfs_bitmap_bit bit) |
---|
192 | { |
---|
193 | rtems_rfs_bitmap_map map; |
---|
194 | rtems_rfs_bitmap_map search_map; |
---|
195 | int index; |
---|
196 | int offset; |
---|
197 | int rc; |
---|
198 | rtems_rfs_bitmap_element element; |
---|
199 | |
---|
200 | rc = rtems_rfs_bitmap_load_map (control, &map); |
---|
201 | if (rc > 0) |
---|
202 | return rc; |
---|
203 | |
---|
204 | if (bit >= control->size) |
---|
205 | return EINVAL; |
---|
206 | |
---|
207 | search_map = control->search_bits; |
---|
208 | index = rtems_rfs_bitmap_map_index (bit); |
---|
209 | offset = rtems_rfs_bitmap_map_offset (bit); |
---|
210 | element = map[index]; |
---|
211 | map[index] = rtems_rfs_bitmap_set (element, 1 << offset); |
---|
212 | |
---|
213 | /* |
---|
214 | * If the element does not change, the bit was already set. There will be no |
---|
215 | * further action to take. |
---|
216 | */ |
---|
217 | if (rtems_rfs_bitmap_match(element, map[index])) |
---|
218 | return 0; |
---|
219 | |
---|
220 | control->free--; |
---|
221 | |
---|
222 | rtems_rfs_buffer_mark_dirty (control->buffer); |
---|
223 | if (rtems_rfs_bitmap_match(map[index], RTEMS_RFS_BITMAP_ELEMENT_SET)) |
---|
224 | { |
---|
225 | bit = index; |
---|
226 | index = rtems_rfs_bitmap_map_index (bit); |
---|
227 | offset = rtems_rfs_bitmap_map_offset (bit); |
---|
228 | search_map[index] = rtems_rfs_bitmap_set (search_map[index], 1 << offset); |
---|
229 | rtems_rfs_bitmap_check(control, &search_map[index]); |
---|
230 | } |
---|
231 | |
---|
232 | return 0; |
---|
233 | } |
---|
234 | |
---|
235 | int |
---|
236 | rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control, |
---|
237 | rtems_rfs_bitmap_bit bit) |
---|
238 | { |
---|
239 | rtems_rfs_bitmap_map map; |
---|
240 | rtems_rfs_bitmap_map search_map; |
---|
241 | int index; |
---|
242 | int offset; |
---|
243 | int rc; |
---|
244 | rtems_rfs_bitmap_element element; |
---|
245 | |
---|
246 | rc = rtems_rfs_bitmap_load_map (control, &map); |
---|
247 | if (rc > 0) |
---|
248 | return rc; |
---|
249 | |
---|
250 | if (bit >= control->size) |
---|
251 | return EINVAL; |
---|
252 | |
---|
253 | search_map = control->search_bits; |
---|
254 | index = rtems_rfs_bitmap_map_index (bit); |
---|
255 | offset = rtems_rfs_bitmap_map_offset (bit); |
---|
256 | element = map[index]; |
---|
257 | map[index] = rtems_rfs_bitmap_clear (element, 1 << offset); |
---|
258 | |
---|
259 | /* |
---|
260 | * If the element does not change, the bit was already clear. There will be |
---|
261 | * no further action to take. |
---|
262 | */ |
---|
263 | if (rtems_rfs_bitmap_match(element, map[index])) |
---|
264 | return 0; |
---|
265 | |
---|
266 | bit = index; |
---|
267 | index = rtems_rfs_bitmap_map_index (bit); |
---|
268 | offset = rtems_rfs_bitmap_map_offset(bit); |
---|
269 | search_map[index] = rtems_rfs_bitmap_clear (search_map[index], 1 << offset); |
---|
270 | rtems_rfs_bitmap_check(control, &search_map[index]); |
---|
271 | rtems_rfs_buffer_mark_dirty (control->buffer); |
---|
272 | control->free++; |
---|
273 | |
---|
274 | return 0; |
---|
275 | } |
---|
276 | |
---|
277 | int |
---|
278 | rtems_rfs_bitmap_map_test (rtems_rfs_bitmap_control* control, |
---|
279 | rtems_rfs_bitmap_bit bit, |
---|
280 | bool* state) |
---|
281 | { |
---|
282 | rtems_rfs_bitmap_map map; |
---|
283 | int index; |
---|
284 | int rc; |
---|
285 | rc = rtems_rfs_bitmap_load_map (control, &map); |
---|
286 | if (rc > 0) |
---|
287 | return rc; |
---|
288 | if (bit >= control->size) |
---|
289 | return EINVAL; |
---|
290 | index = rtems_rfs_bitmap_map_index (bit); |
---|
291 | *state = rtems_rfs_bitmap_test (map[index], bit); |
---|
292 | return 0; |
---|
293 | } |
---|
294 | |
---|
295 | int |
---|
296 | rtems_rfs_bitmap_map_set_all (rtems_rfs_bitmap_control* control) |
---|
297 | { |
---|
298 | rtems_rfs_bitmap_map map; |
---|
299 | size_t elements; |
---|
300 | int e; |
---|
301 | int rc; |
---|
302 | |
---|
303 | rc = rtems_rfs_bitmap_load_map (control, &map); |
---|
304 | if (rc > 0) |
---|
305 | return rc; |
---|
306 | |
---|
307 | elements = rtems_rfs_bitmap_elements (control->size); |
---|
308 | |
---|
309 | control->free = 0; |
---|
310 | |
---|
311 | for (e = 0; e < elements; e++) |
---|
312 | map[e] = RTEMS_RFS_BITMAP_ELEMENT_SET; |
---|
313 | |
---|
314 | elements = rtems_rfs_bitmap_elements (elements); |
---|
315 | |
---|
316 | for (e = 0; e < elements; e++) |
---|
317 | control->search_bits[e] = RTEMS_RFS_BITMAP_ELEMENT_SET; |
---|
318 | |
---|
319 | rtems_rfs_buffer_mark_dirty (control->buffer); |
---|
320 | |
---|
321 | return 0; |
---|
322 | } |
---|
323 | |
---|
324 | int |
---|
325 | rtems_rfs_bitmap_map_clear_all (rtems_rfs_bitmap_control* control) |
---|
326 | { |
---|
327 | rtems_rfs_bitmap_map map; |
---|
328 | rtems_rfs_bitmap_bit last_search_bit; |
---|
329 | size_t elements; |
---|
330 | int e; |
---|
331 | int rc; |
---|
332 | |
---|
333 | rc = rtems_rfs_bitmap_load_map (control, &map); |
---|
334 | if (rc > 0) |
---|
335 | return rc; |
---|
336 | |
---|
337 | elements = rtems_rfs_bitmap_elements (control->size); |
---|
338 | |
---|
339 | control->free = control->size; |
---|
340 | |
---|
341 | for (e = 0; e < elements; e++) |
---|
342 | map[e] = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; |
---|
343 | |
---|
344 | /* |
---|
345 | * Set the un-mapped bits in the last search element so the available logic |
---|
346 | * works. |
---|
347 | */ |
---|
348 | last_search_bit = rtems_rfs_bitmap_map_offset (elements); |
---|
349 | |
---|
350 | if (last_search_bit == 0) |
---|
351 | last_search_bit = rtems_rfs_bitmap_element_bits (); |
---|
352 | |
---|
353 | elements = rtems_rfs_bitmap_elements (elements); |
---|
354 | |
---|
355 | for (e = 0; e < (elements - 1); e++) |
---|
356 | control->search_bits[e] = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; |
---|
357 | |
---|
358 | control->search_bits[elements - 1] = |
---|
359 | rtems_rfs_bitmap_merge (RTEMS_RFS_BITMAP_ELEMENT_CLEAR, |
---|
360 | RTEMS_RFS_BITMAP_ELEMENT_SET, |
---|
361 | rtems_rfs_bitmap_mask (last_search_bit)); |
---|
362 | |
---|
363 | rtems_rfs_buffer_mark_dirty (control->buffer); |
---|
364 | |
---|
365 | return 0; |
---|
366 | } |
---|
367 | |
---|
368 | static int |
---|
369 | rtems_rfs_search_map_for_clear_bit (rtems_rfs_bitmap_control* control, |
---|
370 | rtems_rfs_bitmap_bit* bit, |
---|
371 | bool* found, |
---|
372 | size_t window, |
---|
373 | int direction) |
---|
374 | { |
---|
375 | rtems_rfs_bitmap_map map; |
---|
376 | rtems_rfs_bitmap_bit test_bit; |
---|
377 | rtems_rfs_bitmap_bit end_bit; |
---|
378 | rtems_rfs_bitmap_element* search_bits; |
---|
379 | int search_index; |
---|
380 | int search_offset; |
---|
381 | rtems_rfs_bitmap_element* map_bits; |
---|
382 | int map_index; |
---|
383 | int map_offset; |
---|
384 | int rc; |
---|
385 | |
---|
386 | *found = false; |
---|
387 | |
---|
388 | /* |
---|
389 | * Load the bitmap. |
---|
390 | */ |
---|
391 | rc = rtems_rfs_bitmap_load_map (control, &map); |
---|
392 | if (rc > 0) |
---|
393 | return rc; |
---|
394 | |
---|
395 | /* |
---|
396 | * Calculate the bit we are testing plus the end point we search over. |
---|
397 | */ |
---|
398 | test_bit = *bit; |
---|
399 | end_bit = test_bit + (window * direction); |
---|
400 | |
---|
401 | if (end_bit < 0) |
---|
402 | end_bit = 0; |
---|
403 | else if (end_bit >= control->size) |
---|
404 | end_bit = control->size - 1; |
---|
405 | |
---|
406 | map_index = rtems_rfs_bitmap_map_index (test_bit); |
---|
407 | map_offset = rtems_rfs_bitmap_map_offset (test_bit); |
---|
408 | search_index = rtems_rfs_bitmap_map_index (map_index); |
---|
409 | search_offset = rtems_rfs_bitmap_map_offset (map_index); |
---|
410 | |
---|
411 | search_bits = &control->search_bits[search_index]; |
---|
412 | map_bits = &map[map_index]; |
---|
413 | |
---|
414 | /* |
---|
415 | * Check each bit from the search map offset for a clear bit. |
---|
416 | */ |
---|
417 | do |
---|
418 | { |
---|
419 | /* |
---|
420 | * If any bit is clear find that bit and then search the map element. If |
---|
421 | * all bits are set there are no map bits so move to the next search |
---|
422 | * element. |
---|
423 | */ |
---|
424 | if (!rtems_rfs_bitmap_match (*search_bits, RTEMS_RFS_BITMAP_ELEMENT_SET)) |
---|
425 | { |
---|
426 | while ((search_offset >= 0) |
---|
427 | && (search_offset < rtems_rfs_bitmap_element_bits ())) |
---|
428 | { |
---|
429 | if (!rtems_rfs_bitmap_test (*search_bits, search_offset)) |
---|
430 | { |
---|
431 | /* |
---|
432 | * Find the clear bit in the map. Update the search map and map if |
---|
433 | * found. We may find none are spare if searching up from the seed. |
---|
434 | */ |
---|
435 | while ((map_offset >= 0) |
---|
436 | && (map_offset < rtems_rfs_bitmap_element_bits ())) |
---|
437 | { |
---|
438 | if (!rtems_rfs_bitmap_test (*map_bits, map_offset)) |
---|
439 | { |
---|
440 | *map_bits = rtems_rfs_bitmap_set (*map_bits, 1 << map_offset); |
---|
441 | if (rtems_rfs_bitmap_match(*map_bits, |
---|
442 | RTEMS_RFS_BITMAP_ELEMENT_SET)) |
---|
443 | *search_bits = rtems_rfs_bitmap_set (*search_bits, |
---|
444 | 1 << search_offset); |
---|
445 | control->free--; |
---|
446 | *bit = test_bit; |
---|
447 | *found = true; |
---|
448 | rtems_rfs_buffer_mark_dirty (control->buffer); |
---|
449 | return 0; |
---|
450 | } |
---|
451 | |
---|
452 | if (test_bit == end_bit) |
---|
453 | break; |
---|
454 | |
---|
455 | map_offset += direction; |
---|
456 | test_bit += direction; |
---|
457 | } |
---|
458 | } |
---|
459 | |
---|
460 | map_bits += direction; |
---|
461 | map_index += direction; |
---|
462 | map_offset = direction > 0 ? 0 : rtems_rfs_bitmap_element_bits () - 1; |
---|
463 | |
---|
464 | test_bit = (map_index * rtems_rfs_bitmap_element_bits ()) + map_offset; |
---|
465 | |
---|
466 | search_offset += direction; |
---|
467 | |
---|
468 | if (((direction < 0) && (test_bit <= end_bit)) |
---|
469 | || ((direction > 0) && (test_bit >= end_bit))) |
---|
470 | break; |
---|
471 | } |
---|
472 | } |
---|
473 | else |
---|
474 | { |
---|
475 | /* |
---|
476 | * Move to the next search element. We need to determine the number of |
---|
477 | * bits in the search offset that are being skipped so the map bits |
---|
478 | * pointer can be updated. If we are moving down and we have a search |
---|
479 | * offset of 0 then the search map adjustment is to the top bit of the |
---|
480 | * pervious search bit's value. |
---|
481 | * |
---|
482 | * Align test_bit either up or down depending on the direction to next 32 |
---|
483 | * bit boundary. |
---|
484 | */ |
---|
485 | rtems_rfs_bitmap_bit bits_skipped; |
---|
486 | test_bit &= ~((1 << RTEMS_RFS_ELEMENT_BITS_POWER_2) - 1); |
---|
487 | if (direction > 0) |
---|
488 | { |
---|
489 | bits_skipped = rtems_rfs_bitmap_element_bits () - search_offset; |
---|
490 | test_bit += bits_skipped * rtems_rfs_bitmap_element_bits (); |
---|
491 | map_offset = 0; |
---|
492 | } |
---|
493 | else |
---|
494 | { |
---|
495 | bits_skipped = search_offset + 1; |
---|
496 | /* |
---|
497 | * Need to remove 1 for the rounding up. The above rounds down and |
---|
498 | * adds 1. Remember the logic is for subtraction. |
---|
499 | */ |
---|
500 | test_bit -= ((bits_skipped - 1) * rtems_rfs_bitmap_element_bits ()) + 1; |
---|
501 | map_offset = rtems_rfs_bitmap_element_bits () - 1; |
---|
502 | } |
---|
503 | map_bits += direction * bits_skipped; |
---|
504 | map_index += direction * bits_skipped; |
---|
505 | } |
---|
506 | |
---|
507 | search_bits += direction; |
---|
508 | search_offset = direction > 0 ? 0 : rtems_rfs_bitmap_element_bits () - 1; |
---|
509 | } |
---|
510 | while (((direction < 0) && (test_bit >= end_bit)) |
---|
511 | || ((direction > 0) && (test_bit <= end_bit))); |
---|
512 | |
---|
513 | return 0; |
---|
514 | } |
---|
515 | |
---|
516 | int |
---|
517 | rtems_rfs_bitmap_map_alloc (rtems_rfs_bitmap_control* control, |
---|
518 | rtems_rfs_bitmap_bit seed, |
---|
519 | bool* allocated, |
---|
520 | rtems_rfs_bitmap_bit* bit) |
---|
521 | { |
---|
522 | rtems_rfs_bitmap_bit upper_seed; |
---|
523 | rtems_rfs_bitmap_bit lower_seed; |
---|
524 | rtems_rfs_bitmap_bit window; /* may become a parameter */ |
---|
525 | int rc = 0; |
---|
526 | |
---|
527 | /* |
---|
528 | * By default we assume the allocation failed. |
---|
529 | */ |
---|
530 | *allocated = false; |
---|
531 | |
---|
532 | /* |
---|
533 | * The window is the number of bits we search over in either direction each |
---|
534 | * time. |
---|
535 | */ |
---|
536 | window = RTEMS_RFS_BITMAP_SEARCH_WINDOW; |
---|
537 | |
---|
538 | /* |
---|
539 | * Start from the seed and move in either direction. Search in window amounts |
---|
540 | * of bits from the original seed above then below. That is search from the |
---|
541 | * seed up then from the seed down a window number of bits, then repeat the |
---|
542 | * process from the window distance from the seed, again above then |
---|
543 | * below. Keep moving out until all bits have been searched. |
---|
544 | */ |
---|
545 | upper_seed = seed; |
---|
546 | lower_seed = seed; |
---|
547 | |
---|
548 | /* |
---|
549 | * If the upper and lower seed values have reached the limits of the bitmap |
---|
550 | * we have searched all of the map. The seed may not be aligned to a window |
---|
551 | * boundary so we may need to search a partial window and this may also not |
---|
552 | * be balanced for the upper or lower seeds. We move to the limits, search |
---|
553 | * then return false if no clear bits are found. |
---|
554 | */ |
---|
555 | while (((upper_seed >= 0) && (upper_seed < control->size)) |
---|
556 | || ((lower_seed >= 0) && (lower_seed < control->size))) |
---|
557 | { |
---|
558 | /* |
---|
559 | * Search up first so bits allocated in succession are grouped together. |
---|
560 | */ |
---|
561 | if (upper_seed < control->size) |
---|
562 | { |
---|
563 | *bit = upper_seed; |
---|
564 | rc = rtems_rfs_search_map_for_clear_bit (control, bit, allocated, |
---|
565 | window, 1); |
---|
566 | if ((rc > 0) || *allocated) |
---|
567 | break; |
---|
568 | } |
---|
569 | |
---|
570 | if (lower_seed >= 0) |
---|
571 | { |
---|
572 | *bit = lower_seed; |
---|
573 | rc = rtems_rfs_search_map_for_clear_bit (control, bit, allocated, |
---|
574 | window, -1); |
---|
575 | if ((rc > 0) || *allocated) |
---|
576 | break; |
---|
577 | } |
---|
578 | |
---|
579 | /* |
---|
580 | * Do not bound the limits at the edges of the map. Do not update if an |
---|
581 | * edge has been passed. |
---|
582 | */ |
---|
583 | if (upper_seed < control->size) |
---|
584 | upper_seed += window; |
---|
585 | if (lower_seed >= 0) |
---|
586 | lower_seed -= window; |
---|
587 | } |
---|
588 | |
---|
589 | return 0; |
---|
590 | } |
---|
591 | |
---|
592 | int |
---|
593 | rtems_rfs_bitmap_create_search (rtems_rfs_bitmap_control* control) |
---|
594 | { |
---|
595 | rtems_rfs_bitmap_map search_map; |
---|
596 | rtems_rfs_bitmap_map map; |
---|
597 | size_t size; |
---|
598 | rtems_rfs_bitmap_bit bit; |
---|
599 | int rc; |
---|
600 | |
---|
601 | rc = rtems_rfs_bitmap_load_map (control, &map); |
---|
602 | if (rc > 0) |
---|
603 | return rc; |
---|
604 | |
---|
605 | control->free = 0; |
---|
606 | search_map = control->search_bits; |
---|
607 | size = control->size; |
---|
608 | bit = 0; |
---|
609 | |
---|
610 | rtems_rfs_bitmap_check(control, search_map); |
---|
611 | *search_map = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; |
---|
612 | while (size) |
---|
613 | { |
---|
614 | rtems_rfs_bitmap_element bits; |
---|
615 | int available; |
---|
616 | if (size < rtems_rfs_bitmap_element_bits ()) |
---|
617 | { |
---|
618 | bits = rtems_rfs_bitmap_merge (*map, |
---|
619 | RTEMS_RFS_BITMAP_ELEMENT_SET, |
---|
620 | rtems_rfs_bitmap_mask_section (0, size)); |
---|
621 | available = size; |
---|
622 | } |
---|
623 | else |
---|
624 | { |
---|
625 | bits = *map; |
---|
626 | available = rtems_rfs_bitmap_element_bits (); |
---|
627 | } |
---|
628 | |
---|
629 | if (rtems_rfs_bitmap_match (bits, RTEMS_RFS_BITMAP_ELEMENT_SET)) |
---|
630 | rtems_rfs_bitmap_set (*search_map, bit); |
---|
631 | else |
---|
632 | { |
---|
633 | int b; |
---|
634 | for (b = 0; b < available; b++) |
---|
635 | if (!rtems_rfs_bitmap_test (bits, b)) |
---|
636 | control->free++; |
---|
637 | } |
---|
638 | |
---|
639 | size -= available; |
---|
640 | |
---|
641 | /* Iterate from 0 to 1 less than the number of bits in an element */ |
---|
642 | if (bit == (rtems_rfs_bitmap_element_bits () - 1)) |
---|
643 | { |
---|
644 | bit = 0; |
---|
645 | if (size > 0) |
---|
646 | { |
---|
647 | search_map++; |
---|
648 | rtems_rfs_bitmap_check(control, search_map); |
---|
649 | *search_map = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; |
---|
650 | } |
---|
651 | } |
---|
652 | else |
---|
653 | bit++; |
---|
654 | map++; |
---|
655 | } |
---|
656 | |
---|
657 | return 0; |
---|
658 | } |
---|
659 | |
---|
660 | int |
---|
661 | rtems_rfs_bitmap_open (rtems_rfs_bitmap_control* control, |
---|
662 | rtems_rfs_file_system* fs, |
---|
663 | rtems_rfs_buffer_handle* buffer, |
---|
664 | size_t size, |
---|
665 | rtems_rfs_buffer_block block) |
---|
666 | { |
---|
667 | size_t elements = rtems_rfs_bitmap_elements (size); |
---|
668 | |
---|
669 | control->buffer = buffer; |
---|
670 | control->fs = fs; |
---|
671 | control->block = block; |
---|
672 | control->size = size; |
---|
673 | |
---|
674 | elements = rtems_rfs_bitmap_elements (elements); |
---|
675 | control->search_bits = malloc (elements * sizeof (rtems_rfs_bitmap_element)); |
---|
676 | |
---|
677 | if (!control->search_bits) |
---|
678 | return ENOMEM; |
---|
679 | |
---|
680 | return rtems_rfs_bitmap_create_search (control); |
---|
681 | } |
---|
682 | |
---|
683 | int |
---|
684 | rtems_rfs_bitmap_close (rtems_rfs_bitmap_control* control) |
---|
685 | { |
---|
686 | free (control->search_bits); |
---|
687 | return 0; |
---|
688 | } |
---|