Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/npppd/npppd/../common/slist.c	Lines:	0	152	0.0 %
Date:	2017-11-13	Branches:	0	178	0.0 %


/*	$OpenBSD: slist.c,v 1.7 2015/12/17 07:56:01 tb Exp $ */
/*-
 * Copyright (c) 2009 Internet Initiative Japan Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
/**@file
 * provide list accesses against any pointer
 */
/*
 *	void **list;
 *	list_size;	// allocated size for the list
 *	last_idx;	// The last index
 *	first_idx;	// The first index
 *
 * - first_idx == last_idx means empty.
 * - 0 <= (fist_idx and last_idx) <= (list_size - 1)
 * - Allocated size is (last_idx - first_idx) % list_size.
 *   To make the code for checking empty and full simple, we use only
 *   list_size-1 items instead of using the full size.
 * - XXX Wnen itr_curr is removed...
 */
#include <sys/types.h>

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "slist.h"

#define	GROW_SIZE	256
#define	PTR_SIZE	(sizeof(intptr_t))

#ifdef	SLIST_DEBUG
#include <stdio.h>
#define	SLIST_ASSERT(cond)			\
	if (!(cond)) {							\
		fprintf(stderr,						\
		    "\nAssertion failure("#cond") at (%s):%s:%d\n",	\
		    __func__, __FILE__, __LINE__);			\
	}
#else
#define	SLIST_ASSERT(cond)
#endif

/**
 * Returns 1 if a index is in the valid range, otherwise returns 0.
 */
#define	VALID_IDX(_list, _idx)					\
	  (((_list)->first_idx <= (_list)->last_idx)			\
	? (((_list)->first_idx <= (_idx) && (_idx) < (_list)->last_idx)? 1 : 0)\
	: (((_list)->first_idx <= (_idx) || (_idx) < (_list)->last_idx)? 1 : 0))

/** Convert an index into the internal index */
#define	REAL_IDX(_list, _idx)						\
	(((_list)->first_idx + (_idx)) % (_list)->list_size)

/** Convert a virtual index into the index */
#define	VIRT_IDX(_list, _idx)	(((_list)->first_idx <= (_idx))	\
	? (_idx) - (_list)->first_idx				\
	: (_list)->list_size - (_list)->first_idx + (_idx))

/** Decrement an index */
#define	DECR_IDX(_list, _memb)						\
	(_list)->_memb = ((_list)->list_size + --((_list)->_memb))	\
	    % (_list)->list_size
/** Increment an index */
#define	INCR_IDX(_list, _memb)						\
	(_list)->_memb = (++((_list)->_memb)) % (_list)->list_size

static int          slist_grow (slist *);
static int          slist_grow0 (slist *, int);
static __inline void  slist_swap0 (slist *, int, int);
static __inline void  slist_qsort0(slist *, int (*)(const void *, const void *), int, int);

#define	itr_is_valid(list)	((list)->itr_next >= 0)
#define	itr_invalidate(list)	((list)->itr_next = -1)

/** Initialize a slist */
void
slist_init(slist *list)
{
	memset(list, 0, sizeof(slist));
	itr_invalidate(list);
}

/**
 * Specify the size of a list. The size must be specified with the size you
 * want to use +1. Extra 1 entry is for internal use. The size doesn't shrink.
 */
int
slist_set_size(slist *list, int size)
{
	if (size > list->list_size)
		return slist_grow0(list, size - list->list_size);

	return 0;
}

/** Finish using. Free the buffers and reinit. */
void
slist_fini(slist *list)
{
	free(list->list);
	slist_init(list);
}

/** The length of the list */
int
slist_length(slist *list)
{
	return
	      (list->first_idx <= list->last_idx)
	    ? (list->last_idx - list->first_idx)
	    : (list->list_size - list->first_idx + list->last_idx);
}

