Main Page | Class List | File List | Class Members | File Members

list.h File Reference

This is the linked list header. More...

Go to the source code of this file.

Classes

struct  node
 Node structure. More...

struct  list
 List structure. More...


List

#define list_empty(l)   ((l)->header == NULL ? 1 : 0)
 Is the list empty?

#define list_get_header(l)   ((l)->header->data)
 Get header data.

#define list_get_tail(l)   ((l)->tail->data)
 Get tail data.

#define list_get_current(l)   ((l)->current[(l)->level]->data)
 Get current data.

#define list_get_cur_prev(l)
#define list_get_cur_next(l)
#define list_total(l)   ((l)->n)
 Get number of nodes.

#define for_each_data(l)
#define end_for_each(l)
typedef node Node
typedef list List
void list_init (List *l)
 Initializes a new list.

int list_app (List *l, void *data)
 Appends a node to the list.

int list_ins (List *l, void *data_after, void *data)
 Inserts a node in the list.

int list_ins_order (List *l, void *data, int(*say_when)(const void *, const void *))
 Inserts a node in the list.

Nodelist_node_from_data (List *l, void *data)
 Returns the node associated with data.

int list_del (List *l, void *data)
 Deletes a node of the list.

void list_free (List *l)
 Frees a list.

int list_higher_level (List *l)
 Risens list level.

void list_lower_level (List *l)
 Lowers list level.

void * list_next (List *l, void *data)
 Returns data in the next node.

void * list_prev (List *l, void *data)
 Returns data in the previous node.

void list_sort (List *l, int(*compare)(const void *, const void *))
 Sorts a list.


Detailed Description

This is the linked list header.

Author:
Bruno Barberi Gnecco <brunobg@sourceforge.net>

Define Documentation

#define list_empty  )     ((l)->header == NULL ? 1 : 0)
 

Is the list empty?

Return values:
0 No.
1 Yes.

#define list_get_header  )     ((l)->header->data)
 

Get header data.

Returns:
The header data.

#define list_get_tail  )     ((l)->tail->data)
 

Get tail data.

Returns:
The tail data.

#define list_get_current  )     ((l)->current[(l)->level]->data)
 

Get current data.

See also:
for_each_data.
Returns:
The current data.

#define list_get_cur_prev  ) 
 

Value:

((l)->current[(l)->level]->previous == NULL ? \
                        NULL : (l)->current[(l)->level]->previous->data )

#define list_get_cur_next  ) 
 

Value:

((l)->current[(l)->level]->next == NULL ? \
                        NULL : (l)->current[(l)->level]->next->data )

#define list_total  )     ((l)->n)
 

Get number of nodes.

Returns:
The number of nodes of the list.

#define for_each_data  ) 
 

Value:

if (list_higher_level(l) == 0) { \
   for ( ; (l)->current[(l)->level]; (l)->current[(l)->level] = \
        (l)->current[(l)->level]->next ) { \
     if ( (l)->fix[(l)->level] ) {  \
       int i; \
       for ( i = (l)->level - 1; i >= 0; i-- ) {  \
         \
        \
         if ( (l)->fix[i] == (l)->fix[(l)->level] ) break; \
       } \
       if ( i < 0 ) {   \
         free((l)->fix[(l)->level]); \
       } \
       (l)->fix[(l)->level] = NULL; \
     }

#define end_for_each  ) 
 

Value:

} \
 list_lower_level(l); \
 }


Function Documentation

void list_init List l  ) 
 

Initializes a new list.

You must call this function before using any other list* function. The list must be allocated.

Note that if you have two nodes with the same data, the functions will assume that the first one is the wanted one. This is valid for every list_* function. Not a bug, a feature. Really. ;-)

Parameters:
l A non-NULL pointer to the list.
See also:
list_free

int list_app List l,
void *  data
 

Appends a node to the list.

Appends a node to the end of the list.

Note that if you have two nodes with the same data, the list_* functions will assume that the first one is the one you want. Not a bug, a feature.

Parameters:
l A non-NULL pointer to the list.
data The data to store in the list. Must be non-NULL.
See also:
list_ins, list_ins_order
Return values:
0 OK
-1 error.

int list_ins List l,
void *  data_after,
void *  data
 

Inserts a node in the list.

Inserts a node in the list, just before some other one.

Note that if you have two nodes with the same data, the list_* functions will assume that the first one is the one you want. Not a bug, a feature.

Parameters:
l A non-NULL pointer to the list.
data_after The data (already in the list) that should be after data. If data_after is NULL, appends to the end of the list.
data The data to store in the list. Must be non-NULL.
See also:
list_app, list_ins_order
Return values:
0 OK
-1 error.

