2
\$\begingroup\$

I just finished my linked list library in C and I am trying to find out what should be improved. The functions provided by the library are members of the main data structure (very important).

The entire project can be found here.

Here is the source:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cd9list.h"
#include "callbacks.h"

CD9Node *cd9list_createNode(const void *data, size_t size) 
{
    CD9Node *node = malloc(sizeof(CD9Node));
    if(node == NULL) { // Malloc failed.
        return NULL;
    }

    // Thus we can know when we reach the end of the list.
    if(size != SIZE_ZERO) {
        void *copy = malloc(size);
        memmove(copy, data, size);

        node->data = copy;
    }
    else {    
        memmove(&node->data, &data, sizeof(void *));
    }

    node->next = NULL;
    node->size = size;

    return node;
}

CD9Node *cd9list_getNode(const CD9List *list, size_t index) 
{
   CD9FOREACH_(list, node, i) {
        if(i == index) {
            return node;
        }
    }

    return NULL;
}

CD9List *cd9list_concat(CD9List *list1, CD9List *list2)
{
    CD9List *result   = list1->copy(list1);

    CD9FOREACH_(list2, node) {
        result->appendCopy(result, node->data, node->size);        
    }

    return result;
}

void *cd9list_copyNodeData(const CD9Node *node)
{
    // The user was careless, he shouldn't call this function on an empty
    // node.
    if(node->size == SIZE_ZERO) {
        return NULL; 
    }

    void *data = malloc(node->size);
    memmove(data, node->data, node->size);

    return data;
}

void *cd9list_get(void *self, size_t index)
{
    CD9List *list = (CD9List *)self;
    CD9Node *node = cd9list_getNode(list, index);

    return node->data;
}

void cd9list_append(void *self, const void *data)
{
    CD9List *list = (CD9List *)self;
    list->_insertCopy(list, list->length, data, SIZE_ZERO);
}

void cd9list_appendCopy(void *self, const void *data, size_t size)
{
    CD9List *list = (CD9List *)self;
    list->_insertCopy(list, list->length, data, size);
}

void cd9list_insert(void *self, size_t index, const void *data)
{
    CD9List *list = (CD9List *)self;
    list->_insertCopy(list, index, data, SIZE_ZERO);
}

void cd9list_prepend(void *self, const void *data)
{
    CD9List *list = (CD9List *)self;
    list->_insertCopy(list, 0, data, SIZE_ZERO);
}

void cd9list_prependCopy(void *self, const void *data, size_t size)
{
    CD9List *list = (CD9List *)self;
    list->_insertCopy(list, 0, data, size);
}

void *cd9list_pop(void *self)
{
    CD9List *list = (CD9List *)self;
    CD9Node *node = cd9list_getNode(list, list->length - 1);

    if(node->size == SIZE_ZERO) {
        void *tmp = node->data;
        list->remove(list, list->length - 1);

        return tmp; 
    }

    void *tmp = cd9list_copyNodeData(node);
    list->remove(list, list->length - 1);

    return tmp;
}

void *cd9list_popleft(void *self)
{
    CD9List *list = (CD9List *)self;
    CD9Node *node = cd9list_getNode(list, 0);

    if(node->size == SIZE_ZERO) {
        void *tmp = node->data;
        list->remove(list, 0);

        return tmp;
    }

    void *tmp = cd9list_copyNodeData(node);
    list->remove(list, 0);

    return tmp;
}

CD9List *cd9list_filter(void           *self, 
                        const void     *data,
                        CD9FindCallback cmp)
{
    CD9List *list         = (CD9List *)self;
    CD9List *filteredList = cd9list_createList();

    CD9FOREACH_(list, node) {
        if(!cmp(node->data, data, node->size)) {
            filteredList->appendCopy(filteredList, node->data, node->size);        
        }
    }

    return filteredList;
}    

