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 | ||
11 | /* | |
12 | * ulist is a generic data structure to hold a collection of unique u64 | |
13 | * values. The only operations it supports is adding to the list and | |
14 | * enumerating it. | |
15 | * It is possible to store an auxiliary value along with the key. | |
16 | * | |
17 | * The implementation is preliminary and can probably be sped up | |
18 | * significantly. A first step would be to store the values in an rbtree | |
19 | * as soon as ULIST_SIZE is exceeded. | |
20 | */ | |
21 | ||
22 | /* | |
23 | * number of elements statically allocated inside struct ulist | |
24 | */ | |
25 | #define ULIST_SIZE 16 | |
26 | ||
cd1b413c JS |
27 | struct ulist_iterator { |
28 | int i; | |
29 | }; | |
30 | ||
da5c8135 AJ |
31 | /* |
32 | * element of the list | |
33 | */ | |
34 | struct ulist_node { | |
35 | u64 val; /* value to store */ | |
36 | unsigned long aux; /* auxiliary value saved along with the val */ | |
37 | }; | |
38 | ||
39 | struct ulist { | |
40 | /* | |
41 | * number of elements stored in list | |
42 | */ | |
43 | unsigned long nnodes; | |
44 | ||
45 | /* | |
46 | * number of nodes we already have room for | |
47 | */ | |
48 | unsigned long nodes_alloced; | |
49 | ||
50 | /* | |
51 | * pointer to the array storing the elements. The first ULIST_SIZE | |
52 | * elements are stored inline. In this case the it points to int_nodes. | |
53 | * After exceeding ULIST_SIZE, dynamic memory is allocated. | |
54 | */ | |
55 | struct ulist_node *nodes; | |
56 | ||
57 | /* | |
58 | * inline storage space for the first ULIST_SIZE entries | |
59 | */ | |
60 | struct ulist_node int_nodes[ULIST_SIZE]; | |
61 | }; | |
62 | ||
63 | void ulist_init(struct ulist *ulist); | |
64 | void ulist_fini(struct ulist *ulist); | |
65 | void ulist_reinit(struct ulist *ulist); | |
2eec6c81 | 66 | struct ulist *ulist_alloc(gfp_t gfp_mask); |
da5c8135 AJ |
67 | void ulist_free(struct ulist *ulist); |
68 | int ulist_add(struct ulist *ulist, u64 val, unsigned long aux, | |
1e20932a | 69 | gfp_t gfp_mask); |
3301958b | 70 | int ulist_add_merge(struct ulist *ulist, u64 val, unsigned long aux, |
1e20932a | 71 | unsigned long *old_aux, gfp_t gfp_mask); |
cd1b413c JS |
72 | struct ulist_node *ulist_next(struct ulist *ulist, |
73 | struct ulist_iterator *uiter); | |
74 | ||
75 | #define ULIST_ITER_INIT(uiter) ((uiter)->i = 0) | |
da5c8135 AJ |
76 | |
77 | #endif |