1
\$\begingroup\$

I just finished this big project. Its is called SortedList and it is implemented using a Doubly-Linked List. It data is of type void* and it has 4 default functions: compare, copy, display and free. What they do is in the documented code.

This data structure is my most advanced one and I'd like to have it as a reference to my other data structures, like the way it is documented, the way it is implemented and so on.

Any suggestions, are more than welcome. Feel free to give me a full feedback, even for the smallest details. Please focus on SortedList.h and SortedList.c. If you would like to help me in this project feel free to message me.

The documentation supports doxygen.

I'm making a data structures library located here. My intentions with it is purely educational. So code readability and documentations are key to this project. I do not intend for these structures to be fast and industrial-grade. I just hope this will one day be useful for students and enthusiasts.

P.S. I had to remove a lot of content due to text size limitations like Core.h and CoreSort.h. I also haven't had time to make tests. You can check the latest advancements in the Github repository linked above.

SortedList.h

#ifndef C_DATASTRUCTURES_LIBRARY_SORTEDLIST_H
#define C_DATASTRUCTURES_LIBRARY_SORTEDLIST_H

#include "Core.h"
#include "CoreSort.h"

#ifdef __cplusplus
extern "C" {
#endif

// A sorted doubly-linked list. See the source file for the full documentation.
struct SortedList_s;

/// \brief A type for a sorted doubly-linked list.
///
/// A type for a <code> struct SortedList_s </code> so you don't have to always
/// write the full name of it.
typedef struct SortedList_s SortedList_t;

/// \brief A pointer type for a sorted doubly-linked list.
///
/// Useful for not having to declare every variable as pointer type. This
/// typedef does that for you.
typedef struct SortedList_s *SortedList;

/// \brief Comparator function type.
///
/// A type for a function that compares two elements, returning:
/// - [ > 0] when the first element is greater than the second;
/// - [ < 0] when the first element is less than the second;
/// - 0 when both elements are equal.
typedef int(*sli_compare_f)(void *, void *);

/// \brief A Copy function type.
///
/// A type for a function that takes an input (first parameter) and returns an
/// exact copy of that element.
typedef void *(*sli_copy_f)(void *);

/// \brief Display function type.
///
/// A type for a function that displays an element in the console. Please do
/// not print a newline character.
typedef void(*sli_display_f)(void *);

/// \brief A Free function type.
///
/// A type for a function responsible for completely freeing an element from
/// memory.
typedef void(*sli_free_f)(void *);

///////////////////////////////////// STRUCTURE INITIALIZATION AND DELETION ///

Status sli_init(SortedList *list);

Status sli_create(SortedList *list, SortOrder order, sli_compare_f compare_f,
                sli_copy_f copy_f, sli_display_f display_f, sli_free_f free_f);

Status sli_free(SortedList *list);

Status sli_erase(SortedList *list);

/////////////////////////////////////////////////////////////////// SETTERS ///

Status sli_set_func_compare(SortedList list, sli_compare_f function);

Status sli_set_func_copy(SortedList list, sli_copy_f function);

Status sli_set_func_display(SortedList list, sli_display_f function);

Status sli_set_func_free(SortedList list, sli_free_f function);

Status sli_set_limit(SortedList list, index_t limit);

Status sli_set_order(SortedList list, SortOrder order);

// No setter because the user might break the sorted property of the list.

/////////////////////////////////////////////////////////////////// GETTERS ///

index_t sli_length(SortedList list);

index_t sli_limit(SortedList list);

SortOrder sli_order(SortedList list);

Status sli_get(SortedList list, void **result, index_t index);

////////////////////////////////////////////////////////// INPUT AND OUTPUT ///

Status sli_insert(SortedList list, void *element);

Status sli_insert_all(SortedList list, void **elements, index_t count);

Status sli_remove(SortedList list, void **result, index_t position);

Status sli_remove_max(SortedList list, void **result);

Status sli_remove_min(SortedList list, void **result);

/////////////////////////////////////////////////////////// STRUCTURE STATE ///

bool sli_full(SortedList list);

bool sli_empty(SortedList list);

/////////////////////////////////////////////////////////////////// UTILITY ///

void *sli_max(SortedList list);

void *sli_min(SortedList list);

index_t sli_index_first(SortedList list, void *key);

index_t sli_index_last(SortedList list, void *key);

bool sli_contains(SortedList list, void *key);

Status sli_reverse(SortedList list);

Status sli_copy(SortedList list, SortedList *result);

Status sli_to_array(SortedList list, void ***result, index_t *length);

/////////////////////////////////////////////////////////////////// LINKING ///

Status sli_merge(SortedList list1, SortedList list2);

Status sli_unlink(SortedList list, SortedList *result, index_t position);

Status sli_sublist(SortedList list, SortedList *result, index_t start,
        index_t end);

/////////////////////////////////////////////////////////////////// DISPLAY ///

Status sli_display(SortedList list);

Status sli_display_array(SortedList list);

Status sli_display_raw(SortedList list);

///////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////// Iterator ///
///////////////////////////////////////////////////////////////////////////////

// A sorted list iterator. See the source file for the full documentation.
struct SortedListIterator_s;

/// \brief A type for a sorted list iterator.
///
/// A type for a <code> struct SortedListIterator_s </code>.
typedef struct SortedListIterator_s SortedListIterator_t;

/// \brief A pointer type for a sorted list iterator.
///
/// A pointer type for a <code> struct SortedListIterator_s </code>.
typedef struct SortedListIterator_s *SortedListIterator;

///////////////////////////////////// STRUCTURE INITIALIZATION AND DELETION ///

Status sli_iter_init(SortedListIterator *iter, SortedList target);

Status sli_iter_retarget(SortedListIterator *iter, SortedList target);

Status sli_iter_free(SortedListIterator *iter);

///////////////////////////////////////////////////////////////// ITERATION ///

Status sli_iter_next(SortedListIterator iter);

Status sli_iter_prev(SortedListIterator iter);

Status sli_iter_to_head(SortedListIterator iter);

Status sli_iter_to_tail(SortedListIterator iter);

/////////////////////////////////////////////////////////// STRUCTURE STATE ///

bool sli_iter_has_next(SortedListIterator iter);

bool sli_iter_has_prev(SortedListIterator iter);

////////////////////////////////////////////////////////// SETTER AND GETTER ///

/// Gets a copy of the element pointed by the cursor.
Status sli_iter_get(SortedListIterator iter, void **result);

// No setter because the user might break the sorted property of the list.

////////////////////////////////////////////////////////// INPUT AND OUTPUT ///

// No insert functions because the user might break the sorted property.

Status sli_iter_remove_next(SortedListIterator iter, void **result);

Status sli_iter_remove_curr(SortedListIterator iter, void **result);

Status sli_iter_remove_prev(SortedListIterator iter, void **result);

/////////////////////////////////////////////////////////////////// UTILITY ///

void *sli_iter_peek_next(SortedListIterator iter);

void *sli_iter_peek(SortedListIterator iter);

void *sli_iter_peek_prev(SortedListIterator iter);

#ifdef __cplusplus
}
#endif

