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