20171113:Practical:C:Lists:Vectors:Queues

Introduction/Assignements

This week will dive into lists constructions: linked lists, vectors and queues (implemented using linked lists).

S3#: It is due on Friday, April 13, 2018 at 2pm

The tutorial directory (in your GIT) will have the following form:

• 20171113_lists:
  • linked_lists
  • vectors
  • queues

See the exercises for the detailed content.

Linked Lists

• Directory:
  • linked_lists
    • list.h
    • list.c

Presentation

Linked list is a classical recursive data structure (see this week lecture) that comes in many flavor. We choose a practical approach using external allocation and sentinel.

• External Allocation: all list functions are not responsible for memory allocations nor memory releases. All operations directly receive pre-constructed list cells (for insertion) and returns (disconnected) cells.
• Sentinel: all lists will always contain an empty fake cell at the beginning (before all other cells). An empty list is thus a single sentinel and not a NULL pointer.

The principal impacts on the implementation are:

• Operations that modify the list head don't need to take a double pointer nor returns a new head, just update the next field of the sentinel cell.
• Operations never use malloc(3) nor free(3) (and similar functions) and the client can use its own allocation scheme.
• Searching and elements access is done using an iterator pattern (similar to C++ iterator).
• Searching, inserting and removing can be implemented by composition of simple functions.

Header

Here is the full list header describing the requested functions:

/*
 * list.h : Linked lists
 */
 
#ifndef EPITA_IP_LIST_H_
#define EPITA_IP_LIST_H_
 
/* Simply linked list of integers */
 
struct list {
  struct list *next;
  int          data;
};
 
/*
 * Standard operations
 * We're working with sentinels and external allocation
 * This means that our lists always have a fake head (the sentinel)
 * and all allocations (and free) are performed by the caller, not the operation
 */
 
/*
 * list_init(list)
 * initialise the sentinel node list
 */
void list_init(struct list *list);
 
/*
 * list_is_empty(list)
 * returns true if the list is empty
 * remember, we have a sentinel thus a list always has at least one node,
 * the list is empty if this node doesn't have a next.
 */
int list_is_empty(struct list *list);
 
/*
 * list_len(list)
 * returns the length of the list (don't count the sentinel)
 */
size_t list_len(struct list *list);
 
/*
 * list_push_front(list, elm)
 * attach elm in front of list, that is after the sentinel.
 * Note that elm is already a node, you just have to attach it.
 */
void list_push_front(struct list *list, struct list *elm);
 
/*
 * list_pop_front(list)
 * Extract the first element (not the sentinel) of list.
 * This operation detaches the element from the list and returns it (caller is
 * responsible for freeing it.)
 * If the list is empty, the function returns NULL.
 */
struct list* list_pop_front(struct list *list);
 
/*
 * list_find(list, value)
 * search for the first node containing value and returns (without detaching it)
 * the corresponding list node. The function returns NULL if the value is not
 * present in the list.
 */
struct list* list_find(struct list *list, int value);
 
/*
 * list_lower_bound(list, value)
 * search for the first element not smaller than value in list
 * returns the pointer to the cell BEFORE this element
 */
struct list* list_lower_bound(struct list *list, int value);
 
/*
 * list_is_sorted(list)
 * check whether the list is sorted in increasing order
 */
int list_is_sorted(struct list *list);
 
/*
 * list_insert(list, elm)
 * insert elm in the sorted list (keeping the list sorted)
 * Like list_push_front, elm is already a list node.
 */
void list_insert(struct list *list, struct list *elm);
 
/*
 * More algorithms
 */
 
/*
 * list_rev(list)
 * reverse the list using the same nodes (just move them) and the same sentinel.
 */
void list_rev(struct list *list);
 
/*
 * list_half_split(list, second)
 * split the list in half and put the second half in second
 * second is an empty list (just a sentinel)
 */
void list_half_split(struct list *list, struct list *second);
 
# endif /* EPITA_IP_LIST_H_ */

Implementation

• Implement all functions from list.h in the file list.c

Each function is described by the comment in the header, you can add functions not listed in this header but the must be marked as static since they must not be exported. The file list.c must not contain a main function.

Here are some notes on the implementation:

• list_init(list) takes the node used as sentinel and set the next pointer to NULL
• list_is_empty(list): a list is empty if the next pointer of the sentinel is NULL
• list_len(list): the number of nodes without the sentinel
• list_push_front(list, elm): elm is a list node containing the new value, you'll attach it after the sentinel
• list_pop_front(list) detaches the element after the sentinel and returns it
• list_lower_bound(list, value) returns a pseudo list where the element before the bound serves as a sentinel, such that insert can be implemented with lower bound and push front.
• list_half_split(list, second) can be implemented with only pass and without computing the length

