Voir la source de 20151102:TP:C:Lists

[[category:EPITA:TP:20152016]]

== Assignments ==

For the following practical session, your directory, <tt>20151102_lists</tt>  will contains the following files:

* <tt>20151102_lists</tt>
** <tt>AUTHORS</tt>
** <tt>lists</tt>
*** <tt>Makefile</tt>
*** <tt>list.h</tt>
*** <tt>list.c</tt>
** <tt>vectors</tt>
*** <tt>Makefile</tt>
*** <tt>vector.h</tt>
*** <tt>vector.c</tt>

== Linked Lists ==

We'll now work with linked lists.

We choose a rather simple list implementation: simply linked with sentinel.

The '''sentinel''' is a fake list node at the beginning of the list that is always there. It simplifies operations that modify the list since the entry pointer never change, it's also useful for iterators (see later.)

We also choose to separate node allocation from node insertion: functions that add element provides the already allocated node with data field set. This offers some liberty for further possible extensions (generic intrusive list for example) et simplify operations that moves nodes in the list.

=== Headers and Types ===

Our linked list are defined through the following type:

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

The field <tt>next</tt> is the tail of the list (pointer to the next cell) and the field <tt>value</tt> contains the stored value in the current cell.

Your main goal is to implement all functions described in the following header (<tt>list.h</tt>):

<source lang="C">
/* list.h : linked list data structures */

# ifndef LIST_H_
# define LIST_H_

# include <stdlib.h>

struct list {
  struct list          *next;
  int                   value;
};

static inline
int list_is_empty(struct list *l) { return l->next==NULL; }

/* Basic Operations */

/*
 * list_empty() create a new list (new sentinel)
 */
struct list* list_empty(void);

/*
 * list_len(l) return the number of element in the list
 */
size_t list_len(struct list *l);

/*
 * list_push_front(l, elm) push elm in front of l
 */
void list_push_front(struct list *l, struct list *elm);

/*
 * list_pop_front(l) extract and return first element
 * return NULL if the list is empty.
 */
struct list* list_pop_front(struct list *l);

/*
 * list_find(l,value) search for value in l
 * returns the pointer to the cell containing value
 * returns NULL if not found
 */
struct list* list_find(struct list *l, int value);

/* Sorting */

/*
 * list_insert(l, elm) inserts elm at the right place into a sorted list
 * (increasing order)
 */
void list_insert(struct list *l, struct list *elm);

/*
 * list_sort(l) sort l in increasing order.
 */
void list_sort(struct list *l);

/* Iterator */

typedef struct list    *iterator;

/*
 * list_begin(l) returns an iterator on the head of l
 */
iterator list_begin(struct list *l);

/*
 * list_is_end(it) true if it is the end of the list
 */
int list_is_end(iterator it);

/*
 * list_next(&it) move iterator it to the next position if possible
 */
void list_next(iterator *it);

/*
 * list_get(it) returns the current value
 */
int list_get(iterator it);

# endif
</source>

You must create and fill a file called <tt>list.c</tt> providing code for each functions. The following sections describe each part and operations.

=== Basic Operations ===

For basic operation, you must provides the following functions:

<source lang="C">
/* Basic Operations */

struct list* list_empty(void);
size_t list_len(struct list *l);
void list_push_front(struct list *l, struct list *elm);
struct list* list_find(struct list *l, int value);
struct list* list_pop_front(struct list *l);
</source>

