]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - libfrog/bitmap.c
1 // SPDX-License-Identifier: GPL-2.0+
3 * Copyright (C) 2018 Oracle. All Rights Reserved.
4 * Author: Darrick J. Wong <darrick.wong@oracle.com>
11 #include "platform_defs.h"
17 * Space Efficient Bitmap
19 * Implements a space-efficient bitmap. We use an AVL tree to manage
20 * extent records that tell us which ranges are set; the bitmap key is
21 * an arbitrary uint64_t. The usual bitmap operations (set, clear,
22 * test, test and set) are supported, plus we can iterate set ranges.
25 #define avl_for_each_range_safe(pos, n, l, first, last) \
26 for (pos = (first), n = pos->avl_nextino, l = (last)->avl_nextino; pos != (l); \
27 pos = n, n = pos ? pos->avl_nextino : NULL)
29 #define avl_for_each_safe(tree, pos, n) \
30 for (pos = (tree)->avl_firstino, n = pos ? pos->avl_nextino : NULL; \
32 pos = n, n = pos ? pos->avl_nextino : NULL)
34 #define avl_for_each(tree, pos) \
35 for (pos = (tree)->avl_firstino; pos != NULL; pos = pos->avl_nextino)
38 struct avl64node btn_node
;
45 struct avl64node
*node
)
47 struct bitmap_node
*btn
;
49 btn
= container_of(node
, struct bitmap_node
, btn_node
);
50 return btn
->btn_start
;
55 struct avl64node
*node
)
57 struct bitmap_node
*btn
;
59 btn
= container_of(node
, struct bitmap_node
, btn_node
);
60 return btn
->btn_start
+ btn
->btn_length
;
63 static struct avl64ops bitmap_ops
= {
68 /* Initialize a bitmap. */
71 struct bitmap
**bmapp
)
75 bmap
= calloc(1, sizeof(struct bitmap
));
78 bmap
->bt_tree
= malloc(sizeof(struct avl64tree_desc
));
84 pthread_mutex_init(&bmap
->bt_lock
, NULL
);
85 avl64_init_tree(bmap
->bt_tree
, &bitmap_ops
);
94 struct bitmap
**bmapp
)
97 struct avl64node
*node
;
99 struct bitmap_node
*ext
;
102 avl_for_each_safe(bmap
->bt_tree
, node
, n
) {
103 ext
= container_of(node
, struct bitmap_node
, btn_node
);
111 /* Create a new bitmap extent node. */
112 static struct bitmap_node
*
117 struct bitmap_node
*ext
;
119 ext
= malloc(sizeof(struct bitmap_node
));
123 ext
->btn_node
.avl_nextino
= NULL
;
124 ext
->btn_start
= start
;
125 ext
->btn_length
= len
;
130 /* Create a new bitmap node and insert it. */
137 struct bitmap_node
*ext
;
138 struct avl64node
*node
;
140 ext
= bitmap_node_init(start
, length
);
144 node
= avl64_insert(bmap
->bt_tree
, &ext
->btn_node
);
153 /* Set a region of bits (locked). */
160 struct avl64node
*firstn
;
161 struct avl64node
*lastn
;
162 struct avl64node
*pos
;
165 struct bitmap_node
*ext
;
169 /* Find any existing nodes adjacent or within that range. */
170 avl64_findranges(bmap
->bt_tree
, start
- 1, start
+ length
+ 1,
173 /* Nothing, just insert a new extent. */
174 if (firstn
== NULL
&& lastn
== NULL
)
175 return __bitmap_insert(bmap
, start
, length
);
177 assert(firstn
!= NULL
&& lastn
!= NULL
);
181 avl_for_each_range_safe(pos
, n
, l
, firstn
, lastn
) {
182 ext
= container_of(pos
, struct bitmap_node
, btn_node
);
184 /* Bail if the new extent is contained within an old one. */
185 if (ext
->btn_start
<= start
&&
186 ext
->btn_start
+ ext
->btn_length
>= start
+ length
)
189 /* Check for overlapping and adjacent extents. */
190 if (ext
->btn_start
+ ext
->btn_length
>= start
||
191 ext
->btn_start
<= start
+ length
) {
192 if (ext
->btn_start
< start
) {
193 new_start
= ext
->btn_start
;
194 new_length
+= ext
->btn_length
;
197 if (ext
->btn_start
+ ext
->btn_length
>
198 new_start
+ new_length
)
199 new_length
= ext
->btn_start
+ ext
->btn_length
-
202 avl64_delete(bmap
->bt_tree
, pos
);
207 return __bitmap_insert(bmap
, new_start
, new_length
);
210 /* Set a region of bits. */
219 pthread_mutex_lock(&bmap
->bt_lock
);
220 res
= __bitmap_set(bmap
, start
, length
);
221 pthread_mutex_unlock(&bmap
->bt_lock
);
226 #if 0 /* Unused, provided for completeness. */
227 /* Clear a region of bits. */
234 struct avl64node
*firstn
;
235 struct avl64node
*lastn
;
236 struct avl64node
*pos
;
239 struct bitmap_node
*ext
;
242 struct avl64node
*node
;
245 pthread_mutex_lock(&bmap
->bt_lock
);
246 /* Find any existing nodes over that range. */
247 avl64_findranges(bmap
->bt_tree
, start
, start
+ len
, &firstn
, &lastn
);
249 /* Nothing, we're done. */
250 if (firstn
== NULL
&& lastn
== NULL
) {
251 pthread_mutex_unlock(&bmap
->bt_lock
);
255 assert(firstn
!= NULL
&& lastn
!= NULL
);
257 /* Delete or truncate everything in sight. */
258 avl_for_each_range_safe(pos
, n
, l
, firstn
, lastn
) {
259 ext
= container_of(pos
, struct bitmap_node
, btn_node
);
262 if (ext
->btn_start
< start
)
264 if (ext
->btn_start
+ ext
->btn_length
> start
+ len
)
268 /* Extent totally within range; delete. */
269 avl64_delete(bmap
->bt_tree
, pos
);
273 /* Extent is left-adjacent; truncate. */
274 ext
->btn_length
= start
- ext
->btn_start
;
277 /* Extent is right-adjacent; move it. */
278 ext
->btn_length
= ext
->btn_start
+ ext
->btn_length
-
280 ext
->btn_start
= start
+ len
;
283 /* Extent overlaps both ends. */
284 ext
->btn_length
= start
- ext
->btn_start
;
285 new_start
= start
+ len
;
286 new_length
= ext
->btn_start
+ ext
->btn_length
-
289 ext
= bitmap_node_init(new_start
, new_length
);
293 node
= avl64_insert(bmap
->bt_tree
, &ext
->btn_node
);
302 pthread_mutex_unlock(&bmap
->bt_lock
);
308 /* Iterate the set regions of this bitmap. */
312 int (*fn
)(uint64_t, uint64_t, void *),
315 struct avl64node
*node
;
316 struct bitmap_node
*ext
;
319 pthread_mutex_lock(&bmap
->bt_lock
);
320 avl_for_each(bmap
->bt_tree
, node
) {
321 ext
= container_of(node
, struct bitmap_node
, btn_node
);
322 error
= fn(ext
->btn_start
, ext
->btn_length
, arg
);
326 pthread_mutex_unlock(&bmap
->bt_lock
);
332 /* Do any bitmap extents overlap the given one? (locked) */
339 struct avl64node
*firstn
;
340 struct avl64node
*lastn
;
342 /* Find any existing nodes over that range. */
343 avl64_findranges(bmap
->bt_tree
, start
, start
+ len
, &firstn
, &lastn
);
345 return firstn
!= NULL
&& lastn
!= NULL
;
348 /* Is any part of this range set? */
357 pthread_mutex_lock(&bmap
->bt_lock
);
358 res
= __bitmap_test(bmap
, start
, len
);
359 pthread_mutex_unlock(&bmap
->bt_lock
);
364 /* Are none of the bits set? */
369 return bmap
->bt_tree
->avl_firstino
== NULL
;
379 printf("%"PRIu64
":%"PRIu64
"\n", startblock
, blockcount
);
388 printf("BITMAP DUMP %p\n", bmap
);
389 bitmap_iterate(bmap
, bitmap_dump_fn
, NULL
);
390 printf("BITMAP DUMP DONE\n");