facil.io

View On GitHub

A Simple Linked List

Linked lists come in two main flavors:

  1. Generic (or independent) Linked Lists:

    Where the list’s node structure has a pointer that points to the object being added to the list. This requires objects to be allocated separately from list node, but allows a single object to belong to many lists (one-to-many).

  2. Embedded Linked Lists:

    Where the list’s node structure needs to be embedded within the object, thereby minimizing memory allocation and improving memory locality, while creating a one-to-one restriction (one object can belong to one list).

The single file library fio_llist.h offers both flavors in a simple to use package.

The API is practically the same for both, the only difference is in the prefix (fio_ls_X vs. fio_ls_embd_X).

Data Structure and Initialization.

The container for a list is the same as a node, however, it must be initialized so that it links to itself (see FIO_LS_INIT). i.e.:

fio_ls_s my_list = FIO_LS_INIT(my_list);

The linked list container is a simple data structure shown here… however, it is best to access the data using the API and avoid accessing the data directly. This will both protect the program from future changes to the data structures and minimize possible errors.

/** an embeded linked list. */
typedef struct fio_ls_embd_s {
  struct fio_ls_embd_s *prev;
  struct fio_ls_embd_s *next;
} fio_ls_embd_s;

/** an independent linked list. */
typedef struct fio_ls_s {
  struct fio_ls_s *prev;
  struct fio_ls_s *next;
  const void *obj;
} fio_ls_s;

#define FIO_LS_INIT(name)  { .next = &(name), .prev = &(name) }

The container can be dynamically allocated, placed of the stack or embedded in a dynamic object.

Generic Linked List API

Note that the API is comprised of inline static functions that act like macros, so there is no performance to be gained by accessing the data structure directly (only integrity to be lost).

fio_ls_push

void fio_ls_push(fio_ls_s *pos, const void *obj)

Adds an object to the list’s head.

fio_ls_unshift

void fio_ls_unshift(fio_ls_s *pos, const void *obj)

Adds an object to the list’s tail.

fio_ls_pop

void *fio_ls_pop(fio_ls_s *list)

Removes an object from the list’s head.

fio_ls_shift

void *fio_ls_shift(fio_ls_s *list)

Removes an object from the list’s tail.

fio_ls_remove

void *fio_ls_remove(fio_ls_s *node)

Removes a node from the list, returning the contained object.

fio_ls_is_empty

int fio_ls_is_empty(fio_ls_s *list)

Tests if the list is empty.

fio_ls_any

int fio_ls_any(fio_ls_s *list)

Tests if the list is NOT empty (contains any nodes).

FIO_LS_FOR

FIO_LS_FOR(list, pos)

Iterates through the list using a for loop.

Access the data with pos->obj (pos can be named however you please).

Embedded List API

fio_ls_embd_push

void fio_ls_embd_push(fio_ls_embd_s *dest, fio_ls_embd_s *node)

Adds a node to the list’s head.

fio_ls_embd_unshift

fio_ls_embd_unshift(fio_ls_embd_s *dest, fio_ls_embd_s *node)

Adds a node to the list’s tail.

fio_ls_embd_pop

fio_ls_embd_s *fio_ls_embd_pop(fio_ls_embd_s *list)

Removes a node from the list’s head.

fio_ls_embd_shift

fio_ls_embd_s *fio_ls_embd_shift(fio_ls_embd_s *list)

Removes a node from the list’s tail.

fio_ls_embd_remove

fio_ls_embd_s *fio_ls_embd_remove(fio_ls_embd_s *node)

Removes a node from it’s container list.

fio_ls_embd_is_empty

fio_ls_embd_is_empty(fio_ls_embd_s *list)

Tests if the list is empty.

fio_ls_embd_any

int fio_ls_embd_any(fio_ls_embd_s *list)

Tests if the list is NOT empty (contains any nodes).

FIO_LS_EMBD_FOR

FIO_LS_EMBD_FOR(list, node)

Iterates through the list using a for loop.

Access the data with pos->obj (pos can be named however you pleas..

FIO_LS_EMBD_OBJ

FIO_LS_EMBD_OBJ(type, member, plist) \
        ((type *)((uintptr_t)(plist) - (uintptr_t)(&(((type *)0)->member))))

Takes a list pointer plist and returns a pointer to it’s container.

This uses pointer offset calculations and can be used to calculate any struct’s pointer (not just list containers) as an offset from a pointer of one of it’s members.

This is a very useful macro to have around.