Array-based FIFO queue in C

Question

I have this "generic" implementation of an array-based FIFO-queue. As I have written very little code in C, I don't have an idea what to ask, so feel free to tell anything that comes to mind.

array_queue.h:

#ifndef ARRAY_QUEUE_H
#define ARRAY_QUEUE_H

#ifdef  __cplusplus
extern "C" {
#endif

    /***************************************************************************
    * This structure implements a FIFO queue and it is based on an array. The  *
    * storage array is expanded as needed in order to fit more elements. The   *
    * length of the storage array (capacity) is always a power of two.         *
    * Whenever the load factor of the queue drops below 1/4, the storage array *
    * is contracted by the factor of 2 as not to waste too much memory. The    *
    * storage array is not, however, contracted any further when its length is *
    * at a predefined minimum capacity.                                        *
    *                                                                          *
    *     The queue caches two essential integers: 'm_size' is the amount of   *
    * elements stored in the queue and 'm_head' is the index within the        *
    * storage array containing the head element of the queue. Whenever we      *
    * dequeue an element, we simply return whatever is stored at 'm_head' and  *
    * increment 'm_head' by 1, setting it to zero (0) if 'm_head' becomes the  *
    * capacity of the current storage array. When a new element is enqueued,   *
    * we set it at index '(m_head + m_size) % capacity' whithin the storage    *
    * array and increment 'm_size'.                                            *
    *                                                                          *
    *     The idea behind capacities that are powers of two is that this       *
    * allows doing more efficient modulo arithmetic: whenever we want to find  *
    * 'i mod s', where 'i' is an index and 's' is the capacity, we can do it   *
    * like 'i & (s - 1)'.                                                      *
    *                                                                          *
    *     Despite the fact that this queue may contract or expand (which is    *
    * O(N)), this implementation guarantees constant amortized time for all    *
    * the operations.                                                          *
    ***************************************************************************/
    typedef struct array_queue_t {
        size_t m_size;
        size_t m_capacity;
        size_t m_head;
        void** m_storage;
    } array_queue_t;

    /***************************************************************************
    * Initializes and returns an empty array queue with given capacity. The    *
    * capacity is ceiled up towards the nearest power of two, if not already a *
    * power of two for performance reasons.                                    *
    ***************************************************************************/
    array_queue_t*  array_queue_init    (const size_t initial_capacity);

    /***************************************************************************
    * Releases the resources of the argument queue.                            *
    ***************************************************************************/
    void            array_queue_free    (array_queue_t* p_queue);

    /***************************************************************************
    * Returns the size of the argument queue.                                  *
    ***************************************************************************/
    size_t          array_queue_size    (const array_queue_t* p_queue);

    /***************************************************************************
    * Returns the capacity of the argument queue, which is the amount of       *
    * components in underlying storage array.                                  *
    ***************************************************************************/
    size_t          array_queue_capacity(const array_queue_t* p_queue);

    /***************************************************************************
    * Appends an element to the tail of the argument queue. If appending was   *
    * successful, EXIT_SUCCESS is returned. Otherwise EXIT_FAILURE is          *
    * returned.                                                                *
    ***************************************************************************/
    int             array_queue_enqueue (array_queue_t* p_queue, 
                                         void* p_element);

    /***************************************************************************
    * Removes an element from the head of the argument queue and returns it.   *
    * If the queue is empty or something fails, returns NULL.                  *
    ***************************************************************************/
    const void*     array_queue_dequeue (array_queue_t* p_queue);

#ifdef  __cplusplus
}
#endif

#endif  /* ARRAY_QUEUE_H */

array_queue.c:

#include <stdlib.h>
#include "array_queue.h"

static size_t MINIMUM_CAPACITY = 16;

static size_t max(const size_t a, const size_t b) 
{
    return a > b ? a : b;
}

/*******************************************************************************
* Returns the least power of two that is no smaller than 's'. For example, if  *
* 's' in {5, 6, 7, 8}, 8 is returned; if 's' is in {9, 10, ..., 16}, 16 is     *
* returned, and so on.                                                         *
*******************************************************************************/
static size_t ceil_to_nearest_power_of_two(const size_t s) 
{
    size_t mask = 1;
    size_t max_bit_index = 0;
    size_t bit_count = 0;
    size_t bit_index = 0;

    while (mask) 
    {
        if (s & mask) 
        {
            ++bit_count;
            max_bit_index = bit_index;
        }

        ++bit_index;
        mask <<= 1;
    }

    return bit_count > 1 ? 1 << (max_bit_index + 1) : s;
}

