array.c

/*-
 * Copyright (c) 2009 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by David A. Holland.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#define ARRAYINLINE

#include <types.h>
#include <kern/errno.h>
#include <lib.h>
#include <array.h>

struct array *
array_create(void)
{
        struct array *a;

        a = kmalloc(sizeof(*a));
        if (a != NULL) {
                array_init(a);
        }
        return a;
}

void
array_destroy(struct array *a)
{
        array_cleanup(a);
        kfree(a);
}

void
array_init(struct array *a)
{
        a->num = a->max = 0;
        a->v = NULL;
}

void
array_cleanup(struct array *a)
{
        /*
         * Require array to be empty - helps avoid memory leaks since
         * we don't/can't free anything any contents may be pointing
         * to.
         */
        ARRAYASSERT(a->num == 0);
        kfree(a->v);
#ifdef ARRAYS_CHECKED
        a->v = NULL;
#endif
}

int
array_setsize(struct array *a, unsigned num)
{
        void **newptr;
        unsigned newmax;

        if (num > a->max) {
                /* Don't touch A until the allocation succeeds. */
                newmax = a->max;
                while (num > newmax) {
                        newmax = newmax ? newmax*2 : 4;
                }

                /*
                 * We don't have krealloc, and it wouldn't be
                 * worthwhile to implement just for this. So just
                 * allocate a new block and copy. (Exercise: what
                 * about this and/or kmalloc makes it not worthwhile?)
                 */

                newptr = kmalloc(newmax*sizeof(*a->v));
                if (newptr == NULL) {
                        return ENOMEM;
                }
                memcpy(newptr, a->v, a->num*sizeof(*a->v));
                kfree(a->v);
                a->v = newptr;
                a->max = newmax;
        }
        a->num = num;

        return 0;
}

void
array_remove(struct array *a, unsigned index)
{
        unsigned num_to_move;

        ARRAYASSERT(a->num <= a->max);
        ARRAYASSERT(index < a->num);

        num_to_move = a->num - (index + 1);
        memmove(a->v + index, a->v + index+1, num_to_move*sizeof(void *));
        a->num--;
}