CD9List *cd9list_filterByValue(void *self, const void *data)
{
    CD9List *list     = (CD9List *)self;
    CD9List *filtered = cd9list_createList();

    CD9FOREACH_(list, node) {
        if(node->size == SIZE_ZERO) {
            if(!callbacks_findByAddressCmp(node->data, data, 0)) {
                filtered->appendCopy(filtered, node->data, node->size);
            }
        }
        else {
            if(!callbacks_findByValueCmp(node->data, data, node->size)) {
                filtered->appendCopy(filtered, node->data, node->size);
            }
        }
    }

    return filtered;
}

CD9List *cd9list_filterBySet(void *self, CD9List *set)
{
    CD9List *list     = (CD9List *)self;
    CD9List *filtered = cd9list_createList();

    CD9FOREACH_(list, node) {
        if(node->size == SIZE_ZERO) {
            if(set->findByAddress(set, node->data) == -1) {
                filtered->appendCopy(filtered, node->data, node->size);
            }
        }
        else {
            if(set->findByValue(set, node->data) == -1) {
                filtered->appendCopy(filtered, node->data, node->size);
            }
        }
    }

    return filtered;
}

void cd9list_reverse(void *self)
{
    CD9List *list = (CD9List *)self;

    CD9Node *start = list->nodes->next;
    CD9Node *prev  = list->nodes;
    CD9Node *tmp;

    prev->next = NULL;

    while(start != NULL) {
        tmp = start->next;
        start->next = prev;
        prev = start;
        start = tmp;
    }

    list->nodes = prev;
}

void cd9list_insertCopy(void       *self, 
                        size_t     index, 
                        const void *data, 
                        size_t     size)
{
    CD9List *list = (CD9List *)self;

    if(index == 0) {
        CD9Node *node = cd9list_createNode(data, size);
        CD9Node *tmp = list->nodes;

        list->nodes = node;
        node->next = tmp;

        list->length++;

        return;
    }

    CD9Node *beforeDesiredNode = cd9list_getNode(list, index - 1); 
    CD9Node *tmp               = beforeDesiredNode->next;
    CD9Node *node              = cd9list_createNode(data, size);

    // Adjust the links.
    beforeDesiredNode->next = node;
    node->next = tmp;

    list->length++;
}

CD9List *cd9list_copy(void *self)
{
    CD9List *list       = (CD9List *)self;
    CD9List *secondList = cd9list_createList();

    CD9FOREACH_(list, node) {
        secondList->appendCopy(secondList, node->data, node->size);
    }

    return secondList;
}

CD9List *cd9list_slice(void *self, int start, int stop, size_t step)
{
    CD9List *list   = (CD9List *)self;
    CD9List *result = cd9list_createList();

    if(start < 0) {
        // Since start is negatice, adding it is equivalent to the substraction
        // of the absolute value of start.
        start = list->length + start;
    }

    if(stop < 0) {
        stop = list->length + stop;
    }

    if(stop == 0) {
        stop = list->length;
    }

    for(size_t i = start; i < stop; i += step) {
        CD9Node *node = cd9list_getNode(list, i);
        result->appendCopy(result, node->data, node->size);
    }

    return result;
}

int cd9list_remove(void *self, size_t index)
{
    CD9List *list = (CD9List *)self;

    if(index < 0 || index > (list->length - 1)) {
        return 0; // Not a valid index;
    } 

    if(index == 0) {
        CD9Node *toDelete = list->nodes;
        list->nodes = toDelete->next;
        cd9list_deleteNode(toDelete);
        list->length--;
    }
    else {
        CD9Node *prev = cd9list_getNode(list, index - 1);
        CD9Node *toDelete = cd9list_getNode(list, index);

        prev->next = toDelete->next;
        cd9list_deleteNode(toDelete);

        list->length--;
    }

    return 1; // Removed successfully.
}

int cd9list_find(void *self, const void *toFind, CD9FindCallback cmp)
{
    CD9List *list = (CD9List *)self;

    CD9FOREACH_(list, node, index) {
        if(cmp(node->data, toFind, node->size)) {
            return index;
        }
    }
    return -1;
}

int cd9list_findByAddress(void *self, const void *data) 
{
    CD9List *list = (CD9List *)self;

    return list->find(list, data, callbacks_findByAddressCmp);
}

