Lines Matching full:bitmap
15 #include "scrub/bitmap.h"
19 /* u64 bitmap */
60 /* Iterate each interval of a bitmap. Do not change the bitmap. */ in INTERVAL_TREE_DEFINE()
61 #define for_each_xbitmap64_extent(bn, bitmap) \ in INTERVAL_TREE_DEFINE() argument
62 for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \ in INTERVAL_TREE_DEFINE()
68 /* Clear a range of this bitmap. */
71 struct xbitmap64 *bitmap,
79 while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last))) {
84 xbitmap64_tree_remove(bn, &bitmap->xb_root);
86 xbitmap64_tree_insert(bn, &bitmap->xb_root);
95 xbitmap64_tree_insert(new_bn, &bitmap->xb_root);
98 xbitmap64_tree_remove(bn, &bitmap->xb_root);
100 xbitmap64_tree_insert(bn, &bitmap->xb_root);
103 xbitmap64_tree_remove(bn, &bitmap->xb_root);
105 xbitmap64_tree_insert(bn, &bitmap->xb_root);
109 xbitmap64_tree_remove(bn, &bitmap->xb_root);
117 /* Set a range of this bitmap. */
120 struct xbitmap64 *bitmap, in xbitmap64_set() argument
130 left = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap64_set()
135 error = xbitmap64_clear(bitmap, start, len); in xbitmap64_set()
140 left = xbitmap64_tree_iter_first(&bitmap->xb_root, start - 1, start - 1); in xbitmap64_set()
144 right = xbitmap64_tree_iter_first(&bitmap->xb_root, last + 1, last + 1); in xbitmap64_set()
149 xbitmap64_tree_remove(left, &bitmap->xb_root); in xbitmap64_set()
150 xbitmap64_tree_remove(right, &bitmap->xb_root); in xbitmap64_set()
152 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
156 xbitmap64_tree_remove(left, &bitmap->xb_root); in xbitmap64_set()
158 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
161 xbitmap64_tree_remove(right, &bitmap->xb_root); in xbitmap64_set()
163 xbitmap64_tree_insert(right, &bitmap->xb_root); in xbitmap64_set()
171 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
177 /* Free everything related to this bitmap. */
180 struct xbitmap64 *bitmap) in xbitmap64_destroy() argument
184 while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) { in xbitmap64_destroy()
185 xbitmap64_tree_remove(bn, &bitmap->xb_root); in xbitmap64_destroy()
190 /* Set up a per-AG block bitmap. */
193 struct xbitmap64 *bitmap) in xbitmap64_init() argument
195 bitmap->xb_root = RB_ROOT_CACHED; in xbitmap64_init()
199 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
202 * for a given owner to generate @bitmap; and iterate all the blocks of the
205 * mentioned in sub from all the extents linked in @bitmap, which leaves
206 * @bitmap as the list of blocks that are not accounted for, which we assume
208 * @bitmap can be reaped.
210 * This is the logical equivalent of bitmap &= ~sub.
214 struct xbitmap64 *bitmap, in xbitmap64_disunion() argument
220 if (xbitmap64_empty(bitmap) || xbitmap64_empty(sub)) in xbitmap64_disunion()
224 error = xbitmap64_clear(bitmap, bn->bn_start, in xbitmap64_disunion()
233 /* How many bits are set in this bitmap? */
236 struct xbitmap64 *bitmap) in xbitmap64_hweight() argument
241 for_each_xbitmap64_extent(bn, bitmap) in xbitmap64_hweight()
247 /* Call a function for every run of set bits in this bitmap. */
250 struct xbitmap64 *bitmap, in xbitmap64_walk() argument
257 for_each_xbitmap64_extent(bn, bitmap) { in xbitmap64_walk()
266 /* Does this bitmap have no bits set at all? */
269 struct xbitmap64 *bitmap) in xbitmap64_empty() argument
271 return bitmap->xb_root.rb_root.rb_node == NULL; in xbitmap64_empty()
277 struct xbitmap64 *bitmap, in xbitmap64_test() argument
284 bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap64_test()
296 /* u32 bitmap */
334 /* Iterate each interval of a bitmap. Do not change the bitmap. */ in INTERVAL_TREE_DEFINE()
335 #define for_each_xbitmap32_extent(bn, bitmap) \ in INTERVAL_TREE_DEFINE() argument
336 for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \ in INTERVAL_TREE_DEFINE()
342 /* Clear a range of this bitmap. */
345 struct xbitmap32 *bitmap,
353 while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last))) {
358 xbitmap32_tree_remove(bn, &bitmap->xb_root);
360 xbitmap32_tree_insert(bn, &bitmap->xb_root);
369 xbitmap32_tree_insert(new_bn, &bitmap->xb_root);
372 xbitmap32_tree_remove(bn, &bitmap->xb_root);
374 xbitmap32_tree_insert(bn, &bitmap->xb_root);
377 xbitmap32_tree_remove(bn, &bitmap->xb_root);
379 xbitmap32_tree_insert(bn, &bitmap->xb_root);
383 xbitmap32_tree_remove(bn, &bitmap->xb_root);
391 /* Set a range of this bitmap. */
394 struct xbitmap32 *bitmap, in xbitmap32_set() argument
404 left = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap32_set()
409 error = xbitmap32_clear(bitmap, start, len); in xbitmap32_set()
414 left = xbitmap32_tree_iter_first(&bitmap->xb_root, start - 1, start - 1); in xbitmap32_set()
418 right = xbitmap32_tree_iter_first(&bitmap->xb_root, last + 1, last + 1); in xbitmap32_set()
423 xbitmap32_tree_remove(left, &bitmap->xb_root); in xbitmap32_set()
424 xbitmap32_tree_remove(right, &bitmap->xb_root); in xbitmap32_set()
426 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
430 xbitmap32_tree_remove(left, &bitmap->xb_root); in xbitmap32_set()
432 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
435 xbitmap32_tree_remove(right, &bitmap->xb_root); in xbitmap32_set()
437 xbitmap32_tree_insert(right, &bitmap->xb_root); in xbitmap32_set()
445 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
451 /* Free everything related to this bitmap. */
454 struct xbitmap32 *bitmap) in xbitmap32_destroy() argument
458 while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, 0, -1U))) { in xbitmap32_destroy()
459 xbitmap32_tree_remove(bn, &bitmap->xb_root); in xbitmap32_destroy()
464 /* Set up a per-AG block bitmap. */
467 struct xbitmap32 *bitmap) in xbitmap32_init() argument
469 bitmap->xb_root = RB_ROOT_CACHED; in xbitmap32_init()
473 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
476 * for a given owner to generate @bitmap; and iterate all the blocks of the
479 * mentioned in sub from all the extents linked in @bitmap, which leaves
480 * @bitmap as the list of blocks that are not accounted for, which we assume
482 * @bitmap can be reaped.
484 * This is the logical equivalent of bitmap &= ~sub.
488 struct xbitmap32 *bitmap, in xbitmap32_disunion() argument
494 if (xbitmap32_empty(bitmap) || xbitmap32_empty(sub)) in xbitmap32_disunion()
498 error = xbitmap32_clear(bitmap, bn->bn_start, in xbitmap32_disunion()
507 /* How many bits are set in this bitmap? */
510 struct xbitmap32 *bitmap) in xbitmap32_hweight() argument
515 for_each_xbitmap32_extent(bn, bitmap) in xbitmap32_hweight()
521 /* Call a function for every run of set bits in this bitmap. */
524 struct xbitmap32 *bitmap, in xbitmap32_walk() argument
531 for_each_xbitmap32_extent(bn, bitmap) { in xbitmap32_walk()
540 /* Does this bitmap have no bits set at all? */
543 struct xbitmap32 *bitmap) in xbitmap32_empty() argument
545 return bitmap->xb_root.rb_root.rb_node == NULL; in xbitmap32_empty()
551 struct xbitmap32 *bitmap, in xbitmap32_test() argument
558 bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap32_test()