Mercurial > data_structures

view src/dequeue.c @ 1:392ce56806f9

find changesets by author, revision, files, or words in the commit message
Added dequeue, cmake file, fix copypasta in queue
author Eris Caffee <discordia@eldalin.com>
date Thu, 20 Sep 2012 23:11:40 -0500
parents
children abdba37f67a2
line source
1 #include <stdlib.h>
2 #include <errno.h>
3
4 #include "dequeue.h"
5
6 ////////////////////////////////////////////////////////////////////////////////
7 struct dequeue * dequeue_new(size_t const max)
8 {
9 if (max < 1)
10 {
11 errno = EINVAL;
12 return NULL;
13 }
14
15 struct dequeue * deq = malloc(sizeof(struct dequeue));
16 if (NULL == deq)
17 return NULL;
18
19 deq->bottom = deq->top = deq->count = 0;
20 deq->max = max;
21
22 deq->data = calloc(deq->max, sizeof(void *));
23 if (NULL == deq->data)
24 {
25 free(deq);
26 return NULL;
27 }
28
29 return deq;
30 }
31
32 ////////////////////////////////////////////////////////////////////////////////
33 // Returns:
34 // NULL on error
35 // elem on success and the buffer is not full
36 // the overwritten element on success if the buffer was full
37 void * dequeue_push_top(struct dequeue * deq, void * elem)
38 {
39 if ((NULL == deq) || (NULL == elem))
40 {
41 errno = EINVAL;
42 return NULL;
43 }
44
45 if (deq->count == deq->max)
46 {
47 errno = ENOMEM;
48 return NULL;
49 }
50
51 if (deq->max - 1 == deq->top)
52 deq->top = 0;
53 else
54 deq->top++;
55
56 deq->data[deq->top] = elem;
57 deq->count++;
58
59 return elem;
60 }
61
62 ////////////////////////////////////////////////////////////////////////////////
63 void * dequeue_push_bottom(struct dequeue * deq, void * elem)
64 {
65 if ((NULL == deq) || (NULL == elem))
66 {
67 errno = EINVAL;
68 return NULL;
69 }
70
71 if (deq->count == deq->max)
72 {
73 errno = ENOMEM;
74 return NULL;
75 }
76
77 if (0 == deq->bottom)
78 deq->bottom = deq->max - 1;
79 else
80 deq->bottom--;
81
82 deq->data[deq->bottom] = elem;
83 deq->count++;
84
85 return elem;
86 }
87
88 ////////////////////////////////////////////////////////////////////////////////
89 void * dequeue_pop_top(struct dequeue * deq)
90 {
91 if (NULL == deq)
92 {
93 errno = EINVAL;
94 return NULL;
95 }
96
97 if (deq->count == 0)
98 return NULL;
99
100 void * t = deq->data[deq->top];
101
102 if (deq->top == 0)
103 deq->top = deq->max - 1;
104 else
105 deq->top--;
106
107 deq->count--;
108
109 return t;
110 }
111
112 ////////////////////////////////////////////////////////////////////////////////
113 void * dequeue_pop_bottom(struct dequeue * deq)
114 {
115 if (NULL == deq)
116 {
117 errno = EINVAL;
118 return NULL;
119 }
120
121 if (deq->count == 0)
122 return NULL;
123
124 void * t = deq->data[deq->bottom];
125
126 if (deq->bottom == deq->max - 1)
127 deq->bottom = 0;
128 else
129 deq->bottom++;
130
131 deq->count--;
132
133 return t;
134 }
135
136
137 ////////////////////////////////////////////////////////////////////////////////
138 size_t dequeue_size(struct dequeue * deq)
139 {
140 if (NULL == deq)
141 {
142 errno = EINVAL;
143 return 0;
144 }
145 return deq->count;
146 }
147
148 ////////////////////////////////////////////////////////////////////////////////
149 void dequeue_delete(struct dequeue * deq)
150 {
151 if (NULL != deq)
152 {
153 free(deq->data);
154 free(deq);
155 }
156 }