int cd9list_findByValue(void *self, const void *data)
{
    CD9List *list = (CD9List *)self;

    return list->find(list, data, callbacks_findByValueCmp);
}

/**
 * @brief Helper function used by `cd9list_mergeSort` in order to combine 2
 *        sublists.
 *
 * @param part1 Pointer to the first sublist.
 * @param part2 Pointer to the second sublist.
 * @param cmp The comparison function, see \ref CD9List::sort for more details. 
 *
 * @return CD9Node * A pointer to the merged version of the 2 parts.
 */
CD9Node *cd9list_merge(CD9Node *part1, 
                       CD9Node *part2, 
                       int (*cmp)(const void *, const void *))
{
    CD9Node *temp;

    if(cmp(part1->data, part2->data) <= 0) {
        temp  = part1;
        part1 = part1->next; 
    }
    else {
        temp  = part2;
        part2 = part2->next;
    }

    CD9Node *current = temp;

    while(part1 != NULL && part2 != NULL) {
        if(cmp(part1->data, part2->data) <= 0) {
            current->next = part1;
            part1         = part1->next; 
        }
        else {
            current->next = part2;
            part2         = part2->next;
        }
        current = current->next;
    }

    if(part1 != NULL) {
        current->next = part1;
    }

    if(part2 != NULL) {
        current->next = part2;
    }

    return temp;
}  

/**
 * @brief This is a helper function, its main purpose is to return a pointer
 *        to the node of the list refered by `start` and `stop`. We can't use
 *        `cd9list_getNode` since it requires a pointer to the list and we 
 *        don't have access to it inside `cd9list_mergeSort`.
 * 
 * @param start The starting node of the list.
 * @param stop Pointer to the end of the list.
 *
 * @return CD9Node * A pointer to the middle node of the list delimited by
 *         `start` and `stop`.
 */ 
CD9Node *cd9list_getMidNode(CD9Node *start, CD9Node *stop)
{
    CD9Node *front = start;
    CD9Node *back  = start->next;

    while(back != stop) {
        back = back->next;
        if(back != stop) {
            back  = back->next;
            front = front->next;
        }
    }

    return front;
}

/**
 * @brief This is the function called by `cd9list_sort` in order to sort a 
 *        list. It implements the merge sort algorithm.
 * 
 * @param start A pointer to the starting node of the list that should be
 *        sorted.
 * @param stop A pointer to the stoping node of the list.
 * @param cmp The comparison function. See \ref CD9List::sort for more details.
 *
 * @return CD9Node * It returns a pointer to the sorted version of the list.
 */ 
CD9Node *cd9list_mergeSort(CD9Node *start,
                           CD9Node *stop,
                           int (*cmp)(const void *, const void *))
{
    if(start == stop) {
        start->next = NULL;
        return start;
    }

    CD9Node *midNode     = cd9list_getMidNode(start, stop->next);
    CD9Node *midNodeNext = midNode->next;

    CD9Node *part1 = cd9list_mergeSort(start, midNode, cmp);
    CD9Node *part2 = cd9list_mergeSort(midNodeNext, stop, cmp);

    return cd9list_merge(part1, part2, cmp);
}    

void cd9list_sort(void *self, int (*cmp)(const void *, const void *))
{
    CD9List *list = (CD9List *)self;
    CD9Node *stop = cd9list_getNode(list, list->length - 1);

    list->nodes   = cd9list_mergeSort(list->nodes, stop, cmp); 
}

CD9List *cd9list_createList()
{
    CD9List *list = malloc(sizeof(CD9List));
    if(list == NULL) { // Malloc failed.
        return NULL; 
    }

    list->length = 0;
    list->nodes  = NULL;

    // Now bind the functions;
    list->append         = cd9list_append;
    list->prepend        = cd9list_prepend;
    list->get            = cd9list_get;
    list->insert         = cd9list_insert;
    list->remove         = cd9list_remove;    
    list->find           = cd9list_find;
    list->_insertCopy    = cd9list_insertCopy;
    list->pop            = cd9list_pop;
    list->popleft        = cd9list_popleft;
    list->appendCopy     = cd9list_appendCopy;
    list->prependCopy    = cd9list_prependCopy;
    list->findByAddress  = cd9list_findByAddress;
    list->findByValue    = cd9list_findByValue;
    list->copy           = cd9list_copy;
    list->slice          = cd9list_slice;
    list->reverse        = cd9list_reverse;
    list->sort           = cd9list_sort;
    list->filter         = cd9list_filter;
    list->filterByValue  = cd9list_filterByValue;
    list->filterBySet    = cd9list_filterBySet;

    return list;
}

