[thirdparty/xfsprogs-dev.git] / repair / slab.c

/*
 * Copyright (C) 2016 Oracle.  All Rights Reserved.
 *
 * Author: Darrick J. Wong <darrick.wong@oracle.com>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA.
 */
#include <libxfs.h>
#include "slab.h"

#undef SLAB_DEBUG

#ifdef SLAB_DEBUG
# define dbg_printf(f, a...)  do {printf(f, ## a); fflush(stdout); } while (0)
#else
# define dbg_printf(f, a...)
#endif

/*
 * Slab Arrays and Bags
 *
 * The slab array is a dynamically growable linear array.  Internally it
 * maintains a list of slabs of increasing size; when a slab fills up, another
 * is allocated.  Each slab is sorted individually, which means that one must
 * use an iterator to walk the entire logical array, sorted order or otherwise.
 * Array items can neither be removed nor accessed randomly, since (at the
 * moment) the only user of them (storing reverse mappings) doesn't need either
 * piece.  Pointers are not stable across sort operations.
 *
 * A bag is a collection of pointers.  The bag can be added to or removed from
 * arbitrarily, and the bag items can be iterated.  Bags are used to process
 * rmaps into refcount btree entries.
 */

/*
 * Slabs -- each slab_hdr holds an array of items; when a slab_hdr fills up, we
 * allocate a new one and add to that one.  The slab object coordinates the
 * slab_hdrs.
 */

/* Each slab holds at least 4096 items */
#define MIN_SLAB_NR		4096
/* and cannot be larger than 128M */
#define MAX_SLAB_SIZE		(128 * 1048576)
struct xfs_slab_hdr {
	size_t			sh_nr;
	size_t			sh_inuse;	/* items in use */
	struct xfs_slab_hdr	*sh_next;	/* next slab hdr */
						/* objects follow */
};

struct xfs_slab {
	size_t			s_item_sz;	/* item size */
	size_t			s_nr_slabs;	/* # of slabs */
	size_t			s_nr_items;	/* # of items */
	struct xfs_slab_hdr	*s_first;	/* first slab header */
	struct xfs_slab_hdr	*s_last;	/* last sh_next pointer */
};

/*
 * Slab cursors -- each slab_hdr_cursor tracks a slab_hdr; the slab_cursor
 * tracks the slab_hdr_cursors.  If a compare_fn is specified, the cursor
 * returns objects in increasing order (if you've previously sorted the
 * slabs with qsort_slab()).  If compare_fn == NULL, it returns slab items
 * in order.
 */
struct xfs_slab_hdr_cursor {
	struct xfs_slab_hdr	*hdr;		/* a slab header */
	size_t			loc;		/* where we are in the slab */
};

typedef int (*xfs_slab_compare_fn)(const void *, const void *);

struct xfs_slab_cursor {
	size_t				nr;		/* # of per-slab cursors */
	struct xfs_slab			*slab;		/* pointer to the slab */
	struct xfs_slab_hdr_cursor	*last_hcur;	/* last header we took from */
	xfs_slab_compare_fn		compare_fn;	/* compare items */
	struct xfs_slab_hdr_cursor	hcur[0];	/* per-slab cursors */
};

/*
 * Bags -- each bag is an array of pointers items; when a bag fills up, we
 * resize it.
 */
#define MIN_BAG_SIZE	4096
struct xfs_bag {
	size_t			bg_nr;		/* number of pointers */
	size_t			bg_inuse;	/* number of slots in use */
	void			**bg_ptrs;	/* pointers */
};
#define BAG_SIZE(nr)	(sizeof(struct xfs_bag) + ((nr) * sizeof(void *)))
#define BAG_END(bag)	(&(bag)->bg_ptrs[(bag)->bg_nr])

/*
 * Create a slab to hold some objects of a particular size.
 */
int
init_slab(
	struct xfs_slab	**slab,
	size_t		item_size)
{
	struct xfs_slab	*ptr;

	ptr = calloc(1, sizeof(struct xfs_slab));
	if (!ptr)
		return -ENOMEM;
	ptr->s_item_sz = item_size;
	ptr->s_last = NULL;
	*slab = ptr;

	return 0;
}

/*
 * Frees a slab.
 */
void
free_slab(
	struct xfs_slab		**slab)
{
	struct xfs_slab		*ptr;
	struct xfs_slab_hdr	*hdr;
	struct xfs_slab_hdr	*nhdr;

