OpenSolaris_b135/cmd/sgs/tools/common/alist.c
/*
* 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((void *)lp, (size_t)bsize)) == 0)
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((void *)lp, (size_t)bsize)) == 0)
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;
}