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 struct ulist_iterator { 28 int i; 29 }; 30 31 /* 32 * element of the list 33 */ 34 struct ulist_node { 35 u64 val; /* value to store */ 36 u64 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); 66 struct ulist *ulist_alloc(gfp_t gfp_mask); 67 void ulist_free(struct ulist *ulist); 68 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask); 69 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, 70 u64 *old_aux, gfp_t gfp_mask); 71 struct ulist_node *ulist_next(struct ulist *ulist, 72 struct ulist_iterator *uiter); 73 74 #define ULIST_ITER_INIT(uiter) ((uiter)->i = 0) 75 76 #endif 77