summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Stenberg <daniel@haxx.se>2003-02-07 09:56:08 +0000
committerDaniel Stenberg <daniel@haxx.se>2003-02-07 09:56:08 +0000
commit70e59ede4e28a0972f0c4b3c2fab156ed186dd92 (patch)
treed3a3f64c2a6ecd7722733a8c83bf7530029c85ac
parentbd654cdfbc0fd619ff41e4fc4ee1c2e48e7a910d (diff)
downloadrockbox-70e59ede4e28a0972f0c4b3c2fab156ed186dd92.tar.gz
rockbox-70e59ede4e28a0972f0c4b3c2fab156ed186dd92.zip
not used, removed
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@3218 a1c6a512-1295-4272-9138-f99709370657
Diffstat
-rw-r--r--firmware/common/lists.c301
-rw-r--r--firmware/common/lists.h359
2 files changed, 0 insertions, 660 deletions
diff --git a/firmware/common/lists.c b/firmware/common/lists.c
deleted file mode 100644
index 0699531e20..0000000000
--- a/firmware/common/lists.c
+++ /dev/null
@@ -1,301 +0,0 @@
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******************************************************************************/
51void 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******************************************************************************/
68void 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*****************************************************************************/
84void 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*****************************************************************************/
100LIST_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******************************************************************************/
115int 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******************************************************************************/
137LIST_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******************************************************************************/
161int 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******************************************************************************/
183LIST_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******************************************************************************/
206int 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******************************************************************************/
218int 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******************************************************************************/
230int 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******************************************************************************/
242LIST_NODE *list_get_first(LIST *lh) /* The list to read from */
243{
244 if(list_empty(lh)) /* Return NULL if the list is empty */
245 {
246 return NULL;
247 }
248
249 return lh->first; /* Get first node */
250}
251
252/******************************************************************************
253** FUNCTION: list_get_last
254**
255** DESCRIPTION: Return a LIST_NODE from the end of a LIST.
256**
257** RETURN: The last LIST_NODE or NULL if the list is empty
258******************************************************************************/
259LIST_NODE *list_get_last(LIST *lh) /* The list to read from */
260{
261 if(list_empty(lh)) /* Return NULL if the list is empty */
262 {
263 return NULL;
264 }
265
266 return lh->last;
267}
268
269/******************************************************************************
270** FUNCTION: list_get_next
271**
272** DESCRIPTION: Return the LIST_NODE following the specified one.
273**
274** RETURN: Next LIST_NODE or NULL if the list ends here
275*******************************************************************************/
276LIST_NODE *list_get_next(LIST_NODE *ln) /* The list node to get next from */
277{
278 if(list_last_in_list(ln)) /* Return NULL if this is the end of list */
279 {
280 return NULL;
281 }
282
283 return ln->next;
284}
285
286/******************************************************************************
287** FUNCTION: list_get_prev
288**
289** DESCRIPTION: Return the LIST_NODE preceding the specified one.
290**
291** RETURN: Previous LIST_NODE or NULL if the list ends here
292*******************************************************************************/
293LIST_NODE *list_get_prev(LIST_NODE *ln) /* The list node to get previous from */
294{
295 if(list_first_in_list(ln)) /* Return NULL if this is the start of list */
296 {
297 return NULL;
298 }
299
300 return ln->prev;
301}
diff --git a/firmware/common/lists.h b/firmware/common/lists.h
deleted file mode 100644
index 9237bceeb7..0000000000
--- a/firmware/common/lists.h
+++ /dev/null
@@ -1,359 +0,0 @@
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
132typedef 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
143typedef 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
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*/
168void list_init(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*/
186void 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*/
204void 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*/
222LIST_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*/
238int 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*/
252LIST_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*/
268int 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*/
281LIST_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*/
294int 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*/
307int 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*/
321int 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******************************************************************************/
330LIST_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******************************************************************************/
339LIST_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*******************************************************************************/
348LIST_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*******************************************************************************/
357LIST_NODE *list_get_prev(LIST_NODE *ln); /* The list node to get previous from */
358
359#endif /* LISTS_INCLUDED */
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-17 22:50:49 +0000