/** Extend the size. Used if the list is full. */
static int
slist_grow0(slist *list, int grow_sz)
{
	int size_new;
	void **list_new = NULL;

 	/* just return if it is possible to add one item */
	if (slist_length(list) + 1 < list->list_size)
		/* "+ 1" to avoid the situation list_size == slist_length() */
		return 0;

	size_new = list->list_size + grow_sz;
	if ((list_new = realloc(list->list, PTR_SIZE * size_new))
	    == NULL)
		return -1;

	memset(&list_new[list->list_size], 0,
	    PTR_SIZE * (size_new - list->list_size));

	list->list = list_new;
	if (list->last_idx < list->first_idx && list->last_idx >= 0) {

		/*
		 * space is created at the right side when center has space,
		 * so move left side to right side
		 */
		if (list->last_idx <= grow_sz) {
			/*
			 * The right side has enough space, so move the left
			 * side to right side.
			 */
			memmove(&list->list[list->list_size],
			    &list->list[0], PTR_SIZE * list->last_idx);
			list->last_idx = list->list_size + list->last_idx;
		} else {
			/*
			 * Copy the left side to right side as long as we
			 * can
			 */
			memmove(&list->list[list->list_size],
			    &list->list[0], PTR_SIZE * grow_sz);
			/* Shift the remain to left */
			memmove(&list->list[0], &list->list[grow_sz],
			    PTR_SIZE *(list->last_idx - grow_sz));

			list->last_idx -= grow_sz;
		}
	}
	list->list_size = size_new;

	return 0;
}

static int
slist_grow(slist *list)
{
	return slist_grow0(list, GROW_SIZE);
}

/** Add an item to a list */
void *
slist_add(slist *list, void *item)
{
	if (slist_grow(list) != 0)
		return NULL;

	list->list[list->last_idx] = item;

	if (list->itr_next == -2) {
		/* the iterator points the last, update it. */
		list->itr_next = list->last_idx;
	}

	INCR_IDX(list, last_idx);

	return item;
}

#define slist_get0(list_, idx)	((list_)->list[REAL_IDX((list_), (idx))])

/** Add all items in add_items to a list. */
int
slist_add_all(slist *list, slist *add_items)
{
	int i, n;

	n = slist_length(add_items);
	for (i = 0; i < n; i++) {
		if (slist_add(list, slist_get0(add_items, i)) ==  NULL)
			return 1;
	}

	return 0;
}

/** Return "idx"th item. */
void *
slist_get(slist *list, int idx)
{
	SLIST_ASSERT(idx >= 0);
	SLIST_ASSERT(slist_length(list) > idx);

	if (idx < 0 || slist_length(list) <= idx)
		return NULL;

	return slist_get0(list, idx);
}

/** Store a value in "idx"th item */
int
slist_set(slist *list, int idx, void *item)
{
	SLIST_ASSERT(idx >= 0);
	SLIST_ASSERT(slist_length(list) > idx);

	if (idx < 0 || slist_length(list) <= idx)
		return -1;

	list->list[REAL_IDX(list, idx)] = item;

	return 0;
}

/** Remove the 1st entry and return it. */
void *
slist_remove_first(slist *list)
{
	void *oldVal;

	if (slist_length(list) <= 0)
		return NULL;

	oldVal = list->list[list->first_idx];

	if (itr_is_valid(list) && list->itr_next == list->first_idx)
		INCR_IDX(list, itr_next);

	if (!VALID_IDX(list, list->itr_next))
		itr_invalidate(list);

	INCR_IDX(list, first_idx);

	return oldVal;
}

/** Remove the last entry and return it */
void *
slist_remove_last(slist *list)
{
	if (slist_length(list) <= 0)
		return NULL;

	DECR_IDX(list, last_idx);
	if (!VALID_IDX(list, list->itr_next))
		itr_invalidate(list);

	return list->list[list->last_idx];
}

/** Remove all entries */
void
slist_remove_all(slist *list)
{
	void **list0 = list->list;

	slist_init(list);

	list->list = list0;
}

/* Swap items. This doesn't check boudary. */
static __inline void
slist_swap0(slist *list, int m, int n)
{
	void *m0;

	itr_invalidate(list);	/* Invalidate iterator */

	m0 = list->list[REAL_IDX(list, m)];
	list->list[REAL_IDX(list, m)] = list->list[REAL_IDX(list, n)];
	list->list[REAL_IDX(list, n)] = m0;
}

