1 /***************************************************************************
2 list.c - description
3 -------------------
4 begin : Sun Sep 2 2001
5 copyright : (C) 2001 by Michael Speck
6 email : kulkanie@gmx.net
7 ***************************************************************************/
8
9 /***************************************************************************
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 ***************************************************************************/
17
18 #include <stdlib.h>
19
20 #include "list.h"
21
22 /*
23 ====================================================================
24 Create a new list
25 auto_delete: Free memory of data pointer when deleting entry
26 callback: Use this callback to free memory of data including
27 the data pointer itself.
28 Return Value: List pointer
29 ====================================================================
30 */
list_create(int auto_delete,void (* callback)(void *))31 List *list_create( int auto_delete, void (*callback)(void*) )
32 {
33 List *list = calloc( 1, sizeof( List ) );
34 list->head = calloc( 1, sizeof( ListEntry ) );
35 list->tail = calloc( 1, sizeof( ListEntry ) );
36 list->head->next = list->tail;
37 list->head->prev = list->head;
38 list->tail->next = list->tail;
39 list->tail->prev = list->head;
40 list->auto_delete = auto_delete;
41 list->callback = callback;
42 list->cur_entry = list->head;
43 return list;
44 }
45 /*
46 ====================================================================
47 Delete list and entries.
48 ====================================================================
49 */
list_delete(List * list)50 void list_delete( List *list )
51 {
52 list_clear( list );
53 free( list->head );
54 free( list->tail );
55 free( list );
56 }
57 /*
58 ====================================================================
59 Delete all entries but keep the list. Reset current_entry to head
60 pointer.
61 ====================================================================
62 */
list_clear(List * list)63 void list_clear( List *list )
64 {
65 while( !list_empty( list ) ) list_delete_pos( list, 0 );
66 }
67 /*
68 ====================================================================
69 Insert new item at position.
70 Return Value: True if successful else False.
71 ====================================================================
72 */
list_insert(List * list,void * item,int pos)73 int list_insert( List *list, void *item, int pos )
74 {
75 int i;
76 ListEntry *cur = list->head;
77 ListEntry *new_entry = 0;
78
79 /* check if insertion possible */
80 if ( pos < 0 || pos > list->count ) return 0;
81 if ( item == 0 ) return 0;
82 /* get to previous entry */
83 for (i = 0; i < pos; i++) cur = cur->next;
84 /* create and anchor new entry */
85 new_entry = calloc( 1, sizeof( ListEntry ) );
86 new_entry->item = item;
87 new_entry->next = cur->next;
88 new_entry->prev = cur;
89 cur->next->prev = new_entry;
90 cur->next = new_entry;
91 list->count++;
92 return 1;
93 }
94 /*
95 ====================================================================
96 Add new item at the end of the list.
97 ====================================================================
98 */
list_add(List * list,void * item)99 int list_add( List *list, void *item )
100 {
101 ListEntry *new_entry = 0;
102 /* check if insertion possible */
103 if ( item == 0 ) return 0;
104 /* create and anchor new entry */
105 new_entry = calloc( 1, sizeof( ListEntry ) );
106 new_entry->item = item;
107 new_entry->next = list->tail;
108 new_entry->prev = list->tail->prev;
109 list->tail->prev->next = new_entry;
110 list->tail->prev = new_entry;
111 list->count++;
112 return 1;
113 }
114 /*
115 ====================================================================
116 Delete item at position. If this was the current entry update
117 current_entry to valid previous pointer.
118 Return Value: True if successful else False.
119 ====================================================================
120 */
list_delete_pos(List * list,int pos)121 int list_delete_pos( List *list, int pos )
122 {
123 int i;
124 ListEntry *cur = list->head;
125
126 /* check if deletion possbile */
127 if ( list_empty( list ) ) return 0;
128 if ( pos < 0 || pos >= list->count ) return 0;
129 /* get to correct entry */
130 for ( i = 0; i <= pos; i++ ) cur = cur->next;
131 /* modify anchors */
132 cur->next->prev = cur->prev;
133 cur->prev->next = cur->next;
134 /* decrease counter */
135 list->count--;
136 /* check current_entry */
137 if ( list->cur_entry == cur )
138 list->cur_entry = list->cur_entry->prev;
139 /* free memory */
140 if ( list->auto_delete ) {
141 if ( list->callback )
142 (list->callback)( cur->item );
143 else
144 free( cur->item );
145 }
146 free( cur );
147 return 1;
148 }
149 /*
150 ====================================================================
151 Delete item if in list. If this was the current entry update
152 current_entry to valid previous pointer.
153 Return Value: True if successful else False.
154 ====================================================================
155 */
list_delete_item(List * list,void * item)156 int list_delete_item( List *list, void *item )
157 {
158 return list_delete_pos( list, list_check( list, item ) );
159 }
160 /*
161 ====================================================================
162 Delete entry.
163 Return Value: True if successful else False.
164 ====================================================================
165 */
list_delete_entry(List * list,ListEntry * entry)166 int list_delete_entry( List *list, ListEntry *entry )
167 {
168 /* delete possible? */
169 if ( entry == 0 ) return 0;
170 if ( list->count == 0 ) return 0;
171 if ( entry == list->head || entry == list->tail ) return 0;
172 /* adjust anchor and counter */
173 entry->prev->next = entry->next;
174 entry->next->prev = entry->prev;
175 list->count--;
176 /* check current_entry */
177 if ( list->cur_entry == entry )
178 list->cur_entry = list->cur_entry->prev;
179 /* free memory */
180 if ( list->auto_delete ) {
181 if ( list->callback )
182 (list->callback)( entry->item );
183 else
184 free( entry->item );
185 }
186 free( entry );
187 return 1;
188 }
189 /*
190 ====================================================================
191 Get item from position if in list.
192 Return Value: Item pointer if found else Null pointer.
193 ====================================================================
194 */
list_get(List * list,int pos)195 void* list_get( List *list, int pos )
196 {
197 int i;
198 ListEntry *cur = list->head;
199
200 if ( pos < 0 || pos >= list->count ) return 0;
201 for ( i = 0; i <= pos; i++ ) cur = cur->next;
202 return cur->item;
203 }
204 /*
205 ====================================================================
206 Check if item's in list.
207 Return Value: Position of item else -1.
208 ====================================================================
209 */
list_check(List * list,void * item)210 int list_check( List *list, void *item )
211 {
212 int pos = -1;
213 ListEntry *cur = list->head->next;
214 while ( cur != list->tail ) {
215 pos++;
216 if ( cur->item == item ) break;
217 cur = cur->next;
218 }
219 if ( cur == list->tail ) pos = -1; /* item not found */
220 return pos;
221 }
222 /*
223 ====================================================================
224 Return first item stored in list and set current_entry to this
225 entry.
226 Return Value: Item pointer if found else Null pointer.
227 ====================================================================
228 */
list_first(List * list)229 void* list_first( List *list )
230 {
231 list->cur_entry = list->head->next;
232 return list->head->next->item;
233 }
234 /*
235 ====================================================================
236 Return last item stored in list and set current_entry to this
237 entry.
238 Return Value: Item pointer if found else Null pointer.
239 ====================================================================
240 */
list_last(List * list)241 void* list_last( List *list )
242 {
243 list->cur_entry = list->tail->prev;
244 return list->tail->prev->item;
245 }
246 /*
247 ====================================================================
248 Return item in current_entry.
249 Return Value: Item pointer if found else Null pointer.
250 ====================================================================
251 */
list_current(List * list)252 void* list_current( List *list )
253 {
254 return list->cur_entry->item;
255 }
256 /*
257 ====================================================================
258 Reset current_entry to head of list.
259 ====================================================================
260 */
list_reset(List * list)261 void list_reset( List *list )
262 {
263 list->cur_entry = list->head;
264 }
265 /*
266 ====================================================================
267 Get next item and update current_entry (reset if tail reached)
268 Return Value: Item pointer if found else Null (if tail of list).
269 ====================================================================
270 */
list_next(List * list)271 void* list_next( List *list )
272 {
273 list->cur_entry = list->cur_entry->next;
274 if ( list->cur_entry == list->tail ) list_reset( list );
275 return list->cur_entry->item;
276 }
277 /*
278 ====================================================================
279 Get previous item and update current_entry.
280 Return Value: Item pointer if found else Null (if head of list).
281 ====================================================================
282 */
list_prev(List * list)283 void* list_prev( List *list )
284 {
285 list->cur_entry = list->cur_entry->prev;
286 return list->cur_entry->item;
287 }
288 /*
289 ====================================================================
290 Delete the current entry if not tail or head. This is the entry
291 that contains the last returned item by list_next/prev().
292 Return Value: True if it was a valid deleteable entry.
293 ====================================================================
294 */
list_delete_current(List * list)295 int list_delete_current( List *list )
296 {
297 if ( list->cur_entry == 0 || list->cur_entry == list->head || list->cur_entry == list->tail ) return 0;
298 list_delete_entry( list, list->cur_entry );
299 return 1;
300 }
301 /*
302 ====================================================================
303 Check if list is empty.
304 Return Value: True if list counter is 0 else False.
305 ====================================================================
306 */
list_empty(List * list)307 int list_empty( List *list )
308 {
309 return list->count == 0;
310 }
311 /*
312 ====================================================================
313 Return entry containing the passed item.
314 Return Value: True if entry found else False.
315 ====================================================================
316 */
list_entry(List * list,void * item)317 ListEntry *list_entry( List *list, void *item )
318 {
319 ListEntry *entry = list->head->next;
320 while ( entry != list->tail ) {
321 if ( entry->item == item ) return entry;
322 entry = entry->next;
323 }
324 return 0;
325 }
326 /*
327 ====================================================================
328 Transfer an entry from one list to another list by removing from
329 'source' and adding to 'dest' thus if source does not contain
330 the item this is equvalent to list_add( dest, item ).
331 ====================================================================
332 */
list_transfer(List * source,List * dest,void * item)333 void list_transfer( List *source, List *dest, void *item )
334 {
335 int old_auto_flag;
336 /* add to destination */
337 list_add( dest, item );
338 /* as the pointer is added to dest without changes only the empty
339 entry must be deleted in source */
340 old_auto_flag = source->auto_delete;
341 source->auto_delete = LIST_NO_AUTO_DELETE;
342 list_delete_item( source, item );
343 source->auto_delete = old_auto_flag;
344 }
345 /*
346 ====================================================================
347 Deqeue the first list entry. (must not use auto_delete therefore)
348 ====================================================================
349 */
list_dequeue(List * list)350 void *list_dequeue( List *list )
351 {
352 void *item;
353 if ( list->count > 0 ) {
354 item = list->head->next->item;
355 list_delete_pos( list, 0 );
356 return item;
357 }
358 else
359 return 0;
360 }
361