C:Workshop:2015:D1

Introduction

We have 2 subjects in this session: recycling memory allocator and skip-list.

The MCQ web site is: http://rendu.infoprepa.epita.fr/intra

Recycler

We want to implement a recycler for a fixed kind of data (list cells described later.) Initial capacity will be provided at initialization and you should consider a growing extension.

The memory cells managed by the recycler have the following structures:

struct cell {
  struct cell  *next;
  void         *content;
};

Here is a base version of the recycler structure, you'll probably need to extend it if you want to manage pool extension.

struct memory_recycler_pool {
  size_t        capacity, current;
  struct cell  *free_cell;
  struct cell  *data;
};

You'll build a header file recycler.h and the C code file recycler.c and put everything at the right place in these files.

Create

• Write the function that create the memory pool

struct memory_recycler_pool* new_recycler(size_t cap);

This function allocate and initialize the main data structure and allocate the cell pool using mmap(2).

Get a cell

• Write the function that get a cell from the pool

struct cell* recycler_alloc(struct memory_recycler_pool *mem);

This function first tries to get a cell from the free list, if the free list is empty, it will increase the current index and return the corresponding cell (the one with index current - 1 after increment.) If the free list is empty and the capacity has been reached, the function returns NULL.

Free a Cell

• Write the function that return a cell to the pool

void recycler_free(struct memory_recycler_pool *mem, struct cell* cell);

This function simply add the cell to the free list.

Delete The Pool

• Write the function that properly delete the memory pool

void pool_delete(struct memory_recycler_pool *mem);

The cell pool has been allocated using mmap(2), thus you'll need munmap(2) to free it.

Auto-growing Pool

Extend the memory pool so that when no cell are available, it will allocate a new cell pool.

• Modify all the impacted function to support auto-growing features

Rember that when deleting the pool, you must be able to free all the allocate cell pools.

Testing

In order to test our recycler, we'll implement a BFS on a binary tree. For that we need FIFO queue.

• Implement all the missing operations of queue.h

/* queue.h: queue data structure */
 
# ifndef QUEUE_H_
# define QUEUE_H_
 
# include <stdlib.h>
 
# include "recycler.h"
 
struct queue {
  struct cell                  *head, *tail;
  struct memory_recycler_pool  *mem;
};
 
static inline
struct queue* new_queue(size_t cap) {
  struct queue         *q;
  q = malloc(sizeof (struct queue));
  q->mem = new_recycler(cap);
  // Set up a sentinel
  q->head = recycler_alloc(q->mem);
  q->tail = q->head;
  q->head->next = NULL;
  return q;
}
 
/*
 * push p in the queue
 */
static inline
void queue_push(struct queue *q, void *p) {
  // FIX ME
}
 
/*
 * pop an element from the queue, remove it and return it
 */
static inline
void* queue_take(struct queue *q) {
  // FIX ME
}
 
/*
 * properly delete the queue
 */
void queue_delete(struct queue *q) {
  // FIX ME
}
 
# endif /* QUEUE_H_ */

Now we use the following binary tree structure:

struct tree {
  struct tree          *left, *right;
  int                   key;
};

• Implement a BFS printing functions

void bfs_print(struct tree *t);

You'll print all the keys of the tree in BFS order with newline for each level.

Skip List

You'll now implement the skip list described in lecture this morning. Here is the header:

// skip_list.h
 
# ifndef SKIP_LIST_H_
# define SKIP_LIST_H_
 
# define MAX_LEVEL 7
 
struct cell {
  double        key;
  void         *value;
  size_t        level;
  struct cell  *next[MAX_LEVEL + 1];
  struct cell  *prev[MAX_LEVEL + 1];
};
 
struct skip_list {
  size_t        size;
  struct cell  *head, *tail;
};
 
// Returns a new skip-list
struct skip_list* skip_list_empty(void);
 
// Returns true if list is empty
int skip_list_is_empty(struct skip_list *list);
 
// Returns the cell containing the key, NULL if not found
struct cell* skip_list_find(struct skip_list *list, double key);
 
// Insert (key,value) in the list, returns false if the pair is already there
int skip_list_insert(struct skip_list *list, double key, void *value);
 
# endif

• Implement all the function from the header.

Hints:

• You'll need a generic find function that look for a cell (or possible insertion point) and build the list of predecessors for each level (like in the lecture.)

Here is a possible implementation for the choose_level() function, that will provide an acceptable distribution for the level of a new cell.

static
size_t choose_level() {
  size_t                l = 0;
  unsigned              r;
  r = random();
  for (; l < MAX_LEVEL && r % 2 == 0; r >>= 1) {
    l += 1;
  }
  return l;
}