[deliverable/linux.git] / fs / btrfs / ulist.h

/*
 * 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 <linux/list.h>
#include <linux/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.
 *
 * The implementation is preliminary and can probably be sped up
 * significantly. A first step would be to store the values in an rbtree
 * as soon as ULIST_SIZE is exceeded.
 */

/*
 * number of elements statically allocated inside struct ulist
 */
#define ULIST_SIZE 16

struct ulist_iterator {
	int i;
};

/*
 * element of the list
 */
struct ulist_node {
	u64 val;		/* value to store */
	u64 aux;		/* auxiliary value saved along with the val */
	struct rb_node rb_node;	/* used to speed up search */
};

struct ulist {
	/*
	 * number of elements stored in list
	 */
	unsigned long nnodes;

	/*
	 * number of nodes we already have room for
	 */
	unsigned long nodes_alloced;

	/*
	 * pointer to the array storing the elements. The first ULIST_SIZE
	 * elements are stored inline. In this case the it points to int_nodes.
	 * After exceeding ULIST_SIZE, dynamic memory is allocated.
	 */
	struct ulist_node *nodes;

	struct rb_root root;

	/*
	 * inline storage space for the first ULIST_SIZE entries
	 */
	struct ulist_node int_nodes[ULIST_SIZE];
};

void ulist_init(struct ulist *ulist);
void ulist_fini(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)->i = 0)

#endif
Commit	Line	Data
da5c8135 AJ	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
f7f82b81 WS	11	#include <linux/list.h>
	12	#include <linux/rbtree.h>
	13
da5c8135 AJ	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
cd1b413c JS	30	struct ulist_iterator {
	31	int i;
	32	};
	33
da5c8135 AJ	34	/*
	35	* element of the list
	36	*/
	37	struct ulist_node {
	38	u64 val; /* value to store */
34d73f54	39	u64 aux; /* auxiliary value saved along with the val */
f7f82b81	40	struct rb_node rb_node; /* used to speed up search */
da5c8135 AJ	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
f7f82b81 WS	61	struct rb_root root;
f7f82b81 WS	62
da5c8135 AJ	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);
2eec6c81	72	struct ulist *ulist_alloc(gfp_t gfp_mask);
da5c8135	73	void ulist_free(struct ulist *ulist);
34d73f54 AB	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);
cd1b413c JS	77	struct ulist_node ulist_next(struct ulist ulist,
	78	struct ulist_iterator *uiter);
	79
	80	#define ULIST_ITER_INIT(uiter) ((uiter)->i = 0)
da5c8135 AJ	81
da5c8135 AJ	82	#endif