#endif //C_DATASTRUCTURES_LIBRARY_SORTEDLIST_H

SortedList.c

Sadly the source code is too big so I have omitted all the iterator's functions... You can still check it out here.

#include "SortedList.h"

/// \brief A generic sorted doubly-linked list.
///
/// This is a generic sorted doubly-linked list. Its elements can be added in
/// ASCENDING or DESCENDING order. This property can be set when creating a new
/// list or using sli_set_order(). You can also limit its length using
/// sli_set_limit(). To remove this limitation simply set the limit to a value
/// less than or equal to 0.
///
/// To initialize a list use sli_init(). This only initializes the structure.
/// If you don't set the proper functions later you won't be able to insert
/// elements, copy the list, display the list or even delete it. If you want to
/// initialize it completely, use instead sli_create(). Here you must pass in
/// default functions (compare, copy, display and free), making a complete
/// list.
///
/// To add an element to the list use sli_insert(). To remove, you have three
/// options: sli_remove() that removes an element at a given position;
/// sli_remove_max() that removes the biggest element; and sli_remove_min()
/// that removes the smallest element.
///
/// To delete a list use sli_free(). This completely frees all elements and
/// sets the list pointer to NULL. Note that if you haven't set a delete
/// function you won't be able to delete the list or its elements. You must set
/// a delete function that will be responsible for freeing from memory all
/// elements.
struct SortedList_s
{
    /// \brief List length.
    ///
    /// List current amount of elements linked between the \c head and \c tail
    /// pointers.
    index_t length;

    /// \brief List length limit.
    ///
    /// If it is set to 0 or a negative value then the list has no limit to its
    /// length. Otherwise it won't be able to have more elements than the
    /// specified value. The list is always initialized with no restrictions to
    /// its length, that is, \c limit equals 0. The user won't be able to limit
    /// the list length if it already has more elements than the specified
    /// limit.
    index_t limit;

    /// \brief Points to the first Node on the list.
    ///
    /// Points to the first Node on the list or \c NULL if the list is empty.
    struct SortedListNode_s *head;

    /// \brief Points to the last Node on the list.
    ///
    /// Points to the first Node on the list or \c NULL if the list is empty.
    struct SortedListNode_s *tail;

    /// \brief Defines the order of elements.
    ///
    /// The order of elements can either be \c ASCENDING or \c DESCENDING.
    SortOrder order;

    /// \brief Comparator function.
    ///
    /// A function that compares one element with another that returns an int
    /// with the following rules:
    ///
    /// - <code>[ > 0 ]</code> if first element is greater than the second;
    /// - <code>[ < 0 ]</code> if second element is greater than the first;
    /// - <code>[ 0 ]</code> if elements are equal.
    sli_compare_f d_compare;

    /// \brief Copy function.
    ///
    /// A function that returns an exact copy of an element.
    sli_copy_f d_copy;

    /// \brief Display function.
    ///
    /// A function that displays an element in the console. Useful for
    /// debugging.
    sli_display_f d_display;

    /// \brief Deallocator function.
    ///
    /// A function that completely frees an element from memory.
    sli_free_f d_free;

    /// \brief A version id to keep track of modifications.
    ///
    /// This version id is used by the iterator to check if the structure was
    /// modified. The iterator can only function if its version_id is the same
    /// as the structure's version id, that is, there have been no structural
    /// modifications (except for those done by the iterator itself).
    index_t version_id;
};

/// \brief A SortedList_s node.
///
/// Implementation detail. This is a doubly-linked node with a pointer to the
/// previous node (or \c NULL if it is the head node) and another pointer to
/// the next node (or \c NULL if it is the tail node).
struct SortedListNode_s
{
    /// \brief Data pointer.
    ///
    /// Points to node's data. The data needs to be dynamically allocated.
    void *data;

    /// \brief Next node on the list.
    ///
    /// Next node on the list or \c NULL if this is the tail node.
    struct SortedListNode_s *next;

    /// \brief Previous node on the list.
    ///
    /// Previous node on the list or \c NULL if this is the head node.
    struct SortedListNode_s *prev;
};

/// \brief A type for a sorted list node.
///
/// Defines a type to a <code> struct SortedListNode_s </code>.
typedef struct SortedListNode_s SortedListNode_t;

/// \brief A pointer type for a sorted list node.
///
/// Define a pointer type to a <code> struct SortedListNode_s </code>.
typedef struct SortedListNode_s *SortedListNode;

///////////////////////////////////////////////////// NOT EXPOSED FUNCTIONS ///

static Status sli_make_node(SortedListNode *node, void *data);

static Status sli_free_node(SortedListNode *node, sli_free_f free_f);

static Status sli_get_node_at(SortedList list, SortedListNode *result,
        index_t position);

static Status sli_insert_tail(SortedList list, void *element);

////////////////////////////////////////////// END OF NOT EXPOSED FUNCTIONS ///

