queue.c

Go to the documentation of this file.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "allocate.h"
#include "queue.h"

struct queue
{
   int  size;  
   int  used;  
   int  first; 
   int  next;  
   int* elem;  
};

static bool queue_is_valid(const Queue* queue)
{
   return queue != NULL
      && queue->size  >  0 && queue->elem  != NULL
      && queue->used  >= 0 && queue->used  < queue->size
      && queue->first >= 0 && queue->first < queue->size
      && queue->next  >= 0 && queue->next  < queue->size
      && (queue->first + queue->used) % queue->size == queue->next
      && (  (queue->used >  0 && queue->first != queue->next)
         || (queue->used == 0 && queue->first == queue->next));
}

Queue* queue_new(int size)
{
   Queue* queue;

   assert(size > 0);
   
   queue = allocate(1, sizeof(*queue));

   queue->size  = size + 1;
   queue->used  = 0;
   queue->first = 0;
   queue->next  = 0;
   queue->elem  = allocate(queue->size, sizeof(*queue->elem));

   assert(queue_is_valid(queue));
   
   return queue;
}

void queue_free(Queue* queue)
{
   assert(queue_is_valid(queue));

   deallocate(queue->elem);
   deallocate(queue);
}

void queue_put(Queue* queue, int element)
{
   assert(queue_is_valid(queue));

   if (queue->used == queue->size - 1)
   {
      fprintf(stderr, "Queue overflow size=%d\n", queue->size);
      abort();
   }
   assert(queue->used < queue->size - 1);
   
   queue->elem[queue->next] = element;
   queue->next              = (queue->next + 1) % queue->size;   
   queue->used++;
   
   assert(queue_is_valid(queue));
}

int queue_get(Queue* queue)
{
   int element;
   
   assert(queue_is_valid(queue));

   if (queue->used == 0)
      return -1;
      
   element      = queue->elem[queue->first];
   queue->first = (queue->first + 1) % queue->size;
   queue->used--;
   
   assert(queue_is_valid(queue));

   return element;
}

bool queue_is_empty(const Queue* queue)
{
   assert(queue_is_valid(queue));

   return queue->used == 0;
}