| 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 | */ |
| 21 | struct ulist_iterator { |
| 22 | #ifdef CONFIG_BTRFS_DEBUG |
| 23 | int i; |
| 24 | #endif |
| 25 | struct list_head *cur_list; /* hint to start search */ |
| 26 | }; |
| 27 | |
| 28 | /* |
| 29 | * element of the list |
| 30 | */ |
| 31 | struct ulist_node { |
| 32 | u64 val; /* value to store */ |
| 33 | u64 aux; /* auxiliary value saved along with the val */ |
| 34 | |
| 35 | #ifdef CONFIG_BTRFS_DEBUG |
| 36 | int seqnum; /* sequence number this node is added */ |
| 37 | #endif |
| 38 | |
| 39 | struct list_head list; /* used to link node */ |
| 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 | struct list_head nodes; |
| 50 | struct rb_root root; |
| 51 | }; |
| 52 | |
| 53 | void ulist_init(struct ulist *ulist); |
| 54 | void ulist_reinit(struct ulist *ulist); |
| 55 | struct ulist *ulist_alloc(gfp_t gfp_mask); |
| 56 | void ulist_free(struct ulist *ulist); |
| 57 | int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask); |
| 58 | int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, |
| 59 | u64 *old_aux, gfp_t gfp_mask); |
| 60 | |
| 61 | /* just like ulist_add_merge() but take a pointer for the aux data */ |
| 62 | static inline int ulist_add_merge_ptr(struct ulist *ulist, u64 val, void *aux, |
| 63 | void **old_aux, gfp_t gfp_mask) |
| 64 | { |
| 65 | #if BITS_PER_LONG == 32 |
| 66 | u64 old64 = (uintptr_t)*old_aux; |
| 67 | int ret = ulist_add_merge(ulist, val, (uintptr_t)aux, &old64, gfp_mask); |
| 68 | *old_aux = (void *)((uintptr_t)old64); |
| 69 | return ret; |
| 70 | #else |
| 71 | return ulist_add_merge(ulist, val, (u64)aux, (u64 *)old_aux, gfp_mask); |
| 72 | #endif |
| 73 | } |
| 74 | |
| 75 | struct ulist_node *ulist_next(struct ulist *ulist, |
| 76 | struct ulist_iterator *uiter); |
| 77 | |
| 78 | #define ULIST_ITER_INIT(uiter) ((uiter)->cur_list = NULL) |
| 79 | |
| 80 | #endif |