	ptr = *slab;
	if (!ptr)
		return;
	hdr = ptr->s_first;
	while (hdr) {
		nhdr = hdr->sh_next;
		free(hdr);
		hdr = nhdr;
	}
	free(ptr);
	*slab = NULL;
}

static void *
slab_ptr(
	struct xfs_slab		*slab,
	struct xfs_slab_hdr	*hdr,
	size_t			idx)
{
	char			*p;

	ASSERT(idx < hdr->sh_inuse);
	p = (char *)(hdr + 1);
	p += slab->s_item_sz * idx;
	return p;
}

/*
 * Add an item to the slab.
 */
int
slab_add(
	struct xfs_slab		*slab,
	void			*item)
{
	struct xfs_slab_hdr		*hdr;
	void			*p;

	hdr = slab->s_last;
	if (!hdr || hdr->sh_inuse == hdr->sh_nr) {
		size_t n;

		n = (hdr ? hdr->sh_nr * 2 : MIN_SLAB_NR);
		if (n * slab->s_item_sz > MAX_SLAB_SIZE)
			n = MAX_SLAB_SIZE / slab->s_item_sz;
		hdr = malloc(sizeof(struct xfs_slab_hdr) + (n * slab->s_item_sz));
		if (!hdr)
			return -ENOMEM;
		hdr->sh_nr = n;
		hdr->sh_inuse = 0;
		hdr->sh_next = NULL;
		if (slab->s_last)
			slab->s_last->sh_next = hdr;
		if (!slab->s_first)
			slab->s_first = hdr;
		slab->s_last = hdr;
		slab->s_nr_slabs++;
	}
	hdr->sh_inuse++;
	p = slab_ptr(slab, hdr, hdr->sh_inuse - 1);
	memcpy(p, item, slab->s_item_sz);
	slab->s_nr_items++;

	return 0;
}

#include "threads.h"

struct qsort_slab {
	struct xfs_slab		*slab;
	struct xfs_slab_hdr	*hdr;
	int			(*compare_fn)(const void *, const void *);
};

static void
qsort_slab_helper(
	struct workqueue	*wq,
	xfs_agnumber_t		agno,
	void			*arg)
{
	struct qsort_slab	*qs = arg;

	qsort(slab_ptr(qs->slab, qs->hdr, 0), qs->hdr->sh_inuse,
			qs->slab->s_item_sz, qs->compare_fn);
	free(qs);
}

/*
 * Sort the items in the slab.  Do not run this method if there are any
 * cursors holding on to the slab.
 */
void
qsort_slab(
	struct xfs_slab		*slab,
	int (*compare_fn)(const void *, const void *))
{
	struct workqueue	wq;
	struct xfs_slab_hdr	*hdr;
	struct qsort_slab	*qs;

	/*
	 * If we don't have that many slabs, we're probably better
	 * off skipping all the thread overhead.
	 */
	if (slab->s_nr_slabs <= 4) {
		hdr = slab->s_first;
		while (hdr) {
			qsort(slab_ptr(slab, hdr, 0), hdr->sh_inuse,
					slab->s_item_sz, compare_fn);
			hdr = hdr->sh_next;
		}
		return;
	}

	create_work_queue(&wq, NULL, libxfs_nproc());
	hdr = slab->s_first;
	while (hdr) {
		qs = malloc(sizeof(struct qsort_slab));
		qs->slab = slab;
		qs->hdr = hdr;
		qs->compare_fn = compare_fn;
		queue_work(&wq, qsort_slab_helper, 0, qs);
		hdr = hdr->sh_next;
	}
	destroy_work_queue(&wq);
}

/*
 * init_slab_cursor() -- Create a slab cursor to iterate the slab items.
 *
 * @slab: The slab.
 * @compare_fn: If specified, use this function to return items in ascending order.
 * @cur: The new cursor.
 */
int
init_slab_cursor(
	struct xfs_slab		*slab,
	int (*compare_fn)(const void *, const void *),
	struct xfs_slab_cursor	**cur)
{
	struct xfs_slab_cursor	*c;
	struct xfs_slab_hdr_cursor	*hcur;
	struct xfs_slab_hdr	*hdr;

