3
\$\begingroup\$

For my Operating Systems class, I needed a linked list data structure and didn't have one already written. During the course of thinking about how to implement a linked list again (it had been a while..), I decided that a lot of the most common functions used on linked lists can be implemented based on applying or composing a few core functions.

First, I wrote a function that iterates over the list starting from list->head while applying a function to each element. After each iteration, if the function returned false, then stop iterating and return a pointer to the node which terminated the loop. Otherwise, iterate until list->tail had the function applied to it.

Basically all of the rest of my functions fall from this one function. I was able to quickly implement map by calling the iteration function and always returning true (and therefore the iteration will never end prematurely). I was also able to implement a general iterative "test" function, which requires a function parameter that accepts two node arguments and produces a boolean. The point of the iterative test function is to implement things like sorting or testing for equality in a composable way.

I think my attempt isn't half bad, given that I was writing in C without any anonymous functions or closures (of which my knowledge is limited). That being said, I'm glad to hear what criticisms the community has on the implementation on a whole or nit-picking.

llist.h

#ifndef LLIST_H
#define LLIST_H

/* Fields */
typedef struct _node {
  struct _node *next, *prev;
  void *data;
} node;

typedef struct {
  node *head, *tail;
  size_t size;
} llist;

typedef enum {FALSE, TRUE} bool;

typedef void (*nodefunc)(node *);
typedef bool (*nodeiter)(node *);
typedef bool (*nodetest)(void *, void *);

/* Methods */
void llist_init(llist *l);
void llist_node_init(node *n);

void map(llist *l, nodefunc f);
void *llist_iter(llist *l, nodeiter f);
void *llist_test(llist *l, void *q, nodetest t);

void llist_append(llist *l, node *n);
void llist_remove(llist *l, node *n);
void llist_destroy(llist *l, nodefunc node_free);

#endif

llist.c

#include <stdlib.h>
#include "llist.h"

void llist_init(llist *l) {
  l->head = NULL;
  l->tail = NULL;
  l->size = 0;
}

void llist_node_init(node *n) {
  n->data = NULL;
  n->next = NULL;
  n->prev = NULL;
}

void *llist_iter(llist *l, nodeiter f) {
  node *n = l->head, *next = NULL;
  void *result = 0;

  while (n != NULL && result == 0) {
    next = n->next;
    if (!f(n))
      result = (void*)n;
    n = next;
  }

  return result;
}

void *llist_test(llist *l, void *q, nodetest t) {
  bool iter_test(node *n) {
    return !( t((void*)n->data, q) );
  }
  return llist_iter(l, iter_test);
}

// not a true map since f can have side effects
void map(llist *l, nodefunc f) {
  bool iter_true(node *n) {
    f(n);
    return TRUE;
  }
  llist_iter(l, iter_true);
}

void llist_append(llist *l, node *n) {
  if (l->size == 0) {
    l->head = n;
    l->tail = n;
  } else {
    n->prev = l->tail;
    l->tail->next = n;
    l->tail = n;
  }

  l->size++;
}

void llist_remove(llist *l, node *n) {
  if (n) {
    if (n->prev)
      n->prev->next = n->next;
    else
      l->head = n->next;

    if (n->next)
      n->next->prev = n->prev;
    else
      l->tail = n->prev;

    l->size--;
  }
}

void llist_destroy(llist *l, nodefunc node_free) {
  void iter_remove(node *n) {
    llist_remove(l, n);
    node_free(n);
  }
  map(l, iter_remove);
}

From this, I'm able to implement in a program, for example, a print function based on the type of data that is stored in the linked list:

llist_test.c

#include <stdio.h>
#include <stdlib.h>
#include "llist.h"

void llist_print(llist *l) {
  void iter_print(node *n) {
    printf("value: %d\n", *(int*)n->data);
  }
  map(l, iter_print);
}

void node_free(node *n) { free(n); }

node *alloc_node(int *data) {
  node *n = malloc(sizeof(node));
  llist_node_init(n);
  n->data = data;
  return n;
}

int main() {
  llist *l = malloc(sizeof(llist));
  llist_init(l);

  int x = 4, y = 8;
  llist_append(l, alloc_node(&x));

  // ...

  llist_destroy(l, node_free);
  free(l);

  return 0;
}
\$\endgroup\$
1
\$\begingroup\$

C Standard doesn't allow nested functions. A strictly conforming compiler must fail to compile llist_test and friends. If you are OK with deviating from Standard, take a look at blocks, which are considered much more secure and have a chance (unlike nested functions) to eventually get into Standard.

\$\endgroup\$
  • \$\begingroup\$ Oof. Thanks for the information. This is actually really important for me because my instructor might be compiling with clang, not gcc. That didn't even occur to me until now. \$\endgroup\$ – itsjareds Feb 11 '15 at 15:14
1
\$\begingroup\$
  • Linked lists come in all sorts of flavors--singly linked, doubly linked, circularly linked, .... Instead of using 'll' as the prefix (presumably for linked list), I would suggest using 'dll' for doubly linked list.
  • Watch your namespace pollution. 'node' and '_node' are fairly generic names and it is not unreasonable to expect that a module that includes this header file could define structures of that type. Minimize the expected namespace collision by naming this structure type as '_dllnode' or 'dllnode'.
  • If you want a 'bool' type, I would suggest including 'stdbool.h' instead of defining your own. stdbool.h defines 'true' and 'false'. If memory serves, this is something that is for C99 and later.
  • If you are going to typedef the function pointers, it may be beneficial to change the names to make it easier to identify that these are function pointer typedefs.
  • The name 'map()' appears out of place. All the other routines that operate on a list have a 'llist_' prefix. Consistency is important.
  • As a user of this, I would have expected to see a routine named 'llist_insert' for inserting a node into an arbitrary point in the linked list.
  • This may be a matter of preference, but for a general linked list implementation, I don't think the linked list node should have any references to the data (pointer or otherwise). If you want a node with data ...
struct my_node {
    dll_node  node;
    <data>
};
  • Following the previous, llist_destroy() should be implemented at a higher level. There are going to be lots of times when the user of this module may want the benefits of a linked list, but do not want to dynamically allocate the elements.
  • llist_node_init() should initialize the structure fields in the same order as they were declared. This makes it easier to ensure that items were not missed.
  • As a personal preference, I like to see one variable defined per line. (This is highly subjective).
  • In llist_iter(), 'result' is a pointer and should be initialized to NULL, not 0. Similarly, it should be compared against NULL in the loop.
  • Better yet, rewrite llist_iter() to eliminate the need for 'result' and some unnecessary assignments of 'n' when leaving the loop.
while (n != NULL) {
    if (!f(n)) {
        return (void *)n;
    }
    n = n->next;
}
return NULL;
  • Someone else has already mentioned nested functions, so I won't go into more on that.
  • What is meant by a 'true map'? What is meant by 'map'?
  • In llist_remove(), I would suggest that you avoid one level of indentation by returning early if 'n' is NULL.

Hope this helps.

\$\endgroup\$

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.