| Arne Jansen | da5c813 | 2011-09-13 12:29:12 +0200 | [diff] [blame] | 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 |