	c = malloc(sizeof(struct xfs_slab_cursor) +
		   (sizeof(struct xfs_slab_hdr_cursor) * slab->s_nr_slabs));
	if (!c)
		return -ENOMEM;
	c->nr = slab->s_nr_slabs;
	c->slab = slab;
	c->compare_fn = compare_fn;
	c->last_hcur = NULL;
	hcur = (struct xfs_slab_hdr_cursor *)(c + 1);
	hdr = slab->s_first;
	while (hdr) {
		hcur->hdr = hdr;
		hcur->loc = 0;
		hcur++;
		hdr = hdr->sh_next;
	}
	*cur = c;
	return 0;
}

/*
 * Free the slab cursor.
 */
void
free_slab_cursor(
	struct xfs_slab_cursor	**cur)
{
	if (!*cur)
		return;
	free(*cur);
	*cur = NULL;
}

/*
 * Return the smallest item in the slab, without advancing the iterator.
 * The slabs must be sorted prior to the creation of the cursor.
 */
void *
peek_slab_cursor(
	struct xfs_slab_cursor	*cur)
{
	struct xfs_slab_hdr_cursor	*hcur;
	void			*p = NULL;
	void			*q;
	size_t			i;

	cur->last_hcur = NULL;

	/* no compare function; inorder traversal */
	if (!cur->compare_fn) {
		if (!cur->last_hcur)
			cur->last_hcur = &cur->hcur[0];
		hcur = cur->last_hcur;
		while (hcur < &cur->hcur[cur->nr] &&
			hcur->loc >= hcur->hdr->sh_inuse)
			hcur++;
		if (hcur == &cur->hcur[cur->nr])
			return NULL;
		p = slab_ptr(cur->slab, hcur->hdr, hcur->loc);
		cur->last_hcur = hcur;
		return p;
	}

	/* otherwise return things in increasing order */
	for (i = 0, hcur = &cur->hcur[i]; i < cur->nr; i++, hcur++) {
		if (hcur->loc >= hcur->hdr->sh_inuse)
			continue;
		q = slab_ptr(cur->slab, hcur->hdr, hcur->loc);
		if (!p || cur->compare_fn(p, q) > 0) {
			p = q;
			cur->last_hcur = hcur;
		}
	}

	return p;
}

/*
 * After a peek operation, advance the cursor.
 */
void
advance_slab_cursor(
	struct xfs_slab_cursor	*cur)
{
	ASSERT(cur->last_hcur);
	cur->last_hcur->loc++;
}

/*
 * Retrieve the next item in the slab and advance the cursor.
 */
void *
pop_slab_cursor(
	struct xfs_slab_cursor	*cur)
{
	void			*p;

	p = peek_slab_cursor(cur);
	if (p)
		advance_slab_cursor(cur);
	return p;
}

/*
 * Return the number of items in the slab.
 */
size_t
slab_count(
	struct xfs_slab	*slab)
{
	return slab->s_nr_items;
}

/*
 * Create a bag to point to some objects.
 */
int
init_bag(
	struct xfs_bag	**bag)
{
	struct xfs_bag	*ptr;

	ptr = calloc(1, sizeof(struct xfs_bag));
	if (!ptr)
		return -ENOMEM;
	ptr->bg_ptrs = calloc(MIN_BAG_SIZE, sizeof(void *));
	if (!ptr->bg_ptrs) {
		free(ptr);
		return -ENOMEM;
	}
	ptr->bg_nr = MIN_BAG_SIZE;
	*bag = ptr;
	return 0;
}

/*
 * Free a bag of pointers.
 */
void
free_bag(
	struct xfs_bag	**bag)
{
	struct xfs_bag	*ptr;

	ptr = *bag;
	if (!ptr)
		return;
	free(ptr->bg_ptrs);
	free(ptr);
	*bag = NULL;
}

/*
 * Add an object to the pointer bag.
 */
int
bag_add(
	struct xfs_bag	*bag,
	void		*ptr)
{
	void		**p, **x;

	p = &bag->bg_ptrs[bag->bg_inuse];
	if (p == BAG_END(bag)) {
		/* No free space, alloc more pointers */
		size_t nr;

		nr = bag->bg_nr * 2;
		x = realloc(bag->bg_ptrs, nr * sizeof(void *));
		if (!x)
			return -ENOMEM;
		bag->bg_ptrs = x;
		memset(BAG_END(bag), 0, bag->bg_nr * sizeof(void *));
		bag->bg_nr = nr;
	}
	bag->bg_ptrs[bag->bg_inuse] = ptr;
	bag->bg_inuse++;
	return 0;
}

