20170522:Pratical:C:IntrusiveLists

Introduction

This session goal is to implement and use the concept of intrusive lists. The first part will be dedicated to implementation and second part will demonstrate how to use intrusive lists.

Intrusive Lists

Our goal is to implement a classical intrusive lists header providing the standard features of a list lib. Note that since we want to restrict our code to a header, all functions will be implemented as static inline functions.

List header

Our header list.h will look like this:

/* intrusive lists */
 
# ifndef _LIST_H_
# define _LIST_H_
 
# include <stddef.h>
 
 
/* Macro for content acces */
# define containerof(_TYPE_, _FIELD_, _PTR_) \
  ((_TYPE_*)((char*)(_PTR_) - offsetof(_TYPE_, _FIELD_)))
 
/* node structure for simply linked list node */
struct node {
  struct node *next;
};
 
/* check for emptiness, assuming the presence of a sentinel */
static inline
int list_is_empty(struct node *list)
{
  /* FIX ME */
}
 
/* add an element in front *after* the sentinel       */
/* elm is the node to attach and list is the sentinel */
static inline
void list_add(struct node *list, struct node *elm)
{
  /* FIX ME */
}
 
/* detaches and returns the first element after the sentinel */
static inline
struct node* list_remove(struct node *list)
{
  /* FIX ME */
}
 
/* function type for node comparison                          */
/* returns a negative number if n1 content is smaller than n2 */
/* returns a positive number if n1 content is bigger than n2  */
/* returns 0 if n1 content is equal to n2                     */
typedef int (*node_compare)(struct node *n1, struct node *n2);
 
/* find the first element in list that is not smaller than elm using cmp */
/* returns the node before the searched element                          */
static inline
struct node* list_find(struct node *list , node_compare cmp, struct node *elm)
{
  /* FIX ME */
}
 
# endif

• Complete the file list.h

Testing the code

Here is a test file for the code (with some hole):

# define _XOPEN_SOURCE 500
 
# include <stdio.h>
# include <stdlib.h>
 
# include "list.h"
 
struct data {
  struct node list;
  int a;
};
 
/* list printing */
typedef void (*printer)(struct node *);
 
void print_cell(struct node *node)
{
  printf(" %d", containerof(struct data, list, node)->a);
}
 
void print_list(struct node *list, printer print)
{
  printf("[");
  for (struct node *cur = list; cur->next != NULL; cur = cur->next)
    print(cur->next);
  printf(" ]\n");
}
 
/* Inserting a sorted element in a list */
 
/* comparison function */
int cmp(struct node *n1, struct node *n2)
{
  /* FIX ME */
}
 
/* insert(list, elm) inserts the data cell elm in list using cmp for order */
void insert(struct node *list, struct data *elm)
{
  /* FIX ME */
}
 
 
/* Creating a random list */
void create_random_list(size_t len, struct node *sentinel, struct data store[])
{
  sentinel->next = NULL;
  for (struct data *cur = store; cur != store + len; cur++) {
    int d = random() % 1000;
    printf("> inserting %d\n", d);
    cur->a = d;
    insert(sentinel, cur);
  }
}
 
int main()
{
  // avoid allocation, everything is local
  struct node sentinel;
  struct data store[10];
 
  create_random_list(10, &sentinel, store);
  print_list(&sentinel, print_cell);
 
  return 0;
}