/// \brief Initializes the SortedList_s structure.
///
/// This function initializes the SortedList_s structure but does not sets any
/// default functions. If you don't set them latter you won't be able to add
/// elements, copy the list, free the list or display it. It also sets a
/// default order of \c DESCENDING.
///
/// \param[in,out] list SortedList_s to be allocated.
///
/// \return DS_ERR_ALLOC if list allocation failed.
/// \return DS_OK if all operations are successful.
Status sli_init(SortedList *list)
{
    *list = malloc(sizeof(SortedList_t));

    if (!(*list))
        return DS_ERR_ALLOC;

    (*list)->length = 0;
    (*list)->limit = 0;
    (*list)->version_id = 0;

    (*list)->order = DESCENDING;

    (*list)->head = NULL;
    (*list)->tail = NULL;

    (*list)->d_compare = NULL;
    (*list)->d_copy = NULL;
    (*list)->d_display = NULL;
    (*list)->d_free = NULL;

    return DS_OK;
}

/// \brief Creates a SortedList_s.
///
/// This function completely creates a SortedList_s. This sets the list order
/// of elements and all of its default functions.
///
/// \param[in,out] list SortedList_s to be allocated.
/// \param[in] order The sorting order of the list's elements.
/// \param[in] compare_f A function that compares two elements.
/// \param[in] copy_f A function that makes an exact copy of an element.
/// \param[in] display_f A function that displays in the console an element.
/// \param[in] free_f A function that completely frees from memory an element.
///
/// \return DS_ERR_ALLOC if list allocation failed.
/// \return DS_OK if all operations are successful.
Status sli_create(SortedList *list, SortOrder order, sli_compare_f compare_f,
        sli_copy_f copy_f, sli_display_f display_f, sli_free_f free_f)
{
    *list = malloc(sizeof(SortedList_t));

    if (!(*list))
        return DS_ERR_ALLOC;

    (*list)->length = 0;
    (*list)->limit = 0;
    (*list)->version_id = 0;

    (*list)->order = order;

    (*list)->head = NULL;
    (*list)->tail = NULL;

    (*list)->d_compare = compare_f;
    (*list)->d_copy = copy_f;
    (*list)->d_display = display_f;
    (*list)->d_free = free_f;

    return DS_OK;
}

/// \brief Frees from memory a SortedList_s and all its elements.
///
/// This function frees from memory all the list's elements using its default
/// free function and then frees the list's structure. The variable is then set
/// to \c NULL.
///
/// \param[in,out] list SortedList_s to be freed from memory.
///
/// \return DS_ERR_INCOMPLETE_TYPE if a default free function is not set.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_free(SortedList *list)
{
    if (*list == NULL)
        return DS_ERR_NULL_POINTER;

    if ((*list)->d_free == NULL)
        return DS_ERR_INCOMPLETE_TYPE;

    SortedListNode prev = (*list)->head;

    Status st;

    while ((*list)->head != NULL)
    {
        (*list)->head = (*list)->head->next;

        st = sli_free_node(&prev, (*list)->d_free);

        if (st != DS_OK)
            return st;

        prev = (*list)->head;
    }

    free((*list));

    (*list) = NULL;

    return DS_OK;
}

/// \brief Erases a SortedList_s.
///
/// This function is equivalent to freeing a list and the creating it again.
/// This will reset the list to its initial state with no elements, but will
/// keep all of its default functions and the order of elements.
///
/// \param[in,out] list SortedList_s to be erased.
///
/// \return DS_ERR_INCOMPLETE_TYPE if a default free function is not set.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_erase(SortedList *list)
{
    if (*list == NULL)
        return DS_ERR_NULL_POINTER;

    SortedList new_list;

    Status st = sli_create(&new_list, (*list)->order, (*list)->d_compare,
            (*list)->d_copy, (*list)->d_display, (*list)->d_free);

    if (st !=  DS_OK)
        return st;

    st = sli_free(list);

    // Probably didn't set the free function...
    if (st !=  DS_OK)
    {
        free(new_list);

        return st;
    }

    *list = new_list;

    return DS_OK;
}

/// \brief Sets the default compare function.
///
/// Use this function to set a default compare function. It can only be done
/// when the list is empty, otherwise you would have elements sorted with a
/// different logic. The function needs to comply with the sli_compare_f
/// specifications.
///
/// \param[in] list SortedList_s to set the default compare function.
/// \param[in] function An sli_compare_f kind of function.
///
/// \return DS_ERR_INVALID_OPERATION if the list is not empty.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_set_func_compare(SortedList list, sli_compare_f function)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    // Can only set a new compare function if the list is empty, otherwise you
    // would be adding new elements in the list with a different logic than the
    // elements already in the list.
    if (!sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    list->d_compare = function;

    return DS_OK;
}

/// \brief Sets the default copy function.
///
/// Use this function to set a default compare function. It needs to comply
/// with the sli_copy_f specifications.
///
/// \param[in] list SortedList_s to set the default copy function.
/// \param[in] function An sli_copy_f kind of function.
///
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_set_func_copy(SortedList list, sli_copy_f function)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    list->d_copy = function;

    return DS_OK;
}

/// \brief Sets the default display function
///
/// Use this function to set a default display function. It needs to comply
/// with the sli_display_f specifications. Useful for debugging.
///
/// \param[in] list SortedList_s to set the default display function.
/// \param[in] function An sli_display_f kind of function.
///
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_set_func_display(SortedList list, sli_display_f function)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    list->d_display = function;

    return DS_OK;
}

/// \brief Sets the default free function
///
/// Use this function to set a default free function. It needs to comply
/// with the sli_free_f specifications.
///
/// \param[in] list SortedList_s to set the default free function.
/// \param[in] function An sli_free_f kind of function.
///
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_set_func_free(SortedList list, sli_free_f function)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    list->d_free = function;

    return DS_OK;
}

/// \brief Sets a limit to the specified SortedList_s's length.
///
/// Limit's the SortedList_s's length. You can only set a limit greater or
/// equal to the list's current length and greater than 0. To remove this
/// limitation simply set the limit to 0 or less.
///
/// \param[in] list SortedList_s reference.
/// \param[in] limit Maximum list length.
///
/// \return DS_ERR_INVALID_OPERATION if the limitation is less than the list's
/// current length.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_set_limit(SortedList list, index_t limit)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    // The new limit can't be lower than the list's current length.
    if (list->length > limit && limit > 0)
        return DS_ERR_INVALID_OPERATION;

    list->limit = limit;

    return DS_OK;
}