/*
 * Remove a pointer from a bag.
 */
int
bag_remove(
	struct xfs_bag	*bag,
	size_t		nr)
{
	ASSERT(nr < bag->bg_inuse);
	memmove(&bag->bg_ptrs[nr], &bag->bg_ptrs[nr + 1],
		(bag->bg_inuse - nr - 1) * sizeof(void *));
	bag->bg_inuse--;
	return 0;
}

/*
 * Return the number of items in a bag.
 */
size_t
bag_count(
	struct xfs_bag	*bag)
{
	return bag->bg_inuse;
}

/*
 * Return the nth item in a bag.
 */
void *
bag_item(
	struct xfs_bag	*bag,
	size_t		nr)
{
	if (nr >= bag->bg_inuse)
		return NULL;
	return bag->bg_ptrs[nr];
}
Commit	Line	Data
9c9990ba DW	1	/*
	2	* Copyright (C) 2016 Oracle. All Rights Reserved.
	3	*
	4	* Author: Darrick J. Wong <darrick.wong@oracle.com>
	5	*
	6	* This program is free software; you can redistribute it and/or
	7	* modify it under the terms of the GNU General Public License
	8	* as published by the Free Software Foundation; either version 2
	9	* of the License, or (at your option) any later version.
	10	*
	11	* This program is distributed in the hope that it would be useful,
	12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	* GNU General Public License for more details.
	15	*
	16	* You should have received a copy of the GNU General Public License
	17	* along with this program; if not, write the Free Software Foundation,
	18	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
	19	*/
	20	#include <libxfs.h>
	21	#include "slab.h"
	22
	23	#undef SLAB_DEBUG
	24
	25	#ifdef SLAB_DEBUG
	26	# define dbg_printf(f, a...) do {printf(f, ## a); fflush(stdout); } while (0)
	27	#else
	28	# define dbg_printf(f, a...)
	29	#endif
	30
	31	/*
	32	* Slab Arrays and Bags
	33	*
	34	* The slab array is a dynamically growable linear array. Internally it
	35	* maintains a list of slabs of increasing size; when a slab fills up, another
	36	* is allocated. Each slab is sorted individually, which means that one must
	37	* use an iterator to walk the entire logical array, sorted order or otherwise.
	38	* Array items can neither be removed nor accessed randomly, since (at the
	39	* moment) the only user of them (storing reverse mappings) doesn't need either
	40	* piece. Pointers are not stable across sort operations.
	41	*
	42	* A bag is a collection of pointers. The bag can be added to or removed from
	43	* arbitrarily, and the bag items can be iterated. Bags are used to process
	44	* rmaps into refcount btree entries.
	45	*/
	46
	47	/*
	48	* Slabs -- each slab_hdr holds an array of items; when a slab_hdr fills up, we
	49	* allocate a new one and add to that one. The slab object coordinates the
	50	* slab_hdrs.
	51	*/
	52
	53	/* Each slab holds at least 4096 items */
	54	#define MIN_SLAB_NR 4096
	55	/* and cannot be larger than 128M */
	56	#define MAX_SLAB_SIZE (128 * 1048576)
	57	struct xfs_slab_hdr {
	58	size_t sh_nr;
	59	size_t sh_inuse; /* items in use */
	60	struct xfs_slab_hdr sh_next; / next slab hdr */
	61	/* objects follow */
	62	};
	63
	64	struct xfs_slab {
65	size_t s_item_sz; /* item size */
66	size_t s_nr_slabs; /* # of slabs */
67	size_t s_nr_items; /* # of items */
68	struct xfs_slab_hdr s_first; / first slab header */
69	struct xfs_slab_hdr s_last; / last sh_next pointer */
70	};
71
72	/*
73	* Slab cursors -- each slab_hdr_cursor tracks a slab_hdr; the slab_cursor
74	* tracks the slab_hdr_cursors. If a compare_fn is specified, the cursor
75	* returns objects in increasing order (if you've previously sorted the
76	* slabs with qsort_slab()). If compare_fn == NULL, it returns slab items
77	* in order.
78	*/
79	struct xfs_slab_hdr_cursor {
80	struct xfs_slab_hdr hdr; / a slab header */
81	size_t loc; /* where we are in the slab */
82	};
83
84	typedef int (xfs_slab_compare_fn)(const void , const void *);
85
86	struct xfs_slab_cursor {
87	size_t nr; /* # of per-slab cursors */
88	struct xfs_slab slab; / pointer to the slab */
89	struct xfs_slab_hdr_cursor last_hcur; / last header we took from */
90	xfs_slab_compare_fn compare_fn; /* compare items */
91	struct xfs_slab_hdr_cursor hcur[0]; /* per-slab cursors */
92	};
93
94	/*
95	* Bags -- each bag is an array of pointers items; when a bag fills up, we
96	* resize it.
97	*/
98	#define MIN_BAG_SIZE 4096
99	struct xfs_bag {
100	size_t bg_nr; /* number of pointers */
101	size_t bg_inuse; /* number of slots in use */
102	void *bg_ptrs; / pointers */
103	};
104	#define BAG_SIZE(nr) (sizeof(struct xfs_bag) + ((nr) * sizeof(void *)))
105	#define BAG_END(bag) (&(bag)->bg_ptrs[(bag)->bg_nr])
106
107	/*
108	* Create a slab to hold some objects of a particular size.
109	*/
110	int
111	init_slab(
112	struct xfs_slab **slab,
113	size_t item_size)
114	{
115	struct xfs_slab *ptr;
116
117	ptr = calloc(1, sizeof(struct xfs_slab));
118	if (!ptr)
119	return -ENOMEM;
120	ptr->s_item_sz = item_size;
121	ptr->s_last = NULL;
122	*slab = ptr;
123
124	return 0;
125	}
126
127	/*
128	* Frees a slab.
129	*/
130	void
131	free_slab(
132	struct xfs_slab **slab)
133	{
134	struct xfs_slab *ptr;
135	struct xfs_slab_hdr *hdr;
136	struct xfs_slab_hdr *nhdr;
137
138	ptr = *slab;
139	if (!ptr)
140	return;
141	hdr = ptr->s_first;
142	while (hdr) {
143	nhdr = hdr->sh_next;
144	free(hdr);
145	hdr = nhdr;
146	}
147	free(ptr);
148	*slab = NULL;
149	}
150
151	static void *
152	slab_ptr(
153	struct xfs_slab *slab,
154	struct xfs_slab_hdr *hdr,
155	size_t idx)
156	{
157	char *p;
158
159	ASSERT(idx < hdr->sh_inuse);
160	p = (char *)(hdr + 1);
161	p += slab->s_item_sz * idx;
162	return p;
163	}
164
165	/*
166	* Add an item to the slab.
167	*/
168	int
169	slab_add(
170	struct xfs_slab *slab,
171	void *item)
172	{
173	struct xfs_slab_hdr *hdr;
174	void *p;
175
176	hdr = slab->s_last;
177	if (!hdr \|\| hdr->sh_inuse == hdr->sh_nr) {
178	size_t n;
179
180	n = (hdr ? hdr->sh_nr * 2 : MIN_SLAB_NR);
181	if (n * slab->s_item_sz > MAX_SLAB_SIZE)
182	n = MAX_SLAB_SIZE / slab->s_item_sz;
183	hdr = malloc(sizeof(struct xfs_slab_hdr) + (n * slab->s_item_sz));
184	if (!hdr)
185	return -ENOMEM;
186	hdr->sh_nr = n;
187	hdr->sh_inuse = 0;
188	hdr->sh_next = NULL;
189	if (slab->s_last)
190	slab->s_last->sh_next = hdr;
191	if (!slab->s_first)
192	slab->s_first = hdr;
193	slab->s_last = hdr;
194	slab->s_nr_slabs++;
195	}
196	hdr->sh_inuse++;
197	p = slab_ptr(slab, hdr, hdr->sh_inuse - 1);
198	memcpy(p, item, slab->s_item_sz);
199	slab->s_nr_items++;
200
201	return 0;
202	}
203
39bbc0a9 DW	204	#include "threads.h"
	205
	206	struct qsort_slab {
	207	struct xfs_slab *slab;
	208	struct xfs_slab_hdr *hdr;
	209	int (compare_fn)(const void , const void *);
	210	};
	211
	212	static void
	213	qsort_slab_helper(
62843f36	214	struct workqueue *wq,
39bbc0a9 DW	215	xfs_agnumber_t agno,
	216	void *arg)
	217	{
	218	struct qsort_slab *qs = arg;
	219
	220	qsort(slab_ptr(qs->slab, qs->hdr, 0), qs->hdr->sh_inuse,
	221	qs->slab->s_item_sz, qs->compare_fn);
	222	free(qs);
	223	}
	224
