Voir la source de 20141027:TP:C:IntrusiveList:EN

[[category:EPITA:TP:20142015]]

== 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 <tt>void*</tt> polymorphism. A good example are lists used inside the Linux kernel.

=== Assignements ===

You must commit in <tt>login-tp06</tt>, before next monday, the following files:

* <tt>Makefile</tt>
* <tt>AUTHORS</tt>
* <tt>list.h</tt>
* <tt>testing.c</tt>

== Embedding struct inside struct ==

So we have this list structure:

<source lang="C">
struct list {
  struct list          *next;
};
</source>

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:

<source lang="C">
struct data {
  char                *firstname, *lastname;
  unsigned             uid;
  struct list          list_;
};
</source>

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

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

[[Fichier:IntrusiveListExample.png]]

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

<source lang="C">
// We use offsetof macro from <stddef.h>

// Compute the parent pointer
# define CONTAINER_OF_(TYPENAME_, FIELDNAME_, PTR_)                     \
  ((TYPENAME_*)(((char*)PTR_ - offsetof(TYPENAME_, FIELDNAME_))))
</source>

Theses two macros will be useful later.

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

<source lang="C">
// 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_ */
</source>

== 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 <tt>static inline</tt> modifier.

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

<source lang="C">
/*
 * 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;
}
</source>

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

== Basic Operations ==

* '''Implement the following operations:'''

<source lang="C">
/*
 * 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 */
}
</source>

== 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:

<source lang="C">
// 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;
}
</source>

* '''Compile and test'''

=== Reversing the List ===

* '''Implement the following function'''

<source lang="C">
/*
 * 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);
</source>

Include this code in the previous program and modify <tt>main</tt> to use it:

<source lang="C">
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;
}
</source>

* '''Compile and test'''