/// \brief Sets the sorting order of elements of the specified SortedList_s.
///
/// Sets the sorting order of elements to either \c ASCENDING or \c DESCENDING.
/// You can only set it when the list is empty.
///
/// \param[in] list SortedList_s reference.
/// \param[in] order Sorting order of elements.
///
/// \return DS_ERR_INVALID_OPERATION if the list is not empty.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_set_order(SortedList list, SortOrder order)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (!sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    list->order = order;

    return DS_OK;
}

/// \brief Returns the SortedList_s's length.
///
/// Returns the list's current length or -1 if the list references to \c NULL.
///
/// \param[in] list SortedList_s reference.
///
/// \return -1 if the list reference is \c NULL.
/// \return The list's length.
index_t sli_length(SortedList list)
{
    if (list == NULL)
        return -1;

    return list->length;
}

/// \brief Returns the SortedList_s's limit.
///
/// Returns the list limit or -1 if the list references to \c NULL.
///
/// \param[in] list SortedList_s reference.
///
/// \return -1 if the list reference is \c NULL.
/// \return The list's limit.
index_t sli_limit(SortedList list)
{
    if (list == NULL)
        return -1;

    return list->limit;
}

/// \brief Returns the SortedList_s's sorting order.
///
/// Return the list's sorting order, either ASCENDING, DESCENDING or 0 if the
/// list references to \c NULL.
///
/// \param[in] list SortedList_s reference.
///
/// \return 0 if the list references to \c NULL.
/// \return The list order.
SortOrder sli_order(SortedList list)
{
    if (list == NULL)
        return 0;

    return list->order;
}

/// \brief Returns a copy of an element at a given position.
///
/// This function is zero-based and returns a copy of the element located at
/// the specified index.
///
/// \param[in] list SortedList_s reference.
/// \param[out] result Resulting copy of the element.
/// \param[in] index Element position.
///
/// \return DS_ERR_INCOMPLETE_TYPE if a default copy function is not set.
/// \return DS_ERR_INVALID_OPERATION if the list is empty.
/// \return DS_ERR_NEGATIVE_VALUE if index parameter is negative.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_ERR_OUT_OF_RANGE if index parameter is greater than or equal
/// to the list's length.
/// \return DS_OK if all operations are successful.
Status sli_get(SortedList list, void **result, index_t index)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    if (index < 0)
        return DS_ERR_NEGATIVE_VALUE;

    if (index >= list->length)
        return DS_ERR_OUT_OF_RANGE;

    if (list->d_copy == NULL)
        return DS_ERR_INCOMPLETE_TYPE;

    SortedListNode node;

    Status st = sli_get_node_at(list, &node, index);

    if (st != DS_OK)
        return st;

    *result = list->d_copy(node->data);

    return DS_OK;
}

/// \brief Inserts an element to the specified SortedList_s.
///
/// Inserts an element according to the sort order specified by the list. This
/// function can take up to O(n) to add an element in its correct position.
///
/// \param[in] list SortedList_s reference where the element is to be inserted.
/// \param[in] element Element to be inserted in the list.
///
/// \return DS_ERR_FULL if \c limit is set (different than 0) and the list
/// length reached the specified limit.
/// \return DS_ERR_INCOMPLETE_TYPE if a default compare function is not set.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_insert(SortedList list, void *element)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (list->d_compare == NULL)
        return DS_ERR_INCOMPLETE_TYPE;

    if (sli_full(list))
        return DS_ERR_FULL;

    SortedListNode node;

    Status st = sli_make_node(&node, element);

    if (st != DS_OK)
        return st;

    // First node.
    if (sli_empty(list))
    {
        list->head = node;
        list->tail = node;
    }
    // Insert node in its position.
    else
    {
        SortedListNode scan = list->head;
        SortedListNode before = NULL;

        if (list->order == ASCENDING)
        {
            // Insert 'head'. Change list->head.
            if (list->d_compare(node->data, list->head->data) <= 0)
            {
                // The new element will be the new smallest element.
                node->next = list->head;

                list->head->prev = node;

                list->head = node;
            }
            else
            {
                while (scan != NULL &&
                       list->d_compare(node->data, scan->data) > 0)
                {
                    before = scan;

                    scan = scan->next;
                }

                // Insert 'tail'. Change list->tail.
                if (scan == NULL)
                {
                    // The new element will be the new biggest element.
                    node->prev = before;

                    before->next = node;

                    list->tail = node;
                }
                // Insert at the middle of the list.
                else
                {
                    before->next = node;
                    scan->prev = node;

                    node->next = scan;
                    node->prev = before;
                }
            }
        }
        // Defaults to DESCENDING.
        else
        {
            // Insert 'head'. Change list->head.
            if (list->d_compare(node->data, list->head->data) >= 0)
            {
                // The new element will be the new biggest element.
                node->next = list->head;

                list->head->prev = node;

                list->head = node;
            }
            else
            {
                while (scan != NULL &&
                       list->d_compare(node->data, scan->data) < 0)
                {
                    before = scan;

                    scan = scan->next;
                }

                // Insert 'tail'. Change list->tail.
                if (scan == NULL)
                {
                    // The new element will be the new smallest element.
                    node->prev = before;

                    before->next = node;

                    list->tail = node;
                }
                // Insert at the middle of the list.
                else
                {
                    before->next = node;

                    scan->prev = node;

                    node->next = scan;
                    node->prev = before;
                }
            }
        }
    }

    list->length++;

    list->version_id++;

    return DS_OK;
}

/// \brief Inserts an array of elements to the specified SortedList_s.
///
/// Inserts an array of void pointers into the list, with a size of \c count.
///
/// \param[in] list SortedList_s reference where all elements are to be
/// inserted.
/// \param[in] elements Elements to be inserted in the list.
/// \param[in] count Amount of elements to be inserted.
///
/// \return DS_ERR_NEGATIVE_VALUE if count parameter is negative.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_insert_all(SortedList list, void **elements, index_t count)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (count < 0)
        return DS_ERR_NEGATIVE_VALUE;

    Status st;

    for (index_t i = 0; i < count; i++)
    {
        st = sli_insert(list, elements[i]);

        if (st != DS_OK)
            return st;
    }

    return DS_OK;
}