/** Swap between mth and nth */
void
slist_swap(slist *list, int m, int n)
{
	int len;

	len = slist_length(list);
	SLIST_ASSERT(m >= 0);
	SLIST_ASSERT(n >= 0);
	SLIST_ASSERT(len > m);
	SLIST_ASSERT(len > n);

	if (m < 0 || n < 0)
		return;
	if (m >= len || n >= len)
		return;

	slist_swap0(list, m, n);
}

/** Remove "idx"th item */
void *
slist_remove(slist *list, int idx)
{
	int first, last, idx0, reset_itr;
	void *oldVal;

	SLIST_ASSERT(idx >= 0);
	SLIST_ASSERT(slist_length(list) > idx);

	if (idx < 0 || slist_length(list) <= idx)
		return NULL;

	idx0 = REAL_IDX(list, idx);
	oldVal = list->list[idx0];
	reset_itr = 0;

	first = -1;
	last = -1;

	if (list->itr_next == idx0) {
		INCR_IDX(list, itr_next);
		if (!VALID_IDX(list, list->itr_next))
			list->itr_next = -2;	/* on the last item */
	}

	/* should we reduce the last side or the first side? */
	if (list->first_idx < list->last_idx) {
		/* take the smaller side */
		if (idx0 - list->first_idx < list->last_idx - idx0) {
			first = list->first_idx;
			INCR_IDX(list, first_idx);
		} else {
			last = list->last_idx;
			DECR_IDX(list, last_idx);
		}
	} else {
		/*
		 * 0 < last (unused) first < idx < size, so let's reduce the
		 * first.
		 */
		if (list->first_idx <= idx0) {
			first = list->first_idx;
			INCR_IDX(list, first_idx);
		} else {
			last = list->last_idx;
			DECR_IDX(list, last_idx);
		}
	}

	/* the last side */
	if (last != -1 && last != 0 && last != idx0) {

		/* move left the items that is from idx0 to the last */
		if (itr_is_valid(list) &&
		    idx0 <= list->itr_next && list->itr_next <= last) {
			DECR_IDX(list, itr_next);
			if (!VALID_IDX(list, list->itr_next))
				itr_invalidate(list);
		}

		memmove(&list->list[idx0], &list->list[idx0 + 1],
		    (PTR_SIZE) * (last - idx0));
	}
	/* the first side */
	if (first != -1 && first != idx0) {

		/* move right the items that is from first to the idx0 */
		if (itr_is_valid(list) &&
		    first <= list->itr_next && list->itr_next <= idx0) {
			INCR_IDX(list, itr_next);
			if (!VALID_IDX(list, list->itr_next))
				itr_invalidate(list);
		}

		memmove(&list->list[first + 1], &list->list[first],
		    (PTR_SIZE) * (idx0 - first));
	}
	if (list->first_idx == list->last_idx) {
		list->first_idx = 0;
		list->last_idx = 0;
	}

	return oldVal;
}

/**
 * Shuffle items.
 */
void
slist_shuffle(slist *list)
{
	int i, len;

	len = slist_length(list);
	for (i = len; i > 1; i--)
		slist_swap0(list, i - 1, (int)arc4random_uniform(i));
}

/** Init an iterator. Only one iterator exists.  */
void
slist_itr_first(slist *list)
{
	list->itr_next = list->first_idx;
	if (!VALID_IDX(list, list->itr_next))
		itr_invalidate(list);
}

/**
 * Return whether a iterator can go to the next item.
 * @return Return 1 if the iterator can return the next item.
 *	Return 0 it reaches the end of the list or the list is modified
 *	destructively.
 */
int
slist_itr_has_next(slist *list)
{
	if (list->itr_next < 0)
		return 0;
	return VALID_IDX(list, list->itr_next);
}

/** Return the next item and iterate to the next */
void *
slist_itr_next(slist *list)
{
	void *rval;

	if (!itr_is_valid(list))
		return NULL;
	SLIST_ASSERT(VALID_IDX(list, list->itr_next));

	if (list->list == NULL)
		return NULL;

	rval = list->list[list->itr_next];
	list->itr_curr = list->itr_next;
	INCR_IDX(list, itr_next);

	if (!VALID_IDX(list, list->itr_next))
		list->itr_next = -2;	/* on the last item */

	return rval;
}

