[linux-block.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__

/*
 * 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 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;

	/*
	 * 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
	11	/*
	12	* ulist is a generic data structure to hold a collection of unique u64
	13	* values. The only operations it supports is adding to the list and
	14	* enumerating it.
	15	* It is possible to store an auxiliary value along with the key.
	16	*
	17	* The implementation is preliminary and can probably be sped up
	18	* significantly. A first step would be to store the values in an rbtree
	19	* as soon as ULIST_SIZE is exceeded.
	20	*/
	21
	22	/*
	23	* number of elements statically allocated inside struct ulist
	24	*/
	25	#define ULIST_SIZE 16
	26
cd1b413c JS	27	struct ulist_iterator {
	28	int i;
	29	};
	30
da5c8135 AJ	31	/*
	32	* element of the list
	33	*/
	34	struct ulist_node {
	35	u64 val; /* value to store */
34d73f54	36	u64 aux; /* auxiliary value saved along with the val */
da5c8135 AJ	37	};
	38
	39	struct ulist {
	40	/*
	41	* number of elements stored in list
	42	*/
	43	unsigned long nnodes;
	44
	45	/*
	46	* number of nodes we already have room for
	47	*/
	48	unsigned long nodes_alloced;
	49
	50	/*
	51	* pointer to the array storing the elements. The first ULIST_SIZE
	52	* elements are stored inline. In this case the it points to int_nodes.
	53	* After exceeding ULIST_SIZE, dynamic memory is allocated.
	54	*/
	55	struct ulist_node *nodes;
	56
	57	/*
	58	* inline storage space for the first ULIST_SIZE entries
	59	*/
	60	struct ulist_node int_nodes[ULIST_SIZE];
	61	};
	62
	63	void ulist_init(struct ulist *ulist);
	64	void ulist_fini(struct ulist *ulist);
	65	void ulist_reinit(struct ulist *ulist);
2eec6c81	66	struct ulist *ulist_alloc(gfp_t gfp_mask);
da5c8135	67	void ulist_free(struct ulist *ulist);
34d73f54 AB	68	int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask);
	69	int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
	70	u64 *old_aux, gfp_t gfp_mask);
cd1b413c JS	71	struct ulist_node ulist_next(struct ulist ulist,
	72	struct ulist_iterator *uiter);
	73
	74	#define ULIST_ITER_INIT(uiter) ((uiter)->i = 0)
da5c8135 AJ	75
da5c8135 AJ	76	#endif