Testing

In order to test, you'll write another C file where you test operations one by one. The tests are your responsibility, but here are some useful trick.

In order to display the list, here is an example of a printing function for lists (beware, it contains a goto):

void print_list(struct list *list)
{
  int line = printf("[");
  if (list->next) {
    goto pastfst;
    while (list->next) {
      line += printf(";");
      if (line > 72) {
	printf("\n ");
	line = 1;
      }
      pastfst:
      line += printf(" %d", list->next->data);
      list = list->next;
    }
  }
  printf(" ]\n");
}

While testing you must take care of allocation/free, if you're looking for a nice strategy, you can try to use an array of node …

A way to test your sorted insertion function is to implement an insertion sort, here is the function:

void list_insert_sort(struct list *list)
{
  if (list_is_empty(list))       // nothing to do
    return;
  struct list fake_head = {0,0}; // temporary head
  while (!list_is_empty(list)) {
    struct list *elm = list_pop_front(list);
    list_insert(&fake_head, elm);
  }
  list->next = fake_head.next;   // reattach the sorted list to its sentinel
}

Vectors

• Directory:
  • vectors
    • vector.h
    • vector.c

Vectors are wrappers around arrays in order to provide list like operations. The vector structure contains an array, its capacity and the current number of cells used in the array.

The structure look like this:

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

capacity is the number of cell in data (the array of integers) and size is the number of used cells.

One interesting approach is to make vectors grow automatically: when adding an element to the vector, if the number of used cells is equal to the capacity, you can use realloc(3) in order to obtain a bigger array. A common strategy to avoid to much resizing is to double the capacity each time we need to resize. Here is an example of usage of realloc(3) in order to double the size of data:

// returns false if something goes wrong (realloc fails)
int double_vector_size(struct vector *vect)
{
  int *tmp = realloc(vect->data, 2 * vect->capacity * sizeof (int));
  if (tmp == NULL) {
    // oups no more memory ?
    warn("realloc of data fails");
    return 0;
  }
  vect->data = tmp;
  vect->capacity *= 2;
  return 1;
}

Header

The following file describes the API of vectors:

/*
 * vector.h : Simple vector implementation
 */
 
# ifndef EPITA_IP_VECTOR_H_
# define EPITA_IP_VECTOR_H_
 
# include <stdlib.h>
 
struct vector {
  size_t        capacity, size;
  int          *data;
};
 
/*
 * vector_init(list, value): initializes vect with a storage of capacity integers
 * returns false (0) if allocation fails
 * true (!=0) otherwise
 */
int vector_init(struct vector *vect, size_t capacity);
 
/*
 * vector_make(capacity) create an empty vector
 * with initial storage size capacity
 * returns NULL if something goes wrong (allocations)
 */
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
 * returns false (0) if something goes wrong
 * true (!=0) otherwise
 */
int 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
 * returns false (0) if something goes wrong
 * true (!=0) otherwise
 */
int vector_push_front(struct vector *vect, int x);
 
/*
 * vector_pop_front(vect, &x) get the first element of vect
 * remove the element
 * store result in x
 * return true (!=0) if size was > 0 before pop
 * 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
 * returns true (!=0) if pos <= size of vect
 * returns false (0) otherwise
 * returns false also if something goes wrong
 * 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
 * returns NULL if something goes wrong
 */
struct vector* vector_clone(struct vector *vect);
 
 
# endif

Implementation

• In the file vector.c, implement all the function described in the header vector.h

Some notes:

• As for the previous exercise, you can add functions not in the header as long as they are marked static
• You will need some auxiliary functions for growing storage or shifting array elements
• In all cases of insertion (push and insert), the operation can fail if the growing operation fails
• Remove operations (pop and extract) fails only if the vector is empty (nothing to remove)
• As a bonus, you can handle a shrink case where the size is less than half of the capacity after a remove operation (in that case you will divide the capacity by two).

You are responsible to write your own tests.

Queue

• Directory:
  • queues
    • Makefile
    • queue.h
    • queue.c
    • tree.c

For this part we want to implement traditional FIFO queues using linked lists.

The most efficient queue implementation use single link circular lists. The entry point of the list is the last element (the last pushed element) and its next field points to the first element (the oldest in the queue), after that elements are linked from oldest to most recent. We don't use a sentinel here, but we have an external structure containing the entry point and the size of the queue. Allocation is internal (unlike our previous lists), you must handle correctly cell allocation and release. Here is the structure:

/* standard linked lists */
struct list {
  struct list *next;
  void        *data;
};
 
/*
 * queue container: replace sentinel and add abstraction
 */
struct queue {
  struct list *store;
  size_t       size;
};

