1 | /*
|
---|
2 | * Copyright (c) 2011 Jiri Svoboda
|
---|
3 | * All rights reserved.
|
---|
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 | * - Redistributions in binary form must reproduce the above copyright
|
---|
12 | * notice, this list of conditions and the following disclaimer in the
|
---|
13 | * documentation and/or other materials provided with the distribution.
|
---|
14 | * - The name of the author may not be used to endorse or promote products
|
---|
15 | * derived from this software without specific prior written permission.
|
---|
16 | *
|
---|
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
---|
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
|
---|
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
|
---|
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
|
---|
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
|
---|
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
---|
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
---|
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
---|
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
|
---|
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
---|
27 | */
|
---|
28 |
|
---|
29 | /** @file Doubly linked list.
|
---|
30 | *
|
---|
31 | * Circular, with a head. Nodes structures are allocated separately from data.
|
---|
32 | * Data is stored as 'void *'. We implement several sanity checks to prevent
|
---|
33 | * common usage errors.
|
---|
34 | */
|
---|
35 |
|
---|
36 | #include <stdio.h>
|
---|
37 | #include <stdlib.h>
|
---|
38 | #include <assert.h>
|
---|
39 | #include "mytypes.h"
|
---|
40 |
|
---|
41 | #include "list.h"
|
---|
42 |
|
---|
43 | static list_node_t *list_node_new(void *data);
|
---|
44 | static void list_node_delete(list_node_t *node);
|
---|
45 | static void list_node_insert_between(list_node_t *n, list_node_t *a, list_node_t *b);
|
---|
46 | static void list_node_unlink(list_node_t *n);
|
---|
47 | static bool_t list_node_present(list_t *list, list_node_t *node);
|
---|
48 |
|
---|
49 | /** Initialize list.
|
---|
50 | *
|
---|
51 | * @param list List to initialize.
|
---|
52 | */
|
---|
53 | void list_init(list_t *list)
|
---|
54 | {
|
---|
55 | list->head.prev = &list->head;
|
---|
56 | list->head.next = &list->head;
|
---|
57 | }
|
---|
58 |
|
---|
59 | /** Deinitialize list.
|
---|
60 | *
|
---|
61 | * @param list List to deinitialize.
|
---|
62 | */
|
---|
63 | void list_fini(list_t *list)
|
---|
64 | {
|
---|
65 | assert(list_is_empty(list));
|
---|
66 |
|
---|
67 | list->head.prev = NULL;
|
---|
68 | list->head.next = NULL;
|
---|
69 | }
|
---|
70 |
|
---|
71 | /** Append data to list.
|
---|
72 | *
|
---|
73 | * Create a new list node and append it at the end of the list.
|
---|
74 | *
|
---|
75 | * @param list Linked list.
|
---|
76 | * @param data Data for the new node.
|
---|
77 | */
|
---|
78 | void list_append(list_t *list, void *data)
|
---|
79 | {
|
---|
80 | list_node_t *node;
|
---|
81 |
|
---|
82 | node = list_node_new(data);
|
---|
83 | list_node_insert_between(node, list->head.prev, &list->head);
|
---|
84 | }
|
---|
85 |
|
---|
86 | /** Prepend data to list.
|
---|
87 | *
|
---|
88 | * Create a new list node and prepend it at the beginning of the list.
|
---|
89 | *
|
---|
90 | * @param list Linked list.
|
---|
91 | * @param data Data for the new node.
|
---|
92 | */
|
---|
93 | void list_prepend(list_t *list, void *data)
|
---|
94 | {
|
---|
95 | list_node_t *node;
|
---|
96 |
|
---|
97 | node = list_node_new(data);
|
---|
98 | list_node_insert_between(node, list->head.prev, &list->head);
|
---|
99 | }
|
---|
100 |
|
---|
101 | /** Remove data from list.
|
---|
102 | *
|
---|
103 | * Removes the given node from a list and destroys it. Any data the node might
|
---|
104 | * have is ignored. If asserts are on, we check wheter node is really present
|
---|
105 | * in the list the caller is requesting us to remove it from.
|
---|
106 | *
|
---|
107 | * @param list Linked list.
|
---|
108 | * @param node List node to remove.
|
---|
109 | */
|
---|
110 | void list_remove(list_t *list, list_node_t *node)
|
---|
111 | {
|
---|
112 | /* Check whether node is in the list as claimed. */
|
---|
113 | assert(list_node_present(list, node));
|
---|
114 | list_node_unlink(node);
|
---|
115 | node->data = NULL;
|
---|
116 | list_node_delete(node);
|
---|
117 | }
|
---|
118 |
|
---|
119 | /** Return first list node or NULL if list is empty.
|
---|
120 | *
|
---|
121 | * @param list Linked list.
|
---|
122 | * @return First node of the list or @c NULL if the list is empty.
|
---|
123 | */
|
---|
124 | list_node_t *list_first(list_t *list)
|
---|
125 | {
|
---|
126 | list_node_t *node;
|
---|
127 |
|
---|
128 | assert(list != NULL);
|
---|
129 | node = list->head.next;
|
---|
130 |
|
---|
131 | return (node != &list->head) ? node : NULL;
|
---|
132 | }
|
---|
133 |
|
---|
134 | /** Return last list node or NULL if list is empty.
|
---|
135 | *
|
---|
136 | * @param list Linked list.
|
---|
137 | * @return Last node of the list or @c NULL if the list is empty.
|
---|
138 | */
|
---|
139 | list_node_t *list_last(list_t *list)
|
---|
140 | {
|
---|
141 | list_node_t *node;
|
---|
142 |
|
---|
143 | assert(list != NULL);
|
---|
144 | node = list->head.prev;
|
---|
145 |
|
---|
146 | return (node != &list->head) ? node : NULL;
|
---|
147 | }
|
---|
148 |
|
---|
149 | /** Return next list node or NULL if this was the last one.
|
---|
150 | *
|
---|
151 | * @param list Linked list.
|
---|
152 | * @param node Node whose successor we are interested in.
|
---|
153 | * @return Following list node or @c NULL if @a node is last.
|
---|
154 | */
|
---|
155 | list_node_t *list_next(list_t *list, list_node_t *node)
|
---|
156 | {
|
---|
157 | (void) list;
|
---|
158 | assert(list != NULL);
|
---|
159 | assert(node != NULL);
|
---|
160 |
|
---|
161 | return (node->next != &list->head) ? node->next : NULL;
|
---|
162 | }
|
---|
163 |
|
---|
164 | /** Return previous list node or NULL if this was the last one.
|
---|
165 | *
|
---|
166 | * @param list Linked list.
|
---|
167 | * @param node Node whose predecessor we are interested in.
|
---|
168 | * @return Preceding list node or @c NULL if @a node is last.
|
---|
169 | */
|
---|
170 | list_node_t *list_prev(list_t *list, list_node_t *node)
|
---|
171 | {
|
---|
172 | (void) list;
|
---|
173 | assert(list != NULL);
|
---|
174 | assert(node != NULL);
|
---|
175 |
|
---|
176 | return (node->prev != &list->head) ? node->prev : NULL;
|
---|
177 | }
|
---|
178 |
|
---|
179 | /** Return b_true if list is empty.
|
---|
180 | *
|
---|
181 | * @param list Linked list.
|
---|
182 | * @return @c b_true if list is empty, @c b_false otherwise.
|
---|
183 | */
|
---|
184 | bool_t list_is_empty(list_t *list)
|
---|
185 | {
|
---|
186 | return (list_first(list) == NULL);
|
---|
187 | }
|
---|
188 |
|
---|
189 | /** Change node data.
|
---|
190 | *
|
---|
191 | * Change the data associated with a node.
|
---|
192 | *
|
---|
193 | * @param node List node.
|
---|
194 | * @param data New data for node.
|
---|
195 | */
|
---|
196 | void list_node_setdata(list_node_t *node, void *data)
|
---|
197 | {
|
---|
198 | node->data = data;
|
---|
199 | }
|
---|
200 |
|
---|
201 | /** Create new node.
|
---|
202 | *
|
---|
203 | * @param data Initial data for node.
|
---|
204 | * @return New list node.
|
---|
205 | */
|
---|
206 | static list_node_t *list_node_new(void *data)
|
---|
207 | {
|
---|
208 | list_node_t *node;
|
---|
209 |
|
---|
210 | node = malloc(sizeof(list_node_t));
|
---|
211 | if (node == NULL) {
|
---|
212 | printf("Memory allocation failed.\n");
|
---|
213 | exit(1);
|
---|
214 | }
|
---|
215 |
|
---|
216 | node->prev = NULL;
|
---|
217 | node->next = NULL;
|
---|
218 | node->data = data;
|
---|
219 |
|
---|
220 | return node;
|
---|
221 | }
|
---|
222 |
|
---|
223 | /** Delete node.
|
---|
224 | *
|
---|
225 | * @param node List node. Must not take part in any list.
|
---|
226 | */
|
---|
227 | static void list_node_delete(list_node_t *node)
|
---|
228 | {
|
---|
229 | assert(node->prev == NULL);
|
---|
230 | assert(node->next == NULL);
|
---|
231 | assert(node->data == NULL);
|
---|
232 | free(node);
|
---|
233 | }
|
---|
234 |
|
---|
235 | /** Insert node between two other nodes.
|
---|
236 | *
|
---|
237 | * Inserts @a n between neighboring nodes @a a and @a b.
|
---|
238 | *
|
---|
239 | * @param n Node to insert.
|
---|
240 | * @param a Node to precede @a n.
|
---|
241 | * @param b Node to follow @a n.
|
---|
242 | */
|
---|
243 | static void list_node_insert_between(list_node_t *n, list_node_t *a,
|
---|
244 | list_node_t *b)
|
---|
245 | {
|
---|
246 | assert(n->prev == NULL);
|
---|
247 | assert(n->next == NULL);
|
---|
248 | n->prev = a;
|
---|
249 | n->next = b;
|
---|
250 |
|
---|
251 | assert(a->next == b);
|
---|
252 | assert(b->prev == a);
|
---|
253 | a->next = n;
|
---|
254 | b->prev = n;
|
---|
255 | }
|
---|
256 |
|
---|
257 | /** Unlink node.
|
---|
258 | *
|
---|
259 | * Unlink node from the list it is currently in.
|
---|
260 | *
|
---|
261 | * @param n Node to unlink from its current list.
|
---|
262 | */
|
---|
263 | static void list_node_unlink(list_node_t *n)
|
---|
264 | {
|
---|
265 | list_node_t *a, *b;
|
---|
266 | assert(n->prev != NULL);
|
---|
267 | assert(n->next != NULL);
|
---|
268 |
|
---|
269 | a = n->prev;
|
---|
270 | b = n->next;
|
---|
271 |
|
---|
272 | assert(a->next == n);
|
---|
273 | assert(b->prev == n);
|
---|
274 |
|
---|
275 | a->next = b;
|
---|
276 | b->prev = a;
|
---|
277 |
|
---|
278 | n->prev = NULL;
|
---|
279 | n->next = NULL;
|
---|
280 | }
|
---|
281 |
|
---|
282 | /** Check whether @a node is in list @a list.
|
---|
283 | *
|
---|
284 | * @param list Linked list.
|
---|
285 | * @param node Node.
|
---|
286 | * @return @c b_true if @a node is part of @a list, @c b_false otherwise.
|
---|
287 | */
|
---|
288 | static bool_t list_node_present(list_t *list, list_node_t *node)
|
---|
289 | {
|
---|
290 | list_node_t *m;
|
---|
291 |
|
---|
292 | m = list->head.next;
|
---|
293 | while (m != &list->head) {
|
---|
294 | if (m == node)
|
---|
295 | return b_true;
|
---|
296 | m = m->next;
|
---|
297 | }
|
---|
298 |
|
---|
299 | return b_false;
|
---|
300 | }
|
---|