20141020:TP:C:Lists:EN

Assignments

For the following practical session, you have a repository named login-tp04 that will contains the following files:

• login-tp-04
  • AUTHORS
  • lists
    • Makefile
    • list.h
    • list.c
  • vectors
    • Makefile
    • vector.h
    • vector.c

Your code will be cloned for evaluation monday the 27th of october in the morning.

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:

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

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

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

/* 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

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

Basic Operations

For basic operation, you must provides the following functions:

/* 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);

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

Sorting

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

First, implement the classical sorted insert:

/*
 * 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);

Then implement the sort function:

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

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

The algorithm is quiet simple:

1. detach the sentinel (l) from the list (keeping the list head in a variable head)
2. The sentinel becomes a new list (set next to NULL)
3. Iterate over head:
   • detach the current node cur of head
   • insert cur in l

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:

/* 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);

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

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" : " ");
}

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.

Hints: iterator operations are very simple, for example an iterator is the end if the next pointer is NULL, 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:

/* 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

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