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

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