You need to complete the two functions cmp and insert. For cmp the main difficulties is to extract the data from a list node, this is where the macro containerof is used. Your goal is to retrieve to pointer of type struct data* (one for each parameter) and then simply return the difference of their a field (which will returns a negative number if the first is smaller, 0 if they're equal and a positive number otherwise.)

For insert, you just have to cleverly used list_add and list_find.

• Fix the function cmp and insert
• Compile and run

Multi-sorted lists

We now want to use our intrusive lists. Our goal is to use the ability to attach an element to several lists, we will build a structure with three float fields and three node members and then build three lists from our data sorted on each field.

Data definition

The data is described by the following structure:

struct data {
  size_t id;
  struct node list_a, list_b, list_c;
  float a, b, c;
};

We add some code for creating datas and printing them. We use an array to store all data in one place and randomly initialize each field. The id field will simplify the visualization of our sorted data later.

/* generate random float in [0..range[ */
static inline
float rndfloat(float range)
{
  float x = random();
  x = x / RAND_MAX;
  return x * range;
}
 
/* init data vector */
static inline
void rnddata(struct data records[], size_t len)
{
  for (size_t i = 0; i < len; i++) {
    records[i].id = i;
    records[i].a = rndfloat(10.0);
    records[i].b = rndfloat(10.0);
    records[i].c = rndfloat(10.0);
  }
}
 
/* print data vector */
static
void print_data(struct data records[], size_t len)
{
  for (struct data *cur = records; cur != records + len; cur++) {
    printf("[%zu %g %g %g]\n", cur->id, cur->a, cur->b, cur->c);
  }
}

Generating function with macro

Our toy exercise requires to repeat the same code, with only a field name changing. We can't do that directly but we can use macro for that, here is an example that print the id of an element from a list node (using containerof):

# define _PRINTER(FIELD)                                 \
  static void print_##FIELD(struct node *cell)           \
  {                                                      \
    printf("%zu ",                                       \
      containerof(struct data, list_##FIELD, cell)->id); \
  }
 
/* Now defines the 3 functions */
_PRINTER(a)
_PRINTER(b)
_PRINTER(c)

 Note: this code generates three functions (print_a, print_b and print_c).

 Note: inside a macro, you can append the macro parameter to a name in the code using ##, otherwise you can use the parameter directly.

Building sorted lists

We now want to build a sorted list for each field (a, b and c). The idea is pretty simple, each data member has a field list_X (with X replaced by a, b or c) that will be used to attach the element to sorted list. So, you just have to build a sorted list for each field using sorted insertion.

For that, you first need to build a comparison function (just like in the first section) that take two pointers to node, retrieve the pointer to the data using containerof and then compare the corresponding field. For floating point comparison, we want to avoid possible issues, thus we use standard comparison from math.h:

static inline
int cmpfloat(float a, float b)
{
  if (isless(a,b)) return -1;
  if (isless(b,a)) return 1;
  return 0;
}

Note: this is a little bit pedantic, if a and b are normal float numbers (neither NaN nor infinity), isless is useless here, anyway, let's stay on the safe side.

We want three functions for comparing node on their respective field: we need to retrieve the pointer based on the list field and then compare the corresponding field, the protos for each function look like:

static int compare_a(struct node *elm1, struct node *elm2);
static int compare_b(struct node *elm1, struct node *elm2);
static int compare_c(struct node *elm1, struct node *elm2);

Try to build at least one of the three functions, from their you can either duplicate it or (better) write a macro just like in the printing examples.

In the same idea, we now want to build the sorted list, which requires a function for each field with the following protos:

static void sort_a(struct data records[], size_t len, struct node *list);
static void sort_b(struct data records[], size_t len, struct node *list);
static void sort_c(struct data records[], size_t len, struct node *list);

In each function, list serves as a sentinel for the list. Once again, you may (you must) use a macro to avoid repeating yourself.

You don't need a special insert function like in previous exercise, since you can directly iterate on elements in records and insert them one by one. Note, again, that just need to use list_find and list_add for that.

• Implement comparison and sorting function

Putting all together

Now you can build your code, here is skeleton, just add all functions described before in the FIX ME part:

# define _XOPEN_SOURCE 500
 
# include <stdlib.h>
# include <stdio.h>
# include <math.h>
 
# include "list.h"
 
struct data {
  size_t id;
  struct node list_a, list_b, list_c;
  float a, b, c;
};
 
static inline
float rndfloat(float range)
{
  float x = random();
  x = x / RAND_MAX;
  return x * range;
}
 
static inline
void rnddata(struct data records[], size_t len)
{
  for (size_t i = 0; i < len; i++) {
    records[i].id = i;
    records[i].a = rndfloat(10.0);
    records[i].b = rndfloat(10.0);
    records[i].c = rndfloat(10.0);
  }
}
 
static
void print_data(struct data records[], size_t len)
{
  for (struct data *cur = records; cur != records + len; cur++) {
    printf("[%zu %g %g %g]\n", cur->id, cur->a, cur->b, cur->c);
  }
}
 
# define _PRINTER(FIELD)                                  \
  static void print_##FIELD(struct node *cell)            \
  {                                                       \
    printf("%zu ",                                        \
      containerof(struct data, list_##FIELD, cell)->id);  \
  }
 
_PRINTER(a)
_PRINTER(b)
_PRINTER(c)
 
static
void print_list(struct node *list, void (*printer)(struct node*))
{
  for (; list->next != NULL; list = list->next) {
    printer(list->next);
  }
  printf("\n");
}
 
static inline
int cmpfloat(float a, float b)
{
  if (isless(a,b)) return -1;
  if (isless(b,a)) return 1;
  return 0;
}
 
/******************/
/***** FIX ME *****/
/******************/
 
int main()
{
  size_t len = 10;
  struct data records[10];
 
  rnddata(records, len);
  print_data(records, len);
 
  struct node la;
  struct node lb;
  struct node lc;
 
  sort_a(records, len, &la);
  sort_b(records, len, &lb);
  sort_c(records, len, &lc);
 
  print_list(&la, print_a);
  print_list(&lb, print_b);
  print_list(&lc, print_c);
 
  return 0;
}

• Complete the code, compile it and run it.