Mercurial > data_structures

view src/dequeue.c @ 9:abdba37f67a2

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