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 30struct ulist_iterator { 31 int i; 32}; 33 34/* 35 * element of the list 36 */ 37struct 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 43struct 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 69void ulist_init(struct ulist *ulist); 70void ulist_fini(struct ulist *ulist); 71void ulist_reinit(struct ulist *ulist); 72struct ulist *ulist_alloc(gfp_t gfp_mask); 73void ulist_free(struct ulist *ulist); 74int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask); 75int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, 76 u64 *old_aux, gfp_t gfp_mask); 77struct 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