tjh.dev
Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
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