4
\$\begingroup\$

I've written a small implementation for doubly linked lists. While actually intended to be only used by me in subsequent projects, I wrote it as generically as possible. Maybe this'll be advantageous.
I tested the implementation and resolved as many bugs as possible but maybe there are more lurking somewhere in the code.
Also, the implementation is supposed to be usable for different lists at the same time but operations cannot be performed on one list simultaneously. I'll have to add a spinlock to the list and alter the code a bit for that.

The list works as follows:
the first (head) node has the prev field set to NULL, the last (tail) node has the next field set to NULL. A size field counts the number of nodes in the list. If size == 1, prev and next of this lonely node contain NULL and head == tail == node. If size == 0, head and tail are indeterminate.

Code

Header (dll.h):

#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H

/* When reading through this code, you may encounter functions not being
 * strictly const-correct. This is because I wanted to make const-correctness
 * to depict the CONCEPTUAL const-ness, not const-ness due to some random
 * implementation-detail.
 */

/* From this implementation's perspective, this is not a pointer to the data
 * but really the data itsself.
 */
typedef void* data_t;

/* I second that the name "dll" for "doubly-linked list" is ambiguous
 * with the Windows DLL (Dynamic Link Library) but I don't think this'll
 * lead to any serious confusion.
 */

typedef struct dll_node {
    struct dll_node* prev;
    struct dll_node* next;

    data_t data;
} dll_node_t;

typedef int (*cleanup_op_t)(dll_node_t* node);

typedef struct dll {
    dll_node_t* head;
    dll_node_t* tail;

    cleanup_op_t cleanup_op;

    size_t size;
} dll_t;

/* Initializes a list with zero nodes.
 * `list' - The list to initialize
 * `cleanup_op' - The operation to apply to every datum when it is
 *                removed from the list. This includes the destruction of
 *                the list using `dll_destroy'.
 */
void dll_init(dll_t* list, cleanup_op_t cleanup_op);

/* Data definition with macros - Linux kernel style. C ain't got no
 * constructors - we use ugly macros to make up for that. AFAIK, GCC does
 * offer aping constructors using the attribute "constructor" but that's
 * compiler-specific and therefore not eligible for usage.
 * Use it if you find it useful. The big fat drawback is that the actually
 * hidden stuff going on in this macro needs to be exposed for further
 * operations. Or, when assigning dll_t*'s, you need to know the type too.
 * That completely defeats the purpose of this macro.
 * NOTE: LACK OF DO-WHILE LOOP IS ON PURPOSE TO MAKE THE VARIABLE VISIBLE
 * IN THE OUTER SCOPE!
 */
#define DEFINE_DLL(identifier, cleanup_op) \
    dll_t identifier; \
    dll_init(&identifier, (cleanup_op));

/* Destructs the list, that is, all its nodes and the data they contain.
 * Complexity: O(n)
 * `list' - The list to destruct
 */
void dll_destroy(dll_t* list);

/* The return value indicates whether the traversing function should continue
 * or if the required condition has been met. This enables searching for
 * items in the list and other, crazy stuff the user of this API can think of.
 */
typedef int (*dll_traverse_op_t)(dll_node_t* node);

/* Traverses through a list, starting at the head and going forward to the next
 * nodes, and performs an operation on every node.
 * Complexity: O(n)
 * `list' - The list to traverse through
 * `op' - The operation to perform
 */
void dll_traverse(dll_t* list, dll_traverse_op_t op);

/* Traverses through a list, starting at the tail and going backward to the
 * previous nodes, and performs an operation on every node.
 * Complexity: O(n)
 * `list' - The list to traverse through
 * `op' - The operation to perform
 */
void dll_traverse_rev(dll_t* list, const dll_traverse_op_t op);

/* TODO: is it reasonable to return the created node from the dll_add_* and
 * dll_insert_* functions? Think about that!
 */

/* TODO: THE BELOW COMMENT SERVES AS A TEMPLATE FOR ALL DOCUMENTING COMMENTS
 * IN THIS IMPLEMENTATION. FORM THE OTHER ONES WITH THIS ONE HERE IN MIND!
 */
/* Inserts a node right before another one.
 * Complexity: O(1)
 * `list' - The list to insert into
 * `node' - The node before which to insert the new node
 * `data' - The data stored by the new node
 * Notes:
 * If the list doesn't contain any nodes, a new node is created and added to
 * the list, INDEPENDENT OF THE VALUE OF `node'.
 */
dll_node_t* dll_insert_before(dll_t* list, dll_node_t* node, data_t data);

