path: root/src/queue.c

#include <bh/internal/queue.h>
#include <stdlib.h>
#include <string.h>

/**
 * \defgroup queue Queue
 *
 * Data stucture for storing pointers in queue.
 * \{
 */

/**
 * Creates the new queue object.
 *
 * \return  On success, returns the pointer to the new queue object.
 * \return  On failure, returns a null pointer.
 */
bh_queue_t *bh_queue_new(void)
{
    bh_queue_t *result;

    result = malloc(sizeof(*result));
    if (result)
        bh_queue_init(result);

    return result;
}

/**
 * Frees the \a queue object.
 *
 * \param queue Pointer to the queue object to be freed
 */
void bh_queue_free(bh_queue_t *queue)
{
    bh_queue_destroy(queue);
    free(queue);
}

/**
 * Initializes the \a queue object.
 *
 * \warning This is an internal function.
 *
 * \param queue Pointer to the queue object to be initialized
 */
void bh_queue_init(bh_queue_t *queue)
{
    memset(queue, 0, sizeof(*queue));
}

/**
 * Destroys the \a queue object.
 *
 * \warning This is an internal function.
 *
 * \param queue Pointer to the queue object to be destroyed
 */
void bh_queue_destroy(bh_queue_t *queue)
{
    if (queue->capacity)
        free(queue->data);
}

/**
 * Clears the \a queue object.
 *
 * \param queue Pointer to the queue object to be cleared
 */
void bh_queue_clear(bh_queue_t *queue)
{
    queue->head = 0;
    queue->tail = 0;
    queue->size = 0;
}

/**
 * Reserves the space for \a size elements in the \a queue.
 *
 * This function can both expand and shrink the available space in \a queue.
 *
 * \param queue Pointer to the queue object to be resized in terms of capacity
 * \param size  New capacity of the queue
 *
 * \note Calling this function will invalidate iterators.
 * \note Actual hashmap capacity can be bigger then requested.
 *
 * \return  On success, returns zero value.
 * \return  On failure, returns error code.
 */
int bh_queue_reserve(bh_queue_t *queue,
                     size_t size)
{
    bh_queue_t other;

    /* New capacity should be great or equal to current size */
    if (size < queue->size)
        size = queue->size;

    /* New capacity should not exceed maximum capacity */
    if (size > ((size_t)-1) / sizeof(void *))
        return BH_OOM;

    /* Prevent same size memory reallocation */
    if (size == queue->capacity)
        return BH_OK;

    /* Prepare new empty queue */
    bh_queue_init(&other);
    if (size)
    {
        void *iter;

        /* Allocate new capacity for the queue */
        other.data = malloc(size * sizeof(void *));
        other.capacity = size;
        if (!other.data)
            return BH_OOM;

        /* Iterate over old queue and insert data into new queue */
        iter = bh_queue_iter_next(queue, NULL);
        while (iter)
        {
            bh_queue_insert(&other, bh_queue_iter_value(iter));
            iter = bh_queue_iter_next(queue, iter);
        }
    }

    /* If old queue had allocated data - free it */
    if (queue->capacity)
        free(queue->data);

    /* Copy queue information */
    *queue = other;
    return BH_OK;
}

/**
 * Inserts the \a value into the \a queue.
 *
 * \param queue Pointer to the queue object
 * \param value Value to be inserted
 *
 * \note Calling this function will invalidate iterators.
 *
 * \return  On success, returns zero value.
 * \return  On failure, returns error code.
 */
int bh_queue_insert(bh_queue_t *queue,
                    void *value)
{
    /* Check if queue can contain new element */
    if (queue->size + 1 > queue->capacity)
    {
        size_t capacity;

        /* Check potential size overflow and reserve capacity */
        capacity = (queue->capacity) ? (queue->capacity * 2) : (16);
        if (capacity < queue->capacity || bh_queue_reserve(queue, capacity))
            return BH_OOM;
    }

    /* Increase queue size and advance tail index */
    queue->data[queue->tail] = value;
    queue->size++;
    if (++queue->tail >= queue->capacity)
        queue->tail = 0;

    return BH_OK;
}

/**
 * Removes front value from the \a queue.
 *
 * \param queue Pointer to the queue object
 *
 * \note Calling this function will invalidate iterators.
 */
void bh_queue_remove(bh_queue_t *queue)
{
    /* Do nothing if queue is empty */
    if (!queue->size)
        return;

    /* Decrease queue size and advance head index */
    queue->size--;
    if (++queue->head >= queue->capacity)
        queue->head = 0;
}

/**
 * Returns front value from the \a queue.
 *
 * \param queue Pointer to the queue object
 *
 * \return  On success, returns front value from the queue.
 * \return  On failure, returns null pointer.
 */
void *bh_queue_front(bh_queue_t *queue)
{
    /* Do nothing if queue is empty */
    if (!queue->size)
        return NULL;

    /* Return front element */
    return queue->data[queue->head];
}

/**
 * Checks if the \a queue is empty.
 *
 * \param queue Pointer to the queue object
 *
 * \return  If queue is empty, returns non-zero value
 * \return  If queue is not empty, returns zero value
 */
int bh_queue_empty(bh_queue_t *queue)
{
    return !queue->size;
}

/**
 * Returns the size of the \a queue.
 *
 * \param queue Pointer to the queue object
 *
 * \return  Returns the size of the queue.
 */
size_t bh_queue_size(bh_queue_t *queue)
{
    return queue->size;
}

/**
 * Returns the capacity of the \a queue.
 *
 * \param queue Pointer to the queue object
 *
 * \return  Returns the capacity of the queue.
 */
size_t bh_queue_capacity(bh_queue_t *queue)
{
    return queue->capacity;
}

/**
 * Returns the iterator to the next element in the \a queue.
 *
 * \param queue Pointer to the queue object
 * \param iter  Opaque iterator value
 *
 * \return  If the \a iter doesn't point to the last element of the queue,
 *          returns next iterator value.
 * \return  If the \a iter point to the last element of the queue, returns
 *          null pointer.
 * \return  If the \a iter is the null pointer, returns iterator to the
 *          first element of the queue.
 */
void *bh_queue_iter_next(bh_queue_t *queue,
                         void *iter)
{
    void **element = (void **)iter;

    /* Do nothing if queue is empty */
    if (!queue->size)
        return NULL;

    /* Advance or set iterator */
    if (element)
    {
        element++;
        if (element == queue->data + queue->capacity)
            element = queue->data;

        /* Check if we reached the end */
        if (element == queue->data + queue->tail)
            return NULL;
    }
    else
        element = queue->data + queue->head;

    return element;
}

/**
 * Returns the value, pointed by the queue iterator \a iter.
 *
 * \param iter  Opaque iterator value
 *
 * \return  Returns value, pointed by iterator.
 */
void *bh_queue_iter_value(void *iter)
{
    return *(void **)iter;
}

/**
 * \}
 */