20151116:TP:C:IntrusiveLists

Introduction

The purpose of this session is to implement generic lists using the so-called intrusive-list technics.

The basic idea is: rather than including data inside list cells, we include list cells inside data.

This kind of lists is often used where we need to provide generic implementation of lists and don't want ugly void* polymorphism. A good example are lists used inside the Linux kernel.

This session is pretty easy and straightforward, the purpose is to understand, the code is easy.

Assignments

You must commit in your repository, the following files:

• 20151116_IntrusiveLists/
  • Makefile
  • AUTHORS
  • list.h
  • testing.c

Embedding struct inside struct

So we have this list structure:

struct list {
  struct list          *next;
};

Now, to use it (supposed that we already have coded all operations), we just need to embedded this structure in our data. Consider the following example:

struct data {
  char                *firstname, *lastname;
  unsigned             uid;
  struct list          list_;
};

One of the things we need is to be able to retrieve the beginning of the struct data, when we only have a pointer to the sub-component list_.

In order to do that, first consider the memory layout of your structures:

So, if you have a pointer to a struct list which is in fact embedded inside a struct data and want to compute the corresponding pointer to the parent structure, you need to subtract the offset of the list_ field from your pointer, this can done using the following macros:

// We use offsetof macro from <stddef.h>
 
// Compute the parent pointer
# define CONTAINER_OF_(TYPENAME_, FIELDNAME_, PTR_)                     \
  ((TYPENAME_*)(((char*)PTR_ - offsetof(TYPENAME_, FIELDNAME_))))

Theses two macros will be useful later.

Just group the list structure and the macro in a file call list.h where we will put most of our operations.

// Intrusive lists
 
# ifndef LIST_H_
# define LIST_H_
 
# include <stddef.h>
 
struct list {
  struct list          *next;
};
 
// Compute the parent pointer
# define CONTAINER_OF_(TYPENAME_, FIELDNAME_, PTR_)                     \
  ((TYPENAME_*)(((char*)PTR_ - offsetof(TYPENAME_, FIELDNAME_))))
 
# endif /* LIST_H_ */

Using inlined operations

All the list functions are simple and short and thus can be inlined. In order to provide inlined functions, rather than having code in C files and header presenting only function's prototypes, everything will go inside the header in the form of an inlined functions marked with the static inline modifier.

I provide you with two basic operations as example of inlined functions, just add the following definitions in list.h (before # endif line):

/*
 * list_init(sentinel)
 * Initialize list sentinel
 */
static inline
void list_init(struct list *sentinel) {
  sentinel->next = NULL;
}
 
/*
 * list_is_empty(l)
 * test for empty list (doesn't work for uninitialized list)
 */
static inline
int list_is_empty(struct list *l) {
  return l->next == NULL;
}

For the rest of the session all operations will coded as inlined functions, in the list.h file, by default.

Basic Operations

• Implement the following operations:

/*
 * list_len(l)
 * compute the length of l (without the sentinel)
 */
static inline
size_t list_len(struct list *l) {
  /* FIX ME */
}
 
/*
 * list_push_front(l, cell)
 * add cell in front of the l
 * (keep sentinel unchanged)
 */
static inline
void list_push_front(struct list *l, struct list *cell) {
  /* FIX ME */
}
 
/*
 * list_pop_front(l)
 * extract and return the first element of the list
 * returns NULL if the list is empty
 * (keep sentinel unchanged)
 */
static inline
struct list* list_pop_front(struct list *l) {
  /* FIX ME */
}
 
/*** ACESSORS ***/
 
/*
 * Accessors always return a pointer to the cell *before* the wanted element,
 * so that we can use them as input for push_front/pop_front operations.
 * Unsuccessful accesses (empty list, or access after the last element) always
 * return NULL.
 * You can assume that whether the accessor returns NULL or it returns a
 * pointer p such that p->next != NULL and p->next is the expected cell.
 */
 
/*
 * list_nth(l, n)
 * returns the n-th element, where 0 is the head (not the sentinel)
 */
static inline
struct list* list_nth(struct list *l, size_t n) {
  /* FIX ME */
}
 
/*
 * list_last(l)
 * same as list_nth(l, list_len(l) - 1) but faster
 */
static inline
struct list* list_last(struct list *l) {
  /* FIX ME */
}

Testing

Provided Tests

Here is a simple program using our list that, once all your functions are implemented you can test it with this code:

// testing.c
// Testing intrusive lists
 
# include <stdlib.h>
# include <stdio.h>
 
# include "list.h"
 
// Basic usage: list of integers
 
struct data {
  int           value;
  struct list   list_;
};
 
struct list* build_int_list(int len, struct data storage[]) {
  struct list          *sentinel;
  sentinel = malloc(sizeof (struct list));
  list_init(sentinel);
  for (int i = 0; i < len; ++i) {
    storage[i].value = i;
    list_push_front(sentinel, &(storage[i].list_));
  }
  return sentinel;
}
 
void print_list(struct list *l) {
  int                   line;
  line = printf("[");
  for (struct list *cur = l->next; cur != NULL; cur = cur->next) {
    if (line > 72) {
      printf("\n");
      line = printf(" ");
    }
    line += printf(" %3d;", CONTAINER_OF_(struct data, list_, cur)->value);
  }
  if (line > 72) printf("\n");
  printf(" ]\n");
}
 
# define LEN 100
 
int main() {
  struct list          *l;
  struct data          *storage;
  storage = calloc(LEN, sizeof (struct data));
  l = build_int_list(LEN, storage);
  print_list(l);
  free(l);
  free(storage);
  return 0;
}

• Compile and test

Reversing the List

• Implement the following function

/*
 * reverse(l)
 * pop all element one by one and push them in a new list reusing the original
 * cells.
 * Your function must:
 *   - allocate a new sentinel
 *   - free the original sentinel when done
 */
struct list* reverse(struct list *l);

Include this code in the previous program and modify main to use it:

int main() {
  struct list          *l;
  struct data          *storage;
  storage = calloc(LEN, sizeof (struct data));
  l = build_int_list(LEN, storage);
  print_list(l);
  l = reverse(l);
  print_list(l);
  free(l);
  free(storage);
  return 0;
}

• Compile and test