int list_ins_order List l,
void *  data,
int(*  say_when)(const void *, const void *)
 

Inserts a node in the list.

Inserts a node in the list, in a position determined by a user function. This function is very useful to keep sorted lists.

The list is sweeped in order, and the say_when function is called for each node, receiving as first argument the data being inserted (from now on, data1) and as second the data being sweeped (from now on, data2). If say_when returns a value less than zero, data1 is inserted in the position immediately before data2. If more than zero, data1 is inserted in the position immediately after data2. If zero, nothing is done.

If all nodes are sweeped and the function returned zero to all of them, the new data is appended to the end of the list.

Note that if you have two nodes with the same data, the list_* functions will assume that the first one is the one you want. Not a bug, a feature.

Parameters:
l A non-NULL pointer to the list.
data The data to store in the list. Must be non-NULL.
say_when A pointer to a function that will determine the inserction point. The first argument is the data being inserted, the second is the data sweeped from the list. See above.
See also:
list_app, list_ins, list_sort.
Return values:
0 OK
-1 error.

Node* list_node_from_data List l,
void *  data
 

Returns the node associated with data.

Returns the node associated with data, or NULL is none is found. You should use the node if you need to do some low-level processing on the list, or are looking for speed.

Parameters:
l A non-NULL pointer to the list.
data The data. Must be non-NULL.
See also:
list_higher_level, list_lower_level
Return values:
0 OK
-1 error.

int list_del List l,
void *  data
 

Deletes a node of the list.

Deletes the node associated with data from the list. Take care with this function, since it may damage for_each_data loops.

Be careful when using for_each_data() recursively and calling list_del. It may mangle the current[] pointers, and possibly segfault or do unpredictable or just undesirable behavior. We have been working on a solution for this problem, and solved some of the biggest problems. In a few words, the problem is this: when you delete a node, it may be the current node of a lower level loop. The current code takes care of access to previous/next nodes of the now defunct node. So, if you do something like:

for_each_data(l) { for_each_data(l) { list_del(l, header_data); free(header_data); } end_for_each(l); + tempnode = list_cur_next(l); } end_for_each(l);

It will work, even though the current node in the outer loop was deleted. However, if you replace the line marked with + with the following code:

tempnode = list_next(l, list_get_current(l));

it will break, since list_get_current is likely to return NULL or garbage, since you deleted header_data().

Conclusion: use list_del carefully. The best way to avoid this problem is to not use list_del inside a big stack of loops.

Parameters:
l A non-NULL pointer to the list.
data The data. Must be non-NULL.
See also:
list_free
Return values:
0 OK
-1 error.

void list_free List l  ) 
 

Frees a list.

Frees the list contents. Does NOT free the data in it.

Parameters:
l A non-NULL pointer to the list.
data The data. Must be non-NULL.
See also:
list_del

int list_higher_level List l  ) 
 

Risens list level.

Setups a new level of for_each data. Used mostly internally.

Parameters:
l A non-NULL pointer to the list.
See also:
list_lower_level
Return values:
0 OK
-1 error.

void list_lower_level List l  ) 
 

Lowers list level.

Deletes the highest level of for_each data. Used mostly internally.

Parameters:
l A non-NULL pointer to the list.
See also:
list_lower_level

void* list_next List l,
void *  data
 

Returns data in the next node.

Returns the data associated with the next node in the list.

Avoid calling this function. It is intensive and slow. Keep the result in a variable or, if you need something more, use list_get_node_from_data.

Parameters:
l A non-NULL pointer to the list.
data The data. Must be non-NULL.
See also:
list_prev, list_node_from_data
Returns:
The data associated with the next node.

void* list_prev List l,
void *  data
 

Returns data in the previous node.

Returns the data associated with the previous node in the list.

Avoid calling this function. It is intensive and slow. Keep the result in a variable or, if you need something more, use list_get_node_from_data.

Parameters:
l A non-NULL pointer to the list.
data The data. Must be non-NULL.
See also:
list_next, list_node_from_data
Returns:
The data associated with the previous node.

void list_sort List l,
int(*  compare)(const void *, const void *)
 

Sorts a list.

Similar to qsort. Sorts list, using the (*compare) function, which is provided by the user. The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second. Uses the bubble sort algorithm.

Parameters:
l A non-NULL pointer to the list.
compare The compare function.
See also:
list_ins_order


Generated on Sun Apr 4 11:10:41 2004 for GOCR API by doxygen 1.3.5