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 
27 /*
28  * element of the list
29  */
30 struct ulist_node {
31 	u64 val;		/* value to store */
32 	unsigned long aux;	/* auxiliary value saved along with the val */
33 };
34 
35 struct ulist {
36 	/*
37 	 * number of elements stored in list
38 	 */
39 	unsigned long nnodes;
40 
41 	/*
42 	 * number of nodes we already have room for
43 	 */
44 	unsigned long nodes_alloced;
45 
46 	/*
47 	 * pointer to the array storing the elements. The first ULIST_SIZE
48 	 * elements are stored inline. In this case the it points to int_nodes.
49 	 * After exceeding ULIST_SIZE, dynamic memory is allocated.
50 	 */
51 	struct ulist_node *nodes;
52 
53 	/*
54 	 * inline storage space for the first ULIST_SIZE entries
55 	 */
56 	struct ulist_node int_nodes[ULIST_SIZE];
57 };
58 
59 void ulist_init(struct ulist *ulist);
60 void ulist_fini(struct ulist *ulist);
61 void ulist_reinit(struct ulist *ulist);
62 struct ulist *ulist_alloc(unsigned long gfp_mask);
63 void ulist_free(struct ulist *ulist);
64 int ulist_add(struct ulist *ulist, u64 val, unsigned long aux,
65 	      unsigned long gfp_mask);
66 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_node *prev);
67 
68 #endif
69