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 %

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
}