/* TODO: THE BELOW COMMENT SERVES AS A TEMPLATE FOR ALL DOCUMENTING COMMENTS
 * IN THIS IMPLEMENTATION. FORM THE OTHER ONES WITH THIS ONE HERE IN MIND!
 */
/* Inserts a node right after another one.
 * Complexity: O(1)
 * `list' - The list to insert into
 * `node' - The node after which to insert the new node
 * `data' - The data stored by the new node
 * Notes:
 * If the list doesn't contain any nodes, a new node is created and added to
 * the list, INDEPENDENT OF THE VALUE OF `node'.
 */
dll_node_t* dll_insert_after(dll_t* list, dll_node_t* node, data_t data);

/* The dll_add_* and dll_insert_* functions are very similar, so I wrote the
 * actual, generic implementation in the dll_insert_* functions and built
 * the dll_add_* ones on top of them.
 * Similarly done with the dll_rm and dll_rm_* functions.
 */

/* Add a node to the head of the list.
 * Complexity: O(1)
 * `list' - The list to prepend the node to
 * `data' - The data to be stored in the new node
 */
dll_node_t* dll_add_front(dll_t* list, data_t data);

/* Add a node to the tail of the list.
 * Complexity: O(1)
 * `list' - The list to append the node to
 * `data' - The data to be stored in the new node
 */
dll_node_t* dll_add_back(dll_t* list, data_t data);

/* Removes a node.
 * Complexity: O(1)
 * `list' - The list to remove the node from
 * `node' - The node to remove
 */
void dll_rm(dll_t* list, const dll_node_t* node);

/* Remove the node at the head of the list.
 * Complexity: O(1)
 * `list' - The list to remove the node from
 */
void dll_rm_front(dll_t* list);

/* Remove the node at the tail of the list.
 * Complexity: O(1)
 * `list' - The list to remove the node from
 */
void dll_rm_back(dll_t* list);

#endif

Source (dll.c):

#include <dll.h>
#include <stdlib.h>
#include <assert.h>

void dll_init(dll_t* list, cleanup_op_t cleanup_op) {
    assert(list);

    list->cleanup_op = cleanup_op;
    list->size = 0;
}

void dll_destroy(dll_t* list) {
    assert(list);

    if (list->size == 0)
        return;

    dll_node_t* it = list->head;

    while (it) {
        if (list->cleanup_op)   /* fare well, branch predictor */
            list->cleanup_op(it->data);

        dll_node_t* tmp = it;
        it = it->next;
        free(tmp);
    }
}

void dll_traverse(dll_t* list, dll_traverse_op_t op) {
    assert(list);

    if (list->size == 0)
        return;

    dll_node_t* it = list->head;

    while (it) {
        op(it);
        it = it->next;
    }
}

void dll_traverse_rev(dll_t* list, const dll_traverse_op_t op) {
    if (list->size == 0)
        return;

    dll_node_t* it = list->tail;

    while (it) {
        op(it);
        it = it->prev;
    }
}

dll_node_t* dll_insert_before(dll_t* list, dll_node_t* node, data_t data) {
    assert(list);

    if (list->size == 0)
        assert(node);

    dll_node_t* prev_node = list->size == 0 ? NULL : node->prev;

    dll_node_t* new_node = malloc(sizeof(dll_node_t));
    assert(new_node);
    new_node->data = data;
    new_node->next = list->size == 0 ? NULL : node;
    new_node->prev = prev_node;

    if (list->size == 0)
        list->head = list->tail = new_node;
    else {
        if (node->prev)
            prev_node->next = new_node;
        else {
            assert(node == list->head);
            list->head = new_node;
        }
        node->prev = new_node;
    }

    ++(list->size);

    return new_node;
}

dll_node_t* dll_insert_after(dll_t* list, dll_node_t* node, data_t data) {
    assert(list);

    if (list->size != 0)
        assert(node);

    dll_node_t* next_node = list->size == 0 ? NULL : node->next;

    dll_node_t* new_node = malloc(sizeof(dll_node_t));
    assert(new_node);
    new_node->data = data;
    new_node->next = next_node;
    new_node->prev = list->size == 0 ? NULL : node;

    if (list->size == 0)
        list->head = list->tail = new_node;
    else {
        if (node->next)
            next_node->prev = new_node;
        else {
            assert(node == list->tail);
            list->tail = new_node;
        }
        node->next = new_node;
    }

    ++(list->size);

    return new_node;
}

dll_node_t* dll_add_front(dll_t* list, data_t data) {
    return dll_insert_before(list, list->head, data);
}

dll_node_t* dll_add_back(dll_t* list, data_t data) {
    return dll_insert_after(list, list->tail, data);
}

