dmake: do not set MAKEFLAGS=k

[unleashed/tickless.git] / usr / src / 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;
}