diff options
author | Michael Sevakis <jethead71@rockbox.org> | 2014-04-28 10:17:38 -0400 |
---|---|---|
committer | Michael Sevakis <jethead71@rockbox.org> | 2014-08-16 00:27:01 -0400 |
commit | eb63d8b4a2a7cbe4e98216b48a75391718fcebd7 (patch) | |
tree | 225c00b2edcd1a071f262aa181603e0c8775b249 | |
parent | 278e8664a7393f2ca3050660c85d2142c38a4790 (diff) | |
download | rockbox-eb63d8b4a2a7cbe4e98216b48a75391718fcebd7.tar.gz rockbox-eb63d8b4a2a7cbe4e98216b48a75391718fcebd7.zip |
Add common linked list functions
Forms implemented to a greater or lesser degree at the moment:
ll_* = singly-linked list
lld_* = doubly-linked list
lldc_* = doubly-linked circular list
Change-Id: Ieed5af50fc59165c8b14c3513b3b5d0e6f7de9fa
-rw-r--r-- | firmware/SOURCES | 1 | ||||
-rw-r--r-- | firmware/common/linked_list.c | 312 | ||||
-rw-r--r-- | firmware/include/linked_list.h | 114 |
3 files changed, 427 insertions, 0 deletions
diff --git a/firmware/SOURCES b/firmware/SOURCES index a9f9ce5780..a68c4921ba 100644 --- a/firmware/SOURCES +++ b/firmware/SOURCES | |||
@@ -172,6 +172,7 @@ common/dircache.c | |||
172 | #endif /* HAVE_DIRCACHE */ | 172 | #endif /* HAVE_DIRCACHE */ |
173 | common/filefuncs.c | 173 | common/filefuncs.c |
174 | common/format.c | 174 | common/format.c |
175 | common/linked_list.c | ||
175 | #ifdef APPLICATION | 176 | #ifdef APPLICATION |
176 | common/rbpaths.c | 177 | common/rbpaths.c |
177 | #endif | 178 | #endif |
diff --git a/firmware/common/linked_list.c b/firmware/common/linked_list.c new file mode 100644 index 0000000000..006caacc91 --- /dev/null +++ b/firmware/common/linked_list.c | |||
@@ -0,0 +1,312 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2014 by Michael Sevakis | ||
11 | * | ||
12 | * This program is free software; you can redistribute it and/or | ||
13 | * modify it under the terms of the GNU General Public License | ||
14 | * as published by the Free Software Foundation; either version 2 | ||
15 | * of the License, or (at your option) any later version. | ||
16 | * | ||
17 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
18 | * KIND, either express or implied. | ||
19 | * | ||
20 | ****************************************************************************/ | ||
21 | #include <stddef.h> | ||
22 | #include "linked_list.h" | ||
23 | |||
24 | |||
25 | /** (L)inked (L)ist **/ | ||
26 | |||
27 | /** | ||
28 | * Helper to find the node previous to 'find' | ||
29 | * | ||
30 | * returns: NULL if 'find' is the first node | ||
31 | * last node if the 'find' isn't found in the list | ||
32 | */ | ||
33 | static struct ll_node * ll_search_prev(struct ll_head *list, | ||
34 | struct ll_node *find) | ||
35 | { | ||
36 | struct ll_node *prev = NULL; | ||
37 | struct ll_node *node = list->head; | ||
38 | |||
39 | while (node != NULL && node != find) | ||
40 | { | ||
41 | prev = node; | ||
42 | node = node->next; | ||
43 | } | ||
44 | |||
45 | return prev; | ||
46 | } | ||
47 | |||
48 | /** | ||
49 | * Initializes the singly-linked list | ||
50 | */ | ||
51 | void ll_init(struct ll_head *list) | ||
52 | { | ||
53 | list->head = NULL; | ||
54 | list->tail = NULL; | ||
55 | } | ||
56 | |||
57 | /** | ||
58 | * Adds a node to s singly-linked list using "insert next" | ||
59 | */ | ||
60 | void ll_insert_next(struct ll_head *list, struct ll_node *node, | ||
61 | struct ll_node *newnode) | ||
62 | { | ||
63 | if (node == NULL) | ||
64 | { | ||
65 | node = list->head; | ||
66 | |||
67 | newnode->next = node; | ||
68 | list->head = newnode; | ||
69 | |||
70 | if (node == NULL) | ||
71 | list->tail = node; | ||
72 | } | ||
73 | else | ||
74 | { | ||
75 | struct ll_node *next = node->next; | ||
76 | |||
77 | newnode->next = next; | ||
78 | node->next = newnode; | ||
79 | |||
80 | if (next == NULL) | ||
81 | list->tail = newnode; | ||
82 | } | ||
83 | } | ||
84 | |||
85 | /** | ||
86 | * Adds a node to a singly-linked list using "insert first" | ||
87 | */ | ||
88 | void ll_insert_first(struct ll_head *list, struct ll_node *node) | ||
89 | { | ||
90 | struct ll_node *head = list->head; | ||
91 | |||
92 | node->next = head; | ||
93 | list->head = node; | ||
94 | |||
95 | if (head == NULL) | ||
96 | list->tail = node; | ||
97 | } | ||
98 | |||
99 | /** | ||
100 | * Adds a node to a singly-linked list using "insert last" | ||
101 | */ | ||
102 | void ll_insert_last(struct ll_head *list, struct ll_node *node) | ||
103 | { | ||
104 | struct ll_node *tail = list->tail; | ||
105 | |||
106 | node->next = NULL; | ||
107 | list->tail = node; | ||
108 | |||
109 | if (tail == NULL) | ||
110 | list->head = node; | ||
111 | else | ||
112 | tail->next = node; | ||
113 | } | ||
114 | |||
115 | /** | ||
116 | * Removes the node after "node"; if there is none, nothing is changed | ||
117 | */ | ||
118 | void ll_remove_next(struct ll_head *list, struct ll_node *node) | ||
119 | { | ||
120 | if (node == NULL) | ||
121 | { | ||
122 | node = list->head->next; | ||
123 | |||
124 | list->head = node; | ||
125 | |||
126 | if (node == NULL) | ||
127 | list->tail = NULL; | ||
128 | } | ||
129 | else | ||
130 | { | ||
131 | struct ll_node *next = node->next; | ||
132 | |||
133 | if (next != NULL) | ||
134 | { | ||
135 | next = next->next; | ||
136 | node->next = next; | ||
137 | |||
138 | if (!next) | ||
139 | list->tail = node; | ||
140 | } | ||
141 | } | ||
142 | } | ||
143 | |||
144 | /** | ||
145 | * Removes the first node in the list | ||
146 | */ | ||
147 | void ll_remove_first(struct ll_head *list) | ||
148 | { | ||
149 | struct ll_node *node = list->head->next; | ||
150 | |||
151 | list->head = node; | ||
152 | |||
153 | if (node == NULL) | ||
154 | list->tail = NULL; | ||
155 | } | ||
156 | |||
157 | /** | ||
158 | * Removes the node from the list | ||
159 | */ | ||
160 | void ll_remove(struct ll_head *list, struct ll_node *node) | ||
161 | { | ||
162 | ll_remove_next(list, ll_search_prev(list, node)); | ||
163 | } | ||
164 | |||
165 | |||
166 | /** (L)inked (L)ist (D)ouble **/ | ||
167 | |||
168 | /** | ||
169 | * Initializes the doubly-linked list | ||
170 | */ | ||
171 | void lld_init(struct lld_head *list) | ||
172 | { | ||
173 | list->head = NULL; | ||
174 | list->tail = NULL; | ||
175 | |||
176 | /* tail could be stored in first item's prev pointer but this simplifies | ||
177 | the routines and maintains the non-circularity */ | ||
178 | } | ||
179 | |||
180 | /** | ||
181 | * Adds a node to a doubly-linked list using "insert first" | ||
182 | */ | ||
183 | void lld_insert_first(struct lld_head *list, struct lld_node *node) | ||
184 | { | ||
185 | struct lld_node *head = list->head; | ||
186 | |||
187 | list->head = node; | ||
188 | |||
189 | if (head == NULL) | ||
190 | list->tail = node; | ||
191 | else | ||
192 | head->prev = node; | ||
193 | |||
194 | node->next = head; | ||
195 | node->prev = NULL; | ||
196 | } | ||
197 | |||
198 | /** | ||
199 | * Adds a node to a doubly-linked list using "insert last" | ||
200 | */ | ||
201 | void lld_insert_last(struct lld_head *list, struct lld_node *node) | ||
202 | { | ||
203 | struct lld_node *tail = list->tail; | ||
204 | |||
205 | list->tail = node; | ||
206 | |||
207 | if (tail == NULL) | ||
208 | list->head = node; | ||
209 | else | ||
210 | tail->next = node; | ||
211 | |||
212 | node->next = NULL; | ||
213 | node->prev = tail; | ||
214 | } | ||
215 | |||
216 | /** | ||
217 | * Removes a node from a doubly-linked list | ||
218 | */ | ||
219 | void lld_remove(struct lld_head *list, struct lld_node *node) | ||
220 | { | ||
221 | struct lld_node *next = node->next; | ||
222 | struct lld_node *prev = node->prev; | ||
223 | |||
224 | if (node == list->head) | ||
225 | list->head = next; | ||
226 | |||
227 | if (node == list->tail) | ||
228 | list->tail = prev; | ||
229 | |||
230 | if (prev != NULL) | ||
231 | prev->next = next; | ||
232 | |||
233 | if (next != NULL) | ||
234 | next->prev = prev; | ||
235 | } | ||
236 | |||
237 | |||
238 | /** (L)inked (L)ist (D)ouble (C)ircular **/ | ||
239 | |||
240 | /** | ||
241 | * Helper that inserts a node into a doubly-link circular list; does not | ||
242 | * affect list->head, just returns its state | ||
243 | */ | ||
244 | static inline struct lldc_node * lldc_insert(struct lldc_head *list, | ||
245 | struct lldc_node *node) | ||
246 | { | ||
247 | struct lldc_node *head = list->head; | ||
248 | |||
249 | if (head == NULL) | ||
250 | { | ||
251 | node->prev = node; | ||
252 | node->next = node; | ||
253 | } | ||
254 | else | ||
255 | { | ||
256 | node->prev = head->prev; | ||
257 | node->next = head; | ||
258 | head->prev->next = node; | ||
259 | head->prev = node; | ||
260 | } | ||
261 | |||
262 | return head; | ||
263 | } | ||
264 | |||
265 | /** | ||
266 | * Initializes the doubly-linked circular list | ||
267 | */ | ||
268 | void lldc_init(struct lldc_head *list) | ||
269 | { | ||
270 | list->head = NULL; | ||
271 | } | ||
272 | |||
273 | /** | ||
274 | * Adds a node to a doubly-linked circular list using "insert first" | ||
275 | */ | ||
276 | void lldc_insert_first(struct lldc_head *list, struct lldc_node *node) | ||
277 | { | ||
278 | lldc_insert(list, node); | ||
279 | list->head = node; | ||
280 | } | ||
281 | |||
282 | /** | ||
283 | * Adds a node to a doubly-linked circular list using "insert last" | ||
284 | */ | ||
285 | void lldc_insert_last(struct lldc_head *list, struct lldc_node *node) | ||
286 | { | ||
287 | if (lldc_insert(list, node) == NULL) | ||
288 | list->head = node; | ||
289 | } | ||
290 | |||
291 | /** | ||
292 | * Removes a node from a doubly-linked circular list | ||
293 | */ | ||
294 | void lldc_remove(struct lldc_head *list, struct lldc_node *node) | ||
295 | { | ||
296 | struct lldc_node *next = node->next; | ||
297 | |||
298 | if (node == list->head) | ||
299 | { | ||
300 | if (node == next) | ||
301 | { | ||
302 | list->head = NULL; | ||
303 | return; | ||
304 | } | ||
305 | |||
306 | list->head = next; | ||
307 | } | ||
308 | |||
309 | struct lldc_node *prev = node->prev; | ||
310 | next->prev = prev; | ||
311 | prev->next = next; | ||
312 | } | ||
diff --git a/firmware/include/linked_list.h b/firmware/include/linked_list.h new file mode 100644 index 0000000000..c678cfa7eb --- /dev/null +++ b/firmware/include/linked_list.h | |||
@@ -0,0 +1,114 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2014 by Michael Sevakis | ||
11 | * | ||
12 | * This program is free software; you can redistribute it and/or | ||
13 | * modify it under the terms of the GNU General Public License | ||
14 | * as published by the Free Software Foundation; either version 2 | ||
15 | * of the License, or (at your option) any later version. | ||
16 | * | ||
17 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
18 | * KIND, either express or implied. | ||
19 | * | ||
20 | ****************************************************************************/ | ||
21 | #ifndef LINKED_LIST_H | ||
22 | #define LINKED_LIST_H | ||
23 | |||
24 | /*** | ||
25 | ** NOTES: | ||
26 | ** Node field order chosen so that one type can alias the other for forward | ||
27 | ** list traveral by the same code. | ||
28 | ** | ||
29 | ** Structures are separate, even if logically equivalent, to perform compile- | ||
30 | ** time type checking. | ||
31 | ** | ||
32 | */ | ||
33 | |||
34 | |||
35 | /* (L)inked (L)ist | ||
36 | * | ||
37 | * Format: | ||
38 | * | ||
39 | * XX->YY->ZZ->0 | ||
40 | * head--^ ^ | ||
41 | * tail----------+ | ||
42 | */ | ||
43 | struct ll_head | ||
44 | { | ||
45 | struct ll_node *head; /* First list item */ | ||
46 | struct ll_node *tail; /* Last list item (to make insert_last O(1)) */ | ||
47 | }; | ||
48 | |||
49 | struct ll_node | ||
50 | { | ||
51 | struct ll_node *next; /* Next list item */ | ||
52 | }; | ||
53 | |||
54 | void ll_init(struct ll_head *list); | ||
55 | void ll_insert_next(struct ll_head *list, struct ll_node *node, | ||
56 | struct ll_node *newnode); | ||
57 | void ll_insert_last(struct ll_head *list, struct ll_node *node); | ||
58 | void ll_remove_next(struct ll_head *list, struct ll_node *node); | ||
59 | void ll_remove(struct ll_head *list, struct ll_node *node); | ||
60 | void ll_insert_first(struct ll_head *list, struct ll_node *node); | ||
61 | void ll_remove_first(struct ll_head *list); | ||
62 | |||
63 | |||
64 | /* (L)inked (L)ist (D)double | ||
65 | * | ||
66 | * Format: | ||
67 | * | ||
68 | * 0<-XX<->YY<->ZZ->0 | ||
69 | * head----^ ^ | ||
70 | * tail--------------+ | ||
71 | */ | ||
72 | struct lld_head | ||
73 | { | ||
74 | struct lld_node *head; /* First list item */ | ||
75 | struct lld_node *tail; /* Last list item (to make insert_last O(1)) */ | ||
76 | }; | ||
77 | |||
78 | struct lld_node | ||
79 | { | ||
80 | struct lld_node *next; /* Next list item */ | ||
81 | struct lld_node *prev; /* Previous list item */ | ||
82 | }; | ||
83 | |||
84 | void lld_init(struct lld_head *list); | ||
85 | void lld_insert_first(struct lld_head *list, struct lld_node *node); | ||
86 | void lld_insert_last(struct lld_head *list, struct lld_node *node); | ||
87 | void lld_remove(struct lld_head *list, struct lld_node *node); | ||
88 | |||
89 | |||
90 | /* (L)inked (L)ist (D)ouble (C)ircular | ||
91 | * | ||
92 | * Format: | ||
93 | * +----------------+ | ||
94 | * | | | ||
95 | * +->XX<->YY<->ZZ<-+ | ||
96 | * head------^ | ||
97 | */ | ||
98 | struct lldc_head | ||
99 | { | ||
100 | struct lldc_node *head; /* First list item */ | ||
101 | }; | ||
102 | |||
103 | struct lldc_node | ||
104 | { | ||
105 | struct lldc_node *next; /* Next list item */ | ||
106 | struct lldc_node *prev; /* Previous list item */ | ||
107 | }; | ||
108 | |||
109 | void lldc_init(struct lldc_head *list); | ||
110 | void lldc_insert_first(struct lldc_head *list, struct lldc_node *node); | ||
111 | void lldc_insert_last(struct lldc_head *list, struct lldc_node *node); | ||
112 | void lldc_remove(struct lldc_head *list, struct lldc_node *node); | ||
113 | |||
114 | #endif /* LINKED_LIST_H */ | ||