Lines Matching +full:sub +full:- +full:blocks
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) 2018-2023 Oracle. All Rights Reserved.
36 #define START(node) ((node)->bn_start)
37 #define LAST(node) ((node)->bn_last)
41 * forward-declare them anyway for clarity.
63 for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \ in INTERVAL_TREE_DEFINE()
66 (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
78 uint64_t last = start + len - 1;
80 while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last))) {
81 if (bn->bn_start < start && bn->bn_last > last) {
82 uint64_t old_last = bn->bn_last;
85 xbitmap64_tree_remove(bn, &bitmap->xb_root);
86 bn->bn_last = start - 1;
87 xbitmap64_tree_insert(bn, &bitmap->xb_root);
93 return -ENOMEM;
94 new_bn->bn_start = last + 1;
95 new_bn->bn_last = old_last;
96 xbitmap64_tree_insert(new_bn, &bitmap->xb_root);
97 } else if (bn->bn_start < start) {
99 xbitmap64_tree_remove(bn, &bitmap->xb_root);
100 bn->bn_last = start - 1;
101 xbitmap64_tree_insert(bn, &bitmap->xb_root);
102 } else if (bn->bn_last > last) {
104 xbitmap64_tree_remove(bn, &bitmap->xb_root);
105 bn->bn_start = last + 1;
106 xbitmap64_tree_insert(bn, &bitmap->xb_root);
110 xbitmap64_tree_remove(bn, &bitmap->xb_root);
127 uint64_t last = start + len - 1; in xbitmap64_set()
131 left = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap64_set()
132 if (left && left->bn_start <= start && left->bn_last >= last) in xbitmap64_set()
140 /* Do we have a left-adjacent extent? */ in xbitmap64_set()
141 left = xbitmap64_tree_iter_first(&bitmap->xb_root, start - 1, start - 1); in xbitmap64_set()
142 ASSERT(!left || left->bn_last + 1 == start); in xbitmap64_set()
144 /* Do we have a right-adjacent extent? */ in xbitmap64_set()
145 right = xbitmap64_tree_iter_first(&bitmap->xb_root, last + 1, last + 1); in xbitmap64_set()
146 ASSERT(!right || right->bn_start == last + 1); in xbitmap64_set()
150 xbitmap64_tree_remove(left, &bitmap->xb_root); in xbitmap64_set()
151 xbitmap64_tree_remove(right, &bitmap->xb_root); in xbitmap64_set()
152 left->bn_last = right->bn_last; in xbitmap64_set()
153 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
157 xbitmap64_tree_remove(left, &bitmap->xb_root); in xbitmap64_set()
158 left->bn_last = last; in xbitmap64_set()
159 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
162 xbitmap64_tree_remove(right, &bitmap->xb_root); in xbitmap64_set()
163 right->bn_start = start; in xbitmap64_set()
164 xbitmap64_tree_insert(right, &bitmap->xb_root); in xbitmap64_set()
169 return -ENOMEM; in xbitmap64_set()
170 left->bn_start = start; in xbitmap64_set()
171 left->bn_last = last; in xbitmap64_set()
172 xbitmap64_tree_insert(left, &bitmap->xb_root); in xbitmap64_set()
185 while ((bn = xbitmap64_tree_iter_first(&bitmap->xb_root, 0, -1ULL))) { in xbitmap64_destroy()
186 xbitmap64_tree_remove(bn, &bitmap->xb_root); in xbitmap64_destroy()
191 /* Set up a per-AG block bitmap. */
196 bitmap->xb_root = RB_ROOT_CACHED; in xbitmap64_init()
200 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
203 * for a given owner to generate @bitmap; and iterate all the blocks of the
205 * owner to generate @sub. This routine subtracts all the extents
206 * mentioned in sub from all the extents linked in @bitmap, which leaves
207 * @bitmap as the list of blocks that are not accounted for, which we assume
208 * are the dead blocks of the old metadata structure. The blocks mentioned in
211 * This is the logical equivalent of bitmap &= ~sub.
216 struct xbitmap64 *sub) in xbitmap64_disunion() argument
221 if (xbitmap64_empty(bitmap) || xbitmap64_empty(sub)) in xbitmap64_disunion()
224 for_each_xbitmap64_extent(bn, sub) { in xbitmap64_disunion()
225 error = xbitmap64_clear(bitmap, bn->bn_start, in xbitmap64_disunion()
226 bn->bn_last - bn->bn_start + 1); in xbitmap64_disunion()
243 ret += bn->bn_last - bn->bn_start + 1; in xbitmap64_hweight()
259 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv); in xbitmap64_walk()
272 return bitmap->xb_root.rb_root.rb_node == NULL; in xbitmap64_empty()
283 uint64_t last = start + *len - 1; in xbitmap64_test()
285 bn = xbitmap64_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap64_test()
288 if (bn->bn_start <= start) { in xbitmap64_test()
289 if (bn->bn_last < last) in xbitmap64_test()
290 *len = bn->bn_last - start + 1; in xbitmap64_test()
293 *len = bn->bn_start - start; in xbitmap64_test()
316 * forward-declare them anyway for clarity.
338 for ((bn) = rb_entry_safe(rb_first(&(bitmap)->xb_root.rb_root), \ in INTERVAL_TREE_DEFINE()
341 (bn) = rb_entry_safe(rb_next(&(bn)->bn_rbnode), \
353 uint32_t last = start + len - 1;
355 while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last))) {
356 if (bn->bn_start < start && bn->bn_last > last) {
357 uint32_t old_last = bn->bn_last;
360 xbitmap32_tree_remove(bn, &bitmap->xb_root);
361 bn->bn_last = start - 1;
362 xbitmap32_tree_insert(bn, &bitmap->xb_root);
368 return -ENOMEM;
369 new_bn->bn_start = last + 1;
370 new_bn->bn_last = old_last;
371 xbitmap32_tree_insert(new_bn, &bitmap->xb_root);
372 } else if (bn->bn_start < start) {
374 xbitmap32_tree_remove(bn, &bitmap->xb_root);
375 bn->bn_last = start - 1;
376 xbitmap32_tree_insert(bn, &bitmap->xb_root);
377 } else if (bn->bn_last > last) {
379 xbitmap32_tree_remove(bn, &bitmap->xb_root);
380 bn->bn_start = last + 1;
381 xbitmap32_tree_insert(bn, &bitmap->xb_root);
385 xbitmap32_tree_remove(bn, &bitmap->xb_root);
402 uint32_t last = start + len - 1; in xbitmap32_set()
406 left = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap32_set()
407 if (left && left->bn_start <= start && left->bn_last >= last) in xbitmap32_set()
415 /* Do we have a left-adjacent extent? */ in xbitmap32_set()
416 left = xbitmap32_tree_iter_first(&bitmap->xb_root, start - 1, start - 1); in xbitmap32_set()
417 ASSERT(!left || left->bn_last + 1 == start); in xbitmap32_set()
419 /* Do we have a right-adjacent extent? */ in xbitmap32_set()
420 right = xbitmap32_tree_iter_first(&bitmap->xb_root, last + 1, last + 1); in xbitmap32_set()
421 ASSERT(!right || right->bn_start == last + 1); in xbitmap32_set()
425 xbitmap32_tree_remove(left, &bitmap->xb_root); in xbitmap32_set()
426 xbitmap32_tree_remove(right, &bitmap->xb_root); in xbitmap32_set()
427 left->bn_last = right->bn_last; in xbitmap32_set()
428 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
432 xbitmap32_tree_remove(left, &bitmap->xb_root); in xbitmap32_set()
433 left->bn_last = last; in xbitmap32_set()
434 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
437 xbitmap32_tree_remove(right, &bitmap->xb_root); in xbitmap32_set()
438 right->bn_start = start; in xbitmap32_set()
439 xbitmap32_tree_insert(right, &bitmap->xb_root); in xbitmap32_set()
444 return -ENOMEM; in xbitmap32_set()
445 left->bn_start = start; in xbitmap32_set()
446 left->bn_last = last; in xbitmap32_set()
447 xbitmap32_tree_insert(left, &bitmap->xb_root); in xbitmap32_set()
460 while ((bn = xbitmap32_tree_iter_first(&bitmap->xb_root, 0, -1U))) { in xbitmap32_destroy()
461 xbitmap32_tree_remove(bn, &bitmap->xb_root); in xbitmap32_destroy()
466 /* Set up a per-AG block bitmap. */
471 bitmap->xb_root = RB_ROOT_CACHED; in xbitmap32_init()
475 * Remove all the blocks mentioned in @sub from the extents in @bitmap.
478 * for a given owner to generate @bitmap; and iterate all the blocks of the
480 * owner to generate @sub. This routine subtracts all the extents
481 * mentioned in sub from all the extents linked in @bitmap, which leaves
482 * @bitmap as the list of blocks that are not accounted for, which we assume
483 * are the dead blocks of the old metadata structure. The blocks mentioned in
486 * This is the logical equivalent of bitmap &= ~sub.
491 struct xbitmap32 *sub) in xbitmap32_disunion() argument
496 if (xbitmap32_empty(bitmap) || xbitmap32_empty(sub)) in xbitmap32_disunion()
499 for_each_xbitmap32_extent(bn, sub) { in xbitmap32_disunion()
500 error = xbitmap32_clear(bitmap, bn->bn_start, in xbitmap32_disunion()
501 bn->bn_last - bn->bn_start + 1); in xbitmap32_disunion()
518 ret += bn->bn_last - bn->bn_start + 1; in xbitmap32_hweight()
534 error = fn(bn->bn_start, bn->bn_last - bn->bn_start + 1, priv); in xbitmap32_walk()
547 return bitmap->xb_root.rb_root.rb_node == NULL; in xbitmap32_empty()
558 uint32_t last = start + *len - 1; in xbitmap32_test()
560 bn = xbitmap32_tree_iter_first(&bitmap->xb_root, start, last); in xbitmap32_test()
563 if (bn->bn_start <= start) { in xbitmap32_test()
564 if (bn->bn_last < last) in xbitmap32_test()
565 *len = bn->bn_last - start + 1; in xbitmap32_test()
568 *len = bn->bn_start - start; in xbitmap32_test()