Nicolas Bernard's Toolbox - Lists (and stacks, and ...)

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, &currentpos, 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, &currentpos, 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 */