Mercurial > data_structures

view src/dequeue.c @ 10:68f85ffc6029

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