void cd9list_deleteNode(CD9Node *node)
{
    if(node->size != SIZE_ZERO) {
        // Free the data allocated by cd9list_insertCopy.
        free(node->data);    
    }

    free(node);
}

void cd9list_deleteList(CD9List *list)
{
    CD9Node *phead = list->nodes;
    CD9Node *tmp;

    while(phead != NULL) {
        tmp = phead->next;
        cd9list_deleteNode(phead);
        phead = tmp;
    }

    free(list);
}
\$\endgroup\$
3
  • \$\begingroup\$ It looks like you're trying to implement a C++ object in straight C. Was this your intention? \$\endgroup\$
    – Snowbody
    Commented Apr 5, 2015 at 1:29
  • \$\begingroup\$ @Snowbody and what would be wrong with that in your opinion? \$\endgroup\$
    – Ryan
    Commented Apr 5, 2015 at 3:47
  • \$\begingroup\$ @Snowbody I wanted this library to have an interface that looks like an object oriented one. The reason for this is because I think it looks cleaner. \$\endgroup\$
    – cristid9
    Commented Apr 5, 2015 at 16:01

1 Answer 1

4
\$\begingroup\$

This looks good over all. You've done a lot of things well! I do have a few notes/thoughts though.

Style

I would stick with pure snake_case. mixed_camelCase reads oddly.


I'm not a fan of SIZE_ZERO. Seeing a constant for 0 makes me wonder if there's something strange about it. A literal 0 is clearer.

Technical

All of the internal functions should be declared static so that they cannot be seen out of the compilation unit. Also, if you have anything internal in your header (no idea if you do or not), it should be moved to the source.


I'm probably just missing something, but why do the methods that operate on a CD9List* take a void* instead of a CD9List*? Seems a bit odd since you know the user is always going to be passing a CD9List*.

Design

Some kind of iteration concept should be exposed to the user. The easiest way to do this is to expose the node, but a more abstract approach could be done by creating some kind of iterator that's just a thin wrapper for the nodes (i.e. having some opaque type with iterator_read, iterator_next, etc style functions).

Currently you have to use indexes when you want to operate on a specific slot of the list. This is (very) inefficient, especially since the linear scan can be avoided if already has a pointer to the node.


Speaking of efficiency... once you have an interator concept, I would leave the implementation of inefficient methods up to the consumer. People tend to assume that the methods containers provide are efficient. Making the user implement them themselves might make them (possibly correctly) second guess if they should really be using a linked list. For example, if a consumer needs cd9list_get they might should wonder if a linked list is really the right container.


Unless you're planning on some kind of polymorphism or customizability, your function pointers in CD9List don't accomplish much. It's also a (minor) performance hit since every function call requires a pointer dereference.


It's pretty bold to assume that malloc + memmove can be used for copying and free can be used for deleting. What about elements that may have nested resources? Or what about things that might need custom creation/deletion? For example, your list can't currently store lists--or at least not safely.

Rather than assuming that memmove and free can be used to copy/delete, you should allow the user to optionally provide copy/delete functions that default to a memmove/free approach.


Once copying/deleting is generalized, I would be tempted to have only one concept of value copying for the list instead of how you currently have a concept of either shallow copying or deep copying (or pointer vs value or whatever you want to call it). I can't imagine consumers would often want to deep copy some objects and not others on the same list. Letter the user control how the entire list behaves would simplify use of the list.

Really you could even go all out and provide two versions of each method that might involve a copy: the full version the allows the user to specify a copier, and the simple version that just passes the full version whatever the list's copier is.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.