3
\$\begingroup\$

NOTE: Added a follow-up question with the reviewed code

I am trying to get back to basics with C, so I am doing some data structures in it.

The following is my implementation of a Single Linked List (The code is on github with tests).

LinkedList.h

/* 
 * File:   LinkedList.h
 * Author: antoniocs
 *
 * Created on 26 de Setembro de 2015, 19:54
 */

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct LinkedList LinkedList;
    typedef struct LinkedListNode LinkedListNode;

    struct LinkedList {
        LinkedListNode *head;
        LinkedListNode *tail;
    };

    struct LinkedListNode {
        void *data;
        LinkedListNode *next;
    };

    LinkedList *LLInit();

    LinkedListNode *LLAddHead(LinkedList *, void *);
    LinkedListNode *LLAddTail(LinkedList *, void *);
    LinkedListNode *LLAdd(LinkedList *, void *);

    void *LLRemoveHead(LinkedList *);
    void *LLRemoveTail(LinkedList *);
    void *LLRemoveNode(LinkedList *, LinkedListNode *);

    typedef int (*LLFindCompareFuncPtr)(void *, void *);    
    LinkedListNode *LLFindNodeByData(LinkedList *, void *, LLFindCompareFuncPtr);
    LinkedListNode *LLFindNodeByNext(LinkedList *, LinkedListNode *);


#ifdef  __cplusplus
}
#endif

#endif  /* LINKEDLIST_H */

LinkedList.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "LinkedList.h"
#include "../../../dbg.h"

enum LLAddStrategy {
    HEAD,
    TAIL
};

struct LLFindNodeBaseParams {
    LinkedList *ll;

    void *data;
    LLFindCompareFuncPtr compareFunc;

    LinkedListNode *node;
    LinkedListNode *next;
};

struct FindResult {
    LinkedListNode *prev;
    LinkedListNode *node;
};


static struct FindResult *FindNodeBase(struct LLFindNodeBaseParams *);

