]>
Commit | Line | Data |
---|---|---|
da5c8135 AJ |
1 | /* |
2 | * Copyright (C) 2011 STRATO AG | |
3 | * written by Arne Jansen <sensille@gmx.net> | |
4 | * Distributed under the GNU GPL license version 2. | |
5 | * | |
6 | */ | |
7 | ||
8 | #ifndef __ULIST__ | |
9 | #define __ULIST__ | |
10 | ||
f7f82b81 WS |
11 | #include <linux/list.h> |
12 | #include <linux/rbtree.h> | |
13 | ||
da5c8135 AJ |
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 | * | |
da5c8135 | 20 | */ |
cd1b413c | 21 | struct ulist_iterator { |
4c7a6f74 | 22 | struct list_head *cur_list; /* hint to start search */ |
cd1b413c JS |
23 | }; |
24 | ||
da5c8135 AJ |
25 | /* |
26 | * element of the list | |
27 | */ | |
28 | struct ulist_node { | |
29 | u64 val; /* value to store */ | |
34d73f54 | 30 | u64 aux; /* auxiliary value saved along with the val */ |
4c7a6f74 | 31 | |
4c7a6f74 | 32 | struct list_head list; /* used to link node */ |
f7f82b81 | 33 | struct rb_node rb_node; /* used to speed up search */ |
da5c8135 AJ |
34 | }; |
35 | ||
36 | struct ulist { | |
37 | /* | |
38 | * number of elements stored in list | |
39 | */ | |
40 | unsigned long nnodes; | |
41 | ||
4c7a6f74 | 42 | struct list_head nodes; |
f7f82b81 | 43 | struct rb_root root; |
da5c8135 AJ |
44 | }; |
45 | ||
46 | void ulist_init(struct ulist *ulist); | |
6655bc3d | 47 | void ulist_release(struct ulist *ulist); |
da5c8135 | 48 | void ulist_reinit(struct ulist *ulist); |
2eec6c81 | 49 | struct ulist *ulist_alloc(gfp_t gfp_mask); |
da5c8135 | 50 | void ulist_free(struct ulist *ulist); |
34d73f54 AB |
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); | |
d4b80404 | 54 | int ulist_del(struct ulist *ulist, u64 val, u64 aux); |
4eb1f66d TI |
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, (u64)aux, (u64 *)old_aux, gfp_mask); | |
67 | #endif | |
68 | } | |
69 | ||
cd1b413c JS |
70 | struct ulist_node *ulist_next(struct ulist *ulist, |
71 | struct ulist_iterator *uiter); | |
72 | ||
4c7a6f74 | 73 | #define ULIST_ITER_INIT(uiter) ((uiter)->cur_list = NULL) |
da5c8135 AJ |
74 | |
75 | #endif |