1 | /* SPDX-License-Identifier: GPL-2.0 */ |
2 | /* |
3 | * Copyright (C) 2011 STRATO AG |
4 | * written by Arne Jansen <sensille@gmx.net> |
5 | */ |
6 | |
7 | #ifndef BTRFS_ULIST_H |
8 | #define BTRFS_ULIST_H |
9 | |
10 | #include <linux/list.h> |
11 | #include <linux/rbtree.h> |
12 | |
13 | /* |
14 | * ulist is a generic data structure to hold a collection of unique u64 |
15 | * values. The only operations it supports is adding to the list and |
16 | * enumerating it. |
17 | * It is possible to store an auxiliary value along with the key. |
18 | * |
19 | */ |
20 | struct ulist_iterator { |
21 | struct list_head *cur_list; /* hint to start search */ |
22 | }; |
23 | |
24 | /* |
25 | * element of the list |
26 | */ |
27 | struct ulist_node { |
28 | u64 val; /* value to store */ |
29 | u64 aux; /* auxiliary value saved along with the val */ |
30 | |
31 | struct list_head list; /* used to link node */ |
32 | struct rb_node rb_node; /* used to speed up search */ |
33 | }; |
34 | |
35 | struct ulist { |
36 | /* |
37 | * number of elements stored in list |
38 | */ |
39 | unsigned long nnodes; |
40 | |
41 | struct list_head nodes; |
42 | struct rb_root root; |
43 | }; |
44 | |
45 | void ulist_init(struct ulist *ulist); |
46 | void ulist_release(struct ulist *ulist); |
47 | void ulist_reinit(struct ulist *ulist); |
48 | struct ulist *ulist_alloc(gfp_t gfp_mask); |
49 | void ulist_free(struct ulist *ulist); |
50 | int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask); |
51 | int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, |
52 | u64 *old_aux, gfp_t gfp_mask); |
53 | int ulist_del(struct ulist *ulist, u64 val, u64 aux); |
54 | |
55 | /* just like ulist_add_merge() but take a pointer for the aux data */ |
56 | static inline int ulist_add_merge_ptr(struct ulist *ulist, u64 val, void *aux, |
57 | void **old_aux, gfp_t gfp_mask) |
58 | { |
59 | #if BITS_PER_LONG == 32 |
60 | u64 old64 = (uintptr_t)*old_aux; |
61 | int ret = ulist_add_merge(ulist, val, (uintptr_t)aux, &old64, gfp_mask); |
62 | *old_aux = (void *)((uintptr_t)old64); |
63 | return ret; |
64 | #else |
65 | return ulist_add_merge(ulist, val, aux: (u64)aux, old_aux: (u64 *)old_aux, gfp_mask); |
66 | #endif |
67 | } |
68 | |
69 | struct ulist_node *ulist_next(const struct ulist *ulist, |
70 | struct ulist_iterator *uiter); |
71 | |
72 | #define ULIST_ITER_INIT(uiter) ((uiter)->cur_list = NULL) |
73 | |
74 | #endif |
75 | |