array.c

/* array.c
 *
 * Copyright 2018 Bruce Cowan <bruce@bcowan.me.uk>
 *
 * This file is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 3 of the
 * License, or (at your option) any later version.
 *
 * This file is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * SPDX-License-Identifier: LGPL-3.0-or-later
 */

#include <errno.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "array.h"
#include "mem.h"

#define MIN_SIZE 2

struct _Array
{
    void **data;
    size_t length;
    size_t capacity;
    FreeFunc free_func;
    
    int ref_count;
};

static void
resize_array (Array *array,
              size_t required)
{
    size_t size = MIN_SIZE;

    while (size < required)
    {
        size = (size_t) ceil (size * 1.5);
    }

    array->data = check_realloc (array->data, sizeof (void *) * size);
    array->capacity = size;
}

static bool
index_in_array (const Array *array,
                size_t       index)
{
    if (index < array->length)
        return true;
    else
    {
        errno = EINVAL;
        return false;
    }
}

static void
maybe_shrink (Array *array)
{
    if (array->length <= (size_t) ceil (array->capacity * 0.3))
        resize_array (array, array->length);
}

/**
 * array_new:
 * @func: (nullable): A #FreeFunc which is used to free deleted items
 *
 * Creates a new #Array.
 *
 * Returns: The new #Array, free with array_free()
 */
Array *
array_new (FreeFunc func)
{
    Array *array = check_malloc (sizeof (Array));

    array->data = check_malloc (sizeof (void *) * MIN_SIZE);
    array->length = 0;
    array->capacity = MIN_SIZE;
    array->free_func = func;
    array->ref_count = 1;

    return array;
}

/**
 * array_ref:
 * @array: The array to increase the reference count of
 *
 * Increase the reference account of the array.
 *
 * Returns: The array
 */
Array *
array_ref (Array *array)
{
    array->ref_count++;

    return array;
}

/**
 * array_unref:
 * @array: The array to decrease the reference count of
 *
 * Decrease the reference account of the array. If it becomes 0, it will be
 * freed.
 */
void
array_unref (Array *array)
{
    array->ref_count--;

    if (array->ref_count == 0)
    {
        if (array->free_func)
        {
            for (size_t i = 0; i < array->length; i++)
                array->free_func (array->data[i]);
        }

        free (array->data);
        free (array);
    }
}

/**
 * array_add:
 * @array: An array
 * @val: The value to add to the array
 *
 * Adds a value to an array.
 */
void
array_add (Array      *array,
           const void *val)
{
    if (array->length == array->capacity)
        resize_array (array, array->length + 1);

    array->data[array->length] = (void *) val;
    array->length += 1;
}

/**
 * array_remove_fast:
 * @array: An array
 * @index: The index of the item to remove from @array
 *
 * Removes an item from an array. This function copies the last member of the
 * array to the location of the item to be removed, which means that ordering
 * is not preserved.
 *
 * Returns: %true if successful
 */
bool
array_remove_fast (Array *array,
                   size_t index)
{
    if (!index_in_array (array, index))
    {
        perror ("array_remove_fast");
        return false;
    }

    if (array->free_func)
        array->free_func (array->data[index]);

    void *last = array->data[array->length - 1];
    array->data[index] = last;

    array->length -= 1;
    maybe_shrink (array);

    return true;
}

/**
 * array_remove:
 * @array: An array
 * @index: The index of the item to remove from @array
 *
 * Removes an item from an array. This function moves the items following the
 * removed item down one space. This preserves the ordering of the items, but is
 * slower than array_remove_fast().
 *
 * Returns: %true if successful
 */
bool
array_remove (Array *array,
              size_t index)
{
    if (!index_in_array (array, index))
    {
        perror ("array_remove");
        return false;
    }

    if (array->free_func)
        array->free_func (array->data[index]);

    memmove (array->data + index,
             array->data + index + 1,
             sizeof (void *) * (array->length - index - 1));

    array->length -= 1;
    maybe_shrink (array);

    return true;
}

/**
 * array_set:
 * @array: An array
 * @index: The index of the item to set a value for
 * @val: The value to set the item to
 *
 * Sets an element of @array to @val, using the @index.
 *
 * Returns: %true if successful
 */
bool
array_set (Array      *array,
           size_t      index,
           const void *val)
{
    if (!index_in_array (array, index))
    {
        perror ("array_set");
        return false;
    }

    array->data[index] = (void *) val;
    return true;
}

/**
 * array_get:
 * @array: An array
 * @index: The index of @array to get a value from
 *
 * Get a value of @array, using @index.
 *
 * Returns: (transfer none): The value at @index of @array
 */
const void *
array_get (const Array *array,
           size_t       index)
{
    if (index_in_array (array, index))
        return array->data[index];
    else
    {
        perror ("array_get");
        return NULL;
    }
}

/**
 * array_get_length:
 * @array: An array
 *
 * Gets the number of elements in an array.
 *
 * Returns: The length of the array
 */
size_t
array_get_length (const Array *array)
{
    return array->length;
}

/**
 * array_get_capacity:
 * @array: An array
 *
 * Get the capacity (proportional to memory usage) of @array.
 *
 * Returns: The capacity, in items.
 */
size_t
array_get_capacity (const Array *array)
{
    return array->capacity;
}

/**
 * array_sort:
 * @array: An array
 * @func: A function which returns -1 for less than, 0 for equal, and 1 for more than
 *
 * Sorts the array
 */
void
array_sort (Array      *array,
            CompareFunc func)
{
    qsort (*array->data, array->length, sizeof (void *), func);
}