/*******************************************************************************
* If the storage array of the input queue is full, attempts to double its      *
* size. If the expansion is required, but fails, 'EXIT_FAILURE' is returned.   *
* Otherwise 'EXIT_SUCCESS' is returned.                                        *
*******************************************************************************/
static int ensure_capacity(array_queue_t* p_queue)
{
    size_t i;
    void** new_storage;

    if (!(p_queue && p_queue->m_storage)) return EXIT_FAILURE;

    if (p_queue->m_size == p_queue->m_capacity) 
    {
        new_storage = (void**) malloc((p_queue->m_capacity << 1) * 
                                      sizeof(void*));

        if (!new_storage) return EXIT_FAILURE;

        for (i = 0; i < p_queue->m_size; ++i) {
            new_storage[i] = p_queue->m_storage[(p_queue->m_head + i) & 
                                                (p_queue->m_capacity - 1)];
        }

        free(p_queue->m_storage);
        p_queue->m_storage = new_storage;
        p_queue->m_capacity <<= 1;
        p_queue->m_head = 0;
    }

    return EXIT_SUCCESS;
}

/*******************************************************************************
* Contracts the storage array of the input queue, if the load factor of the    *
* queue is below 1/4. At contraction, the length of the storage array          *
* is halved. Since the capacity is a power of two, the new capacity is a power *
* of two as well.                                                              *
*******************************************************************************/
static void try_contract_table(array_queue_t* p_queue) 
{
    size_t i;
    size_t index;
    void** p_new_storage;

    if (!(p_queue && p_queue->m_storage))              return;
    if (p_queue->m_capacity == MINIMUM_CAPACITY)       return;
    if (p_queue->m_size >= (p_queue->m_capacity >> 2)) return;

    p_new_storage = (void**) malloc((p_queue->m_capacity >> 1) * sizeof(void*));

    if (!p_new_storage) return;

    for (i = 0; i < p_queue->m_size; ++i) {
        index = (p_queue->m_head + i) & (p_queue->m_capacity - 1);
        p_new_storage[i] = p_queue->m_storage[index];
    }

    free(p_queue->m_storage);
    p_queue->m_storage = p_new_storage;
    p_queue->m_capacity >>= 1;
    p_queue->m_head = 0;
}

array_queue_t* array_queue_init(size_t initial_capacity) 
{
    array_queue_t* p_queue;

    initial_capacity = max(initial_capacity, MINIMUM_CAPACITY);
    initial_capacity = ceil_to_nearest_power_of_two(initial_capacity);

    p_queue = (array_queue_t*) malloc(sizeof(array_queue_t));

    p_queue->m_capacity = initial_capacity;
    p_queue->m_storage = (void**) malloc(sizeof(void*) * initial_capacity);
    p_queue->m_head = 0;
    p_queue->m_size = 0;

    return p_queue;
}

void array_queue_free(array_queue_t* p_queue) 
{
    if (!p_queue) return;
    if (p_queue->m_storage) 
        free(p_queue->m_storage);

    free(p_queue);
}

size_t array_queue_size(const array_queue_t* p_queue) 
{
    return p_queue ? p_queue->m_size : 0;
}

size_t array_queue_capacity(const array_queue_t* p_queue)
{
    return p_queue ? p_queue->m_capacity : 0;
}

int array_queue_enqueue(array_queue_t* p_queue, void* p_element) 
{
    size_t index;

    if (!(p_queue && p_queue->m_storage))         return EXIT_FAILURE;
    if (ensure_capacity(p_queue) == EXIT_FAILURE) return EXIT_FAILURE;

    index = (p_queue->m_head + p_queue->m_size) & (p_queue->m_capacity - 1);
    p_queue->m_storage[index] = p_element;
    p_queue->m_size++;
    return EXIT_SUCCESS;
}