/// \brief Removes an element at a specified position from a SortedList_s.
///
/// Removes an element at the specified position. The position is 0 based so
/// the first element is at the position 0.
///
/// \param[in] list SortedList_s reference where an element is to be removed.
/// \param[out] result Resulting element removed from the list.
/// \param[in] position Element's position.
///
/// \return DS_ERR_INVALID_OPERATION if list is empty.
/// \return DS_ERR_ITER if during iteration the scanner references to \c NULL.
/// \return DS_ERR_NEGATIVE_VALUE if position parameter is negative.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_ERR_OUT_OF_RANGE if position parameter is greater than or equal
/// to the list's length.
/// \return DS_OK if all operations are successful.
Status sli_remove(SortedList list, void **result, index_t position)
{
    *result = NULL;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    if (position < 0)
        return DS_ERR_NEGATIVE_VALUE;

    if (position >= list->length)
        return DS_ERR_OUT_OF_RANGE;

    SortedListNode node;

    // Remove head
    if (position == 0)
    {
        node = list->head;

        *result = node->data;

        list->head = list->head->next;

        if (list->head != NULL)
            list->head->prev = NULL;
    }
    // Remove tail
    else if (position == list->length - 1)
    {
        node = list->tail;

        *result = node->data;

        list->tail = list->tail->prev;

        if (list->tail != NULL)
            list->tail->next = NULL;
    }
    // Remove somewhere in the middle
    else
    {
        Status st = sli_get_node_at(list, &node, position);

        if (st != DS_OK)
            return st;

        // Unlink the current node
        // Behold the power of doubly-linked lists!
        node->prev->next = node->next;
        node->next->prev = node->prev;

        *result = node->data;
    }

    free(node);

    list->length--;

    list->version_id++;

    if (sli_empty(list))
    {
        list->head = NULL;
        list->tail = NULL;
    }

    return DS_OK;
}

/// \brief Removes the highest value from the specified SortedList_s.
///
/// Removes the highest value from the list. Depending on the sort order of
/// elements this function is equivalent to removing an element from the head
/// of the list or from tail.
///
/// \param[in] list SortedList_s reference where an element is to be removed.
/// \param[out] result Resulting element removed from the list.
///
/// \return DS_ERR_INVALID_OPERATION if list is empty.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_remove_max(SortedList list, void **result)
{
    *result = NULL;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    SortedListNode node;

    // Remove from tail.
    if (list->order == ASCENDING)
    {
        node = list->tail;

        *result = node->data;

        list->tail = list->tail->prev;
        list->tail->next = NULL;

        free(node);
    }
    // Remove from head.
    else
    {
        node = list->head;

        *result = node->data;

        list->head = list->head->next;
        list->head->prev = NULL;

        free(node);
    }

    list->length--;

    if (sli_empty(list))
    {
        list->head = NULL;
        list->tail = NULL;
    }

    list->version_id++;

    return DS_OK;
}

/// \brief Removes the smallest value from the specified SortedList_s.
///
/// Removes the smallest value from the list. Depending on the sort order of
/// elements this function is equivalent to removing an element from the head
/// of the list or from tail.
///
/// \param[in] list SortedList_s reference where an element is to be removed.
/// \param[out] result Resulting element removed from the list.
///
/// \return DS_ERR_INVALID_OPERATION if list is empty.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_remove_min(SortedList list, void **result)
{
    *result = NULL;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    SortedListNode node;

    // Remove from head.
    if (list->order == ASCENDING)
    {
        node = list->head;

        *result = node->data;

        list->head = list->head->next;
        list->head->prev = NULL;

        free(node);
    }
    // Remove from tail.
    else
    {
        node = list->tail;

        *result = node->data;

        list->tail = list->tail->prev;
        list->tail->next = NULL;

        free(node);
    }

    list->length--;

    if (sli_empty(list))
    {
        list->head = NULL;
        list->tail = NULL;
    }

    list->version_id++;

    return DS_OK;
}

/// \brief Checks if the specified SortedList_s is full.
///
/// Returns true if the list is full or false otherwise. The list can only be
/// full if its limit is set to a value higher than 0 and respecting all rules
/// from sli_set_limit().
///
/// \warning This function does not checks for \c NULL references and is prone
/// to provoke run-time errors if not used correctly.
///
/// \param[in] list SortedList_s reference.
///
/// \return True if the list is full.
/// \return False if the list is not full.
bool sli_full(SortedList list)
{
    return list->limit > 0 && list->length >= list->limit;
}

/// \brief Checks if specified SortedList_s list is empty.
///
/// Returns true if the list is empty or false otherwise. The list is empty
/// when its length is 0. If every function works properly there is no need to
/// check if the head or tail pointers are \c NULL or not. The length variable
/// already tracks it.
///
/// \warning This function does not checks for \c NULL references and is prone
/// to provoke run-time errors if not used correctly.
///
/// \param[in] list SortedList_s reference.
///
/// \return True if the list is empty.
/// \return False if the list is not empty.
bool sli_empty(SortedList list)
{
    return list->length == 0;
}

/// \brief Returns the highest element from the specified SortedList_s.
///
/// Returns a reference to the highest element in the list or NULL if the list
/// is empty. Use this as a read-only. If you make any changes to this element
/// the internal structure of the list will change and may cause undefined
/// behaviour.
///
/// \param[in] list SortedList_s reference.
///
/// \return NULL if the list references to \c NULL or if the list is empty.
/// \return The highest element in the list.
void *sli_max(SortedList list)
{
    if (list == NULL)
        return NULL;

    if (sli_empty(list))
        return NULL;

    if (list->order == ASCENDING)
        return list->tail->data;

    return list->head->data;
}