9c9990ba DW	225	/*
	226	* Sort the items in the slab. Do not run this method if there are any
	227	* cursors holding on to the slab.
	228	*/
	229	void
	230	qsort_slab(
	231	struct xfs_slab *slab,
	232	int (compare_fn)(const void , const void *))
	233	{
62843f36	234	struct workqueue wq;
9c9990ba	235	struct xfs_slab_hdr *hdr;
39bbc0a9 DW	236	struct qsort_slab *qs;
	237
	238	/*
	239	* If we don't have that many slabs, we're probably better
	240	* off skipping all the thread overhead.
	241	*/
	242	if (slab->s_nr_slabs <= 4) {
	243	hdr = slab->s_first;
	244	while (hdr) {
	245	qsort(slab_ptr(slab, hdr, 0), hdr->sh_inuse,
	246	slab->s_item_sz, compare_fn);
	247	hdr = hdr->sh_next;
	248	}
	249	return;
	250	}
9c9990ba	251
39bbc0a9	252	create_work_queue(&wq, NULL, libxfs_nproc());
9c9990ba DW	253	hdr = slab->s_first;
9c9990ba DW	254	while (hdr) {
39bbc0a9 DW	255	qs = malloc(sizeof(struct qsort_slab));
	256	qs->slab = slab;
	257	qs->hdr = hdr;
	258	qs->compare_fn = compare_fn;
	259	queue_work(&wq, qsort_slab_helper, 0, qs);
9c9990ba DW	260	hdr = hdr->sh_next;
9c9990ba DW	261	}
39bbc0a9	262	destroy_work_queue(&wq);
9c9990ba DW	263	}
	264
	265	/*
	266	* init_slab_cursor() -- Create a slab cursor to iterate the slab items.
	267	*
	268	* @slab: The slab.
	269	* @compare_fn: If specified, use this function to return items in ascending order.
	270	* @cur: The new cursor.
	271	*/
	272	int
	273	init_slab_cursor(
	274	struct xfs_slab *slab,
	275	int (compare_fn)(const void , const void *),
	276	struct xfs_slab_cursor **cur)
	277	{
	278	struct xfs_slab_cursor *c;
	279	struct xfs_slab_hdr_cursor *hcur;
	280	struct xfs_slab_hdr *hdr;
	281
	282	c = malloc(sizeof(struct xfs_slab_cursor) +
	283	(sizeof(struct xfs_slab_hdr_cursor) * slab->s_nr_slabs));
	284	if (!c)
	285	return -ENOMEM;
	286	c->nr = slab->s_nr_slabs;
	287	c->slab = slab;
	288	c->compare_fn = compare_fn;
	289	c->last_hcur = NULL;
	290	hcur = (struct xfs_slab_hdr_cursor *)(c + 1);
	291	hdr = slab->s_first;
	292	while (hdr) {
	293	hcur->hdr = hdr;
	294	hcur->loc = 0;
	295	hcur++;
	296	hdr = hdr->sh_next;
	297	}
	298	*cur = c;
	299	return 0;
	300	}
	301
	302	/*
	303	* Free the slab cursor.
	304	*/
	305	void
	306	free_slab_cursor(
	307	struct xfs_slab_cursor **cur)
	308	{
	309	if (!*cur)
	310	return;
	311	free(*cur);
	312	*cur = NULL;
	313	}
	314
	315	/*
	316	* Return the smallest item in the slab, without advancing the iterator.
	317	* The slabs must be sorted prior to the creation of the cursor.
	318	*/
	319	void *
	320	peek_slab_cursor(
	321	struct xfs_slab_cursor *cur)
	322	{
	323	struct xfs_slab_hdr_cursor *hcur;
	324	void *p = NULL;
	325	void *q;
	326	size_t i;
327
328	cur->last_hcur = NULL;
329
330	/* no compare function; inorder traversal */
331	if (!cur->compare_fn) {
332	if (!cur->last_hcur)
333	cur->last_hcur = &cur->hcur[0];
334	hcur = cur->last_hcur;
335	while (hcur < &cur->hcur[cur->nr] &&
336	hcur->loc >= hcur->hdr->sh_inuse)
337	hcur++;
338	if (hcur == &cur->hcur[cur->nr])
339	return NULL;
340	p = slab_ptr(cur->slab, hcur->hdr, hcur->loc);
341	cur->last_hcur = hcur;
342	return p;
343	}
344
345	/* otherwise return things in increasing order */
346	for (i = 0, hcur = &cur->hcur[i]; i < cur->nr; i++, hcur++) {
347	if (hcur->loc >= hcur->hdr->sh_inuse)
348	continue;
349	q = slab_ptr(cur->slab, hcur->hdr, hcur->loc);
350	if (!p \|\| cur->compare_fn(p, q) > 0) {
351	p = q;
352	cur->last_hcur = hcur;
353	}
354	}
355
356	return p;
357	}
358
359	/*
360	* After a peek operation, advance the cursor.
361	*/
362	void
363	advance_slab_cursor(
364	struct xfs_slab_cursor *cur)
365	{
366	ASSERT(cur->last_hcur);
367	cur->last_hcur->loc++;
368	}
369
370	/*
371	* Retrieve the next item in the slab and advance the cursor.
372	*/
373	void *
374	pop_slab_cursor(
375	struct xfs_slab_cursor *cur)
376	{
377	void *p;
378
379	p = peek_slab_cursor(cur);
380	if (p)
381	advance_slab_cursor(cur);
382	return p;
383	}
384
385	/*
386	* Return the number of items in the slab.
387	*/
388	size_t
389	slab_count(
390	struct xfs_slab *slab)
391	{
392	return slab->s_nr_items;
393	}
394
395	/*
396	* Create a bag to point to some objects.
397	*/
398	int
399	init_bag(
400	struct xfs_bag **bag)
401	{
402	struct xfs_bag *ptr;
403
404	ptr = calloc(1, sizeof(struct xfs_bag));
405	if (!ptr)
406	return -ENOMEM;
407	ptr->bg_ptrs = calloc(MIN_BAG_SIZE, sizeof(void *));
408	if (!ptr->bg_ptrs) {
409	free(ptr);
410	return -ENOMEM;
411	}
412	ptr->bg_nr = MIN_BAG_SIZE;
413	*bag = ptr;
414	return 0;
415	}
416
417	/*
418	* Free a bag of pointers.
419	*/
420	void
421	free_bag(
422	struct xfs_bag **bag)
423	{
424	struct xfs_bag *ptr;
425
426	ptr = *bag;
427	if (!ptr)
428	return;
429	free(ptr->bg_ptrs);
430	free(ptr);
431	*bag = NULL;
432	}
433
434	/*
435	* Add an object to the pointer bag.
436	*/
437	int
438	bag_add(
439	struct xfs_bag *bag,
440	void *ptr)
441	{
442	void p, x;
443
444	p = &bag->bg_ptrs[bag->bg_inuse];
445	if (p == BAG_END(bag)) {
446	/* No free space, alloc more pointers */
447	size_t nr;
448
449	nr = bag->bg_nr * 2;
450	x = realloc(bag->bg_ptrs, nr * sizeof(void *));
451	if (!x)
452	return -ENOMEM;
453	bag->bg_ptrs = x;
454	memset(BAG_END(bag), 0, bag->bg_nr * sizeof(void *));
455	bag->bg_nr = nr;
456	}
457	bag->bg_ptrs[bag->bg_inuse] = ptr;
458	bag->bg_inuse++;
459	return 0;
460	}
461
462	/*
463	* Remove a pointer from a bag.
464	*/
465	int
466	bag_remove(
467	struct xfs_bag *bag,
468	size_t nr)
469	{
470	ASSERT(nr < bag->bg_inuse);
471	memmove(&bag->bg_ptrs[nr], &bag->bg_ptrs[nr + 1],
4cf0d1f7	472	(bag->bg_inuse - nr - 1) * sizeof(void *));
9c9990ba DW	473	bag->bg_inuse--;
	474	return 0;
	475	}
	476
	477	/*
	478	* Return the number of items in a bag.
	479	*/
	480	size_t
	481	bag_count(
	482	struct xfs_bag *bag)
	483	{
	484	return bag->bg_inuse;
	485	}
	486
	487	/*
	488	* Return the nth item in a bag.
	489	*/
	490	void *
	491	bag_item(
	492	struct xfs_bag *bag,
	493	size_t nr)
	494	{
	495	if (nr >= bag->bg_inuse)
	496	return NULL;
	497	return bag->bg_ptrs[nr];
	498	}