Voir la source de C:Workshop:2015:D1

[[category:EPITA:TP:20142015]]

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

<source lang="C">
struct cell {
  struct cell  *next;
  void         *content;
};
</source>

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

<source lang="C">
struct memory_recycler_pool {
  size_t        capacity, current;
  struct cell  *free_cell;
  struct cell  *data;
};
</source>

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

=== Create ===

* '''Write the function that create the memory pool'''

<source lang="C">
struct memory_recycler_pool* new_recycler(size_t cap);
</source>

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

=== Get a cell ===

* '''Write the function that get a cell from the pool'''

<source lang="C">
struct cell* recycler_alloc(struct memory_recycler_pool *mem);
</source>

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

=== Free a Cell ===

* '''Write the function that return a cell to the pool'''

<source lang="C">
void recycler_free(struct memory_recycler_pool *mem, struct cell* cell);
</source>

This function simply add the cell to the free list.

=== Delete The Pool ===

* '''Write the function that properly delete the memory pool'''

<source lang="C">
void pool_delete(struct memory_recycler_pool *mem);
</source>

The cell pool has been allocated using <tt>mmap(2)</tt>, thus you'll need <tt>munmap(2)</tt> 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 <tt>queue.h</tt>'''

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

Now we use the following binary tree structure:

<source lang="C">
struct tree {
  struct tree          *left, *right;
  int                   key;
};
</source>

* '''Implement a BFS printing functions'''

<source lang="C">
void bfs_print(struct tree *t);
</source>

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:

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

* '''Implement all the function from the header.'''

'''Hints:'''
* You'll need a generic <tt>find</tt> 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 <tt>choose_level()</tt> function, that will provide an acceptable distribution for the level of a new cell.

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