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