We choose to implement queues of void pointers, this will be useful for the last part of the exercise (BFS in a binary tree).

Refer to the slides on lists for all the details, but here is some idea:

• When the queue is empty, the inner list is the NULL pointer.
• When the queue contains a single element, the inner list contains a single cell that points to iteself
• When pushing a new element, you insert it after the entry point and it becomes the new entry point
• When poping an element, you extract the next of the entry point (don't forget to keep the list connected), handle the case of a queue with a single element with case.

Header

/*
 * queue.h: dynamic queue
 */
 
# ifndef EPITA_S3_QUEUE_H_
# define EPITA_S3_QUEUE_H_
 
/* standard linked lists */
struct list {
  struct list *next;
  void        *data;
};
 
/*
 * queue container: replace sentinel and add abstraction
 */
struct queue {
  struct list *store;
  size_t       size;
};
 
/*
 * queue_init(queue) initialize an empty queue container
 * allocation of the container is kept external for more flexibility
 */
void queue_init(struct queue *queue);
 
/*
 * queue_is_empty(queue) test for emptyness
 */
int queue_is_empty(struct queue *queue);
 
/*
 * queue_push(queue, elm) push elm
 */
void queue_push(struct queue *queue, void *elm);
 
/*
 * queue_pop(queue) pop the next element (FIFO order)
 * returns NULL if the queue is empty
 */
void* queue_pop(struct queue *queue);
 
# endif /* EPITA_S3_QUEUE_H_ */

Implementation

• In the file queue.c implement all function from the header.

Same constraints as for the two other exercices.

Testing

Here is a basic test for your code (provided for convenience):

/* testing.c : testing queue */
 
# include <assert.h>
# include <err.h>
# include <stdio.h>
# include <stdlib.h>
 
# include "queue.h"
 
void simple_test(size_t len)
{
  printf(">>> Simple Test: <<<\n");
  struct queue queue;
  queue_init(&queue);
  int *data = calloc(len, sizeof (int));
  if (!data)
    err(1, "allocating data failed, dying");
  printf("  Push:\n");
  for (size_t i = 0; i < len; ++i) {
    data[i] = (int)i;
    queue_push(&queue, data + i);
    printf("    pushed: %d\n", data[i]);
    assert(queue.size == i + 1);
  }
  printf("  after push, size: %zu\n", queue.size);
  assert(queue.size == len);
  while (!queue_is_empty(&queue)) {
    int *elm = queue_pop(&queue);
    assert(elm);
    printf("    pop: %d\n", *elm);
  }
  printf("  after pop, size: %zu\n", queue.size);
  assert(queue.size == 0);
  free(data);
}
 
int main(int argc, char *argv[])
{
  size_t len = 16;
  if (argc > 1)
    len = strtoul(argv[1], NULL, 10);
  simple_test(len);
  return 0;
}

BFS

As a concrete use case for your queue, you will implement a tree breadth first traversal (BFS, or parcours largeur in french).

• Complete the file tree.c
• Write a Makefile that produce the executable tree from your code

/*
 * tree.c: testing queue using binary trees
 */
 
# include <assert.h>
# include <err.h>
# include <stdio.h>
# include <stdlib.h>
 
# include "queue.h"
 
struct tree {
  struct tree *left, *right;
  int key;
};
 
struct tree* build_tree(long depth, int *key)
{
  struct tree *node = NULL;
  if (depth >= 0) {
    node = malloc(sizeof (struct tree));
    if (!node)
      err(1, "tree node allocation failed, dying");
    node->left = build_tree(depth - 1, key);
    *key += 1;
    node->key = *key;
    node->right = build_tree(depth - 1, key);
  }
  return node;
}
 
void bfs(struct tree *root)
{
  // FIX ME
}
 
void delete_tree(struct tree *root)
{
  if (root) {
    delete_tree(root->left);
    delete_tree(root->right);
    free(root);
  }
}
 
int main(int argc, char *argv[])
{
  long depth = 3;
  if (argc > 1)
    depth = strtol(argv[1], NULL, 10);
  int key = 0;
  struct tree *root = build_tree(depth, &key);
  bfs(root);
  delete_tree(root);
  return 0;
}

Here is a description of the BFS algorithm:

BFS(root):
  if root:
    queue = new queue
    queue_push(queue, root)
    queue_push(queue, None)
    while not queue_is_empty(queue):
      node = queue_pop(queue)
      if node:
        print(node.key, end=' ')
        if node.left:
          queue_push(queue, node.left)
        if node.right:
          queue_push(queue, node.right)
      else:
        print()
        if not queue_is_empty(queue):
          queue_push(queue, None)

It's a classical BFS with level detection. The algorithm just print each key with a space between keys and a newline at the end of each level.