/*
* Basic list library
*
* Copyright 2001-2009 Nicolas Bernard
* All rights reserved.
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*
*/
#ifndef _NB_LISTS_
#define _NB_LISTS_
#ifdef _REENTRANT
#include
#endif /* _REENTRANT */
/* beware: reentrant part not tested ! */
#define MAXLIST 1024
/* this is the maximum number of list you can have in an application. You can
change it (remember to recompile list.c then), but if doing so remember that
it is a signed int (don't put a too big value, nor a value <= 0). */
typedef /*@abstract@*/ /*@mutable@*/ int list_t;
/* you can think that a list_t is a "list descriptor", in the same way you have
file descriptors. */
typedef enum {
NO_ERROR, /* = 0; success */
ERR_NO_SUCH_POS, /* 1 returned if the nth elt has been asked but
doesn't exist */
NO_FOUND, /* 2 research failed: elt not found */
MUTEX_ERROR_LOCK, /* 3 problem with a mutex during locking (only if
compiled with -D_REENTRANT) */
MUTEX_ERROR_UNLOCK, /* 4 problem with a mutex during unlocking (only
if compiled with -D_REENTRANT) */
MUTEX_ERROR_OTHER, /* 5 problem with a mutex (only if compiled
with -D_REENTRANT) */
MAX_LIST_REACHED, /* 6 list creation failed because there is already
MAXLIST lists */
NO_SUCH_LIST, /* 7 there is no list associated with the list_t
used */
NO_MEM, /* 8 operation failed: not enough memory */
NOT_IMPLEMENTED, /* 9 not implemented yet! */
BAD_PARAMETERS, /* 10 parameters given are incorrect */
IO_ERROR, /* 11 error while reading or writing */
INTERNAL_ERROR, /* 12 internal incoherency detected */
} list_error;
/* list_error is a type which describe the error that can happen. A function
which return a list_error is usually not able to return any list_error,
but only some specific ones. */
list_t list_create(void);
/* create a list and returns a list descriptor or (list_t) -1 if an error
occured. */
list_error list_delete(list_t);
/* destroy a list (free each of its element then the list structure).
request to delete a non-existing list are silently ignored.
Beware: list_delete do a free of each element of the list. It may cause
crash if some of those element were freed elsewere by the application, or
memory leaks if elements contain pointer to allocated memory which is not
referenced elsewere. */
int list_size(list_t);
/* returns the number of elements in the list passed as parameter.*/
list_error list_add_head(list_t, void* data);
/* add an element at the head of the list.
[Complexity: O(1)] */
list_error list_add_tail(list_t, void* data);
/* add an element at the end of the list
[Complexity: O(1)] */
list_error list_add_at_pos(list_t, unsigned int pos, void* data);
/* add an element _before_ the posth element. the index begins at 0.
[Complexity: O(pos), O(1) if pos == 0 or pos == nb_of_elt] */
list_error list_del_head(list_t);
/* remove the head of the list.
Beware: the content is freed. cf. list_delete's beware.
[Complexity: O(1)] */
list_error list_del_tail(list_t);
/* remove the tail of the list
Beware: the content is freed. cf. list_delete's beware.
if the element must not be freed, you can use list_pop instead.
[Complexity: O(1)]*/
list_error list_remove_tail(list_t);
list_error list_del_at_pos(list_t, unsigned int pos);
/* remove the posth element. The index begins at 0.
Beware: the content is freed. cf. list_delete's beware.
[Complexity: O(pos), O(1) if pos == 0 or pos == nb_of_elt] */
list_error list_remove_at_pos(list_t l, unsigned int pos);
/*@null@*/ void* list_get_at_pos(list_t, unsigned int pos);
/* returns the element at pos. Index starts at 0.
if the list doesn't exist, or doesn't has at least pos + 1 elements, NULL
is returned.
*/
/*@null@*/ void* list_get_head(list_t L);
/*@null@*/ void* list_get_tail(list_t L);
#define list_push(l, x) list_add_tail(l, x)
/* lists can be used as stack. newest elements are at the tail. This function
pushes on the stack. */
/*@null@*/ void* list_pop(list_t);
/* lists can be used as stack. newest elements are at the tail. This function
pops from the stack. */
list_error list_search(list_t, void*, int ((void*,void*)), unsigned int*);
/* given a list descriptor, content (the same kind that you store in the list),
a comparison function returning a true value if two elements it takes as
parameters are equal and false (0) otherwise, and a pointer on an unsigned
int, this function will store the position of the first matching element in
this last pointer. It will returns NO_FOUND if there is no match in the
whole list. nb: the second arg of this function is passed as the second
arg of the comparison function. */
/********** Current position ************************************************
* Each list has a current pointer which can be used to remember a position *
* in a list, or to accelerate iterations on big lists *
****************************************************************************
A typical use could be such code, which iterate through a list in 0(n):
elt = list_current_reset(l);
if (elt != NULL) do {
...
} while ((elt = list_next(l)) != NULL);
a variant is:
for (elt = list_current_reset(l);
elt != NULL;
elt = list_next(l)) {
...
}
*****************************************************************************/
void* list_current_reset(list_t L);
/* put current at the beginning and return the first element */
list_error list_current_setpos(list_t L, unsigned int position);
/* put current on an arbitrary position (first elt is at pos 0 */
unsigned int list_current_getpos(list_t L);
/* put current on an arbitrary position (first elt is at pos 0 */
list_error list_current_del(list_t L);
/* delete the current element. Current then points on the element which was
following the deleted one. */
list_error list_current_remove(list_t L);
/* remove the current element. Current then points on the element which was
following the deleted one. The element is no more in the list but is not
freed */
void* list_next(list_t L);
/* set and return current = next */
void* list_previous(list_t L);
/* set and return current = prev */
void* list_current(list_t L);
/* return current */
#ifndef NDEBUG
#include
void list_stat(FILE* f); /* stdio.h needed */
#endif
#ifdef WITH_DATALOC
#include "dataloc.h"
list_error list_pack(list_t L, struct dataloc* loc, int eltsize, int (*cbeltwrite)(struct dataloc* loc, const void* elt));
list_t list_unpack(struct dataloc* loc, list_error *e, int eltsize, int (*cbeltwrite)(struct dataloc* loc, void** elt));
#endif /* WITH_DATALOC */
#endif /* _NB_LISTS_ */