/// \brief Returns the smallest element from the specified SortedList_s.
///
/// Returns a reference to the smallest element in the list or NULL if the list
/// is empty. Use this as a read-only. If you make any changes to this element
/// the internal structure of the list will change and may cause undefined
/// behaviour.
///
/// \param[in] list SortedList_s reference.
///
/// \return NULL if the list references to \c NULL or if the list is empty.
/// \return The highest element in the list.
void *sli_min(SortedList list)
{
    if (list == NULL)
        return NULL;

    if (sli_empty(list))
        return NULL;

    if (list->order == ASCENDING)
        return list->head->data;

    return list->tail->data;
}

/// \brief Returns the index of the first element that matches a key.
///
/// Returns the index of the first element that matches a given key or -1 if it
/// could not be found.
///
/// \param[in] list SortedList_s reference.
/// \param[in] key Key to be searched in the list.
///
/// \return -2 if the list references to \c NULL.
/// \return -1 if the element was not found.
/// \return The index of the matched element.
index_t sli_index_first(SortedList list, void *key)
{
    if (list == NULL)
        return -2;

    SortedListNode scan = list->head;

    index_t index = 0;

    while (scan != NULL)
    {
        if (list->d_compare(scan->data, key) == 0)
            return index;

        index++;

        scan = scan->next;
    }

    return -1;
}

/// \brief Returns the index of the last element that matches a key.
///
/// Returns the index of the first element that matches a given key or -1 if it
/// could not be found.
///
/// \param[in] list SortedList_s reference.
/// \param[in] key Key to be searched in the list.
///
/// \return -2 if the list references to \c NULL.
/// \return -1 if the element was not found.
/// \return The index of the matched element.
index_t sli_index_last(SortedList list, void *key)
{
    if (list == NULL)
        return -2;

    SortedListNode scan = list->tail;

    index_t index = 0;

    while (scan != NULL)
    {
        if (list->d_compare(scan->data, key) == 0)
            return list->length - 1 - index;

        index++;

        scan = scan->prev;
    }

    return -1;
}

/// \brief Checks if a given element is present in the specified SortedList_s.
///
/// Returns true if the element is present in the list, otherwise false.
///
/// \warning This function does not checks for \c NULL references for either
/// the list parameter or if the default compare function is set.
///
/// \param[in] list SortedList_s reference.
/// \param[in] key Key to be matched.
///
/// \return True if the element is present in the list.
/// \return False if the element is not present in the list.
bool sli_contains(SortedList list, void *key)
{
    SortedListNode scan = list->head;

    while (scan != NULL)
    {
        if (list->d_compare(scan->data, key) == 0)
            return true;

        scan = scan->next;
    }

    return false;
}

/// \brief Reverses a SortedList_s.
///
/// Reverses the chain of elements from the list and changes the sort order of
/// elements. This function only changes the \c next and \c prev pointers from
/// each element and the \c head and \c tail pointers of the list struct.
///
/// \param[in] list SortedList_s reference to be reversed.
///
/// \return DS_ERR_NULL_POINTER if node references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_reverse(SortedList list)
{
    // Reverse just like a doubly-linked list and change the list order
    // ASCENDING -> DESCENDING
    // DESCENDING -> ASCENDING

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (list->length != 1)
    {
        SortedListNode prev = NULL;
        SortedListNode curr = list->head;
        SortedListNode next = NULL;

        list->tail = list->head;

        while (curr != NULL)
        {
            next = curr->next;

            curr->next = prev;
            curr->prev = next;

            prev = curr;

            curr = next;
        }

        list->head = prev;
    }

    // If list length is 1 then just by doing this will do the trick
    list->order = (list->order == ASCENDING) ? DESCENDING : ASCENDING;

    list->version_id++;

    return DS_OK;
}

/// \brief Makes a copy of the specified SortedList_s.
///
/// Makes an exact copy of a list.
///
/// \param[in] list SortedList_s to be copied.
/// \param[out] result Resulting copy.
///
/// \return DS_ERR_INCOMPLETE_TYPE if either a default copy or a default free
/// functions are not set.
/// \return DS_ERR_NULL_POINTER if node references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_copy(SortedList list, SortedList *result)
{
    *result = NULL;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (list->d_copy == NULL || list->d_free == NULL)
        return DS_ERR_INCOMPLETE_TYPE;

    Status st = sli_create(result, list->order, list->d_compare, list->d_copy,
            list->d_display, list->d_free);

    if (st != DS_OK)
        return st;

    (*result)->limit = list->limit;

    SortedListNode scan = list->head;

    void *elem;

    while (scan != NULL)
    {
        elem = list->d_copy(scan->data);

        st = sli_insert_tail(*result, elem);

        if (st != DS_OK)
        {
            list->d_free(elem);

            return st;
        }

        scan = scan->next;
    }

    return DS_OK;
}

/// \brief Copies the elements of the list to a C array.
///
/// Makes a copy of every element into an array respecting the order of the
/// elements in the list. The array needs to be an array of void pointers and
/// uninitialized. If any error is returned, the default values for \c result
/// and \c length are \c NULL and -1 respectively.
///
/// \param[in] list SortedList_s reference.
/// \param[out] result Resulting array.
/// \param[out] length Resulting array's length.
///
/// \return DS_ERR_INCOMPLETE_TYPE if a default copy function is not set.
/// \return DS_ERR_NULL_POINTER if list references to \c NULL.
/// \return DS_OK if all operations are successful.
Status sli_to_array(SortedList list, void ***result, index_t *length)
{
    // If anything goes wrong...
    *result = NULL;
    *length = -1;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    if (list->d_copy == NULL)
        return DS_ERR_INCOMPLETE_TYPE;

    *length = list->length;

    *result = malloc(sizeof(void*) * (*length));

    if (!(*result))
        return DS_ERR_NULL_POINTER;

    SortedListNode scan = list->head;

    for (index_t i = 0; i < *length; i++)
    {
        (*result)[i] = list->d_copy(scan->data);

        scan = scan->next;
    }

    return DS_OK;
}

/// \brief Merge two SortedList_s.
///
/// Removes all elements from list2 and inserts them into list1.
///
/// \param[in] list1 SortedList_s where elements are added to.
/// \param[in] list2 SortedList_s where elements are removed from.
///
/// \return DS_ERR_NULL_POINTER if either list1 or list2 references are
/// \c NULL.
Status sli_merge(SortedList list1, SortedList list2)
{
    if (list1 == NULL || list2 == NULL)
        return DS_ERR_NULL_POINTER;

    Status st;

    void *result;

    while (!sli_empty(list2))
    {
        st = sli_remove(list2, &result, 0);

        if (st != DS_OK)
            return st;

        st = sli_insert(list1, result);

        if (st != DS_OK)
            return st;
    }

    return DS_OK;
}