const void* array_queue_dequeue(array_queue_t* p_queue) 
{
    size_t index;
    const void* p_ret;

    if (!(p_queue && p_queue->m_storage)) return NULL;
    if (!p_queue->m_size)                 return NULL;

    p_ret = p_queue->m_storage[p_queue->m_head];
    p_queue->m_head = (p_queue->m_head + 1) & (p_queue->m_capacity - 1);
    p_queue->m_size--;
    try_contract_table(p_queue);
    return p_ret;
}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include "array_queue.h"

/*******************************************************************************
* The amount of elements to load into the array queue in the                   *
* 'test_large_queue'.                                                          *
*******************************************************************************/
static const size_t N = 5000000;

/*******************************************************************************
* Returns the amount of milliseconds since Unix epoch.                         *
*******************************************************************************/
static unsigned long long get_milliseconds()
{
    struct timeval tva;
    gettimeofday(&tva, NULL);
    return tva.tv_sec * 1000 + tva.tv_usec / 1000;
}

/*******************************************************************************
* Tests that the queue runs correctly in a non-trivial use case.               *
*******************************************************************************/
static void test_simple_usage_of_array_queue() 
{
    size_t i;
    array_queue_t* p_queue = array_queue_init(12);

    for (i = 0; i < 32; ++i) 
        array_queue_enqueue(p_queue, (void*) i);

    for (i = 0; i < 16; ++i) {
        if (i != (size_t) array_queue_dequeue(p_queue)) {
            printf("Test failed!");
            return;
        }
    }

    if (array_queue_size(p_queue) != 16) 
    {
        printf("Test failed!");
        return;
    }

    for (i = 32; i < 100; ++i) {
        array_queue_enqueue(p_queue, (void*) i);
    }

    for (i = 16; i < 100; ++i) {
        if (i != (size_t) array_queue_dequeue(p_queue)) {
            printf("Test failed!");
            return;
        }
    }

    if (array_queue_size(p_queue) != 0) 
        printf("Test failed!");
}

/*******************************************************************************
* Tests that the queue works correctly on large data and profiles its          *
* performance.                                                                 *
*******************************************************************************/
static void test_large_queue() 
{
    size_t i;
    size_t j;

    unsigned long long ta;
    unsigned long long tb;

    array_queue_t* p_queue = array_queue_init(12);

    ta = get_milliseconds();

    for (i = 1; i <= N; ++i)
        array_queue_enqueue(p_queue, (void*) i);

    tb = get_milliseconds();

    printf ("Loading %zu elements into the queue took %llu ms.\n", N, (tb - ta));

    ta = get_milliseconds();

    for (i = 1; i <= N; ++i) 
        if (i != (j = (size_t) array_queue_dequeue(p_queue)))
        {
            printf("The queue is out of order. Expected: %zu, actual: %zu.\n",
                   i, j);
            return;
        }

    tb = get_milliseconds();

    printf("Unloading the queue took %llu ms.\n", (tb - ta));

    if (array_queue_capacity(p_queue) != 16) 
        printf("The queue did not contract correctly: expected 16, but was "\
               "%zu!\n", array_queue_capacity(p_queue));
}

/*******************************************************************************
* Runs the tests for the array queue.                                          *
*******************************************************************************/
int main(int argc, char** argv) {
    test_simple_usage_of_array_queue();
    test_large_queue();
    return EXIT_SUCCESS;
}

Answer 1

Couldn't ceil_to_nearest_power_of_two be simpler?

static size_t ceil_to_nearest_power_of_two(const size_t s) 
{
    size_t ceiling = 1;

    // if bit_count was 0, then s was 0; much easier to check first
    if ( 0 == s )
    {
        return 0;
    }

    // adding ceiling < s keeps from passing the ceiling
    while ( ceiling && ceiling < s ) 
    {
        ceiling <<= 1;
    }

    // if bit_count was 1, then ceiling will equal s
    return ceiling;
}

Note that I use the block form even for single statements. This helps avoid a class of bug where someone modifies the code thinking that it will only occur in the if or while but it actually occurs all the time. This can be hard to spot in diff views. It's especially problematic if no one notices immediately. It's easy to skim over the problem. Debugging this once can take longer than a lifetime of adding curly brackets.

It's also worth noting that both your original function and this function will return 0 if s is greater than half the maximum size_t value.