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.h | |
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.h')
-rw-r--r-- | firmware/common/lists.h | 359 |
1 files changed, 359 insertions, 0 deletions
diff --git a/firmware/common/lists.h b/firmware/common/lists.h new file mode 100644 index 0000000000..d9713b6a15 --- /dev/null +++ b/firmware/common/lists.h | |||
@@ -0,0 +1,359 @@ | |||
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 | #ifndef LISTS_INCLUDED | ||
20 | #define LISTS_INCLUDED | ||
21 | /* | ||
22 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | ||
23 | * DESCRIPTION * | ||
24 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | ||
25 | |||
26 | Functions for handling of a double linked list (code in lists.c): | ||
27 | |||
28 | list_init - Initiate a LIST structure | ||
29 | list_insert_before - Insert a node in a list before another node | ||
30 | list_insert_after - Insert a node in a list after another node | ||
31 | list_extract - Extract a node from a list | ||
32 | list_extract_first - Extract a node from the beginning of a list | ||
33 | list_extract_last - Extract a node from the end of a list | ||
34 | list_add_first - Add a node at the beginning of a list | ||
35 | list_add_last - Add a node at the end of a list | ||
36 | list_last_in_list - Check if a node is last in the list | ||
37 | list_first_in_list - Check if a node is first in the list | ||
38 | list_empty - Check if a list is empty | ||
39 | list_get_first - Returns the first node in the list | ||
40 | list_get_last - Returns the last node in the list | ||
41 | list_get_next - Returns the next node | ||
42 | list_get_prev - Returns the previous node | ||
43 | |||
44 | General about the list functions: | ||
45 | |||
46 | This package contains two structs and a set of functions implementing a | ||
47 | double linked list. When using a list with these, add nodes with | ||
48 | list_add_first or list_add_last and extract nodes with list_extract_first or list_extract_last. | ||
49 | |||
50 | A FIFO queue can be implemented using list_add_last to insert | ||
51 | nodes at the end and list_extract_first to extract nodes at the beginning | ||
52 | of the list. | ||
53 | |||
54 | When using the list-functions you need one instance of the type LIST | ||
55 | (contains the start pointer etc), You also need to call InitList once. | ||
56 | When calling InitList you decide if the list shall have a max size, | ||
57 | and if so how big it will be. | ||
58 | |||
59 | NOTE! when using list_insert_before, list_insert_after and | ||
60 | list_extract the num_nodes field in the LIST struct will not be updated. | ||
61 | |||
62 | To use the list-functions you define a struct with LIST_NODE as one member. | ||
63 | When a LIST_NODE is extracted from the list the address of the LIST_NODE | ||
64 | is returned. If the LIST_NODE field is not the first field in your struct, | ||
65 | you must subtract the returned address with the size of the field that is | ||
66 | before LIST_NODE in your struct to get the start address of your struct. | ||
67 | |||
68 | For example: Consider you want to use the list-functions to implement a FIFO | ||
69 | queue for the test_list_sig signal, using the OSE operating system. | ||
70 | |||
71 | You may declare your signal struct something like: | ||
72 | |||
73 | typedef struct | ||
74 | { | ||
75 | SIGSELECT sig_no; | ||
76 | LIST_NODE list_node; | ||
77 | . | ||
78 | . | ||
79 | } TEST_LIST_STRUCT; | ||
80 | |||
81 | In your code you may have: | ||
82 | |||
83 | LIST test_list; | ||
84 | TEST_LIST_STRUCT *list_sig; | ||
85 | LIST_NODE *ln; | ||
86 | |||
87 | list_init_list(&test_list, MAX_NODES_IN_LIST); | ||
88 | |||
89 | for(;;) | ||
90 | { | ||
91 | sig = receive(all); | ||
92 | switch(sig->sig_no) | ||
93 | { | ||
94 | case TEST_ADD: | ||
95 | if (list_add_first(&test_list, &sig->list_node)) | ||
96 | { | ||
97 | * The list was full * | ||
98 | * Handle the returned sig * | ||
99 | } | ||
100 | |||
101 | case TEST_REM: | ||
102 | if (ln = list_extract_last(&test_list)) | ||
103 | { | ||
104 | list_sig = (TEST_LIST_STRUCT *)((char)ln - sizeof(SIGSELECT)); | ||
105 | * Continue ... * | ||
106 | } | ||
107 | else | ||
108 | { | ||
109 | * handle empty list * | ||
110 | |||
111 | */ | ||
112 | |||
113 | /*-------------------------------------------------------------------- | ||
114 | List handling definitions | ||
115 | ----------------------------------------------------------------------*/ | ||
116 | |||
117 | /* Used as input parameter to list_init_list */ | ||
118 | #define NO_SIZE_CHECK 0 | ||
119 | |||
120 | #ifndef NULL | ||
121 | #define NULL ((void *)0) | ||
122 | #endif | ||
123 | |||
124 | |||
125 | /*********************************************************************** | ||
126 | ** Type definitions | ||
127 | ** | ||
128 | ** The LIST_NODE, and LIST types are used by the LIST class in common drv | ||
129 | ************************************************************************/ | ||
130 | |||
131 | |||
132 | typedef struct list_node | ||
133 | { | ||
134 | /*** NOTE! The next and prev fields | ||
135 | are never NULL within a LIST. | ||
136 | Use list_first_in_list and | ||
137 | list_last_in_list to check if a node | ||
138 | is first or last in the list ***/ | ||
139 | struct list_node *next; /* Successor node */ | ||
140 | struct list_node *prev; /* Predessor node */ | ||
141 | } LIST_NODE; | ||
142 | |||
143 | typedef struct | ||
144 | { | ||
145 | /* The three list node fields are | ||
146 | used for internal represenation | ||
147 | of the list. */ | ||
148 | LIST_NODE *first; /* First node in list */ | ||
149 | LIST_NODE *last_prev; /* Always NULL */ | ||
150 | LIST_NODE *last; /* Last node in list */ | ||
151 | int num_nodes; /* Number of nodes in list */ | ||
152 | int max_num_nodes; /* Max number of nodes in list */ | ||
153 | } LIST; | ||
154 | |||
155 | |||
156 | /****************************************************************************** | ||
157 | ** | ||
158 | ** FUNCTION: list_init_list | ||
159 | ** | ||
160 | ** DESCRIPTION: Initiate a LIST structure. | ||
161 | ** | ||
162 | ** INPUT: The LIST to be initiated | ||
163 | ** | ||
164 | ** Max nr of elements in the list, or NO_SIZE_CHECK if | ||
165 | ** list may be of any size | ||
166 | ******************************************************************************* | ||
167 | */ | ||
168 | void list_init_list(LIST *list, /* The list to initiate */ | ||
169 | int max_num_nodes); /* Maximum number of nodes */ | ||
170 | |||
171 | /****************************************************************************** | ||
172 | ** | ||
173 | ** FUNCTION: list_insert_before | ||
174 | ** | ||
175 | ** DESCRIPTION: Insert a LIST_NODE before another LIST_NODE in a LIST. | ||
176 | ** | ||
177 | ** INPUT: The reference LIST_NODE | ||
178 | ** | ||
179 | ** The LIST_NODE to be inserted | ||
180 | ** | ||
181 | ** OBSERVE: When using list_insert_before, list_insert_after | ||
182 | ** and list_extract the nume_nodes field in the LIST struct | ||
183 | ** will not be updated. | ||
184 | ****************************************************************************** | ||
185 | */ | ||
186 | void list_insert_before(LIST_NODE *ref, /* The reference node */ | ||
187 | LIST_NODE *ln); /* The node to insert */ | ||
188 | |||
189 | /***************************************************************************** | ||
190 | ** | ||
191 | ** FUNCTION: list_insert_after | ||
192 | ** | ||
193 | ** DESCRIPTION: Insert a LIST_NODE after another LIST_NODE in a LIST. | ||
194 | ** | ||
195 | ** INPUT: The reference LIST_NODE | ||
196 | ** | ||
197 | ** The LIST_NODE to be inserted | ||
198 | ** | ||
199 | ** OBSERVE: When using list_insert_before, list_insert_after | ||
200 | ** and list_extract the num_nodes field in the LIST struct | ||
201 | ** will not be updated. | ||
202 | ******************************************************************************* | ||
203 | */ | ||
204 | void list_insert_after(LIST_NODE *ref, /* The reference node */ | ||
205 | LIST_NODE *ln); /* The node to insert */ | ||
206 | |||
207 | /****************************************************************************** | ||
208 | ** | ||
209 | ** FUNCTION: list_extract | ||
210 | ** | ||
211 | ** DESCRIPTION: Extract a LIST_NODE from a LIST. | ||
212 | ** | ||
213 | ** INPUT: The LIST_NODE to be removed. | ||
214 | ** | ||
215 | ** RETURN: The same LIST_NODE pointer that was passed as a parameter | ||
216 | ** | ||
217 | ** OBSERVE: When using list_insert_before, list_insert_after | ||
218 | ** and list_extract the num_nodes field in the LIST struct | ||
219 | ** will not be updated. | ||
220 | ******************************************************************************* | ||
221 | */ | ||
222 | LIST_NODE *list_extract(LIST_NODE *ln); /* The node to extract */ | ||
223 | |||
224 | /****************************************************************************** | ||
225 | ** | ||
226 | ** FUNCTION: list_add_first | ||
227 | ** | ||
228 | ** DESCRIPTION: Add a LIST_NODE at the beginning of a LIST. | ||
229 | ** | ||
230 | ** INPUT: The LIST | ||
231 | ** | ||
232 | ** The LIST_NODE | ||
233 | ** | ||
234 | ** RETURN: TRUE if OK | ||
235 | ** FALSE if list is full | ||
236 | ******************************************************************************* | ||
237 | */ | ||
238 | int list_add_first(LIST *list, /* The list to add to */ | ||
239 | LIST_NODE *ln); /* The node to add */ | ||
240 | |||
241 | /****************************************************************************** | ||
242 | ** | ||
243 | ** FUNCTION: list_extract_first | ||
244 | ** | ||
245 | ** DESCRIPTION: Extract a LIST_NODE from the beginning of a LIST. | ||
246 | ** | ||
247 | ** INPUT: The LIST from where a node is to be removed. | ||
248 | ** | ||
249 | ** RETURN: The extracted LIST_NODE or NULL if the list is empty | ||
250 | ******************************************************************************* | ||
251 | */ | ||
252 | LIST_NODE *list_extract_first(LIST *list); /* The list to extract from */ | ||
253 | |||
254 | /****************************************************************************** | ||
255 | ** | ||
256 | ** FUNCTION: list_add_last | ||
257 | ** | ||
258 | ** DESCRIPTION: Add a LIST_NODE at the end of a LIST. | ||
259 | ** | ||
260 | ** INPUT: The LIST | ||
261 | ** | ||
262 | ** The LIST_NODE | ||
263 | ** | ||
264 | ** RETURN: TRUE if OK | ||
265 | ** FALSE if list is full | ||
266 | ******************************************************************************* | ||
267 | */ | ||
268 | int list_add_last(LIST *list, /* The list to add to */ | ||
269 | LIST_NODE *ln); /* The node to add */ | ||
270 | /****************************************************************************** | ||
271 | ** | ||
272 | ** FUNCTION: list_extract_last | ||
273 | ** | ||
274 | ** DESCRIPTION: Extract a LIST_NODE from the end of a LIST. | ||
275 | ** | ||
276 | ** INPUT: The LIST from where a node is to be removed. | ||
277 | ** | ||
278 | ** RETURN: The extracted LIST_NODE or NULL if the list is empty | ||
279 | ******************************************************************************* | ||
280 | */ | ||
281 | LIST_NODE *list_extract_last(LIST *list); /* The list to extract from */ | ||
282 | |||
283 | /****************************************************************************** | ||
284 | ** | ||
285 | ** FUNCTION: list_last_in_list | ||
286 | ** | ||
287 | ** DESCRIPTION: Check if a LIST_NODE is at the end of the list | ||
288 | ** | ||
289 | ** INPUT: The LIST_NODE to check | ||
290 | ** | ||
291 | ** RETURN: TRUE if LIST_NODE is last in the list, else FALSE. | ||
292 | ******************************************************************************* | ||
293 | */ | ||
294 | int list_last_in_list(LIST_NODE *ln); /* The node to check */ | ||
295 | |||
296 | /****************************************************************************** | ||
297 | ** | ||
298 | ** FUNCTION: list_first_in_list | ||
299 | ** | ||
300 | ** DESCRIPTION: Check if a LIST_NODE is first in the list | ||
301 | ** | ||
302 | ** INPUT: The LIST_NODE to check | ||
303 | ** | ||
304 | ** RETURN: TRUE if LIST_NODE is first in the list, else FALSE. | ||
305 | ******************************************************************************* | ||
306 | */ | ||
307 | int list_first_in_list(LIST_NODE *ln); /* The node to check */ | ||
308 | |||
309 | /****************************************************************************** | ||
310 | ** | ||
311 | ** FUNCTION: list_list_empty | ||
312 | ** | ||
313 | ** DESCRIPTION: Check if a LIST is empty | ||
314 | ** | ||
315 | ** INPUT: The LIST to check | ||
316 | ** | ||
317 | ** RETURN: TRUE if LIST is empty, else FALSE. | ||
318 | ** | ||
319 | ******************************************************************************* | ||
320 | */ | ||
321 | int list_empty(LIST *list); /* The list to check */ | ||
322 | |||
323 | /****************************************************************************** | ||
324 | ** FUNCTION: list_get_first | ||
325 | ** | ||
326 | ** DESCRIPTION: Return a LIST_NODE from the beginning of a LIST. | ||
327 | ** | ||
328 | ** RETURN: The first LIST_NODE or NULL if the list is empty | ||
329 | ******************************************************************************/ | ||
330 | LIST_NODE *list_get_first(LIST *lh); /* The list to read from */ | ||
331 | |||
332 | /****************************************************************************** | ||
333 | ** FUNCTION: list_get_last | ||
334 | ** | ||
335 | ** DESCRIPTION: Return a LIST_NODE from the end of a LIST. | ||
336 | ** | ||
337 | ** RETURN: The last LIST_NODE or NULL if the list is empty | ||
338 | ******************************************************************************/ | ||
339 | LIST_NODE *list_get_last(LIST *lh); /* The list to read from */ | ||
340 | |||
341 | /****************************************************************************** | ||
342 | ** FUNCTION: list_get_next | ||
343 | ** | ||
344 | ** DESCRIPTION: Return the LIST_NODE following the specified one. | ||
345 | ** | ||
346 | ** RETURN: Next LIST_NODE or NULL if the list ends here | ||
347 | *******************************************************************************/ | ||
348 | LIST_NODE *list_get_next(LIST_NODE *ln); /* The list node to get next from */ | ||
349 | |||
350 | /****************************************************************************** | ||
351 | ** FUNCTION: list_get_prev | ||
352 | ** | ||
353 | ** DESCRIPTION: Return the LIST_NODE preceding the specified one. | ||
354 | ** | ||
355 | ** RETURN: Previous LIST_NODE or NULL if the list ends here | ||
356 | *******************************************************************************/ | ||
357 | LIST_NODE *list_get_prev(LIST_NODE *ln); /* The list node to get previous from */ | ||
358 | |||
359 | #endif /* LISTS_INCLUDED */ | ||