* <tt>list_empty()</tt> allocate memory for the sentinel and set <tt>next</tt> to <tt>NULL</tt>
* <tt>list_len(l)</tt> compute the number of elements in the list (don't count the sentinel !
* <tt>list_push_front(l, elm)</tt> take an already allocated node and add it at the beginning of the list.
* <tt>list_pop_front(l)</tt> detach and returns the first node (not the sentinel !)
* <tt>list_find(l, value)</tt> look for a node containing <tt>value</tt> and returns a pointer to it. It returns <tt>NULL</tt> if the function doesn't find the value, it returns <tt>NULL</tt>.

=== Sorting ===

We now want to sort a list using the most basic sorting algorithm: insertion sort.

First, implement the classical sorted insert:

<source lang="C">
/*
 * list_insert(l, elm) inserts elm at the right place into a sorted list
 * (increasing order)
 */
void list_insert(struct list *l, struct list *elm);
</source>

Then implement the sort function:

<source lang="C">
/*
 * list_sort(l) sort l in increasing order.
 */
void list_sort(struct list *l);
</source>

The sort is in place, meaning that you'll reuse node from the original list.

The algorithm is quiet simple:
# detach the sentinel (<tt>l</tt>) from the list (keeping the list head in a variable <tt>head</tt>)
# The sentinel becomes a ''new list'' (set <tt>next</tt> to <tt>NULL</tt>)
# Iterate over <tt>head</tt>:
#* detach the current node <tt>cur</tt> of <tt>head</tt>
#* insert <tt>cur</tt> in <tt>l</tt>

=== Iterators ===

Iterators provide an abstract interface for iteration over list. A correct list API should provide (almost) all operations by the mean of iterators, in this exercise we keep the interface limited to the minimum: initial iterator, test for end of list, content access and moving to the next element.

The required function are:

<source lang="C">
/* Iterator */

typedef struct list    *iterator;

/*
 * list_begin(l) returns an iterator on the head of l
 */
iterator list_begin(struct list *l);

/*
 * list_is_end(it) true if it is the end of the list
 */
int list_is_end(iterator it);

/*
 * list_next(&it) move iterator it to the next position if possible
 */
void list_next(iterator *it);

/*
 * list_get(it) returns the current value
 */
int list_get(iterator it);

/*
 * list_insert_at(it, elm) insert elm before the node pointed by it
 */
void list_insert_at(iterator it, struct list *elm);
</source>

The following example demonstrate the use of iterator to traverse a list in order to print the list content:

<source lang="C">
void iterator_print(struct list *l) {
  int                           line;
  line = printf("l = [");

  // Iterate using iterators
  for (iterator it = list_begin(l); !list_is_end(it); list_next(&it)) {
    assert(it && it->next);
    if (line > 72) // break long lines
      line = printf("\n     ") - 1;
    line += printf(" %3d;", list_get(it));
  }

  printf("%s]\n", line>72 ? "\n" : " ");
}
</source>

In order to provide operations like insertion before an element of the list, the iterator will be place before the ''current node''. The iterator itself is in fact one of the node of list, and the targeted element is the next node.

[[Fichier:Basic_Iterator.png|border|600px|Iterators]]

'''Hints:''' iterator operations are very simple, for example an iterator is ''the end'' if the next pointer is <tt>NULL</tt>, the ''get'' operation just return the value of the next node …

== Vectors ==

Vectors (or contiguous lists) are lists backed with array. These vector should be able to grow in size automatically (see the end of the subject.)

* '''Your goal is to implement the functions of the following header:'''

<source lang="C">
/* vector.h : Simple vector implementation */

# ifndef VECTOR_H_
# define VECTOR_H_

# include <stdlib.h>

struct vector {
  size_t        capacity, size;
  int          *data;
};

/*
 * vector_make(capacity) create an empty vector
 * with initial storage size capacity
 */
struct vector* vector_make(size_t capacity);

/*
 * vector_push_back(vect, x) add x at the end of vect
 * if vect is full increase capacity
 */
void vector_push_back(struct vector *vect, int x);

/*
 * vector_pop_back(vect, &x) get the last element of vect
 * remove the element
 * store result in x
 * return true (!=0) if size > 0
 * return false (0) otherwise
 */
int  vector_pop_back(struct vector *vect, int *x);

/*
 * vector_push_front(vect, x) add x at the beginning of vect
 * if vect is full increase capacity
 */
void vector_push_front(struct vector *vect, int x);

/*
 * vector_pop_back(vect, &x) get the first element of vect
 * remove the element
 * store result in x
 * return true (!=0) if size > 0
 * return false (0) otherwise
 */
int  vector_pop_front(struct vector *vect, int *x);

/*
 * vector_insert_at(vect, pos, x) add x in pos cell of vect
 * return true (!=0) if pos <= size of vect
 * return false (0) otherwise
 * vector_insert_at(v, v->size, x) is equivalent to vector_push_back(v, x)
 * vector_insert_at(v, 0, x) is equivalent to vector_push_front(v, x)
 * if vect is full increase capacity
 */
int vector_insert_at(struct vector *vect, size_t pos, int x);

/*
 * vector_extract_at(vect, pos, &x) get the pos element of vect
 * remove the element
 * store result in x
 * return false (0) if size == 0 or pos >= size
 * vector_extract_at(v, v->size - 1, &x) is equivalent to vector_pop_back(v, &x)
 * vector_extract_at(v, 0, &x) is equivalent to vector_pop_front(v, &x)
 */
int vector_extract_at(struct vector *vect, size_t pos, int *x);

/*
 * vector_clone(vect) create a complete copy of vect
 * both storage contains the same elements but are not at the same memory place
 */
struct vector* vector_clone(struct vector *vect);


# endif
</source>

Our vector should be able to '''grow''': when initial capacity is reached, you must realloc the <tt>data</tt> array (using <tt>realloc(3)</tt>). We choose to grow our vector by multiplying the capacity by two every time we grow our vector.