20161114:TP:C:queue

Introduction

Our goal is to implement classical queue using circular simply linked list.

The architecture for this practical session:

20151114_queue/
  AUTHORS
  Makefile
  queue.h
  queue.c
  testing.c
  tree.c

Queue implementation

The header for the queue:

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

• Implement all function described in queue.h in a new file queue.c

Testing

Here is a simple test for validating the queue:

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

Tree Breadth First Traversal

In order to test our queue more deeply, we'll implement a BFS on a binary tree.

Here is the skeleton:

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

• Complete tree.c by implementing the function bfs(struct tree *root)