xref: /illumos-gate/usr/src/cmd/sgs/common/alist.c (revision fb12490a)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 #include <sgs.h>
27 #include <string.h>
28 #include <stdio.h>
29 #include <sys/debug.h>
30 
31 /*
32  * Alist manipulation.  An Alist is a list of elements formed into an array.
33  * Traversal of the list is an array scan, which because of the locality of
34  * each reference is probably more efficient than a link-list traversal.
35  *
36  * See alist.h for more background information about array lists.
37  */
38 
39 /*
40  * Insert a value into an array at a specified index:
41  *
42  *	alist_insert(): Insert an item into an Alist at the specified index
43  *	alist_insert_by_offset(): Insert an item into an Alist at the
44  *		specified offset relative to the list address.
45  *	aplist_insert() Insert a pointer into an APlist at the specified index
46  *
47  * entry:
48  *	Note: All the arguments for all three routines are listed here.
49  *	The routine to which a given argument applies is given with
50  *	each description.
51  *
52  *	llp [all] - Address of a pointer to an Alist/APlist. The pointer should
53  *		be initialized to NULL before its first use.
54  *	datap [alist_insert / aplist_insert] - Pointer to item data, or
55  *		NULL. If non-null the data referenced is copied into the
56  *		Alist item. Otherwise, the list item is zeroed, and
57  *		further initialization is left to the caller.
58  *	ptr [aplist_insert] - Pointer to be inserted.
59  *	size [alist_insert / alist_insert_by_offset] - Size of an item
60  *		in the array list, in bytes. As with any array, A given
61  *		Alist can support any item size, but every item in that
62  *		list must have the same size.
63  *	init_arritems [all] - Initial allocation size: On the first insertion
64  *		into the array list, room for init_arritems items is allocated.
65  *	idx [alist_insert / aplist_insert] - Index at which to insert the
66  *		new item. This index must lie within the existing list,
67  *		or be the next index following.
68  *	off [alist_insert_by_offset] - Offset at which  to insert the new
69  *		item, based from the start of the Alist. The offset of
70  *		the first item is ALIST_OFF_DATA.
71  *
72  * exit:
73  *	The item is inserted at the specified position. This operation
74  *	can cause memory for the list to be allocated, or reallocated,
75  *	either of which will cause the value of the list pointer
76  *	to change.
77  *
78  *	These routines can only fail if unable to allocate memory,
79  *	in which case NULL is returned.
80  *
81  *	If a pointer list (aplist_insert), then the pointer
82  *	is stored in the requested index. On success, the address
83  *	of the pointer within the list is returned.
84  *
85  *	If the list contains arbitrary data (not aplist_insert): If datap
86  *	is non-NULL, the data it references is copied into the item at
87  *	the index. If datap is NULL, the specified item is zeroed.
88  *	On success, a pointer to the inserted item is returned.
89  *
90  *	The  caller must not retain the returned pointer from this
91  *	routine across calls to the list module. It is only safe to use
92  *	it until the next call to this module for the given list.
93  *
94  */
95 void *
alist_insert(Alist ** lpp,const void * datap,size_t size,Aliste init_arritems,Aliste idx)96 alist_insert(Alist **lpp, const void *datap, size_t size,
97     Aliste init_arritems, Aliste idx)
98 {
99 	Alist	*lp = *lpp;
100 	char	*addr;
101 
102 	/* The size and initial array count need to be non-zero */
103 	ASSERT(init_arritems != 0);
104 	ASSERT(size != 0);
105 
106 	if (lp == NULL) {
107 		Aliste bsize;
108 
109 		/*
110 		 * First time here, allocate a new Alist.  Note that the
111 		 * Alist al_desc[] entry is defined for 1 element,
112 		 * but we actually allocate the number we need.
113 		 */
114 		bsize = size * init_arritems;
115 		bsize = S_ROUND(bsize, sizeof (void *));
116 		bsize = ALIST_OFF_DATA + bsize;
117 		if ((lp = malloc((size_t)bsize)) == NULL)
118 			return (NULL);
119 		lp->al_arritems = init_arritems;
120 		lp->al_nitems = 0;
121 		lp->al_next = ALIST_OFF_DATA;
122 		lp->al_size = size;
123 		*lpp = lp;
124 	} else {
125 		/* We must get the same value for size every time */
126 		ASSERT(size == lp->al_size);
127 
128 		if (lp->al_nitems >= lp->al_arritems) {
129 			/*
130 			 * The list is full: Increase the memory allocation
131 			 * by doubling it.
132 			 */
133 			Aliste	bsize;
134 
135 			bsize = lp->al_size * lp->al_arritems * 2;
136 			bsize = S_ROUND(bsize, sizeof (void *));
137 			bsize = ALIST_OFF_DATA + bsize;
138 			if ((lp = realloc(lp, (size_t)bsize)) == NULL)
139 				return (NULL);
140 			lp->al_arritems *= 2;
141 			*lpp = lp;
142 		}
143 	}
144 
145 	/*
146 	 * The caller is not supposed to use an index that
147 	 * would introduce a "hole" in the array.
148 	 */
149 	ASSERT(idx <= lp->al_nitems);
150 
151 	addr = (idx * lp->al_size) + (char *)lp->al_data;
152 
153 	/*
154 	 * An appended item is added to the next available array element.
155 	 * An insert at any other spot requires that the data items that
156 	 * exist at the point of insertion be shifted down to open a slot.
157 	 */
158 	if (idx < lp->al_nitems)
159 		(void) memmove(addr + lp->al_size, addr,
160 		    (lp->al_nitems - idx) * lp->al_size);
161 
162 	lp->al_nitems++;
163 	lp->al_next += lp->al_size;
164 	if (datap != NULL)
165 		(void) memcpy(addr, datap, lp->al_size);
166 	else
167 		(void) memset(addr, 0, lp->al_size);
168 	return (addr);
169 }
170 
171 void *
alist_insert_by_offset(Alist ** lpp,const void * datap,size_t size,Aliste init_arritems,Aliste off)172 alist_insert_by_offset(Alist **lpp, const void *datap, size_t size,
173     Aliste init_arritems, Aliste off)
174 {
175 	Aliste idx;
176 
177 	if (*lpp == NULL) {
178 		ASSERT(off == ALIST_OFF_DATA);
179 		idx = 0;
180 	} else {
181 		idx = (off - ALIST_OFF_DATA) / (*lpp)->al_size;
182 	}
183 
184 	return (alist_insert(lpp, datap, size, init_arritems, idx));
185 }
186 
187 void *
aplist_insert(APlist ** lpp,const void * ptr,Aliste init_arritems,Aliste idx)188 aplist_insert(APlist **lpp, const void *ptr, Aliste init_arritems, Aliste idx)
189 {
190 	APlist	*lp = *lpp;
191 
192 	/* The initial array count needs to be non-zero */
193 	ASSERT(init_arritems != 0);
194 
195 	if (lp == NULL) {
196 		Aliste bsize;
197 
198 		/*
199 		 * First time here, allocate a new APlist.  Note that the
200 		 * APlist apl_desc[] entry is defined for 1 element,
201 		 * but we actually allocate the number we need.
202 		 */
203 		bsize = APLIST_OFF_DATA + (sizeof (void *) * init_arritems);
204 		if ((lp = malloc((size_t)bsize)) == NULL)
205 			return (NULL);
206 		lp->apl_arritems = init_arritems;
207 		lp->apl_nitems = 0;
208 		*lpp = lp;
209 	} else if (lp->apl_nitems >= lp->apl_arritems) {
210 		/*
211 		 * The list is full: Increase the memory allocation
212 		 * by doubling it.
213 		 */
214 		Aliste	bsize;
215 
216 		bsize = APLIST_OFF_DATA +
217 		    (2 * sizeof (void *) * lp->apl_arritems);
218 		if ((lp = realloc(lp, (size_t)bsize)) == NULL)
219 			return (NULL);
220 		lp->apl_arritems *= 2;
221 		*lpp = lp;
222 	}
223 
224 	/*
225 	 * The caller is not supposed to use an index that
226 	 * would introduce a "hole" in the array.
227 	 */
228 	ASSERT(idx <= lp->apl_nitems);
229 
230 	/*
231 	 * An appended item is added to the next available array element.
232 	 * An insert at any other spot requires that the data items that
233 	 * exist at the point of insertion be shifted down to open a slot.
234 	 */
235 	if (idx < lp->apl_nitems)
236 		(void) memmove((char *)&lp->apl_data[idx + 1],
237 		    (char *)&lp->apl_data[idx],
238 		    (lp->apl_nitems - idx) * sizeof (void *));
239 
240 	lp->apl_nitems++;
241 	lp->apl_data[idx] = (void *)ptr;
242 	return (&lp->apl_data[idx]);
243 }
244 
245 /*
246  * Append a value to a list. These are convenience wrappers on top
247  * of the insert operation. See the description of those routine above
248  * for details.
249  */
250 void *
alist_append(Alist ** lpp,const void * datap,size_t size,Aliste init_arritems)251 alist_append(Alist **lpp, const void *datap, size_t size,
252     Aliste init_arritems)
253 {
254 	Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->al_nitems;
255 
256 	return (alist_insert(lpp, datap, size, init_arritems, ndx));
257 }
258 
259 void *
aplist_append(APlist ** lpp,const void * ptr,Aliste init_arritems)260 aplist_append(APlist **lpp, const void *ptr, Aliste init_arritems)
261 {
262 	Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->apl_nitems;
263 
264 	return (aplist_insert(lpp, ptr, init_arritems, ndx));
265 }
266 
267 /*
268  * Delete the item at a specified index/offset, and decrement the variable
269  * containing the index:
270  *
271  *	alist_delete - Delete an item from an Alist at the specified
272  *		index.
273  *	alist_delete_by_offset - Delete an item from an Alist at the
274  *		specified offset from the list pointer.
275  *	aplist_delete - Delete a pointer from an APlist at the specified
276  *		index.
277  *
278  * entry:
279  *	alp - List to delete item from
280  *	idxp - Address of variable containing the index of the
281  *		item to delete.
282  *	offp - Address of variable containing the offset of the
283  *		item to delete.
284  *
285  * exit:
286  *	The item at the position given by (*idxp) or (*offp), depending
287  *	on the routine, is removed from the list. Then, the position
288  *	variable (*idxp or *offp) is decremented by one item. This is done
289  *	to facilitate use of this routine within a TRAVERSE loop.
290  *
291  * note:
292  *	Deleting the last element in an array list is cheap, but
293  *	deleting any other item causes a memory copy to occur to
294  *	move the following items up. If you intend to traverse the
295  *	entire list, deleting every item as you go, it will be cheaper
296  *	to omit the delete within the traverse, and then call
297  *	the reset function reset() afterwards.
298  */
299 void
alist_delete(Alist * lp,Aliste * idxp)300 alist_delete(Alist *lp, Aliste *idxp)
301 {
302 	Aliste	idx = *idxp;
303 
304 
305 	/* The list must be allocated and the index in range */
306 	ASSERT(lp != NULL);
307 	ASSERT(idx < lp->al_nitems);
308 
309 	/*
310 	 * If the element to be removed is not the last entry of the array,
311 	 * slide the following elements over the present element.
312 	 */
313 	if (idx < --lp->al_nitems) {
314 		char *addr = (idx * lp->al_size) + (char *)lp->al_data;
315 
316 		(void) memmove(addr, addr + lp->al_size,
317 		    (lp->al_nitems - idx) * lp->al_size);
318 	}
319 	lp->al_next -= lp->al_size;
320 
321 	/* Decrement the callers index variable */
322 	(*idxp)--;
323 }
324 
325 void
alist_delete_by_offset(Alist * lp,Aliste * offp)326 alist_delete_by_offset(Alist *lp, Aliste *offp)
327 {
328 	Aliste idx;
329 
330 	ASSERT(lp != NULL);
331 	idx = (*offp - ALIST_OFF_DATA) / lp->al_size;
332 
333 	alist_delete(lp, &idx);
334 	*offp -= lp->al_size;
335 }
336 
337 void
aplist_delete(APlist * lp,Aliste * idxp)338 aplist_delete(APlist *lp, Aliste *idxp)
339 {
340 	Aliste	idx = *idxp;
341 
342 
343 	/* The list must be allocated and the index in range */
344 	ASSERT(lp != NULL);
345 	ASSERT(idx < lp->apl_nitems);
346 
347 	/*
348 	 * If the element to be removed is not the last entry of the array,
349 	 * slide the following elements over the present element.
350 	 */
351 	if (idx < --lp->apl_nitems)
352 		(void) memmove(&lp->apl_data[idx], &lp->apl_data[idx + 1],
353 		    (lp->apl_nitems - idx) * sizeof (void *));
354 
355 	/* Decrement the callers index variable */
356 	(*idxp)--;
357 }
358 
359 /*
360  * Delete the pointer with a specified value from the APlist.
361  *
362  * entry:
363  *	lp - Initialized APlist to delete item from
364  *	ptr - Pointer to be deleted.
365  *
366  * exit:
367  *	The list is searched for an item containing the given pointer,
368  *	and if a match is found, that item is delted and True (1) returned.
369  *	If no match is found, then False (0) is returned.
370  *
371  * note:
372  *	See note for delete operation, above.
373  */
374 int
aplist_delete_value(APlist * lp,const void * ptr)375 aplist_delete_value(APlist *lp, const void *ptr)
376 {
377 	size_t	idx;
378 
379 	/*
380 	 * If the pointer is found in the list, use aplist_delete to
381 	 * remove it, and we're done.
382 	 */
383 	for (idx = 0; idx < lp->apl_nitems; idx++)
384 		if (ptr == lp->apl_data[idx]) {
385 			aplist_delete(lp, &idx);
386 			return (1);
387 		}
388 
389 	/* If we get here, the item was not in the list */
390 	return (0);
391 }
392 
393 /*
394  * Search the APlist for an element with a given value, and
395  * if not found, optionally append the element to the end of the list.
396  *
397  * entry:
398  *	lpp, ptr - As per aplist_insert().
399  *	init_arritems - As per aplist_insert() if a non-zero value.
400  *		A value of zero is special, and is taken to indicate
401  *		that no insert operation should be performed if
402  *		the item is not found in the list.
403  *
404  * exit
405  *	The given item is compared to every item in the given APlist.
406  *	If it is found, ALE_EXISTS is returned.
407  *
408  *	If it is not found: If init_arr_items is False (0), then
409  *	ALE_NOTFOUND is returned. If init_arr_items is True, then
410  *	the item is appended to the list, and ALE_CREATE returned on success.
411  *
412  *	On failure, which can only occur due to memory allocation failure,
413  *	ALE_ALLOCFAIL is returned.
414  *
415  * note:
416  *	The test operation used by this routine is a linear
417  *	O(N) operation, and is not efficient for more than a
418  *	few items.
419  */
420 aplist_test_t
aplist_test(APlist ** lpp,const void * ptr,Aliste init_arritems)421 aplist_test(APlist **lpp, const void *ptr, Aliste init_arritems)
422 {
423 	APlist	*lp = *lpp;
424 	size_t	idx;
425 
426 	/* Is the pointer already in the list? */
427 	if (lp != NULL)
428 		for (idx = 0; idx < lp->apl_nitems; idx++)
429 			if (ptr == lp->apl_data[idx])
430 				return (ALE_EXISTS);
431 
432 	/* Is this a no-insert case? If so, report that the item is not found */
433 	if (init_arritems == 0)
434 		return (ALE_NOTFND);
435 
436 	/* Add it to the end of the list */
437 	if (aplist_append(lpp, ptr, init_arritems) == NULL)
438 		return (ALE_ALLOCFAIL);
439 	return (ALE_CREATE);
440 }
441 
442 /*
443  * Reset the given list to its empty state. Any memory allocated by the
444  * list is preserved, ready for reuse, but the list is set to its
445  * empty state, equivalent to having called the delete operation for
446  * every item.
447  *
448  * Note that no cleanup of the discarded items is done. The caller must
449  * take care of any necessary cleanup before calling aplist_reset().
450  */
451 void
alist_reset(Alist * lp)452 alist_reset(Alist *lp)
453 {
454 	if (lp != NULL) {
455 		lp->al_nitems = 0;
456 		lp->al_next = ALIST_OFF_DATA;
457 	}
458 }
459 
460 void
aplist_reset(APlist * lp)461 aplist_reset(APlist *lp)
462 {
463 	if (lp != NULL)
464 		lp->apl_nitems = 0;
465 }
466