/** Delete the current iterated item  */
void *
slist_itr_remove(slist *list)
{
	SLIST_ASSERT(list != NULL);

	return slist_remove(list, VIRT_IDX(list, list->itr_curr));
}

/** Sort the list items by quick sort algorithm using given compar */
void
slist_qsort(slist *list, int (*compar)(const void *, const void *))
{
	if (list->first_idx != list->last_idx)	/* is not empty */
		slist_qsort0(list, compar, 0, slist_length(list) - 1);
}

static __inline void
slist_qsort0(slist *list, int (*compar)(const void *, const void *), int l,
    int r)
{
	int i, j;
	void *p;

	i = l;
	j = r;
	p = slist_get0(list, (j + i) / 2);
	while (i <= j) {
		while (compar(slist_get0(list, i), p) < 0)
			i++;
		while (compar(slist_get0(list, j), p) > 0)
			j--;
		if (i <= j)
			slist_swap0(list, i++, j--);
	}
	if (l < j)
		slist_qsort0(list, compar, l, j);
	if (i < r)
		slist_qsort0(list, compar, i, r);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: slist.c,v 1.7 2015/12/17 07:56:01 tb Exp $ */
2			/*-
3			* Copyright (c) 2009 Internet Initiative Japan Inc.
4			* All rights reserved.
5			*
6			* Redistribution and use in source and binary forms, with or without
7			* modification, are permitted provided that the following conditions
8			* are met:
9			* 1. Redistributions of source code must retain the above copyright
10			* notice, this list of conditions and the following disclaimer.
11			* 2. Redistributions in binary form must reproduce the above copyright
12			* notice, this list of conditions and the following disclaimer in the
13			* documentation and/or other materials provided with the distribution.
14			*
15			* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16			* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18			* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19			* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20			* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21			* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23			* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24			* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25			* SUCH DAMAGE.
26			*/
27			/**@file
28			* provide list accesses against any pointer
29			*/
30			/*
31			* void **list;
32			* list_size; // allocated size for the list
33			* last_idx; // The last index
34			* first_idx; // The first index
35			*
36			* - first_idx == last_idx means empty.
37			* - 0 <= (fist_idx and last_idx) <= (list_size - 1)
38			* - Allocated size is (last_idx - first_idx) % list_size.
39			* To make the code for checking empty and full simple, we use only
40			* list_size-1 items instead of using the full size.
41			* - XXX Wnen itr_curr is removed...
42			*/
43			#include <sys/types.h>
44
45			#include <stdint.h>
46			#include <stdlib.h>
47			#include <string.h>
48
49			#include "slist.h"
50
51			#define GROW_SIZE 256
52			#define PTR_SIZE (sizeof(intptr_t))
53
54			#ifdef SLIST_DEBUG
55			#include <stdio.h>
56			#define SLIST_ASSERT(cond) \
57			if (!(cond)) { \
58			fprintf(stderr, \
59			"\nAssertion failure("#cond") at (%s):%s:%d\n", \
60			__func__, __FILE__, __LINE__); \
61			}
62			#else
63			#define SLIST_ASSERT(cond)
64			#endif
65
66			/**
67			* Returns 1 if a index is in the valid range, otherwise returns 0.
68			*/
69			#define VALID_IDX(_list, _idx) \
70			(((_list)->first_idx <= (_list)->last_idx) \
71			? (((_list)->first_idx <= (_idx) && (_idx) < (_list)->last_idx)? 1 : 0)\
72			: (((_list)->first_idx <= (_idx) \|\| (_idx) < (_list)->last_idx)? 1 : 0))
73
74			/** Convert an index into the internal index */
75			#define REAL_IDX(_list, _idx) \
76			(((_list)->first_idx + (_idx)) % (_list)->list_size)
77
78			/** Convert a virtual index into the index */
79			#define VIRT_IDX(_list, _idx) (((_list)->first_idx <= (_idx)) \
80			? (_idx) - (_list)->first_idx \
81			: (_list)->list_size - (_list)->first_idx + (_idx))
82
83			/** Decrement an index */
84			#define DECR_IDX(_list, _memb) \
85			(_list)->_memb = ((_list)->list_size + --((_list)->_memb)) \
86			% (_list)->list_size
87			/** Increment an index */
88			#define INCR_IDX(_list, _memb) \
89			(_list)->_memb = (++((_list)->_memb)) % (_list)->list_size
90
91			static int slist_grow (slist *);
92			static int slist_grow0 (slist *, int);
93			static __inline void slist_swap0 (slist *, int, int);
94			static __inline void slist_qsort0(slist , int ()(const void , const void ), int, int);
95
96			#define itr_is_valid(list) ((list)->itr_next >= 0)
97			#define itr_invalidate(list) ((list)->itr_next = -1)
98
99			/** Initialize a slist */
100			void
101			slist_init(slist *list)
102			{
103			memset(list, 0, sizeof(slist));
104			itr_invalidate(list);
105			}
106
107			/**
108			* Specify the size of a list. The size must be specified with the size you
109			* want to use +1. Extra 1 entry is for internal use. The size doesn't shrink.
110			*/
111			int
112			slist_set_size(slist *list, int size)
113			{
114			if (size > list->list_size)
115			return slist_grow0(list, size - list->list_size);
116
117			return 0;
118			}
119
120			/** Finish using. Free the buffers and reinit. */
121			void
122			slist_fini(slist *list)
123			{
124			free(list->list);
125			slist_init(list);
126			}
127
128			/** The length of the list */
129			int
130			slist_length(slist *list)
131			{
132			return
133			(list->first_idx <= list->last_idx)
134			? (list->last_idx - list->first_idx)
135			: (list->list_size - list->first_idx + list->last_idx);
136			}
137
138			/** Extend the size. Used if the list is full. */
139			static int
140			slist_grow0(slist *list, int grow_sz)
141			{
142			int size_new;
143			void **list_new = NULL;
144
145			/* just return if it is possible to add one item */
146			if (slist_length(list) + 1 < list->list_size)
147			/* "+ 1" to avoid the situation list_size == slist_length() */
148			return 0;
149
150			size_new = list->list_size + grow_sz;
151			if ((list_new = realloc(list->list, PTR_SIZE * size_new))
152			== NULL)
153			return -1;
154
155			memset(&list_new[list->list_size], 0,
156			PTR_SIZE * (size_new - list->list_size));
157
158			list->list = list_new;
159			if (list->last_idx < list->first_idx && list->last_idx >= 0) {
160
161			/*
162			* space is created at the right side when center has space,
163			* so move left side to right side
164			*/
165			if (list->last_idx <= grow_sz) {
166			/*
167			* The right side has enough space, so move the left
168			* side to right side.
169			*/
170			memmove(&list->list[list->list_size],
171			&list->list[0], PTR_SIZE * list->last_idx);
172			list->last_idx = list->list_size + list->last_idx;
173			} else {
174			/*
175			* Copy the left side to right side as long as we
176			* can
177			*/
178			memmove(&list->list[list->list_size],
179			&list->list[0], PTR_SIZE * grow_sz);
180			/* Shift the remain to left */
181			memmove(&list->list[0], &list->list[grow_sz],
182			PTR_SIZE *(list->last_idx - grow_sz));
183
184			list->last_idx -= grow_sz;
185			}
186			}
187			list->list_size = size_new;
188
189			return 0;
190			}
191
192			static int
193			slist_grow(slist *list)
194			{
195			return slist_grow0(list, GROW_SIZE);
196			}
197
198			/** Add an item to a list */
199			void *
200			slist_add(slist list, void item)
201			{
202			if (slist_grow(list) != 0)
203			return NULL;
204
205			list->list[list->last_idx] = item;
206
207			if (list->itr_next == -2) {
208			/* the iterator points the last, update it. */
209			list->itr_next = list->last_idx;
210			}
211
212			INCR_IDX(list, last_idx);
213
214			return item;
215			}
216
217			#define slist_get0(list_, idx) ((list_)->list[REAL_IDX((list_), (idx))])
218
219			/** Add all items in add_items to a list. */
220			int
221			slist_add_all(slist list, slist add_items)
222			{
223			int i, n;
224
225			n = slist_length(add_items);
226			for (i = 0; i < n; i++) {
227			if (slist_add(list, slist_get0(add_items, i)) == NULL)
228			return 1;
229			}
230
231			return 0;
232			}
233
234			/** Return "idx"th item. */
235			void *
236			slist_get(slist *list, int idx)
237			{
238			SLIST_ASSERT(idx >= 0);
239			SLIST_ASSERT(slist_length(list) > idx);
240
241			if (idx < 0 \|\| slist_length(list) <= idx)
242			return NULL;
243
244			return slist_get0(list, idx);
245			}
246
247			/** Store a value in "idx"th item */
248			int
249			slist_set(slist list, int idx, void item)
250			{
251			SLIST_ASSERT(idx >= 0);
252			SLIST_ASSERT(slist_length(list) > idx);
253
254			if (idx < 0 \|\| slist_length(list) <= idx)
255			return -1;
256
257			list->list[REAL_IDX(list, idx)] = item;
258
259			return 0;
260			}
261
262			/** Remove the 1st entry and return it. */
263			void *
264			slist_remove_first(slist *list)
265			{
266			void *oldVal;
267
268			if (slist_length(list) <= 0)
269			return NULL;
270
271			oldVal = list->list[list->first_idx];
272
273			if (itr_is_valid(list) && list->itr_next == list->first_idx)
274			INCR_IDX(list, itr_next);
275
276			if (!VALID_IDX(list, list->itr_next))
277			itr_invalidate(list);
278
279			INCR_IDX(list, first_idx);
280
281			return oldVal;
282			}
283
284			/** Remove the last entry and return it */
285			void *
286			slist_remove_last(slist *list)
287			{
288			if (slist_length(list) <= 0)
289			return NULL;
290
291			DECR_IDX(list, last_idx);
292			if (!VALID_IDX(list, list->itr_next))
293			itr_invalidate(list);
294
295			return list->list[list->last_idx];
296			}
297
298			/** Remove all entries */
299			void
300			slist_remove_all(slist *list)
301			{
302			void **list0 = list->list;
303
304			slist_init(list);
305
306			list->list = list0;
307			}
308
309			/* Swap items. This doesn't check boudary. */
310			static __inline void
311			slist_swap0(slist *list, int m, int n)
312			{
313			void *m0;
314
315			itr_invalidate(list); /* Invalidate iterator */
316
317			m0 = list->list[REAL_IDX(list, m)];
318			list->list[REAL_IDX(list, m)] = list->list[REAL_IDX(list, n)];
319			list->list[REAL_IDX(list, n)] = m0;
320			}
321
322			/** Swap between mth and nth */
323			void
324			slist_swap(slist *list, int m, int n)
325			{
326			int len;
327
328			len = slist_length(list);
329			SLIST_ASSERT(m >= 0);
330			SLIST_ASSERT(n >= 0);
331			SLIST_ASSERT(len > m);
332			SLIST_ASSERT(len > n);
333
334			if (m < 0 \|\| n < 0)
335			return;
336			if (m >= len \|\| n >= len)
337			return;
338
339			slist_swap0(list, m, n);
340			}
341
342			/** Remove "idx"th item */
343			void *
344			slist_remove(slist *list, int idx)
345			{
346			int first, last, idx0, reset_itr;
347			void *oldVal;
348
349			SLIST_ASSERT(idx >= 0);
350			SLIST_ASSERT(slist_length(list) > idx);
351
352			if (idx < 0 \|\| slist_length(list) <= idx)
353			return NULL;
354
355			idx0 = REAL_IDX(list, idx);
356			oldVal = list->list[idx0];
357			reset_itr = 0;
358
359			first = -1;
360			last = -1;
361
362			if (list->itr_next == idx0) {
363			INCR_IDX(list, itr_next);
364			if (!VALID_IDX(list, list->itr_next))
365			list->itr_next = -2; /* on the last item */
366			}
367
368			/* should we reduce the last side or the first side? */
369			if (list->first_idx < list->last_idx) {
370			/* take the smaller side */
371			if (idx0 - list->first_idx < list->last_idx - idx0) {
372			first = list->first_idx;
373			INCR_IDX(list, first_idx);
374			} else {
375			last = list->last_idx;
376			DECR_IDX(list, last_idx);
377			}
378			} else {
379			/*
380			* 0 < last (unused) first < idx < size, so let's reduce the
381			* first.
382			*/
383			if (list->first_idx <= idx0) {
384			first = list->first_idx;
385			INCR_IDX(list, first_idx);
386			} else {
387			last = list->last_idx;
388			DECR_IDX(list, last_idx);
389			}
390			}
391
392			/* the last side */
393			if (last != -1 && last != 0 && last != idx0) {
394
395			/* move left the items that is from idx0 to the last */
396			if (itr_is_valid(list) &&
397			idx0 <= list->itr_next && list->itr_next <= last) {
398			DECR_IDX(list, itr_next);
399			if (!VALID_IDX(list, list->itr_next))
400			itr_invalidate(list);
401			}
402
403			memmove(&list->list[idx0], &list->list[idx0 + 1],
404			(PTR_SIZE) * (last - idx0));
405			}
406			/* the first side */
407			if (first != -1 && first != idx0) {
408
409			/* move right the items that is from first to the idx0 */
410			if (itr_is_valid(list) &&
411			first <= list->itr_next && list->itr_next <= idx0) {
412			INCR_IDX(list, itr_next);
413			if (!VALID_IDX(list, list->itr_next))
414			itr_invalidate(list);
415			}
416
417			memmove(&list->list[first + 1], &list->list[first],
418			(PTR_SIZE) * (idx0 - first));
419			}
420			if (list->first_idx == list->last_idx) {
421			list->first_idx = 0;
422			list->last_idx = 0;
423			}
424
425			return oldVal;
426			}
427
428			/**
429			* Shuffle items.
430			*/
431			void
432			slist_shuffle(slist *list)
433			{
434			int i, len;
435
436			len = slist_length(list);
437			for (i = len; i > 1; i--)
438			slist_swap0(list, i - 1, (int)arc4random_uniform(i));
439			}
440
441			/** Init an iterator. Only one iterator exists. */
442			void
443			slist_itr_first(slist *list)
444			{
445			list->itr_next = list->first_idx;
446			if (!VALID_IDX(list, list->itr_next))
447			itr_invalidate(list);
448			}
449
450			/**
451			* Return whether a iterator can go to the next item.
452			* @return Return 1 if the iterator can return the next item.
453			* Return 0 it reaches the end of the list or the list is modified
454			* destructively.
455			*/
456			int
457			slist_itr_has_next(slist *list)
458			{
459			if (list->itr_next < 0)
460			return 0;
461			return VALID_IDX(list, list->itr_next);
462			}
463
464			/** Return the next item and iterate to the next */
465			void *
466			slist_itr_next(slist *list)
467			{
468			void *rval;
469
470			if (!itr_is_valid(list))
471			return NULL;
472			SLIST_ASSERT(VALID_IDX(list, list->itr_next));
473
474			if (list->list == NULL)
475			return NULL;
476
477			rval = list->list[list->itr_next];
478			list->itr_curr = list->itr_next;
479			INCR_IDX(list, itr_next);
480
481			if (!VALID_IDX(list, list->itr_next))
482			list->itr_next = -2; /* on the last item */
483
484			return rval;
485			}
486
487			/** Delete the current iterated item */
488			void *
489			slist_itr_remove(slist *list)
490			{
491			SLIST_ASSERT(list != NULL);
492
493			return slist_remove(list, VIRT_IDX(list, list->itr_curr));
494			}
495
496			/** Sort the list items by quick sort algorithm using given compar */
497			void
498			slist_qsort(slist list, int (compar)(const void , const void ))
499			{
500			if (list->first_idx != list->last_idx) /* is not empty */
501			slist_qsort0(list, compar, 0, slist_length(list) - 1);
502			}
503
504			static __inline void
505			slist_qsort0(slist list, int (compar)(const void , const void ), int l,
506			int r)
507			{
508			int i, j;
509			void *p;
510
511			i = l;
512			j = r;
513			p = slist_get0(list, (j + i) / 2);
514			while (i <= j) {
515			while (compar(slist_get0(list, i), p) < 0)
516			i++;
517			while (compar(slist_get0(list, j), p) > 0)
518			j--;
519			if (i <= j)
520			slist_swap0(list, i++, j--);
521			}
522			if (l < j)
523			slist_qsort0(list, compar, l, j);
524			if (i < r)
525			slist_qsort0(list, compar, i, r);
526			}