1 /*
2 Copyright (C) 2003 Commonwealth Scientific and Industrial Research
3 Organisation (CSIRO) Australia
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
7 are met:
8
9 - Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
12 - Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
15
16 - Neither the name of CSIRO Australia nor the names of its
17 contributors may be used to endorse or promote products derived from
18 this software without specific prior written permission.
19
20 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
23 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ORGANISATION OR
24 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #include "config.h"
34 #include <stdlib.h>
35
36 #include "oggz_dlist.h"
37 #include "oggz_macros.h"
38
39 typedef struct OggzDListElem {
40 struct OggzDListElem * next;
41 struct OggzDListElem * prev;
42 void * data;
43 } OggzDListElem;
44
45 struct _OggzDList {
46 OggzDListElem * head;
47 OggzDListElem * tail;
48 };
49
50 OggzDList *
oggz_dlist_new(void)51 oggz_dlist_new (void) {
52
53 OggzDList *dlist;
54 OggzDListElem *dummy_front, *dummy_back;
55
56 dlist = oggz_malloc(sizeof(OggzDList));
57 if (dlist == NULL) return NULL;
58
59 dummy_front = oggz_malloc(sizeof(OggzDListElem));
60 if (dummy_front == NULL) {
61 oggz_free (dlist);
62 return NULL;
63 }
64
65 dummy_back = oggz_malloc(sizeof(OggzDListElem));
66 if (dummy_back == NULL) {
67 oggz_free (dummy_front);
68 oggz_free (dlist);
69 return NULL;
70 }
71
72 dummy_front->next = dummy_back;
73 dummy_front->prev = NULL;
74
75 dummy_back->prev = dummy_front;
76 dummy_back->next = NULL;
77
78 dlist->head = dummy_front;
79 dlist->tail = dummy_back;
80
81 return dlist;
82 }
83
84 void
oggz_dlist_delete(OggzDList * dlist)85 oggz_dlist_delete(OggzDList *dlist) {
86
87 OggzDListElem *p;
88
89 for (p = dlist->head->next; p != NULL; p = p->next) {
90 oggz_free(p->prev);
91 }
92
93 oggz_free(dlist->tail);
94 oggz_free(dlist);
95
96 }
97
98 int
oggz_dlist_is_empty(OggzDList * dlist)99 oggz_dlist_is_empty(OggzDList *dlist) {
100 return (dlist->head->next == dlist->tail);
101 }
102
103 int
oggz_dlist_append(OggzDList * dlist,void * elem)104 oggz_dlist_append(OggzDList *dlist, void *elem) {
105
106 OggzDListElem *new_elem;
107
108 if (dlist == NULL) return -1;
109
110 new_elem = oggz_malloc(sizeof(OggzDListElem));
111 if (new_elem == NULL) return -1;
112
113 new_elem->data = elem;
114 new_elem->next = dlist->tail;
115 new_elem->prev = dlist->tail->prev;
116 new_elem->prev->next = new_elem;
117 new_elem->next->prev = new_elem;
118
119 return 0;
120 }
121
122 int
oggz_dlist_prepend(OggzDList * dlist,void * elem)123 oggz_dlist_prepend(OggzDList *dlist, void *elem) {
124
125 OggzDListElem *new_elem;
126
127 if (dlist == NULL) return -1;
128
129 new_elem = oggz_malloc(sizeof(OggzDListElem));
130 if (new_elem == NULL) return -1;
131
132 new_elem->data = elem;
133 new_elem->prev = dlist->head;
134 new_elem->next = dlist->head->next;
135 new_elem->prev->next = new_elem;
136 new_elem->next->prev = new_elem;
137
138 return 0;
139 }
140
141 int
oggz_dlist_iter(OggzDList * dlist,OggzDListIterFunc func)142 oggz_dlist_iter(OggzDList *dlist, OggzDListIterFunc func) {
143
144 OggzDListElem *p;
145
146 for (p = dlist->head->next; p != dlist->tail; p = p->next) {
147 int r = func(p->data);
148 if (r == DLIST_ITER_ERROR) {
149 return -1;
150 }
151
152 if (r == DLIST_ITER_CANCEL) {
153 break;
154 }
155 }
156
157 return 0;
158 }
159
160 void
oggz_dlist_reverse_iter(OggzDList * dlist,OggzDListIterFunc func)161 oggz_dlist_reverse_iter(OggzDList *dlist, OggzDListIterFunc func) {
162
163 OggzDListElem *p;
164
165 for (p = dlist->tail->prev; p != dlist->head; p = p->prev) {
166 if (func(p->data) == DLIST_ITER_CANCEL) {
167 break;
168 }
169 }
170 }
171
172 int
oggz_dlist_deliter(OggzDList * dlist,OggzDListIterFunc func)173 oggz_dlist_deliter(OggzDList *dlist, OggzDListIterFunc func) {
174
175 OggzDListElem *p, *q;
176 int result = 0;
177
178 for (p = dlist->head->next; p != dlist->tail; p = q) {
179 int r = func(p->data);
180 if (r == DLIST_ITER_ERROR) {
181 result = -1;
182 }
183
184 if (r == DLIST_ITER_CANCEL) {
185 break;
186 }
187
188 q = p->next;
189 p->prev->next = p->next;
190 p->next->prev = p->prev;
191
192 oggz_free(p);
193 }
194 return result;
195 }
196
197 void
oggz_dlist_reverse_deliter(OggzDList * dlist,OggzDListIterFunc func)198 oggz_dlist_reverse_deliter(OggzDList *dlist, OggzDListIterFunc func) {
199
200 OggzDListElem *p, *q;
201
202 for (p = dlist->tail->prev; p != dlist->head; p = q) {
203 if (func(p->data) == DLIST_ITER_CANCEL) {
204 break;
205 }
206 q = p->prev;
207 p->prev->next = p->next;
208 p->next->prev = p->prev;
209
210 oggz_free(p);
211 }
212
213 }
214