Download: list.h list.c
list.h
1: /*
2: * Basic list library
3: *
4: * Copyright 2001-2009 Nicolas Bernard <http://www.lafraze.net/nbernard/>
5: * All rights reserved.
6: *
7: * Permission to use, copy, modify, and distribute this software for any
8: * purpose with or without fee is hereby granted, provided that the above
9: * copyright notice and this permission notice appear in all copies.
10: *
11: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18: *
19: */
20:
21: #ifndef _NB_LISTS_
22: #define _NB_LISTS_
23:
24: #ifdef _REENTRANT
25: #include <pthread.h>
26: #endif /* _REENTRANT */
27: /* beware: reentrant part not tested ! */
28:
29: #define MAXLIST 1024
30: /* this is the maximum number of list you can have in an application. You can
31: change it (remember to recompile list.c then), but if doing so remember that
32: it is a signed int (don't put a too big value, nor a value <= 0). */
33:
34: typedef /*@abstract@*/ /*@mutable@*/ int list_t;
35: /* you can think that a list_t is a "list descriptor", in the same way you have
36: file descriptors. */
37:
38: typedef enum {
39: NO_ERROR, /* = 0; success */
40: ERR_NO_SUCH_POS, /* 1 returned if the nth elt has been asked but
41: doesn't exist */
42: NO_FOUND, /* 2 research failed: elt not found */
43: MUTEX_ERROR_LOCK, /* 3 problem with a mutex during locking (only if
44: compiled with -D_REENTRANT) */
45: MUTEX_ERROR_UNLOCK, /* 4 problem with a mutex during unlocking (only
46: if compiled with -D_REENTRANT) */
47: MUTEX_ERROR_OTHER, /* 5 problem with a mutex (only if compiled
48: with -D_REENTRANT) */
49: MAX_LIST_REACHED, /* 6 list creation failed because there is already
50: MAXLIST lists */
51: NO_SUCH_LIST, /* 7 there is no list associated with the list_t
52: used */
53: NO_MEM, /* 8 operation failed: not enough memory */
54: NOT_IMPLEMENTED, /* 9 not implemented yet! */
55: BAD_PARAMETERS, /* 10 parameters given are incorrect */
56: IO_ERROR, /* 11 error while reading or writing */
57: INTERNAL_ERROR, /* 12 internal incoherency detected */
58: } list_error;
59: /* list_error is a type which describe the error that can happen. A function
60: which return a list_error is usually not able to return any list_error,
61: but only some specific ones. */
62:
63:
64:
65: list_t list_create(void);
66: /* create a list and returns a list descriptor or (list_t) -1 if an error
67: occured. */
68:
69: list_error list_delete(list_t);
70: /* destroy a list (free each of its element then the list structure).
71: request to delete a non-existing list are silently ignored.
72:
73: Beware: list_delete do a free of each element of the list. It may cause
74: crash if some of those element were freed elsewere by the application, or
75: memory leaks if elements contain pointer to allocated memory which is not
76: referenced elsewere. */
77:
78:
79:
80: int list_size(list_t);
81: /* returns the number of elements in the list passed as parameter.*/
82:
83:
84:
85: list_error list_add_head(list_t, void* data);
86: /* add an element at the head of the list.
87: [Complexity: O(1)] */
88:
89: list_error list_add_tail(list_t, void* data);
90: /* add an element at the end of the list
91: [Complexity: O(1)] */
92:
93: list_error list_add_at_pos(list_t, unsigned int pos, void* data);
94: /* add an element _before_ the posth element. the index begins at 0.
95: [Complexity: O(pos), O(1) if pos == 0 or pos == nb_of_elt] */
96:
97: list_error list_del_head(list_t);
98: /* remove the head of the list.
99: Beware: the content is freed. cf. list_delete's beware.
100: [Complexity: O(1)] */
101:
102: list_error list_del_tail(list_t);
103: /* remove the tail of the list
104: Beware: the content is freed. cf. list_delete's beware.
105: if the element must not be freed, you can use list_pop instead.
106: [Complexity: O(1)]*/
107:
108: list_error list_remove_tail(list_t);
109:
110: list_error list_del_at_pos(list_t, unsigned int pos);
111: /* remove the posth element. The index begins at 0.
112: Beware: the content is freed. cf. list_delete's beware.
113: [Complexity: O(pos), O(1) if pos == 0 or pos == nb_of_elt] */
114:
115: list_error list_remove_at_pos(list_t l, unsigned int pos);
116:
117: /*@null@*/ void* list_get_at_pos(list_t, unsigned int pos);
118: /* returns the element at pos. Index starts at 0.
119: if the list doesn't exist, or doesn't has at least pos + 1 elements, NULL
120: is returned.
121: */
122:
123: /*@null@*/ void* list_get_head(list_t L);
124: /*@null@*/ void* list_get_tail(list_t L);
125:
126: #define list_push(l, x) list_add_tail(l, x)
127: /* lists can be used as stack. newest elements are at the tail. This function
128: pushes on the stack. */
129:
130: /*@null@*/ void* list_pop(list_t);
131: /* lists can be used as stack. newest elements are at the tail. This function
132: pops from the stack. */
133:
134:
135:
136: list_error list_search(list_t, void*, int ((void*,void*)), unsigned int*);
137: /* given a list descriptor, content (the same kind that you store in the list),
138: a comparison function returning a true value if two elements it takes as
139: parameters are equal and false (0) otherwise, and a pointer on an unsigned
140: int, this function will store the position of the first matching element in
141: this last pointer. It will returns NO_FOUND if there is no match in the
142: whole list. nb: the second arg of this function is passed as the second
143: arg of the comparison function. */
144:
145:
146:
147:
148: /********** Current position ************************************************
149: * Each list has a current pointer which can be used to remember a position *
150: * in a list, or to accelerate iterations on big lists *
151: ****************************************************************************
152:
153: A typical use could be such code, which iterate through a list in 0(n):
154:
155: elt = list_current_reset(l);
156: if (elt != NULL) do {
157: ...
158: } while ((elt = list_next(l)) != NULL);
159:
160:
161: a variant is:
162:
163: for (elt = list_current_reset(l);
164: elt != NULL;
165: elt = list_next(l)) {
166: ...
167: }
168:
169: *****************************************************************************/
170:
171: void* list_current_reset(list_t L);
172: /* put current at the beginning and return the first element */
173:
174: list_error list_current_setpos(list_t L, unsigned int position);
175: /* put current on an arbitrary position (first elt is at pos 0 */
176: unsigned int list_current_getpos(list_t L);
177: /* put current on an arbitrary position (first elt is at pos 0 */
178:
179: list_error list_current_del(list_t L);
180: /* delete the current element. Current then points on the element which was
181: following the deleted one. */
182:
183: list_error list_current_remove(list_t L);
184: /* remove the current element. Current then points on the element which was
185: following the deleted one. The element is no more in the list but is not
186: freed */
187:
188: void* list_next(list_t L);
189: /* set and return current = next */
190:
191: void* list_previous(list_t L);
192: /* set and return current = prev */
193:
194: void* list_current(list_t L);
195: /* return current */
196:
197: #ifndef NDEBUG
198: #include <stdio.h>
199: void list_stat(FILE* f); /* stdio.h needed */
200: #endif
201:
202: #ifdef WITH_DATALOC
203:
204: #include "dataloc.h"
205: list_error list_pack(list_t L, struct dataloc* loc, int eltsize, int (*cbeltwrite)(struct dataloc* loc, const void* elt));
206: list_t list_unpack(struct dataloc* loc, list_error *e, int eltsize, int (*cbeltwrite)(struct dataloc* loc, void** elt));
207:
208: #endif /* WITH_DATALOC */
209:
210: #endif /* _NB_LISTS_ */
list.c
1: /*
2: * Basic list library
3: *
4: * Copyright 2001-2009 Nicolas Bernard <http://www.lafraze.net/nbernard/>
5: * All rights reserved.
6: *
7: * Permission to use, copy, modify, and distribute this software for any
8: * purpose with or without fee is hereby granted, provided that the above
9: * copyright notice and this permission notice appear in all copies.
10: *
11: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18: *
19: */
20:
21: /**\bug _reeentrant code is untested and buggy */
22:
23: #include <assert.h>
24: #include <stdlib.h>
25: #include <stdio.h>
26: #include <stdbool.h>
27: #include <string.h>
28:
29: #include "list.h"
30:
31: struct link {
32: struct link* prev;
33: void* data;
34: struct link* next;
35: };
36:
37: typedef struct {
38: /*@null@*/ struct link* first;
39: /*@null@*/ struct link* last;
40: /*@null@*/ struct link* lcurrent;
41: unsigned int currentpos;
42: #ifdef _REENTRANT
43: pthread_mutex_t list_lock;
44: #endif /* _REENTRANT */
45: unsigned int nb_of_elt;
46: } list;
47:
48: static list* LA[MAXLIST];
49:
50: static inline list_error
51: list_lock(list_t L)
52: {
53: #ifdef _REENTRANT
54: int err = pthread_mutex_lock(&LA[L]->list_lock);
55: if (err) {
56: char errbuf[40]; /* Flawfinder: ignore */
57: strerror_r(err, errbuf, 40);
58: fprintf(stderr, "locking: %s", errbuf);
59: return MUTEX_ERROR_LOCK;
60: }
61: #else
62: L = 0; /* to avoid a warning */
63: #endif
64: return NO_ERROR;
65: }
66:
67: static inline list_error
68: list_unlock(list_t L)
69: {
70: #ifdef _REENTRANT
71: if (pthread_mutex_unlock(&LA[L]->list_lock))
72: return MUTEX_ERROR_UNLOCK;
73: #else
74: L = 0; /* to avoid a warning */
75: #endif
76: return NO_ERROR;
77: }
78:
79: static inline int
80: list_vrfy(list_t L)
81: {
82: if (L < 0)
83: return -1;
84: if (L >= MAXLIST)
85: return -2;
86: if (LA[L] == NULL)
87: return -3;
88: return 0;
89: }
90:
91: void
92: list_stat(FILE* f)
93: {
94: #ifndef NDEBUG
95: unsigned int count = 0;
96: list_t idx = 0;
97: for (idx = 0; idx < MAXLIST; idx++) {
98: if (LA[idx] != NULL)
99: count++;
100: }
101: fprintf(f, "%u/%d list in use\n", count, MAXLIST);
102: for (idx = 0; idx < MAXLIST; idx++) {
103: if (LA[idx] != NULL) {
104: fprintf(f, "#list[%d]: %d; ", idx, list_size(idx));
105: }
106: }
107: fprintf(f, "\n");
108: #endif
109: }
110:
111: list_t
112: list_create(void)
113: { /** \bug we should put a mutex on LA */
114: list_t idx = 0;
115: for (idx = 0; idx < MAXLIST; idx++) {
116: if (LA[idx] == NULL)
117: break;
118: }
119: if (idx >= MAXLIST || LA[idx] != NULL)
120: return -1;
121: LA[idx] = (list*) malloc(sizeof(list));
122: if (LA[idx] == NULL)
123: return -1;
124: LA[idx]->first = NULL;
125: LA[idx]->last = NULL;
126: LA[idx]->lcurrent = NULL;
127: LA[idx]->currentpos = 0;
128: LA[idx]->nb_of_elt = 0;
129: #ifdef _REENTRANT
130: pthread_mutex_init(&LA[idx]->list_lock, NULL);
131: #endif /* _REENTRANT */
132: return idx;
133: }
134:
135: list_error
136: list_delete(list_t L)
137: {
138: struct link* next = NULL;
139: struct link* current = NULL;
140: list_error eunl, err = NO_ERROR;
141: if (list_vrfy(L) != 0)
142: return NO_SUCH_LIST;
143: err = list_lock(L);
144: if (err != NO_ERROR)
145: return err;
146: next = LA[L]->first;
147: if (next != NULL) do {
148: current = next;
149: next = next->next;
150: free(current->data);
151: current->data = NULL;
152: free(current);
153: } while(next != NULL);/* old: && next != LA[L]->last); */
154: eunl = list_unlock(L);
155: assert(eunl == NO_ERROR);
156: #ifdef _REENTRANT
157: pthread_mutex_destroy(&LA[L]->list_lock);
158: #endif /* _REENTRANT */
159: free(LA[L]);
160: // if (L == 0) fprintf(stderr, "\n\n\t\tdeleting list 0\n\n");
161: LA[L] = NULL;
162: return NO_ERROR;
163: }
164:
165: /*@null@*/
166: static struct link*
167: link_create(void* data)
168: {
169: struct link* l = (struct link *) malloc(sizeof(struct link));
170: if (l == NULL)
171: return NULL;
172: l->data = data; l->prev = NULL; l->next = NULL;
173: return l;
174: }
175:
176: static list_error
177: list_add_head_internal(list_t L, void* data)
178: {
179: struct link* l = NULL;
180: if (list_vrfy(L) != 0)
181: return NO_SUCH_LIST;
182: l = link_create(data);
183: if (l == NULL)
184: return NO_MEM;
185: if (LA[L]->first != NULL) {
186: l->next = LA[L]->first; l->next->prev = l; LA[L]->first = l;
187: } else { /* L is empty */
188: assert(LA[L]->last == NULL);
189: LA[L]->first = l; LA[L]->last = l;
190: }
191: LA[L]->nb_of_elt++;
192: if (LA[L]->currentpos)
193: LA[L]->currentpos++;
194: return NO_ERROR;
195: }
196:
197: list_error
198: list_add_head(list_t L, void* data)
199: {
200: list_error e, el;
201: if (list_vrfy(L) != 0)
202: return NO_SUCH_LIST;
203: el = list_lock(L);
204: if (el != NO_ERROR)
205: return el;
206: e = list_add_head_internal(L, data);
207: el = list_unlock(L);
208: assert(el == NO_ERROR);
209: return e;
210: }
211:
212: static list_error
213: list_add_tail_internal(list_t L, void* data)
214: {
215: struct link* l = NULL;
216: if (list_vrfy(L) != 0)
217: return NO_SUCH_LIST;
218: l = link_create(data);
219: if (l == NULL)
220: return NO_MEM;
221: if (LA[L]->last != NULL) {
222: l->prev = LA[L]->last; l->prev->next = l; LA[L]->last = l;
223: } else { /* L is empty */
224: assert(LA[L]->first == NULL);
225: LA[L]->first = l; LA[L]->last = l;
226: }
227: LA[L]->nb_of_elt++;
228: return NO_ERROR;
229: }
230:
231: list_error
232: list_add_tail(list_t L, void* data)
233: {
234: list_error e, el;
235: if (list_vrfy(L) != 0)
236: return NO_SUCH_LIST;
237: el = list_lock(L);
238: if (el != NO_ERROR)
239: return el;
240: e = list_add_tail_internal(L, data);
241: el = list_unlock(L);
242: assert(el == NO_ERROR);
243: return e;
244: }
245:
246: list_error
247: list_add_at_pos(list_t L, unsigned int pos, void* data)
248: {
249: list_error ret, eunl;
250: struct link* l = NULL;
251: if (list_vrfy(L) != 0)
252: return NO_SUCH_LIST;
253: l = link_create(data);
254: if (l == NULL)
255: return NO_MEM;
256: if (list_lock(L) != NO_ERROR) {
257: free(l);
258: return MUTEX_ERROR_LOCK;
259: }
260: if (pos) {
261: if (pos > LA[L]->nb_of_elt) {
262: ret = ERR_NO_SUCH_POS;
263: } else {
264: if (pos == LA[L]->nb_of_elt) {
265: ret = list_add_tail_internal(L, data);
266: } else {
267: unsigned int i = 1;
268: struct link* current = LA[L]->first->next;
269: for (i = 1; i != pos; i++) {
270: current = current->next;
271: }
272: current->prev->next = l;
273: l->prev = current->prev;
274: current->prev = l;
275: l->next = current;
276: LA[L]->nb_of_elt++;
277: ret = NO_ERROR;
278: }
279: }
280: } else {
281: ret = list_add_head_internal(L, data);
282: }
283: if (pos && pos <= LA[L]->currentpos)
284: LA[L]->currentpos++;
285: eunl = list_unlock(L);
286: assert(eunl == NO_ERROR);
287: return ret;
288: }
289:
290: static void
291: list_del_head_internal(list_t L, bool del)
292: {
293: struct link* l = NULL;
294: if (list_vrfy(L) != 0)
295: return;
296: l = LA[L]->first;
297: if (l != NULL) {
298: LA[L]->first = l->next;
299: if (LA[L]->nb_of_elt == 1)
300: LA[L]->last = NULL;
301: else
302: LA[L]->first->prev = NULL;
303: if (LA[L]->lcurrent == l)
304: LA[L]->lcurrent = LA[L]->first;
305: if (del) {
306: free(l->data);
307: l->data = NULL;
308: }
309: free(l);
310: LA[L]->nb_of_elt--;
311: if (LA[L]->currentpos)
312: LA[L]->currentpos--;
313: }
314: }
315:
316: list_error
317: list_del_head(list_t L)
318: {
319: list_error ret, eunl;
320: if (list_vrfy(L) != 0)
321: return NO_SUCH_LIST;
322: ret = list_lock(L);
323: if (ret != NO_ERROR)
324: return ret;
325: list_del_head_internal(L, true);
326: eunl = list_unlock(L);
327: assert(eunl == NO_ERROR);
328: return NO_ERROR;
329: }
330:
331: static void
332: list_del_tail_internal(list_t L, bool del)
333: {
334: struct link* l = NULL;
335: if (list_vrfy(L) != 0)
336: return;
337: l = LA[L]->last;
338: if (l != NULL) {
339: LA[L]->last = l->prev;
340: if (LA[L]->nb_of_elt == 1)
341: LA[L]->first = NULL;
342: else
343: LA[L]->last->next = NULL;
344: if (LA[L]->lcurrent == l)
345: LA[L]->lcurrent = NULL;
346: if (del) {
347: free(l->data);
348: l->data = NULL;
349: }
350: free(l);
351: LA[L]->nb_of_elt--;
352: if (LA[L]->currentpos == LA[L]->nb_of_elt - 1)
353: LA[L]->currentpos = 0;
354: }
355: }
356:
357: list_error
358: list_del_tail(list_t L)
359: {
360: list_error ret, eunl;
361: if (list_vrfy(L) != 0)
362: return NO_SUCH_LIST;
363: ret = list_lock(L);
364: if (ret != NO_ERROR)
365: return ret;
366: list_del_tail_internal(L, true);
367: eunl = list_unlock(L);
368: assert(eunl == NO_ERROR);
369: return NO_ERROR;
370: }
371:
372: list_error
373: list_remove_tail(list_t L)
374: {
375: list_error ret, eunl;
376: if (list_vrfy(L) != 0)
377: return NO_SUCH_LIST;
378: ret = list_lock(L);
379: if (ret != NO_ERROR)
380: return ret;
381: list_del_tail_internal(L, false);
382: eunl = list_unlock(L);
383: assert(eunl == NO_ERROR);
384: return NO_ERROR;
385: }
386:
387: list_error
388: list_del_at_pos_int(list_t L, unsigned int pos, bool del)
389: {
390: list_error ret, eunl;
391: if (list_vrfy(L) != 0)
392: return NO_SUCH_LIST;
393: if (list_lock(L) != NO_ERROR)
394: return MUTEX_ERROR_LOCK;
395: if (pos) {
396: if (pos >= LA[L]->nb_of_elt) {
397: ret = ERR_NO_SUCH_POS;
398: } else {
399: if (pos == LA[L]->nb_of_elt - 1) {
400: list_del_tail_internal(L, del);
401: ret = NO_ERROR;
402: } else { /* not the first, not the last... */
403: unsigned int i = 1;
404: struct link* current = LA[L]->first;
405: for (i = 1; i <= pos; i++) {
406: current = current->next;
407: }
408: current->prev->next = current->next;
409: current->next->prev = current->prev;
410: if (LA[L]->lcurrent == current)
411: LA[L]->lcurrent = current->next;
412: if (del) {
413: free(current->data);
414: current->data = NULL;
415: }
416: free(current);
417: LA[L]->nb_of_elt--;
418: ret = NO_ERROR;
419: if (LA[L]->currentpos > pos)
420: LA[L]->currentpos--;
421: }
422: }
423: } else {
424: list_del_head_internal(L, del);
425: ret = NO_ERROR;
426: }
427: eunl = list_unlock(L);
428: assert(eunl == NO_ERROR);
429: return ret;
430: }
431:
432: list_error list_del_at_pos(list_t l, unsigned int pos)
433: {
434: return list_del_at_pos_int(l, pos, true);
435: }
436:
437: list_error list_remove_at_pos(list_t l, unsigned int pos)
438: {
439: return list_del_at_pos_int(l, pos, false);
440: }
441:
442: static inline unsigned int
443: list_size_internal(list_t L)
444: {
445: return LA[L]->nb_of_elt;
446: }
447:
448: int
449: list_size(list_t L)
450: {
451: int ret = 0;
452: list_error eunl;
453: if (list_vrfy(L) != 0)
454: return -1;
455: if (list_lock(L) != NO_ERROR)
456: return -1;
457: ret = (int) list_size_internal(L); /** \bug unsigned --> signed */
458: eunl = list_unlock(L);
459: assert(eunl == NO_ERROR);
460: return ret;
461: }
462:
463: /*@null@*/
464: static inline void*
465: list_get_head_internal(list_t L)
466: {
467: if (LA[L]->first == NULL)
468: return NULL;
469: return LA[L]->first->data;
470: }
471:
472: /*@null@*/
473: void*
474: list_get_head(list_t L)
475: {
476: void* ret = NULL;
477: list_error eunl;
478: if (list_vrfy(L) != 0)
479: return NULL;
480: if (list_lock(L) != NO_ERROR)
481: return NULL;
482: ret = list_get_head_internal(L);
483: eunl = list_unlock(L);
484: assert(eunl == NO_ERROR);
485: return ret;
486: }
487:
488: /*@null@*/
489: static inline void*
490: list_get_tail_internal(list_t L)
491: {
492: if (LA[L]->last == NULL)
493: return NULL;
494: return LA[L]->last->data;
495: }
496:
497: /*@null@*/
498: void*
499: list_get_tail(list_t L)
500: {
501: void* ret = NULL;
502: list_error eunl;
503: if (list_vrfy(L) != 0)
504: return NULL;
505: if (list_lock(L) != NO_ERROR)
506: return NULL;
507: ret = list_get_tail_internal(L);
508: eunl = list_unlock(L);
509: assert(eunl == NO_ERROR);
510: return ret;
511: }
512:
513: /*@null@*/
514: void*
515: list_get_at_pos(list_t L, unsigned int pos)
516: {
517: list_error eunl;
518: void* ret;
519: if (list_vrfy(L) != 0)
520: return NULL;
521: if (list_lock(L) != NO_ERROR)
522: return NULL;
523: if (pos) {
524: if (pos >= LA[L]->nb_of_elt) {
525: ret = NULL;
526: } else {
527: if (pos == LA[L]->nb_of_elt - 1) {
528: ret = list_get_tail_internal(L);
529: } else {
530: unsigned int i = 0;
531: struct link* current = LA[L]->first;
532: for (i = 0; i != pos; i++) {
533: current = current->next;
534: }
535: ret = current->data;
536: }
537: }
538: } else {
539: ret = list_get_head_internal(L);
540: }
541: eunl = list_unlock(L);
542: assert(eunl == NO_ERROR);
543: return ret;
544: }
545:
546: /*@null@*/
547: void*
548: list_pop(list_t L)
549: {
550: list_error eunl;
551: void* ret = NULL;
552: struct link* l = NULL;
553: if (list_vrfy(L) != 0)
554: return NULL;
555: if (list_lock(L) != NO_ERROR)
556: return NULL;
557: l = LA[L]->last;
558: if (l != NULL) {
559: LA[L]->last = l->prev;
560: if (l->prev != NULL)
561: l->prev->next = NULL;
562: if (LA[L]->nb_of_elt == 1)
563: LA[L]->first = LA[L]->last; /* = NULL */
564: if (LA[L]->lcurrent == l)
565: LA[L]->lcurrent = NULL;
566: ret = l->data;
567: l->data = NULL;
568: free(l);
569: LA[L]->nb_of_elt--;
570: if (LA[L]->currentpos == list_size_internal(L) - 1)
571: LA[L]->currentpos = 0;
572: }
573: eunl = list_unlock(L);
574: assert(eunl == NO_ERROR);
575: return ret;
576: }
577:
578: list_error
579: list_search(list_t L, void* elt, int (eq(void*,void*)), unsigned int* position)
580: {
581: unsigned int i = 0;
582: list_error eunl, ret = NO_FOUND;
583: struct link* li;
584: if (list_vrfy(L) != 0)
585: return NO_SUCH_LIST;
586: if (list_lock(L) != NO_ERROR)
587: return MUTEX_ERROR_LOCK;
588: li = LA[L]->first;
589: for (i = 0; i < LA[L]->nb_of_elt; i++) {
590: if (eq(li->data, elt)) {
591: *position = i;
592: ret = NO_ERROR;
593: break;
594: }
595: li = li->next;
596: }
597: eunl = list_unlock(L);
598: assert(eunl == NO_ERROR);
599: return ret;
600: }
601:
602: /*@null@*/
603: static void*
604: list_current_reset_internal(list_t L)
605: {
606: LA[L]->lcurrent = LA[L]->first;
607: LA[L]->currentpos = 0;
608: if (LA[L]->lcurrent != NULL)
609: return LA[L]->lcurrent->data;
610:
611: return NULL;
612: }
613:
614: /*@null@*/
615: void*
616: list_current_reset(list_t L)
617: {
618: void* elt = NULL;
619: list_error eunl;
620: if (list_vrfy(L) != 0)
621: return NULL;
622: if (list_lock(L) != NO_ERROR)
623: return NULL;
624: elt = list_current_reset_internal(L);
625: eunl = list_unlock(L);
626: assert(eunl == NO_ERROR);
627: return elt;
628: }
629:
630: /*@null@*/
631: static inline void*
632: list_next_internal(list_t L)
633: {
634: if (LA[L]->lcurrent == NULL)
635: return NULL;
636: LA[L]->lcurrent = LA[L]->lcurrent->next;
637: LA[L]->currentpos++;
638: if (LA[L]->lcurrent != NULL)
639: return LA[L]->lcurrent->data;
640: return NULL;
641: }
642:
643: /*@null@*/
644: static inline void*
645: list_previous_internal(list_t L)
646: {
647: if (LA[L]->lcurrent == NULL)
648: return NULL;
649: LA[L]->lcurrent = LA[L]->lcurrent->prev;
650: LA[L]->currentpos--;
651: if (LA[L]->lcurrent != NULL)
652: return LA[L]->lcurrent->data;
653: LA[L]->currentpos = 0;
654: return NULL;
655: }
656:
657: /*@null@*/
658: void*
659: list_next(list_t L)
660: {
661: void* elt = NULL;
662: list_error eunl;
663: if (list_vrfy(L) != 0)
664: return NULL;
665: if (list_lock(L) != NO_ERROR)
666: return NULL;
667: if (list_size_internal(L) != 0) {
668: elt = list_next_internal(L);
669: }
670: eunl = list_unlock(L);
671: assert(eunl == NO_ERROR);
672: return elt;
673: }
674:
675: /*@null@*/
676: void*
677: list_current(list_t L)
678: {
679: void* elt = NULL;
680: list_error eunl;
681: if (list_vrfy(L) != 0)
682: return NULL;
683: if (list_lock(L) != NO_ERROR)
684: return NULL;
685: if (list_size_internal(L) != 0)
686: if (LA[L]->lcurrent != NULL)
687: elt = LA[L]->lcurrent->data;
688: eunl = list_unlock(L);
689: assert(eunl == NO_ERROR);
690: return elt;
691: }
692:
693: /*@null@*/
694: void*
695: list_previous(list_t L)
696: {
697: void* elt = NULL;
698: list_error eunl;
699: if (list_vrfy(L) != 0)
700: return NULL;
701: if (list_lock(L) != NO_ERROR)
702: return NULL;
703: if (list_size_internal(L) == 0)
704: return NULL;
705: elt = list_previous_internal(L);
706: eunl = list_unlock(L);
707: assert(eunl == NO_ERROR);
708: return elt;
709: }
710:
711: list_error
712: list_current_setpos(list_t L, unsigned int position)
713: {
714: struct link* next = NULL;
715: unsigned int i = 0;
716: if (list_vrfy(L) != 0)
717: return NO_SUCH_LIST;
718: if (LA[L]->nb_of_elt <= position)
719: return NO_FOUND;
720: next = LA[L]->first;
721: for (i = 0; i < position; i++) {
722: if (next == NULL)
723: return INTERNAL_ERROR;
724: next = next->next;
725: }
726: LA[L]->currentpos = position;
727: if (next == NULL)
728: return INTERNAL_ERROR;
729: LA[L]->lcurrent = next;
730: return NO_ERROR;
731: }
732:
733: unsigned int
734: list_current_getpos(list_t L)
735: {
736: if (list_vrfy(L) != 0)
737: return NO_SUCH_LIST;
738:
739: if ((int) LA[L]->currentpos >= list_size(L))
740: return 0;
741: return LA[L]->currentpos;
742: }
743:
744: static void
745: list_current_del_internal(list_t L, bool del)
746: {
747: struct link* next;
748: if (LA[L]->lcurrent == NULL)
749: return;
750: if (LA[L]->lcurrent == LA[L]->last) {
751: list_del_tail_internal(L, del);
752: return;
753: }
754: if (LA[L]->lcurrent == LA[L]->first) {
755: list_del_head_internal(L, del);
756: return;
757: }
758: LA[L]->lcurrent->prev->next = LA[L]->lcurrent->next;
759: LA[L]->lcurrent->next->prev = LA[L]->lcurrent->prev;
760: LA[L]->nb_of_elt--;
761: next = LA[L]->lcurrent->next;
762: if (del) {
763: free(LA[L]->lcurrent->data);
764: LA[L]->lcurrent->data = NULL;
765: }
766: free(LA[L]->lcurrent);
767: LA[L]->lcurrent = next;
768: }
769:
770: list_error
771: list_current_del(list_t L)
772: {
773: list_error eunl;
774: if (list_vrfy(L) != 0)
775: return NO_SUCH_LIST;
776: if (list_size_internal(L) == 0)
777: return ERR_NO_SUCH_POS;
778: if (list_lock(L) != NO_ERROR)
779: return MUTEX_ERROR_LOCK;
780: list_current_del_internal(L, true);
781: eunl = list_unlock(L);
782: assert(eunl == NO_ERROR);
783: return NO_ERROR;
784: }
785:
786: list_error
787: list_current_remove(list_t L)
788: {
789: list_error eunl;
790: if (list_vrfy(L) != 0)
791: return NO_SUCH_LIST;
792: if (list_size_internal(L) == 0)
793: return ERR_NO_SUCH_POS;
794: if (list_lock(L) != NO_ERROR)
795: return MUTEX_ERROR_LOCK;
796: list_current_del_internal(L, false);
797: eunl = list_unlock(L);
798: assert(eunl == NO_ERROR);
799: return NO_ERROR;
800: }
801:
802: #ifdef WITH_DATALOC
803:
804: list_error
805: list_pack(list_t L, struct dataloc* loc, int eltsize,
806: int (*cbeltwrite)(struct dataloc* loc, const void* elt))
807: {/**\bug we don't take the mutex. */
808: if (list_vrfy(L) != 0)
809: return NO_SUCH_LIST;
810: if (eltsize <= 0 && cbeltwrite == NULL)
811: return BAD_PARAMETERS;
812: if (eltsize > 0 && cbeltwrite != NULL)
813: return BAD_PARAMETERS;
814: if (loc == NULL)
815: return BAD_PARAMETERS;
816: int err = writeloc(loc, &LA[L]->nb_of_elt, sizeof LA[L]->nb_of_elt);
817: if (err < 0)
818: return IO_ERROR;
819: unsigned int count = 0;
820: unsigned int currentpos = 0;
821: struct link* currentsav = LA[L]->lcurrent;
822: struct link* next = LA[L]->first;
823: if (next != NULL) do {
824: if (cbeltwrite != NULL) {
825: assert(eltsize <= 0);
826: if (cbeltwrite(loc, next->data) < 0)
827: return IO_ERROR;
828: } else {
829: err = writeloc(loc, next->data, eltsize);
830: if (err < 0)
831: return IO_ERROR;
832: }
833: if (next == currentsav)
834: currentpos = count;
835: count++;
836: } while ((next = next->next) != NULL);
837:
838: if (count != LA[L]->nb_of_elt)
839: return INTERNAL_ERROR;
840: {
841: uint8_t c = currentsav != NULL ? 1 : 0;
842: err = writeloc(loc, &c, sizeof c);
843: if (err < 0)
844: return IO_ERROR;
845: if (currentsav != NULL) {
846: assert(currentpos == LA[L]->currentpos);
847: int err = writeloc(loc, ¤tpos, sizeof currentpos);
848: if (err < 0)
849: return IO_ERROR;
850: }
851: }
852: return NO_ERROR;
853: }
854:
855: list_t
856: list_unpack(struct dataloc* loc, list_error *e, int eltsize,
857: int (*cbeltread)(struct dataloc* loc, void** elt))
858: {
859: if (e == NULL)
860: return -1;
861: if (loc == NULL) {
862: *e = BAD_PARAMETERS;
863: return -1;
864: }
865: if (eltsize <= 0 && cbeltread == NULL) {
866: *e = BAD_PARAMETERS;
867: return -1;
868: }
869: if (eltsize > 0 && cbeltread != NULL) {
870: *e = BAD_PARAMETERS;
871: return -1;
872: }
873: list_t L = list_create();
874: if (L == (list_t) -1) {
875: *e = NO_MEM;
876: return -1;
877: }
878: unsigned int nbelt = 0;
879: int err = readloc(loc, &nbelt, sizeof nbelt);
880: if (err < 0) {
881: *e = IO_ERROR;
882: return -1;
883: }
884: for (unsigned int i = 0; i < nbelt; i++) {
885: void* elt = NULL;
886: if (cbeltread != NULL) {
887: assert(eltsize <= 0);
888: err = cbeltread(loc, &elt);
889: if (err < 0) {
890: *e = IO_ERROR;
891: return -1;
892: }
893: } else {
894: elt = calloc(1, eltsize);
895: if (elt == NULL) {
896: *e = NO_MEM;
897: return -1;
898: }
899: err = readloc(loc, elt, eltsize);
900: if (err < 0) {
901: *e = IO_ERROR;
902: free(elt);
903: return -1;
904: }
905: }
906: list_error lerr = list_add_tail(L, elt);
907: if (lerr != NO_ERROR) {
908: *e = lerr;
909: if (cbeltread == NULL)
910: free(elt);
911: /**\bug: if cbeltread != NULL, the elt it allocated
912: is not freed (we cannot, it could be an tree
913: structure or whatever... */
914: return -1;
915: }
916: }
917: if (nbelt != LA[L]->nb_of_elt) {
918: *e = INTERNAL_ERROR;
919: return -1;
920: }
921: {
922: uint8_t iscurrent = 0;
923: int err = readloc(loc, &iscurrent, sizeof iscurrent);
924: if (err < 0 || (err == 0 && iscurrent != 0 && iscurrent != 1)) {
925: *e = IO_ERROR;
926: return -1;
927: }
928: if (iscurrent == 1) {
929: unsigned int currentpos = 0;
930: err = readloc(loc, ¤tpos, sizeof currentpos);
931: if (err < 0) {
932: *e = IO_ERROR;
933: return -1;
934: }
935: list_error lerr = list_current_setpos(L, currentpos);
936: if (lerr != NO_ERROR)
937: return lerr;
938: }
939: }
940: return L;
941: }
942:
943: #endif /* WITH_DATALOC */