/// \brief Unlinks elements from the specified SortedList_s.
///
/// Unlinks all elements starting from \c position all the way to the end of
/// the list. The \c result list must not have been initialized.
///
/// \param[in] list SortedList_s reference.
/// \param[out] result Resulting sublist.
/// \param[in] position Position to unlink the elements from the list.
///
/// \return DS_ERR_INVALID_OPERATION if the list is empty.
/// \return DS_ERR_NEGATIVE_VALUE if position parameter is negative.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_ERR_OUT_OF_RANGE if position parameter is greater than or equal
/// to the list's length.
/// \return DS_OK if all operations are successful.
Status sli_unlink(SortedList list, SortedList *result, index_t position)
{
    *result = NULL;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    if (position < 0)
        return DS_ERR_NEGATIVE_VALUE;

    if (position >= list->length)
        return DS_ERR_OUT_OF_RANGE;

    Status st = sli_create(result, list->order, list->d_compare, list->d_copy,
            list->d_display, list->d_free);

    if (st != DS_OK)
        return st;

    (*result)->limit = list->limit;

    SortedListNode node, new_tail;

    // Special case
    if (position == 0)
    {
        // Simply transfer everything from one list to another.
        (*result)->length = list->length;
        (*result)->head = list->head;
        (*result)->tail = list->tail;

        list->length = 0;
        list->head = NULL;
        list->tail = NULL;
    }
    else
    {
        st = sli_get_node_at(list, &node, position);

        if (st != DS_OK)
            return st;

        // New list tail. The position parameter is inclusive so go one node
        // back.
        new_tail = node->prev;

        // Separating chains.
        node->prev = NULL;
        new_tail->next = NULL;

        // Resulting list head is node and tail is the old list tail.
        (*result)->head = node;
        (*result)->tail = list->tail;

        list->tail = new_tail;

        // Recalculate lengths
        (*result)->length = list->length - position;

        list->length = position;
    }

    list->version_id++;

    return DS_OK;
}

/// \brief Extracts a sublist from the specified SortedList_s.
///
/// Extracts a sublist from the specified SortedList_s. The sublist is stored
/// in the \c result SortedList_s.
///
/// \param[in] list SortedList_s where the sublist is to be removed from.
/// \param[out] result An uninitialized SortedList_s to receive the resulting
/// sublist.
/// \param[in] start Start of the sublist.
/// \param[in] end End of the sublist.
///
/// \return DS_ERR_INVALID_ARGUMENT if the start parameter is greater than the
/// end parameter.
/// \return DS_ERR_INVALID_OPERATION if the list is empty.
/// \return DS_ERR_NEGATIVE_VALUE if either start or end parameters are
/// negative.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_ERR_OUT_OF_RANGE if the end parameter is greater than or equal
/// to the list's length.
/// \return DS_OK if all operations are successful.
Status sli_sublist(SortedList list, SortedList *result, index_t start,
        index_t end)
{
    *result = NULL;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (start < 0 || end < 0)
        return DS_ERR_NEGATIVE_VALUE;

    if (end < start)
        return DS_ERR_INVALID_ARGUMENT;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    if (end >= list->length)
        return DS_ERR_OUT_OF_RANGE;

    Status st = sli_create(result, list->order, list->d_compare, list->d_copy,
            list->d_display, list->d_free);

    if (st != DS_OK)
        return st;

    (*result)->limit = list->limit;

    SortedListNode node;

    // Remove only one node
    if (start == end)
    {
        st = sli_get_node_at(list, &node, start);

        if (st != DS_OK)
            return st;

        if (node->next != NULL)
            node->next->prev = node->prev;
        if (node->prev != NULL)
            node->prev->next = node->next;

        node->next = NULL, node->prev = NULL;

        (*result)->head = node;
        (*result)->tail = node;

    }
    // Simply transfer everything
    else if (start == 0 && end == list->length - 1)
    {
        (*result)->head = list->head;
        (*result)->tail = list->tail;

        list->head = NULL;
        list->tail = NULL;
    }
    // Remove from head to end
    else if (start == 0)
    {
        st = sli_get_node_at(list, &node, end);

        if (st != DS_OK)
            return st;

        // New list head. The position parameters are inclusive so go one node
        // forward.
        SortedListNode new_head = node->next;

        // Separating chains.
        node->next = NULL;
        new_head->prev = NULL;

        (*result)->head = list->head;
        (*result)->tail = node;

        list->head = new_head;
    }
    // Remove from start to tail
    else if (end == list->length - 1)
    {
        st = sli_get_node_at(list, &node, start);

        if (st != DS_OK)
            return st;

        // New list tail. The position parameters are inclusive so go one node
        // back.
        SortedListNode new_tail = node->prev;

        // Separating chains.
        node->prev = NULL;
        new_tail->next = NULL;

        // Resulting list head is node and tail is the old list tail.
        (*result)->head = node;
        (*result)->tail = list->tail;

        list->tail = new_tail;
    }
    // Start and end are inner nodes
    else
    {
        // 'before' the 'start' node and 'after' the 'end' node
        SortedListNode before, after;

        st += sli_get_node_at(list, &before, start - 1);
        st += sli_get_node_at(list, &after, end + 1);

        if (st != DS_OK)
            return st;

        (*result)->head = before->next;
        (*result)->tail = after->prev;

        before->next = after;
        after->prev = before;

        (*result)->head->prev = NULL;
        (*result)->tail->next = NULL;
    }

    (*result)->length = end - start + 1;

    list->length -= (*result)->length;

    list->version_id++;

    return DS_OK;
}

