queue.c 2.07 KB
Newer Older
Andrei Paskevich's avatar
Andrei Paskevich committed
1
2
3
4
5
6
7
8
9
10
11
/********************************************************************/
/*                                                                  */
/*  The Why3 Verification Platform   /   The Why3 Development Team  */
/*  Copyright 2010-2016   --   INRIA - CNRS - Paris-Sud University  */
/*                                                                  */
/*  This software is distributed under the terms of the GNU Lesser  */
/*  General Public License version 2.1, with the special exception  */
/*  on linking described in file LICENSE.                           */
/*                                                                  */
/********************************************************************/

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <assert.h>
#include <stdlib.h>
#include "queue.h"
#include "string.h"

void simple_push(pqueue q, void* elt);
void resize_queue(pqueue q);

pqueue init_queue(unsigned int capacity) {
  assert (capacity > 0);
  pqueue res = (pqueue) malloc(sizeof(t_queue));
  res->capacity = capacity;
  res->len = 0;
  res->pointer = 0;
  res->data = (void**) malloc(sizeof(void*) * capacity);
  return res;
}

void* queue_pop(pqueue q) {
  void* tmp;
  assert (q->len > 0);
  tmp = q->data[q->pointer];
  q->len--;
  q->pointer = (q->pointer + 1) % q->capacity;
  return tmp;
}

void simple_push(pqueue q, void* elt) {
  q->data[(q->pointer + q->len) % q->capacity] = elt;
  q->len++;
}

void resize_queue(pqueue q) {
  unsigned int old_cap, new_cap, old_p, new_p;
  old_cap = q->capacity;
  old_p = q->pointer;
  new_cap = 2 * old_cap;
  new_p = new_cap - old_cap + old_p;
  q->data = (void**) realloc(q->data, sizeof(void*) * new_cap);
  memcpy(q->data + new_p,
         q->data + old_p,
         sizeof(void*) * (old_cap - old_p));
  q->capacity = new_cap;
  q->pointer = new_p;
}

void queue_push(pqueue q, void* elt) {
  if (q->len == q->capacity) {
    resize_queue(q);
  }
  simple_push(q, elt);
}

bool queue_is_empty(pqueue q) {
  return (q->len == 0);
}

unsigned int queue_length(pqueue q) {
  return (q->len);
}

void free_queue(pqueue q) {
  assert(queue_is_empty (q));
  free(q->data);
  free(q);
}