Statistics
| Branch: | Revision:

grapes / src / Utils / fifo_queue.c @ f83be11a

History | View | Annotate | Download (3.37 KB)

1
#include <stdlib.h>
2
#include <stdio.h>
3

    
4
#include "fifo_queue.h"
5

    
6
typedef struct fifo_queue {
7
  void **store;
8

    
9
  int max_size;
10
  int current_size;
11
  int head_ptr;
12
  int tail_ptr;
13
} fifo_queue_t;
14

    
15
fifo_queue_p fifo_queue_create(int size)
16
{
17
  fifo_queue_p queue;
18

    
19
  if (size <= 0) return NULL;
20

    
21
  queue = malloc(sizeof(fifo_queue_t));
22
  if (!queue) return NULL;
23

    
24
  queue->store = calloc(size, sizeof(void *));
25
  if (!queue->store) {
26
    free(queue);
27
    return NULL;
28
  }
29

    
30
  queue->max_size = size;
31
  queue->current_size = 0;
32
  queue->head_ptr = 0;
33
  queue->tail_ptr = 0;
34
  return queue;
35
}
36

    
37
void fifo_queue_destroy(fifo_queue_p queue, void (*free_ptr)(void *ptr))
38
{
39
  int i, pos;
40

    
41
  if (free_ptr == NULL)
42
    free_ptr = &free;
43

    
44
  /* deallocating elements */
45
  if (queue->current_size > 0) {
46
    for (i=0; i<queue->current_size; i++) {
47
      pos = (queue->head_ptr + i > queue->max_size - 1) ?
48
        (queue->head_ptr + i) - (queue->max_size) : queue->head_ptr + i;
49

    
50
      free_ptr(queue->store[pos]);
51
    }
52
  }
53

    
54
  free(queue->store);
55
  free(queue);
56
}
57

    
58
int fifo_queue_size(fifo_queue_p queue)
59
{
60
  return queue->current_size;
61
}
62

    
63
int fifo_queue_add(fifo_queue_p queue, void *el)
64
{
65
  if (!queue) return 1;
66
  if (!el) return 1;
67

    
68
  /* expand the array if needed */
69
  if (queue->current_size + 1 > queue->max_size) {
70
    void **new_store;
71
    int new_size;
72
    int i, j;
73

    
74
    new_size = queue->max_size * 2;
75

    
76
    new_store =  calloc(new_size, sizeof(void *));
77

    
78
    if (!new_store) return 2;
79

    
80
    for (i=0; i<queue->current_size; i++) {
81
      j = (queue->head_ptr + i > queue->max_size - 1) ?
82
        (queue->head_ptr + i) - (queue->max_size) : queue->head_ptr + i;
83

    
84
      new_store[i] = queue->store[j];
85
    }
86

    
87
    free(queue->store);
88
    queue->store = new_store;
89

    
90
    queue->max_size = new_size;
91
    queue->head_ptr = 0;
92
    queue->tail_ptr = queue->current_size;
93
  }
94

    
95
  /* Add the element to the queue */
96
  if (queue->tail_ptr == queue->max_size)
97
    queue->tail_ptr = 0;
98

    
99
  queue->store[queue->tail_ptr] = el;
100
  queue->tail_ptr++;
101
  queue->current_size++;
102

    
103
  /*
104
    fprintf(stderr,
105
          "fifo_queue: Added element at pos %d " \
106
          "(head=%d, tail=%d, curr_size=%d, max_size=%d)\n",
107
          queue->tail_ptr - 1,
108
          queue->head_ptr, queue->tail_ptr,
109
          queue->current_size, queue->max_size);
110
  */
111

    
112
  return 0;
113
}
114

    
115
void* fifo_queue_get_head(fifo_queue_p queue)
116
{
117
  if (!queue) return NULL;
118
  if (queue->current_size == 0) return NULL;
119
  return queue->store[queue->head_ptr];
120
}
121

    
122
void* fifo_queue_get(fifo_queue_p queue, int nr)
123
{
124
  int pos;
125
  if (!queue) return NULL;
126
  if (queue->current_size < nr) return NULL;
127

    
128
  pos = (queue->head_ptr + nr > queue->max_size - 1) ?
129
    (queue->head_ptr + nr) - (queue->max_size) : queue->head_ptr + nr;
130

    
131

    
132
  return queue->store[pos];
133
}
134

    
135
void* fifo_queue_remove_head(fifo_queue_p queue)
136
{
137
  void *el;
138
  if (!queue) return NULL;
139
  if (queue->current_size == 0) return NULL;
140

    
141
  el = queue->store[queue->head_ptr];
142

    
143
  queue->current_size--;
144
  queue->head_ptr++;
145

    
146
  if (queue->head_ptr == queue->max_size){
147
    queue->head_ptr = 0;
148
  }
149

    
150
  if (queue->current_size == 0) {
151
    queue->head_ptr = 0;
152
    queue->tail_ptr = 0;
153
  }
154

    
155
  /*
156
  fprintf(stderr,
157
          "fifo_queue: Removed element at pos %d " \
158
          "(head=%d, tail=%d, curr_size=%d, max_size=%d)\n",
159
          queue->head_ptr - 1,
160
          queue->head_ptr, queue->tail_ptr,
161
          queue->current_size, queue->max_size);
162
  */
163
  return el;
164
}