/* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License (the "License"). * You may not use this file except in compliance with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or http://www.opensolaris.org/os/licensing. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright 2009 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. */ #include <sgs.h> #include <string.h> #include <stdio.h> #include <sys/debug.h> /* * Alist manipulation. An Alist is a list of elements formed into an array. * Traversal of the list is an array scan, which because of the locality of * each reference is probably more efficient than a link-list traversal. * * See alist.h for more background information about array lists. */ /* * Insert a value into an array at a specified index: * * alist_insert(): Insert an item into an Alist at the specified index * alist_insert_by_offset(): Insert an item into an Alist at the * specified offset relative to the list address. * aplist_insert() Insert a pointer into an APlist at the specified index * * entry: * Note: All the arguments for all three routines are listed here. * The routine to which a given argument applies is given with * each description. * * llp [all] - Address of a pointer to an Alist/APlist. The pointer should * be initialized to NULL before its first use. * datap [alist_insert / aplist_insert] - Pointer to item data, or * NULL. If non-null the data referenced is copied into the * Alist item. Otherwise, the list item is zeroed, and * further initialization is left to the caller. * ptr [aplist_insert] - Pointer to be inserted. * size [alist_insert / alist_insert_by_offset] - Size of an item * in the array list, in bytes. As with any array, A given * Alist can support any item size, but every item in that * list must have the same size. * init_arritems [all] - Initial allocation size: On the first insertion * into the array list, room for init_arritems items is allocated. * idx [alist_insert / aplist_insert] - Index at which to insert the * new item. This index must lie within the existing list, * or be the next index following. * off [alist_insert_by_offset] - Offset at which to insert the new * item, based from the start of the Alist. The offset of * the first item is ALIST_OFF_DATA. * * exit: * The item is inserted at the specified position. This operation * can cause memory for the list to be allocated, or reallocated, * either of which will cause the value of the list pointer * to change. * * These routines can only fail if unable to allocate memory, * in which case NULL is returned. * * If a pointer list (aplist_insert), then the pointer * is stored in the requested index. On success, the address * of the pointer within the list is returned. * * If the list contains arbitrary data (not aplist_insert): If datap * is non-NULL, the data it references is copied into the item at * the index. If datap is NULL, the specified item is zeroed. * On success, a pointer to the inserted item is returned. * * The caller must not retain the returned pointer from this * routine across calls to the list module. It is only safe to use * it until the next call to this module for the given list. * */ void * alist_insert(Alist **lpp, const void *datap, size_t size, Aliste init_arritems, Aliste idx) { Alist *lp = *lpp; char *addr; /* The size and initial array count need to be non-zero */ ASSERT(init_arritems != 0); ASSERT(size != 0); if (lp == NULL) { Aliste bsize; /* * First time here, allocate a new Alist. Note that the * Alist al_desc[] entry is defined for 1 element, * but we actually allocate the number we need. */ bsize = size * init_arritems; bsize = S_ROUND(bsize, sizeof (void *)); bsize = ALIST_OFF_DATA + bsize; if ((lp = malloc((size_t)bsize)) == NULL) return (NULL); lp->al_arritems = init_arritems; lp->al_nitems = 0; lp->al_next = ALIST_OFF_DATA; lp->al_size = size; *lpp = lp; } else { /* We must get the same value for size every time */ ASSERT(size == lp->al_size); if (lp->al_nitems >= lp->al_arritems) { /* * The list is full: Increase the memory allocation * by doubling it. */ Aliste bsize; bsize = lp->al_size * lp->al_arritems * 2; bsize = S_ROUND(bsize, sizeof (void *)); bsize = ALIST_OFF_DATA + bsize; if ((lp = realloc(lp, (size_t)bsize)) == NULL) return (NULL); lp->al_arritems *= 2; *lpp = lp; } } /* * The caller is not supposed to use an index that * would introduce a "hole" in the array. */ ASSERT(idx <= lp->al_nitems); addr = (idx * lp->al_size) + (char *)lp->al_data; /* * An appended item is added to the next available array element. * An insert at any other spot requires that the data items that * exist at the point of insertion be shifted down to open a slot. */ if (idx < lp->al_nitems) (void) memmove(addr + lp->al_size, addr, (lp->al_nitems - idx) * lp->al_size); lp->al_nitems++; lp->al_next += lp->al_size; if (datap != NULL) (void) memcpy(addr, datap, lp->al_size); else (void) memset(addr, 0, lp->al_size); return (addr); } void * alist_insert_by_offset(Alist **lpp, const void *datap, size_t size, Aliste init_arritems, Aliste off) { Aliste idx; if (*lpp == NULL) { ASSERT(off == ALIST_OFF_DATA); idx = 0; } else { idx = (off - ALIST_OFF_DATA) / (*lpp)->al_size; } return (alist_insert(lpp, datap, size, init_arritems, idx)); } void * aplist_insert(APlist **lpp, const void *ptr, Aliste init_arritems, Aliste idx) { APlist *lp = *lpp; /* The initial array count needs to be non-zero */ ASSERT(init_arritems != 0); if (lp == NULL) { Aliste bsize; /* * First time here, allocate a new APlist. Note that the * APlist apl_desc[] entry is defined for 1 element, * but we actually allocate the number we need. */ bsize = APLIST_OFF_DATA + (sizeof (void *) * init_arritems); if ((lp = malloc((size_t)bsize)) == NULL) return (NULL); lp->apl_arritems = init_arritems; lp->apl_nitems = 0; *lpp = lp; } else if (lp->apl_nitems >= lp->apl_arritems) { /* * The list is full: Increase the memory allocation * by doubling it. */ Aliste bsize; bsize = APLIST_OFF_DATA + (2 * sizeof (void *) * lp->apl_arritems); if ((lp = realloc(lp, (size_t)bsize)) == NULL) return (NULL); lp->apl_arritems *= 2; *lpp = lp; } /* * The caller is not supposed to use an index that * would introduce a "hole" in the array. */ ASSERT(idx <= lp->apl_nitems); /* * An appended item is added to the next available array element. * An insert at any other spot requires that the data items that * exist at the point of insertion be shifted down to open a slot. */ if (idx < lp->apl_nitems) (void) memmove((char *)&lp->apl_data[idx + 1], (char *)&lp->apl_data[idx], (lp->apl_nitems - idx) * sizeof (void *)); lp->apl_nitems++; lp->apl_data[idx] = (void *)ptr; return (&lp->apl_data[idx]); } /* * Append a value to a list. These are convenience wrappers on top * of the insert operation. See the description of those routine above * for details. */ void * alist_append(Alist **lpp, const void *datap, size_t size, Aliste init_arritems) { Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->al_nitems; return (alist_insert(lpp, datap, size, init_arritems, ndx)); } void * aplist_append(APlist **lpp, const void *ptr, Aliste init_arritems) { Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->apl_nitems; return (aplist_insert(lpp, ptr, init_arritems, ndx)); } /* * Delete the item at a specified index/offset, and decrement the variable * containing the index: * * alist_delete - Delete an item from an Alist at the specified * index. * alist_delete_by_offset - Delete an item from an Alist at the * specified offset from the list pointer. * aplist_delete - Delete a pointer from an APlist at the specified * index. * * entry: * alp - List to delete item from * idxp - Address of variable containing the index of the * item to delete. * offp - Address of variable containing the offset of the * item to delete. * * exit: * The item at the position given by (*idxp) or (*offp), depending * on the routine, is removed from the list. Then, the position * variable (*idxp or *offp) is decremented by one item. This is done * to facilitate use of this routine within a TRAVERSE loop. * * note: * Deleting the last element in an array list is cheap, but * deleting any other item causes a memory copy to occur to * move the following items up. If you intend to traverse the * entire list, deleting every item as you go, it will be cheaper * to omit the delete within the traverse, and then call * the reset function reset() afterwards. */ void alist_delete(Alist *lp, Aliste *idxp) { Aliste idx = *idxp; /* The list must be allocated and the index in range */ ASSERT(lp != NULL); ASSERT(idx < lp->al_nitems); /* * If the element to be removed is not the last entry of the array, * slide the following elements over the present element. */ if (idx < --lp->al_nitems) { char *addr = (idx * lp->al_size) + (char *)lp->al_data; (void) memmove(addr, addr + lp->al_size, (lp->al_nitems - idx) * lp->al_size); } lp->al_next -= lp->al_size; /* Decrement the callers index variable */ (*idxp)--; } void alist_delete_by_offset(Alist *lp, Aliste *offp) { Aliste idx; ASSERT(lp != NULL); idx = (*offp - ALIST_OFF_DATA) / lp->al_size; alist_delete(lp, &idx); *offp -= lp->al_size; } void aplist_delete(APlist *lp, Aliste *idxp) { Aliste idx = *idxp; /* The list must be allocated and the index in range */ ASSERT(lp != NULL); ASSERT(idx < lp->apl_nitems); /* * If the element to be removed is not the last entry of the array, * slide the following elements over the present element. */ if (idx < --lp->apl_nitems) (void) memmove(&lp->apl_data[idx], &lp->apl_data[idx + 1], (lp->apl_nitems - idx) * sizeof (void *)); /* Decrement the callers index variable */ (*idxp)--; } /* * Delete the pointer with a specified value from the APlist. * * entry: * lp - Initialized APlist to delete item from * ptr - Pointer to be deleted. * * exit: * The list is searched for an item containing the given pointer, * and if a match is found, that item is delted and True (1) returned. * If no match is found, then False (0) is returned. * * note: * See note for delete operation, above. */ int aplist_delete_value(APlist *lp, const void *ptr) { size_t idx; /* * If the pointer is found in the list, use aplist_delete to * remove it, and we're done. */ for (idx = 0; idx < lp->apl_nitems; idx++) if (ptr == lp->apl_data[idx]) { aplist_delete(lp, &idx); return (1); } /* If we get here, the item was not in the list */ return (0); } /* * Search the APlist for an element with a given value, and * if not found, optionally append the element to the end of the list. * * entry: * lpp, ptr - As per aplist_insert(). * init_arritems - As per aplist_insert() if a non-zero value. * A value of zero is special, and is taken to indicate * that no insert operation should be performed if * the item is not found in the list. * * exit * The given item is compared to every item in the given APlist. * If it is found, ALE_EXISTS is returned. * * If it is not found: If init_arr_items is False (0), then * ALE_NOTFOUND is returned. If init_arr_items is True, then * the item is appended to the list, and ALE_CREATE returned on success. * * On failure, which can only occur due to memory allocation failure, * ALE_ALLOCFAIL is returned. * * note: * The test operation used by this routine is a linear * O(N) operation, and is not efficient for more than a * few items. */ aplist_test_t aplist_test(APlist **lpp, const void *ptr, Aliste init_arritems) { APlist *lp = *lpp; size_t idx; /* Is the pointer already in the list? */ if (lp != NULL) for (idx = 0; idx < lp->apl_nitems; idx++) if (ptr == lp->apl_data[idx]) return (ALE_EXISTS); /* Is this a no-insert case? If so, report that the item is not found */ if (init_arritems == 0) return (ALE_NOTFND); /* Add it to the end of the list */ if (aplist_append(lpp, ptr, init_arritems) == NULL) return (ALE_ALLOCFAIL); return (ALE_CREATE); } /* * Reset the given list to its empty state. Any memory allocated by the * list is preserved, ready for reuse, but the list is set to its * empty state, equivalent to having called the delete operation for * every item. * * Note that no cleanup of the discarded items is done. The caller must * take care of any necessary cleanup before calling aplist_reset(). */ void alist_reset(Alist *lp) { if (lp != NULL) { lp->al_nitems = 0; lp->al_next = ALIST_OFF_DATA; } } void aplist_reset(APlist *lp) { if (lp != NULL) lp->apl_nitems = 0; }
