source: mainline/uspace/lib/c/generic/adt/dyn_array.c@ 1be7bee

/*
 * Copyright (c) 2015 Michal Koutny
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - 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.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
 */

/** @addtogroup libc
 * @{
 */
/** @file
 *
 * Implementation of dynamic array that grows or shrinks based upon no. of
 * items it contains. Non-negligible part of implementation is in @ref
 * dyn_array.h because of type genericity.
 */

#include <assert.h>
#include <errno.h>
#include <adt/dyn_array.h>
#include <macros.h>
#include <mem.h>
#include <stdlib.h>




static int dyn_array_realloc(dyn_array_t *da, size_t capacity)
{
        if (capacity == da->capacity) {
                return EOK;
        }

        void *new_data = realloc(da->_data, da->_item_size * capacity);
        if (new_data) {
                da->_data = new_data;
                da->capacity = capacity;
        }
        return (new_data == NULL) ? ENOMEM : EOK;
}

void dyn_array_destroy(dyn_array_t *da)
{
        dyn_array_clear(da);
        free(da->_data);
        da->capacity = 0;
}

/** Remove item at given position, shift rest of array */
void dyn_array_remove(dyn_array_t *da, size_t index)
{
        assert(index < da->size);
        _dyn_array_unshift(da, index, 1);
        int rc = dyn_array_reserve(da, da->size);
        assert(rc == EOK);
}

/** Clear dynamic array (empty) */
void dyn_array_clear(dyn_array_t *da)
{
        da->size = 0;
}

/** Clear subsequence of array
 *
 * @param[in/out]  da
 * @param[in]      begin  index of first item to remove
 * @param[in]      end    index behind last item to remove
 */
void dyn_array_clear_range(dyn_array_t *da, size_t begin, size_t end)
{
        assert(begin < da->size);
        assert(end <= da->size);

        _dyn_array_unshift(da, begin, end - begin);
        int rc = dyn_array_reserve(da, da->size);
        assert(rc == EOK);
}

/** Concatenate two arrays
 *
 * @param[in/out]  da1  first array and concatenated output
 * @param[in]      da2  second array, it is untouched
 *
 * @return EOK on success
 * @return ENOMEM when allocation fails
 */
int dyn_array_concat(dyn_array_t *da1, dyn_array_t *da2)
{
        assert(da1->_item_size == da2->_item_size);

        int rc = dyn_array_reserve(da1, da1->size + da2->size);
        if (rc != EOK) {
                return rc;
        }
        void *dst = da1->_data + da1->size * da1->_item_size;
        void *src = da2->_data;
        size_t size = da1->_item_size * da2->size;
        memcpy(dst, src, size);
        da1->size += da2->size;

        return EOK;
}

/** Grows/shrinks array so that it effeciently stores desired capacity
 *
 * @param      da
 * @param[in]  desired capacity of array (items)
 *
 * @return EOK
 * @return ENOMEM
 */
int dyn_array_reserve(dyn_array_t *da, size_t capacity)
{
        const size_t factor = 2;
        size_t new_capacity;
        if (capacity > da->capacity) {
                new_capacity = max(da->capacity * factor, capacity);
        } else if (capacity < da->capacity / factor) {
                new_capacity = min(da->capacity / factor, capacity);
        } else {
                new_capacity = capacity;
        }

        return dyn_array_realloc(da, new_capacity);
}

void _dyn_array_initialize(dyn_array_t *da, size_t item_size)
{
        da->_item_size = item_size;
        da->_data = NULL;

        da->capacity = 0;
        da->size = 0;
}

/** Shift block of array
 *
 * Extends size of dynamic array, assumes sufficient capacity.
 *
 * @param      da
 * @param[in]  index   first item shifted
 * @param[in]  offset  shift in no. of items
 */
void _dyn_array_shift(dyn_array_t *da, size_t index, size_t offset)
{
        assert(da->capacity >= da->size + offset);

        void *src = da->_data + index * da->_item_size;
        void *dst = da->_data + (index + offset) * da->_item_size;
        size_t size = (da->size - index) * da->_item_size;
        memmove(dst, src, size);
        da->size += offset;
}

/** Unshift block of array
 *
 * Reduce size of dynamic array
 *
 * @param      da
 * @param[in]  index   first item unshifted (removed)
 * @param[in]  offset  shift in no. of items
 */
void _dyn_array_unshift(dyn_array_t *da, size_t index, size_t offset)
{
        void *src = da->_data + (index + offset) * da->_item_size;
        void *dst = da->_data + index * da->_item_size;
        size_t size = (da->size - index - offset) * da->_item_size;
        memmove(dst, src, size);
        da->size -= offset;
}


/** @}
 */