typedef bool(*findByFuncPtr)(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static bool FindByData(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
//To the outside this function is not really necessary
static struct FindResult *LLFindNode(LinkedList *, LinkedListNode *);
static bool FindByNode(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static bool FindByNextNode(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static struct FindResult *InitFindResult(void);
static bool FindResultSetResult(bool, struct FindResult *, LinkedListNode *);
//static struct LLFindNodeBaseParams *InitLLFindNodeBaseParams();



static LinkedListNode *NodeInit();
static LinkedListNode *LLAddBase(LinkedList *, void *, enum LLAddStrategy);

LinkedList *LLInit() {
    LinkedList *ll = malloc(sizeof (LinkedList));
    check(ll, "Unable to allocate memory for linked list");

    ll->head = NULL;
    ll->tail = NULL;

    return ll;

error:
    return NULL;
}

/**
 * Add an item to the linked list in the head or the tail
 * 
 * @param ll
 * @param data
 * @param type
 * @return int (will be 1 for failure and 0 for sucess)
 */
LinkedListNode *LLAddBase(LinkedList *ll, void *data, enum LLAddStrategy stype) {
    check(ll, "LLAddBase received null pointer");
    LinkedListNode *node = NodeInit(data, NULL);

    if (ll->head == NULL) {
        ll->tail = ll->head = node;
    } else {
        if (stype == HEAD) {
            node->next = ll->head;
            ll->head = node;
        } else {
            ll->tail->next = node;
            ll->tail = ll->tail->next;
        }
    }

    return node;
error:
    return NULL;
}

/**
 * Add a node to the start of the Linked List
 * 
 * @param ll
 * @param data
 * @return
 */
LinkedListNode *LLAddHead(LinkedList *ll, void *data) {
    return LLAddBase(ll, data, HEAD);
}

/**
 * Add a node to the end of the Linked List
 *
 * @param ll
 * @param data
 * @return
 */
LinkedListNode *LLAddTail(LinkedList *ll, void *data) {
    return LLAddBase(ll, data, TAIL);
}

/**
 * Shorter alias for LLAddTail
 * 
 * @param ll
 * @param data
 * @return
 */
LinkedListNode *LLAdd(LinkedList *ll, void *data) {
    return LLAddTail(ll, data);
}

/**
 *
 * @param data
 * @param next
 * @return
 */
LinkedListNode *NodeInit(void *data, LinkedListNode *next) {
    LinkedListNode *lln = malloc(sizeof (LinkedListNode));
    check(lln, "Unable to allocate memory for linked list node");

    lln->data = data;
    lln->next = next;

    return lln;
error:
    return NULL;
}

void *LLRemoveHead(LinkedList *ll) {
    return LLRemoveNode(ll, ll->head);
}

void *LLRemoveTail(LinkedList *ll) {
    return LLRemoveNode(ll, ll->tail);
}

void *LLRemoveNode(LinkedList *ll, LinkedListNode *node) {
    void *data = node->data;
    struct FindResult *res = LLFindNode(ll, node);

    check(res->node, "Node not found on List");

    if (node == ll->head) {
        if (ll->head->next == NULL) {
            ll->head = ll->tail = NULL;
        } else {
            ll->head = ll->head->next;
        }
    } else {
        if (node == ll->tail) {
            res->prev->next = NULL;
            ll->tail = res->prev;
        } else {
            res->prev->next = node->next;
        }
    }

    free(node);
    return data;

error:
    return NULL;
}

struct FindResult *LLFindNode(LinkedList *ll, LinkedListNode *node) {

    struct LLFindNodeBaseParams fnbParams = {
        .ll = ll,
        .node = node
    };
    struct FindResult *res = FindNodeBase(&fnbParams);
    return res;
}

LinkedListNode *LLFindNodeByData(LinkedList *ll, void *data, LLFindCompareFuncPtr func) {

    struct LLFindNodeBaseParams fnbParams = {
        .ll = ll,
        .data = data,
        .compareFunc = func
    };
    struct FindResult *res = FindNodeBase(&fnbParams);

    LinkedListNode *node = res->node;
    free(res);

    return node;
}

LinkedListNode *LLFindNodeByNext(LinkedList *ll, LinkedListNode *nodeNext) {

    struct LLFindNodeBaseParams fnbParams = {
        .ll = ll,
        .next = nodeNext
    };
    struct FindResult *res = FindNodeBase(&fnbParams);

    LinkedListNode *node = res->node;
    free(res);

    return node;
}

struct FindResult *FindNodeBase(struct LLFindNodeBaseParams *params) {
    findByFuncPtr fptr = NULL;

    if (params->data != NULL && params->compareFunc != NULL) {
        fptr = FindByData;
    } else if (params->node != NULL) {
        fptr = FindByNode;
    } else if (params->next != NULL) {
        fptr = FindByNextNode;
    } else {
        goto error;
    }

    LinkedListNode *node = params->ll->head;
    struct FindResult *res = InitFindResult();

    check(res, "Unable to allocate memory for FindResult structure");
    bool foundNode = false;

    while (node != NULL) {
        if ((foundNode = fptr(params, res, node))) {
            break;
        }
        node = node->next;
    }

    if (foundNode == false) {
        res->node = NULL;
        res->prev = NULL;
    }

    return res;

error:
    return NULL;
}

bool FindByData(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
    return FindResultSetResult(params->compareFunc(params->data, node->data) == 0, res, node);
}

bool FindByNode(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
    return FindResultSetResult(params->node == node, res, node);
}

bool FindByNextNode(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
    return FindResultSetResult(params->next == node->next, res, node);
}

bool FindResultSetResult(bool condition, struct FindResult *res, LinkedListNode *node) {
    if (condition) {
        res->node = node;
    } else {
        res->prev = node;
    }

    return condition;
}

struct FindResult *InitFindResult() {
    struct FindResult *res = malloc(sizeof (struct FindResult));
    check(res, "Unable to allocate memory for FindResult");

    res->node = NULL;
    res->prev = NULL;

    return res;

error:
    return NULL;
}

Please tell me if anything seems off.

I also thought about creating separate files for each of the functions and then having one header file that would just combine everything. What are your thoughts on that?

All the tests are passing (you can see the test file in the github link provided)

Thanks!

\$\endgroup\$
  • 1
    \$\begingroup\$ Please add the definition for the check thing, whatever it is; I have a feeling people might want to comment on that. \$\endgroup\$ – Mat Oct 14 '15 at 11:06
  • 1
    \$\begingroup\$ Re-run your code with valgrind. On my machine it reports memory leaks: definitely lost: 72 bytes in 9 blocks, indirectly lost: 136 bytes in 17 blocks. You probably miss a few free(). \$\endgroup\$ – Arkadiusz Drabczyk Oct 14 '15 at 12:19
  • \$\begingroup\$ @Mat Its one of Zed Shaws debug helpers. Its on github. But basically if the condition fails it will go to the error label \$\endgroup\$ – AntonioCS Oct 14 '15 at 18:11
2
\$\begingroup\$

First, the header:

  1. You are currently creating a typedef-name and a struct tag with the same name (so far, so good), and then defining the struct, in the same header-file but separately.
    Consider merging them:

    typedef struct LinkedList {
        /* lots of members here */
    } LinkedList;
    
  2. Why do you define a typedef for the comparison-function?

  3. Also, are you really sure the pointers given to the user-supplied comparison-function should not be const-qualified?
  4. Finally, why don't you allow for a context-pointer?

    Just make it the same as qsort and qsort_s in the standard library.

Next, the sourcefile:

  1. Why do you add forward-declarations instead of defining before use?
    DRY (Don't Repeat Yourself)

  2. Avoid sizeof(SomeType), use sizeof expression instead.
    Thus the types cannot get out-of-sync.

There are many more good points in the other reviews.

\$\endgroup\$
  • \$\begingroup\$ Thanks for this: 1 - I have fixed this. 2 - Why not? 3 - Good point will change it. 4 - Can you explain this a bit more please? Source file points: 1 - Sorry I don't understand what you mean by this. 2 - Will change this. \$\endgroup\$ – AntonioCS Oct 14 '15 at 18:10
  • \$\begingroup\$ header-2: Well, such an alias can only be justified if it makes things simpler, and more than it adds cost by adding things to keep in mind. I doubt that here, especially as the callback is quite simple. header-4: Conforming to well-known interfaces, unless there's a good reason to diverge, is always a good idea. And you want to allow a context-pointer so iff your comparator can be configured or whatever, that doesn't break reentrancy or concurrency. source-1: If you define your helper-functions before first use, you can dispense with forward-declarations. Pointless duplication is pointless. \$\endgroup\$ – Deduplicator Oct 14 '15 at 18:21
  • \$\begingroup\$ Regarding 2 I use that alias in other places, for example, in the struct LLFindNodeBaseParams. 4 - I am sorry but I am just not understanding what context-pointer means. I have seen the link and noticed that qsort_s had a 5th parameter named context but don't really understand what it means or how to use it. Do you have additional reading material or example where I could maybe better understand what you mean? Thanks \$\endgroup\$ – AntonioCS Oct 14 '15 at 18:44
  • \$\begingroup\$ The fact that you use it repeatedly in the implementation should not show in the public interface. Regarding context-pointer, let's say the data sorted is a name. Now when you sort it, which locales sorting-rules do you use? That's an example of "context" the comparison-function might need to work properly. \$\endgroup\$ – Deduplicator Oct 14 '15 at 19:01
  • 1
    \$\begingroup\$ @AntonioCS: Just be sure to make it a follow-up-question instead of an edit. Optionally, if you don't want to ask for a re-review, adding as an answer is also good. \$\endgroup\$ – Deduplicator Oct 14 '15 at 21:20
2
\$\begingroup\$

When removing a head node:

if (node == ll->head) {
    if (ll->head->next == NULL) {
        ll->head = ll->tail = NULL;
    } else {
        ll->head = ll->head->next;
    }

ll->head becomes ll->head->next regardless of its NULLness. Code could be streamlined:

if (node == ll->head) {
    ll->head = ll->head->next;
    if (ll->head == NULL) {
        ll->tail = NULL;
    }

Similarly, in a general case the res->prev->next is also well-defined:

} else {
    res->prev->next = node->next;
    if (node == ll->tail) {
        ll->tail = res->prev;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks so much for this. The logic does look a lot cleaner! \$\endgroup\$ – AntonioCS Oct 14 '15 at 18:21
1
\$\begingroup\$
/**
 * Add an item to the linked list in the head or the tail
 * 
 * @param ll
 * @param data
 * @param type
 * @return int (will be 1 for failure and 0 for sucess)
 */
LinkedListNode *LLAddBase(LinkedList *ll, void *data, enum LLAddStrategy stype) {
    check(ll, "LLAddBase received null pointer");
    LinkedListNode *node = NodeInit(data, NULL);

    if (ll->head == NULL) {
        ll->tail = ll->head = node;
    } else {
        if (stype == HEAD) {
            node->next = ll->head;
            ll->head = node;
        } else {
            ll->tail->next = node;
            ll->tail = ll->tail->next;
        }
    }

    return node;
error:
    return NULL;
}

Your documentation here is wrong. You say I get int back, and what I get back is... a LinkedListNode*.

if (node == ll->head) {
    if (ll->head->next == NULL) {
        ll->head = ll->tail = NULL;
    } else {
        ll->head = ll->head->next;
    }
} else {
    if (node == ll->tail) {
        res->prev->next = NULL;
        ll->tail = res->prev;
    } else {
        res->prev->next = node->next;
    }
}

Else statement containing only an if-else chain, can be merged.


FindNodeBase silently fails with goto error and returning NULL if you provide it with bad params. You might want to replace this with a check(fptr, "Bad params for FindNodeBase, can't determine find function").

\$\endgroup\$
  • \$\begingroup\$ Thanks so much for your great points. I have fixed all of them! \$\endgroup\$ – AntonioCS Oct 14 '15 at 18:22

Your Answer

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

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