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