diff options
author | Mark Fasheh <mfasheh@suse.de> | 2014-05-07 13:07:16 -0700 |
---|---|---|
committer | David Sterba <dsterba@suse.cz> | 2014-08-22 14:39:33 +0200 |
commit | 2ab405af95d43972b57c7806981220a6949df643 (patch) | |
tree | 0e8a1c39ba870c923bb4c193f64b0be8e97a5167 /ulist.h | |
parent | 2dfafb471004bdd78c191d14d2792eb9ec391987 (diff) |
btrfs-progs: import ulist
qgroup-verify.c wants this for walking root refs.
Signed-off-by: Mark Fasheh <mfasheh@suse.de>
Signed-off-by: David Sterba <dsterba@suse.cz>
Diffstat (limited to 'ulist.h')
-rw-r--r-- | ulist.h | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/ulist.h b/ulist.h new file mode 100644 index 00000000..2a0e9489 --- /dev/null +++ b/ulist.h @@ -0,0 +1,66 @@ +/* + * Copyright (C) 2011 STRATO AG + * written by Arne Jansen <sensille@gmx.net> + * Distributed under the GNU GPL license version 2. + * + */ + +#ifndef __ULIST__ +#define __ULIST__ + +#include "kerncompat.h" +#include "list.h" +#include "rbtree.h" + +/* + * ulist is a generic data structure to hold a collection of unique u64 + * values. The only operations it supports is adding to the list and + * enumerating it. + * It is possible to store an auxiliary value along with the key. + * + */ +struct ulist_iterator { +#ifdef CONFIG_BTRFS_DEBUG + int i; +#endif + struct list_head *cur_list; /* hint to start search */ +}; + +/* + * element of the list + */ +struct ulist_node { + u64 val; /* value to store */ + u64 aux; /* auxiliary value saved along with the val */ + +#ifdef CONFIG_BTRFS_DEBUG + int seqnum; /* sequence number this node is added */ +#endif + + struct list_head list; /* used to link node */ + struct rb_node rb_node; /* used to speed up search */ +}; + +struct ulist { + /* + * number of elements stored in list + */ + unsigned long nnodes; + + struct list_head nodes; + struct rb_root root; +}; + +void ulist_init(struct ulist *ulist); +void ulist_reinit(struct ulist *ulist); +struct ulist *ulist_alloc(gfp_t gfp_mask); +void ulist_free(struct ulist *ulist); +int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask); +int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, + u64 *old_aux, gfp_t gfp_mask); +struct ulist_node *ulist_next(struct ulist *ulist, + struct ulist_iterator *uiter); + +#define ULIST_ITER_INIT(uiter) ((uiter)->cur_list = NULL) + +#endif |