diff options
author | Linus Nielsen Feltzing <linus@haxx.se> | 2002-04-23 09:00:08 +0000 |
---|---|---|
committer | Linus Nielsen Feltzing <linus@haxx.se> | 2002-04-23 09:00:08 +0000 |
commit | 77861463a2c04a56fb4e9574c3fac34ee64ceedc (patch) | |
tree | 6163a973042e7d4d0c01610aa787fe8b4fbdd2c8 /firmware/common/lists.c | |
parent | c92bead2cfefaff61008f358ab223cf7b77bdc29 (diff) | |
download | rockbox-77861463a2c04a56fb4e9574c3fac34ee64ceedc.tar.gz rockbox-77861463a2c04a56fb4e9574c3fac34ee64ceedc.zip |
First version
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@187 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'firmware/common/lists.c')
-rw-r--r-- | firmware/common/lists.c | 305 |
1 files changed, 305 insertions, 0 deletions
diff --git a/firmware/common/lists.c b/firmware/common/lists.c new file mode 100644 index 0000000000..46380e744f --- /dev/null +++ b/firmware/common/lists.c | |||
@@ -0,0 +1,305 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Linus Nielsen Feltzing | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | /* | ||
20 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | ||
21 | |||
22 | Description: | ||
23 | |||
24 | This file contains functions implementing a double linked list. | ||
25 | The functions uses the types LIST and LISTNODE. | ||
26 | There is a trick with the three nodes in LIST. By placing the | ||
27 | tail_pred field in middle, makes it possible to avoid special code | ||
28 | to handle nodes in the beginning or end of the list. | ||
29 | |||
30 | The 'head' and 'tail' field in LIST are never NULL, even if the | ||
31 | list is empty. | ||
32 | |||
33 | The 'succ' and 'pred' field in a LIST_NODE that is in the list, | ||
34 | are never NULL. The 'pred' field for the first LIST_NODE points | ||
35 | to the 'head' field in LIST. The 'succ' node for the last LIST_NODE | ||
36 | points the the tail_pred field in LIST. | ||
37 | |||
38 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | ||
39 | */ | ||
40 | #include "lists.h" | ||
41 | |||
42 | /**************************************************************************** | ||
43 | ** FUNCTION: list_init | ||
44 | ** | ||
45 | ** DESCRIPTION: Initiate a LIST structure. | ||
46 | ** If max_num_nodes is set to NO_SIZE_CHECK there | ||
47 | ** will be no check of the length of the list. | ||
48 | ** | ||
49 | ** RETURN: Nothing | ||
50 | ******************************************************************************/ | ||
51 | void list_init(LIST *list, /* The list to initiate */ | ||
52 | int max_num_nodes) /* Maximum number of nodes */ | ||
53 | { | ||
54 | list->first = (LIST_NODE *)&list->last_prev; | ||
55 | list->last_prev = NULL; | ||
56 | list->last = (LIST_NODE *)&list->first; | ||
57 | list->num_nodes = 0; | ||
58 | list->max_num_nodes = max_num_nodes; | ||
59 | } | ||
60 | |||
61 | /**************************************************************************** | ||
62 | ** FUNCTION: list_insert_before | ||
63 | ** | ||
64 | ** DESCRIPTION: Insert a LIST_NODE in a list before another node in a LIST. | ||
65 | ** | ||
66 | ** RETURN: Nothing | ||
67 | ******************************************************************************/ | ||
68 | void list_insert_before(LIST_NODE *ref, /* The reference node */ | ||
69 | LIST_NODE *ln) /* The node to insert */ | ||
70 | { | ||
71 | ln->next = ref; /* ref is after us */ | ||
72 | ln->prev = ref->prev; /* ref's prev is before us */ | ||
73 | ref->prev = ln; /* we are before ref */ | ||
74 | ln->prev->next = ln; /* we are after ref's prev */ | ||
75 | } | ||
76 | |||
77 | /**************************************************************************** | ||
78 | ** FUNCTION: list_insert_after | ||
79 | ** | ||
80 | ** DESCRIPTION: Insert a LIST_NODE in a list after another node in a LIST. | ||
81 | ** | ||
82 | ** RETURN: Nothing | ||
83 | *****************************************************************************/ | ||
84 | void list_insert_after(LIST_NODE *ref, /* The reference node */ | ||
85 | LIST_NODE *ln) /* The node to insert */ | ||
86 | { | ||
87 | ln->prev = ref; /* ref is before us */ | ||
88 | ln->next = ref->next; /* ref's next is after us */ | ||
89 | ref->next = ln; /* we are after ref */ | ||
90 | ln->next->prev = ln; /* we are before ref's next */ | ||
91 | } | ||
92 | |||
93 | /**************************************************************************** | ||
94 | ** FUNCTION: list_extract_node | ||
95 | ** | ||
96 | ** DESCRIPTION: Extract a LIST_NODE from a list. | ||
97 | ** | ||
98 | ** RETURN: The same LIST_NODE pointer that was passed as a parameter. | ||
99 | *****************************************************************************/ | ||
100 | LIST_NODE *list_extract_node(LIST_NODE *ln) /* The node to extract */ | ||
101 | { | ||
102 | ln->prev->next = ln->next; /* Our prev's next points to our next */ | ||
103 | ln->next->prev = ln->prev; /* Our next's prev points to our prev */ | ||
104 | return ln; | ||
105 | } | ||
106 | |||
107 | /****************************************************************************** | ||
108 | ** FUNCTION: list_add_first | ||
109 | ** | ||
110 | ** DESCRIPTION: Add a LIST_NODE at the beginning of a LIST. | ||
111 | ** | ||
112 | ** RETURN: 1 if OK | ||
113 | ** 0 if list was full | ||
114 | ******************************************************************************/ | ||
115 | int list_add_first(LIST *list, /* The list to add to */ | ||
116 | LIST_NODE *ln) /* The node to add */ | ||
117 | { | ||
118 | if (NO_SIZE_CHECK != list->max_num_nodes) | ||
119 | { | ||
120 | if(list->num_nodes >= list->max_num_nodes) /* List full? */ | ||
121 | { | ||
122 | return 0; | ||
123 | } | ||
124 | } | ||
125 | list_insert_after((LIST_NODE *)list, ln); | ||
126 | list->num_nodes++; /* Increment node counter */ | ||
127 | return 1; | ||
128 | } | ||
129 | |||
130 | /****************************************************************************** | ||
131 | ** FUNCTION: list_extract_first | ||
132 | ** | ||
133 | ** DESCRIPTION: Extract a LIST_NODE from the beginning of a LIST. | ||
134 | ** | ||
135 | ** RETURN: The extracted LIST_NODE or NULL if the list is empty | ||
136 | ******************************************************************************/ | ||
137 | LIST_NODE *list_extract_first(LIST *list) /* The list to extract from */ | ||
138 | { | ||
139 | LIST_NODE *ln; | ||
140 | |||
141 | if(list_empty(list)) /* Return NULL if the list is empty */ | ||
142 | { | ||
143 | return NULL; | ||
144 | } | ||
145 | |||
146 | ln = list_extract_node((LIST_NODE *)list->first); /* Get first node */ | ||
147 | |||
148 | list->num_nodes--; /* Decrement node counter */ | ||
149 | |||
150 | return ln; | ||
151 | } | ||
152 | |||
153 | /****************************************************************************** | ||
154 | ** FUNCTION: list_add_last | ||
155 | ** | ||
156 | ** DESCRIPTION: Add a LIST_NODE at the end of a LIST. | ||
157 | ** | ||
158 | ** RETURN: NULL if OK | ||
159 | ** 0 if list was full | ||
160 | ******************************************************************************/ | ||
161 | int list_add_last(LIST *list, /* The list to add to */ | ||
162 | LIST_NODE *ln) /* The node to add */ | ||
163 | { | ||
164 | if (NO_SIZE_CHECK != list->max_num_nodes) | ||
165 | { | ||
166 | if(list->num_nodes >= list->max_num_nodes) /* List full? */ | ||
167 | { | ||
168 | return 0; | ||
169 | } | ||
170 | } | ||
171 | list_insert_before((LIST_NODE *)&list->last_prev, ln); | ||
172 | list->num_nodes++; /* Increment node counter */ | ||
173 | return 1; | ||
174 | } | ||
175 | |||
176 | /****************************************************************************** | ||
177 | ** FUNCTION: list_extract_last | ||
178 | ** | ||
179 | ** DESCRIPTION: Extract a LIST_NODE from the end of a LIST. | ||
180 | ** | ||
181 | ** RETURN: The extracted LIST_NODE or NULL if the list is empty | ||
182 | ******************************************************************************/ | ||
183 | LIST_NODE *list_extract_last(LIST *list) /* The list to extract from */ | ||
184 | { | ||
185 | LIST_NODE *ln; | ||
186 | |||
187 | if(list_empty(list)) /* Return NULL if the list is empty */ | ||
188 | { | ||
189 | return NULL; | ||
190 | } | ||
191 | |||
192 | ln = list_extract_node((LIST_NODE *)list->last); | ||
193 | |||
194 | list->num_nodes--; /* Decrement node counter */ | ||
195 | |||
196 | return ln; /* Is NULL if the list is empty */ | ||
197 | } | ||
198 | |||
199 | /****************************************************************************** | ||
200 | ** FUNCTION: list_last_in_list | ||
201 | ** | ||
202 | ** DESCRIPTION: Check if a LIST_NODE is last in the list | ||
203 | ** | ||
204 | ** RETURN: 1 if last in list | ||
205 | ******************************************************************************/ | ||
206 | int list_last_in_list(LIST_NODE *ln) /* The node to check */ | ||
207 | { | ||
208 | return ln->next->next == NULL; | ||
209 | } | ||
210 | |||
211 | /***************************************************************************** | ||
212 | ** FUNCTION: list_first_in_list | ||
213 | ** | ||
214 | ** DESCRIPTION: Check if a LIST_NODE is first in the list | ||
215 | ** | ||
216 | ** RETURN: 1 if first in list | ||
217 | ******************************************************************************/ | ||
218 | int list_first_in_list(LIST_NODE *ln) /* The node to check */ | ||
219 | { | ||
220 | return ln->prev->prev == NULL; | ||
221 | } | ||
222 | |||
223 | /****************************************************************************** | ||
224 | ** FUNCTION: list_empty | ||
225 | ** | ||
226 | ** DESCRIPTION: Check if a LIST is empty | ||
227 | ** | ||
228 | ** RETURN: 1 if list is empty | ||
229 | ******************************************************************************/ | ||
230 | int list_empty(LIST *list) /* The list to check */ | ||
231 | { | ||
232 | return list->first == (LIST_NODE *)&list->last_prev; | ||
233 | } | ||
234 | |||
235 | /****************************************************************************** | ||
236 | ** FUNCTION: list_get_first | ||
237 | ** | ||
238 | ** DESCRIPTION: Return a LIST_NODE from the beginning of a LIST. | ||
239 | ** | ||
240 | ** RETURN: The first LIST_NODE or NULL if the list is empty | ||
241 | ******************************************************************************/ | ||
242 | LIST_NODE *list_get_first(LIST *lh) /* The list to read from */ | ||
243 | { | ||
244 | LIST_NODE *ln; | ||
245 | |||
246 | if(list_empty(lh)) /* Return NULL if the list is empty */ | ||
247 | { | ||
248 | return NULL; | ||
249 | } | ||
250 | |||
251 | return lh->first; /* Get first node */ | ||
252 | } | ||
253 | |||
254 | /****************************************************************************** | ||
255 | ** FUNCTION: list_get_last | ||
256 | ** | ||
257 | ** DESCRIPTION: Return a LIST_NODE from the end of a LIST. | ||
258 | ** | ||
259 | ** RETURN: The last LIST_NODE or NULL if the list is empty | ||
260 | ******************************************************************************/ | ||
261 | LIST_NODE *list_get_last(LIST *lh) /* The list to read from */ | ||
262 | { | ||
263 | LIST_NODE *ln; | ||
264 | |||
265 | if(list_empty(lh)) /* Return NULL if the list is empty */ | ||
266 | { | ||
267 | return NULL; | ||
268 | } | ||
269 | |||
270 | return lh->last; | ||
271 | } | ||
272 | |||
273 | /****************************************************************************** | ||
274 | ** FUNCTION: list_get_next | ||
275 | ** | ||
276 | ** DESCRIPTION: Return the LIST_NODE following the specified one. | ||
277 | ** | ||
278 | ** RETURN: Next LIST_NODE or NULL if the list ends here | ||
279 | *******************************************************************************/ | ||
280 | LIST_NODE *list_get_next(LIST_NODE *ln) /* The list node to get next from */ | ||
281 | { | ||
282 | if(list_last_in_list(ln)) /* Return NULL if this is the end of list */ | ||
283 | { | ||
284 | return NULL; | ||
285 | } | ||
286 | |||
287 | return ln->next; | ||
288 | } | ||
289 | |||
290 | /****************************************************************************** | ||
291 | ** FUNCTION: list_get_prev | ||
292 | ** | ||
293 | ** DESCRIPTION: Return the LIST_NODE preceding the specified one. | ||
294 | ** | ||
295 | ** RETURN: Previous LIST_NODE or NULL if the list ends here | ||
296 | *******************************************************************************/ | ||
297 | LIST_NODE *list_get_prev(LIST_NODE *ln) /* The list node to get previous from */ | ||
298 | { | ||
299 | if(list_first_in_list(ln)) /* Return NULL if this is the start of list */ | ||
300 | { | ||
301 | return NULL; | ||
302 | } | ||
303 | |||
304 | return ln->prev; | ||
305 | } | ||