2
\$\begingroup\$

Now I have this circular array-based list in C. Circularity allows pushing/popping to the both ends of the list in constant amortized time. Inserting/removing at random locations runs in linear time, yet I optimized it a little bit: Suppose we are inserting an element at arbitrary location. We can shift the left elements one position to the left, or the right elements one position to the right. This implementation will choose the option that minimized the amount of shifts. So, what do you think?

list.h:

#ifndef LIST_H #define LIST_H #include <stdbool.h> #include <stdlib.h> #ifdef __cplusplus extern "C" { #endif typedef struct list_t list_t; /*************************************************************************** * Allocates the new, empty list with initial capacity. * ***************************************************************************/ list_t* list_t_alloc(size_t initial_capacity); /*************************************************************************** * Inserts the element to in front of the head of the list. Returns true if * * operation was successful. * ***************************************************************************/ bool list_t_push_front(list_t* p_list, void* p_element); /*************************************************************************** * Appends the element to the tail of the list. Returns true if operation * * was successful. * ***************************************************************************/ bool list_t_push_back(list_t* p_list, void* p_element); /*************************************************************************** * Inserts the element into the list before index'th element. Returns true * * if operation was successful. * ***************************************************************************/ bool list_t_insert(list_t* p_list, size_t index, void* p_element); /*************************************************************************** * Returns the amount of elements stored in the list. * ***************************************************************************/ size_t list_t_size(list_t* p_list); /*************************************************************************** * Returns the index'th element of the list. Returns NULL if the index is * * out of range. * ***************************************************************************/ void* list_t_get(list_t* p_list, size_t index); /*************************************************************************** * Sets the index'th element of the list. Returns the old value. If the * * index is out of range, returns NULL. * ***************************************************************************/ void* list_t_set(list_t* p_list, size_t index, void* p_new_value); /*************************************************************************** * Removes and returns the front element of the list. If list is empty, * * returns NULL. * ***************************************************************************/ void* list_t_pop_front(list_t* p_list); /*************************************************************************** * Removes and returns the last element of the list. If list is empty, * * returns NULL. * ***************************************************************************/ void* list_t_pop_back(list_t* p_list); /*************************************************************************** * Removes the element at index 'index' from the list and returns the * * it. If the list is empty or the index is out of range, returns NULL. * ***************************************************************************/ void* list_t_remove_at(list_t* p_list, size_t index); /*************************************************************************** * Returns true if the list contains the specified element using the * * equality function. Returns false otherwise. * ***************************************************************************/ bool list_t_contains(list_t* p_list, void* p_element, bool (*p_equals_function)(void*, void*)); /*************************************************************************** * Clears this list. The client programmer is responsible for memory- * * managing the contents. * ***************************************************************************/ void list_t_clear(list_t* p_list); /*************************************************************************** * Clears and deallocates the list. * ***************************************************************************/ void list_t_free(list_t* p_list); #ifdef __cplusplus } #endif #endif /* LIST_H */

list.c:

#include "list.h" #include <stdbool.h> #include <stdlib.h> typedef struct list_t { void** p_table; size_t size; size_t capacity; size_t head; size_t mask; } list_t; static const size_t MINIMUM_CAPACITY = 16; static size_t max(size_t a, size_t b) { return a < b ? b : a; } static size_t fix_initial_capacity(size_t initial_capacity) { size_t ret = 1; initial_capacity = max(initial_capacity, MINIMUM_CAPACITY); while (ret < initial_capacity) ret <<= 1; return ret; } list_t* list_t_alloc(size_t initial_capacity) { list_t* p_ret = malloc(sizeof(*p_ret)); if (!p_ret) return NULL; initial_capacity = fix_initial_capacity(initial_capacity); p_ret->p_table = malloc(sizeof(void*) * initial_capacity); if (!p_ret->p_table) { free(p_ret); return NULL; } p_ret->capacity = initial_capacity; p_ret->mask = initial_capacity - 1; p_ret->head = 0; p_ret->size = 0; return p_ret; } static bool ensure_capacity_before_add(list_t* p_list) { void** p_new_table; size_t i; size_t new_capacity; if (p_list->size < p_list->capacity) return true; new_capacity = 2 * p_list->capacity; p_new_table = malloc(sizeof(void*) * new_capacity); if (!p_new_table) return false; for (i = 0; i < p_list->size; ++i) { p_new_table[i] = p_list->p_table[(p_list->head + i) & p_list->mask]; } free(p_list->p_table); p_list->p_table = p_new_table; p_list->capacity = new_capacity; p_list->mask = new_capacity - 1; p_list->head = 0; return true; } bool list_t_push_front(list_t* p_list, void* p_element) { if (!p_list) return false; if (!ensure_capacity_before_add(p_list)) return false; p_list->head = (p_list->head - 1) & p_list->mask; p_list->p_table[p_list->head] = p_element; p_list->size++; return true; } bool list_t_push_back(list_t* p_list, void* p_element) { if (!p_list) return false; if (!ensure_capacity_before_add(p_list)) return false; p_list->p_table[(p_list->head + p_list->size) & p_list->mask] = p_element; p_list->size++; return true; } bool list_t_insert(list_t* p_list, size_t index, void* p_element) { size_t elements_before; size_t elements_after; size_t i; size_t head; size_t mask; size_t size; if (!p_list) return false; if (!ensure_capacity_before_add(p_list)) return false; if (index > p_list->size) return false; elements_before = index; elements_after = p_list->size - index; head = p_list->head; mask = p_list->mask; size = p_list->size; if (elements_before < elements_after) { /* Move preceding elements one position to the left. */ for (i = 0; i < elements_before; ++i) { p_list->p_table[(head + i - 1) & mask] = p_list->p_table[(head + i) & mask]; } head = (head - 1) & mask; p_list->p_table[(head + index) & mask] = p_element; p_list->head = head; } else { /* Move the following elements one position to the right. */ for (i = 0; i < elements_after; ++i) { p_list->p_table[(head + size - i) & mask] = p_list->p_table[(head + size - i - 1) & mask]; } p_list->p_table[(head + index) & mask] = p_element; } p_list->size++; return true; } size_t list_t_size(list_t* p_list) { return p_list ? p_list->size : 0; } void* list_t_get(list_t* p_list, size_t index) { if (!p_list) return NULL; if (index >= p_list->size) return NULL; return p_list->p_table[(p_list->head + index) & p_list->mask]; } void* list_t_set(list_t* p_list, size_t index, void* p_new_value) { void* p_ret; if (!p_list) return NULL; if (index >= p_list->size) return NULL; p_ret = p_list->p_table[(p_list->head + index) & p_list->mask]; p_list->p_table[(p_list->head + index) & p_list->mask] = p_new_value; return p_ret; } void* list_t_pop_front(list_t* p_list) { void* p_ret; if (!p_list) return NULL; if (p_list->size == 0) return NULL; p_ret = p_list->p_table[p_list->head]; p_list->head++; p_list->size--; return p_ret; } void* list_t_pop_back(list_t* p_list) { void* p_ret; if (!p_list) return NULL; if (p_list->size == 0) return NULL; p_ret = p_list->p_table[(p_list->head + p_list->size - 1) & p_list->mask]; p_list->size--; return p_ret; } void* list_t_remove_at(list_t* p_list, size_t index) { void* p_ret; size_t head; size_t mask; size_t elements_before; size_t elements_after; size_t i; size_t j; if (!p_list) return NULL; if (index >= p_list->size) return NULL; head = p_list->head; mask = p_list->mask; p_ret = p_list->p_table[(head + index) & mask]; elements_before = index; elements_after = p_list->size - index - 1; if (elements_before < elements_after) { /* Move the preceding elements one position to the right. */ for (i = 0, j = elements_before; i < elements_before; ++i, --j) { p_list->p_table[(head + j) & mask] = p_list->p_table[(head + j - 1) & mask]; } p_list->head = (head + 1) & mask; } else { /* Move the following elements one position to the left. */ for (i = 0; i < elements_after; ++i) { p_list->p_table[(head + index + i) & mask] = p_list->p_table[(head + index + i + 1) & mask]; } } p_list->size--; return p_ret; } bool list_t_contains(list_t* p_list, void* p_element, bool (*p_equals_function)(void*, void*)) { size_t i; if (!p_list) return false; if (!p_equals_function) return false; for (i = 0; i < p_list->size; ++i) { if (p_equals_function(p_element, p_list->p_table[(p_list->head + i) & p_list->mask])) { return true; } } return false; } void list_t_clear(list_t* p_list) { if (!p_list) return; p_list->head = 0; p_list->size = 0; } void list_t_free(list_t* p_list) { if (!p_list) return; free(p_list->p_table); free(p_list); }

You can find everything needed for running the demonstration here.

\$\endgroup\$

    1 Answer 1

    Reset to default
    1
    \$\begingroup\$

    Bug

    In pop_front(), you do this:

    p_list->head++;

    but it should have been this:

    p_list->head = (p_list->head + 1) & p_list->mask;

    You did this correctly in all the other places, so you must have missed this one.

    Slightly confusing loop

    In remove_at(), you have this loop:

     /* Move the preceding elements one position to the right. */ for (i = 0, j = elements_before; i < elements_before; ++i, --j) { p_list->p_table[(head + j) & mask] = p_list->p_table[(head + j - 1) & mask]; }

    This loop is correct but a little confusing to me because you have two loop variables. I think you could remove the i variable and just use j like this:

     /* Move the preceding elements one position to the right. */ for (j = elements_before; j > 0; --j) { p_list->p_table[(head + j) & mask] = p_list->p_table[(head + j - 1) & mask]; }

    Capacity

    I don't know if I like the fact that you are always rounding up the capacity to a power of 2. On the one hand, it makes the index calculation fast. On the other hand, if someone wanted a list with a fixed capacity, you might use up to double the memory required.

    Depending on the use case, either way might be better. But in my opinion, lower memory usage would be more beneficial than the performance hit from using a modulo operator.

    \$\endgroup\$

      Start asking to get answers

      Find the answer to your question by asking.

      Ask question

      Explore related questions

      See similar questions with these tags.