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