void dll_rm(dll_t* list, const dll_node_t* node) {
    assert(list);
    assert(node);
    assert(list->size != 0);

    if (list->cleanup_op)
        list->cleanup_op(node->data);

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

    /* Casting away const-ness is bad but it's just a necessary
     * implementation detail here. I hope it's not undefined behavior...
     * in C++, it is, if the object the casted pointer is pointing to is
     * const, AFAIK. Only if it is non-const but pointed to by a const
     * pointer casting away const-ness is well-defined.
     * But I think the rules differ in C. (C != C++!)
     */
    free((dll_node_t*) node);

    --(list->size);
}

void dll_rm_front(dll_t* list) {
    dll_rm(list, list->head);
}

void dll_rm_back(dll_t* list) {
    dll_rm(list, list->tail);
}

Questions

  1. A node stores its data in a member of type data_t. Should I replace data_t with void* and use that void* as a generic pointer to data? What do you think?
  2. There's a comment on const-correctness in the header file, literally:

    /* When reading through this code, you may encounter functions not being
      * strictly const-correct. This is because I wanted to make const-correctness
      * to depict the CONCEPTUAL const-ness, not const-ness due to some random
      * implementation-detail. */
    

    Do you agree with me to make functions conceptually const or should I only use const when it's absolutely necessary (and let implementation details shine through)?

  3. Are the names dll_t and dll_node_t alright? Or could this be confused with Microsoft's Dynamic Link Libraries? Also, should I change the macro used as a header guard to DLL_H or is it fine as it stands?

  4. What do you think of the implementation and the approach? Does it seem usable? Is the code alright?

\$\endgroup\$
4
\$\begingroup\$

Data storage

If you change your data_t typedef to be anything other than void*, your linked list implementation has to be copied and modified to handle multiple types (so it's less generic); on the other hand, you get better type safety. The tradeoff is probably in how you're going to use it.

One thought: I would suggest looking at how the linux kernel does linked lists: they have a list_head struct, which is then included inside the data types that you want to put into a list. So it looks something like (e.g., if you had a linked list of strings):

struct list_head {
    struct list_head *next, *prev;
};

struct element {
    char *s;
    struct list_head list;
};

Then, you have a bunch of linked-list functions which operate on list_head pointers, and use an offsetof macro to get back from the list_head to the enclosing structure.

Not to say that this is better, but it's arguably a more type-safe way to get 'generic' linked lists in C. Both approaches are valid, though (and yours is more 'classic').

Const correctness

I would generally say that things should be const whenever possible, because it makes programs easier to reason about. I generally encounter the opposite problem to the one you're describing, though: something is conceptually const, but for incidental implementation reasons it needs to be mutable.

DLL naming

Well, 'dll' isn't the clearest name, because of the conceptual collision with Windows libraries. It probably isn't a big deal unless you're writing software on Windows and using dlls. I would be tempted to just call this module "list", or "ll", though.

The only real constraint on the include guard macro is that it not collide with any other names in your program. I suspect that DOUBLY_LINKED_LIST_H is probably fine. (Obviously, if you have some style guide or standard, that probably specifies a convention).

Implementation

This is pretty nice code overall. If I were feeling picky:

  • Names ending in _t are strictly reserved for the standard, iirc. Struct tags are in a different namespace, so it's totally reasonable to do typedef struct foo {} foo;.
  • I'd be inclined to prefer consistency of bracing at least within a particular control structure (so if () {} else {} rather than if () ; else {} even if one branch has only one statement).
  • I'd be inclined to break section up the files a little with comments---while I'm not a fan of those huge ASCII-art comment headers, I find files easier to read if they have little headers like

    /* --- type declarations --- */
    

    ...

    /* --- function declarations --- */
    

    ...

    /* --- function definitions --- */
    

    Just a little extra stuff to help find your way around the file, and separate things which are conceptually different. It may be that not everyone agrees with me on that, though.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice, thank you for enlightening about common practices in the Linux kernel \$\endgroup\$ – janos Feb 8 '16 at 17:44
  • \$\begingroup\$ It's been some time but I just stumbled across this and this made me think if _t prefixes are really reserved for the standard. Do you have some trustworthy source for that? \$\endgroup\$ – cadaniluk Mar 31 '16 at 21:23
  • 1
    \$\begingroup\$ @cad it seems that I didn't quite remember correctly: names with the suffix _t are marked as reserved by the POSIX standard, not the C standard. Pragmatically, that still puts them in the "this won't end well" category w.r.t. portability and forward compatibility, so I would still avoid them, but it is a slightly more relaxed restriction. \$\endgroup\$ – David Morris Apr 2 '16 at 10:30

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.