/// \brief Displays a SortedList_s in the console.
///
/// Displays a SortedList_s in the console with its elements separated by
/// arrows indicating a doubly-linked list.
///
/// \param[in] list The SortedList_s to be displayed in the console.
///
/// \return DS_ERR_INCOMPLETE_TYPE if a default display function is not set.
/// \return DS_ERR_NULL_POINTER if the list reference is \c NULL.
/// \return DS_OK if all operations were successful.
Status sli_display(SortedList list)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (list->d_display == NULL)
        return DS_ERR_INCOMPLETE_TYPE;

    if (sli_empty(list))
    {
        printf("\nSorted List\n[ empty ]\n");

        return DS_OK;
    }

    SortedListNode scan = list->head;

    printf("\nSorted List\nNULL <-> ");

    while (scan != NULL)
    {
        list->d_display(scan->data);

        printf(" <-> ");

        scan = scan->next;
    }

    printf(" NULL\n");

    return DS_OK;
}

/// \brief Displays a SortedList_s in the console.
///
/// Displays a SortedList_s in the console like an array with its elements
/// separated by commas, delimited with brackets.
///
/// \param[in] list The SortedList_s to be displayed in the console.
///
/// \return DS_ERR_INCOMPLETE_TYPE if a default display function is not set.
/// \return DS_ERR_NULL_POINTER if the list reference is \c NULL.
/// \return DS_OK if all operations were successful.
Status sli_display_array(SortedList list)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (list->d_display == NULL)
        return DS_ERR_INCOMPLETE_TYPE;

    if (sli_empty(list))
    {
        printf("\n[ empty ]\n");

        return DS_OK;
    }

    SortedListNode scan = list->head;

    printf("\nSorted List\n[ ");

    while (scan->next != NULL)
    {
        list->d_display(scan->data);

        printf(", ");

        scan = scan->next;
    }

    list->d_display(scan->data);

    printf(" ]\n");

    return DS_OK;
}

///////////////////////////////////////////////////// NOT EXPOSED FUNCTIONS ///

/// \brief Builds a new SortedListNode_s.
///
/// Implementation detail. Function responsible for allocating a new
/// SortedListNode_s.
///
/// \param[in,out] node SortedListNode_s to be allocated.
/// \param[in] data Node's data member.
///
/// \return DS_ERR_ALLOC if node allocation failed.
/// \return DS_OK if all operations are successful.
static Status sli_make_node(SortedListNode *node, void *data)
{
    *node = malloc(sizeof(SortedListNode_t));

    if (!(*node))
        return DS_ERR_ALLOC;

    (*node)->data = data;

    (*node)->next = NULL;
    (*node)->prev = NULL;

    return DS_OK;
}

/// \brief Frees a SortedListNode_s and its data.
///
/// Implementation detail. Frees a SortedListNode_s and its data using the
/// list's default free function.
///
/// \param[in,out] node SortedListNode_s to be freed from memory.
/// \param[in] free_f List's default free function.
///
/// \return DS_ERR_NULL_POINTER if node references to \c NULL.
/// \return DS_OK if all operations are successful.
static Status sli_free_node(SortedListNode *node, sli_free_f free_f)
{
    if (*node == NULL)
        return DS_ERR_NULL_POINTER;

    free_f((*node)->data);

    free(*node);

    *node = NULL;

    return DS_OK;
}

/// \brief Gets a node from a specific position.
///
/// Implementation detail. Searches for a node in O(n / 2), the search starts
/// at the tail pointer if position is greater than half the list's length,
/// otherwise it starts at the head pointer.
///
/// \param[in] list SortedList_s to search for the node.
/// \param[out] result Resulting node.
/// \param[in] position Node's position.
///
/// \return DS_ERR_INVALID_OPERATION if list is empty.
/// \return DS_ERR_ITER if during iteration the scanner references to \c NULL.
/// \return DS_ERR_NEGATIVE_VALUE if position parameter is negative.
/// \return DS_ERR_NULL_POINTER if the list references to \c NULL.
/// \return DS_ERR_OUT_OF_RANGE if position parameter is greater than or equal
/// to the list's length.
/// \return DS_OK if all operations are successful.
static Status sli_get_node_at(SortedList list, SortedListNode *result,
        index_t position)
{
    // This function effectively searches for a given node. If the position is
    // greater than the list length the search will begin at the end of the list,
    // reducing the amount of iterations needed. This effectively reduces searches
    // to O(n / 2) iterations.
    *result = NULL;

    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_empty(list))
        return DS_ERR_INVALID_OPERATION;

    if (position < 0)
        return DS_ERR_NEGATIVE_VALUE;

    if (position >= list->length)
        return DS_ERR_OUT_OF_RANGE;

    // Start looking for the node at the start of the list
    if (position <= list->length / 2)
    {
        (*result) = list->head;

        for (index_t i = 0; i < position; i++)
        {
            // Bad iteration :(
            if ((*result) == NULL)
                return DS_ERR_ITER;

            (*result) = (*result)->next;
        }
    }
    // Start looking for the node at the end of the list
    else
    {
        (*result) = list->tail;

        for (index_t i = list->length - 1; i > position; i--)
        {
            // Bad iteration :(
            if ((*result) == NULL)
                return DS_ERR_ITER;

            (*result) = (*result)->prev;
        }
    }

    return DS_OK;
}

/// \brief Inserts an element at the tail of the list.
///
/// Implementation detail. Used to copy a list.
///
/// \param[in] list SortedList_s to insert the element.
/// \param[in] element Element to be inserted at the tail of the list.
///
/// \return DS_ERR_FULL if the list has reached its limited length.
/// \return DS_ERR_NULL_POINTER if node references to \c NULL.
/// \return DS_OK if all operations are successful.
static Status sli_insert_tail(SortedList list, void *element)
{
    if (list == NULL)
        return DS_ERR_NULL_POINTER;

    if (sli_full(list))
        return DS_ERR_FULL;

    SortedListNode node;

    Status st = sli_make_node(&node, element);

    if (st != DS_OK)
        return st;

    if (sli_empty(list))
    {
        list->head = node;
        list->tail = node;
    }
    else
    {
        list->tail->next = node;

        node->prev = list->tail;

        list->tail = node;
    }

    (list->length)++;

    return DS_OK;
}

////////////////////////////////////////////// END OF NOT EXPOSED FUNCTIONS ///
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.