TaPAS  0.2
Macros | Typedefs | Functions
ccl-list.h File Reference

Generic simple linked list. More...

#include <ccl/ccl-assert.h>
#include <ccl/ccl-protos.h>
#include <ccl/ccl-iterator.h>

Go to the source code of this file.

Macros

#define FIRST(l)   ((l)->first)
 Returns first pair of the list l.
 
#define CAR(p)   ((p)->car)
 Returns the car part of the pair p.
 
#define CDR(p)   ((p)->cdr)
 Returns the cdr part of the pair p.
 
#define CADR(p)   (CAR (CDR (p)))
 Shortcut for CAR (CDR (p))
 
#define CDDR(p)   (CDR (CDR (p)))
 Shortcut for CDR (CDR (p))
 
#define CADDR(p)   (CAR (CDDR (p)))
 Shortcut for CAR (CDDR (p))
 
#define CDDDR(p)   (CDR (CDDR (p)))
 Shortcut for CDR (CDDR (p))
 
#define CADDDR(p)   (CAR (CDDDR (p)))
 Shortcut for CAR (CDDDR (p))
 
#define CDDDDR(p)   (CDR (CDDDR (p)))
 Shortcut for CDR (CDDDR (p))
 
#define CADDDDR(p)   (CAR (CDDDDR (p)))
 Shortcut for CAR (CDDDDR (p))
 
#define CDDDDDR(p)   (CDR (CDDDDR (p)))
 Shortcut for CDR (CDDDDR (p))
 
#define ccl_list_get_size(l)   (ccl_pre ((l) != NULL), (l)->size)
 Returns the number of elements in the list. More...
 
#define ccl_list_get_length(l)   ccl_list_get_size(l)
 Returns the number of elements in the list. More...
 
#define ccl_list_is_empty(l)   (ccl_list_get_size (l) ==0)
 Checks if the list l contains no element. More...
 

Typedefs

typedef struct ccl_list_st ccl_list
 Type of a generic list.
 
typedef struct ccl_pair_st ccl_pair
 Type of a cell of a ccl_list. More...
 

Functions

ccl_listccl_list_create (void)
 Creates a new list. More...
 
void ccl_list_delete (ccl_list *l)
 Deletes the list l. More...
 
void ccl_list_clear (ccl_list *l, ccl_delete_proc *del)
 Makes empty the list l. More...
 
void ccl_list_clear_and_delete (ccl_list *l, ccl_delete_proc *del)
 Deletes the list l and stored objects. More...
 
void ccl_list_add (ccl_list *l, void *obj)
 Adds an object obj at the end of the list l. More...
 
int ccl_list_has (const ccl_list *l, void *obj)
 Checks if the object obj belongs to l. More...
 
void ccl_list_put_first (ccl_list *l, void *obj)
 Adds an object obj at the beginning of the list l. More...
 
void * ccl_list_take_first (ccl_list *l)
 Removes the first object of the list l. More...
 
void ccl_list_sort (ccl_list *l, ccl_compare_func *cmp)
 (Quick-)Sort the list l using the comparison function cmp. If cmp == CCL_DEFAULT_COMPARE_FUNC, addresses of objects are compared. More...
 
int ccl_list_insert (ccl_list *l, void *obj, ccl_compare_func *cmp)
 Inserts the object obj into the ordered list l. More...
 
int ccl_list_equals (const ccl_list *l1, const ccl_list *l2)
 Checks if l1 and l2 are equals. More...
 
ccl_listccl_list_dup (const ccl_list *l)
 Duplicates the list l. More...
 
ccl_listccl_list_deep_dup (const ccl_list *l, ccl_duplicate_func *dup)
 Duplicates the list l and stored objects. More...
 
void * ccl_list_get_at (ccl_list *l, int index)
 Returns the object at the postion index. More...
 
void ccl_list_remove (ccl_list *l, void *p)
 Removes the object p from the list l. More...
 
void ccl_list_sub (ccl_list *l1, const ccl_list *l2)
 Removes the objects of l2 from l1. More...
 
void ccl_list_append (ccl_list *l1, const ccl_list *l2)
 append l2 to l1 More...
 
int ccl_list_get_index (const ccl_list *l, void *ptr, ccl_compare_func *cmp)
 Returns the position of ptr in the list l. More...
 
int ccl_list_compare (const ccl_list *l1, const ccl_list *l2, ccl_compare_func *cmp)
 Compares the two lists l1 and l2 with the lexicographical order. More...
 
unsigned int ccl_list_hash (const ccl_list *l)
 Computes a hashed value for the list l. More...
 
unsigned int ccl_list_hash_all (const ccl_list *l, ccl_hash_func *h)
 Computes a hashed value for the list l. More...
 
void ** ccl_list_to_array (const ccl_list *l, int *p_size)
 Return a newly allocated array containing all elements of l. More...
 

Detailed Description

Generic simple linked list.

Definition in file ccl-list.h.

Macro Definition Documentation

#define ccl_list_get_length (   l)    ccl_list_get_size(l)

Returns the number of elements in the list.

Parameters
lthe list
Precondition
l != NULL
Returns
the number of elements in the list.

Definition at line 174 of file ccl-list.h.

#define ccl_list_get_size (   l)    (ccl_pre ((l) != NULL), (l)->size)

Returns the number of elements in the list.

Parameters
lthe list
Precondition
l != NULL
Returns
the number of elements in the list.

Definition at line 166 of file ccl-list.h.

#define ccl_list_is_empty (   l)    (ccl_list_get_size (l) ==0)

Checks if the list l contains no element.

Parameters
lthe list
Precondition
l != NULL
Returns
a non null value if l is empty

Definition at line 182 of file ccl-list.h.

Typedef Documentation

typedef struct ccl_pair_st ccl_pair

Type of a cell of a ccl_list.

A pair is just a couple (car, cdr) where car is the address of an object and cdr the address of the next pair (or cell) in the linked list.

Definition at line 42 of file ccl-list.h.

Function Documentation

void ccl_list_add ( ccl_list l,
void *  obj 
)

Adds an object obj at the end of the list l.

A new pair containing obj is appended to l. The operation is done in constant time.

Parameters
lthe list
objthe obejct put at the end of l
Precondition
l != NULL
void ccl_list_append ( ccl_list l1,
const ccl_list l2 
)

append l2 to l1

Parameters
l1the first list
l2the second list
Precondition
l1 != NULL
l2 != NULL
void ccl_list_clear ( ccl_list l,
ccl_delete_proc del 
)

Makes empty the list l.

The function deletes all pairs in l and apply the deletion function del on each stored object. del can be NULL. The list is made empty but not deleted.

Parameters
lthe list
dela pointer to a deletion function
Precondition
l != NULL
void ccl_list_clear_and_delete ( ccl_list l,
ccl_delete_proc del 
)

Deletes the list l and stored objects.

The function removes all resources allocated to l including the objects stored in each pair. The function applies the deletion function del to each object.

Parameters
lthe list
dela pointer to a deletion function
Precondition
l != NULL
int ccl_list_compare ( const ccl_list l1,
const ccl_list l2,
ccl_compare_func cmp 
)

Compares the two lists l1 and l2 with the lexicographical order.

The function orders l1 and l2 with the lexicographic order induced by cmp.

Parameters
l1the first list
l2the second list
cmpthe comparison function for stored objects
Precondition
l1 != NULL
l2 != NULL
Return values
<0 if l1 < l2
=0 if l1 == l2
>0 if l1 > l2
ccl_list* ccl_list_create ( void  )

Creates a new list.

Returns
a new empty list
ccl_list* ccl_list_deep_dup ( const ccl_list l,
ccl_duplicate_func dup 
)

Duplicates the list l and stored objects.

The function creates a new list containing the same objects than l. The objects are duplicated using the dup function. If dup == CCL_DEFAULT_DUPLICATE_FUNC then the funtion behaves like ccl_list_dup.

Parameters
lthe list to duplicate
dupthe function used to duplciate objects
Precondition
l != NULL
Returns
a copy of l
void ccl_list_delete ( ccl_list l)

Deletes the list l.

The function deletes the resources allocated for the storage of l. Objects stored into pairs are not deleted. In order to free objects the ccl_list_clear_and_delete must be used.

Parameters
lthe list
Precondition
l != NULL
ccl_list* ccl_list_dup ( const ccl_list l)

Duplicates the list l.

The function creates a new list containing the same pointed objects than l. The objects are not duplicated.

Parameters
lthe list to duplicate
Precondition
l != NULL
Returns
a copy of l
int ccl_list_equals ( const ccl_list l1,
const ccl_list l2 
)

Checks if l1 and l2 are equals.

The function checks if the two lists l1 and l2 are equal i.e. they represent the same sequence of pointed objects.

Parameters
l1the first list
l2the second list
Precondition
l1 != NULL
l2 != NULL
Returns
a non null value if l1 and l2 are equal.
void* ccl_list_get_at ( ccl_list l,
int  index 
)

Returns the object at the postion index.

Parameters
lthe list
indexthe index of the object
Precondition
0 <= index && index < ccl_list_get_size(l)
Returns
the object of l stored at the position index
int ccl_list_get_index ( const ccl_list l,
void *  ptr,
ccl_compare_func cmp 
)

Returns the position of ptr in the list l.

The function looks for the object ptr in the list l. The search is made according to the comparison function cmp. If cmp == CCL_DEFAULT_COMPARE_FUNC, the objects are compared using their addresses.

The function returns the index of the first instance of ptr found in l or -1 if the object is not found.

Parameters
lthe list
ptrthe object to find in the list
cmpthe comparison function
Precondition
l != NULL
Returns
the position of ptr in l or -1 if it is not found.
int ccl_list_has ( const ccl_list l,
void *  obj 
)

Checks if the object obj belongs to l.

Parameters
lthe list
objthe object whose existence is checked
Precondition
l != NULL
Returns
a non-null value if object belongs to l.
unsigned int ccl_list_hash ( const ccl_list l)

Computes a hashed value for the list l.

The address of stored objects is used to compute the hashed value of l.

Parameters
lthe list
Precondition
l != NULL
Returns
a hashed value for l.
unsigned int ccl_list_hash_all ( const ccl_list l,
ccl_hash_func h 
)

Computes a hashed value for the list l.

The hashed value computed by the function uses the function h to compute an hashed value for each object stored in the list. If h is CCL_DEFAULT_HASH_FUNC the function behaves like ccl_list_hash.

Parameters
lthe list
hthe hashing function for objects.
Precondition
l != NULL
Returns
a hashed value for l.
int ccl_list_insert ( ccl_list l,
void *  obj,
ccl_compare_func cmp 
)

Inserts the object obj into the ordered list l.

The function inserts the object obj before the first pair p such obj < CAR(p) (according to cmp). obj is inserted even if it is already present in l.

If cmp == CCL_DEFAULT_COMPARE_FUNC, addresses of objects are compared.

Parameters
lthe list
objthe object to insert into l
cmpthe comparison function for objects stored in the list l
Precondition
l != NULL
Returns
the position (starting from 0) where obj is inserted.
void ccl_list_put_first ( ccl_list l,
void *  obj 
)

Adds an object obj at the beginning of the list l.

A new pair containing obj is added before the head of l.

Parameters
lthe list
objthe object added in the list l
Precondition
!= NULL
void ccl_list_remove ( ccl_list l,
void *  p 
)

Removes the object p from the list l.

If the object pointed by p is found in l then the first pair containing it is removed. The object pointed by p is not deleted.

Parameters
lthe list
pthe object to remove.
Precondition
l != NULL
void ccl_list_sort ( ccl_list l,
ccl_compare_func cmp 
)

(Quick-)Sort the list l using the comparison function cmp. If cmp == CCL_DEFAULT_COMPARE_FUNC, addresses of objects are compared.

Parameters
lthe list
cmpthe comparison function for objects stored in the list l
Precondition
l != NULL
void ccl_list_sub ( ccl_list l1,
const ccl_list l2 
)

Removes the objects of l2 from l1.

Parameters
l1the first list
l2the second list
Precondition
l1 != NULL
l2 != NULL
void* ccl_list_take_first ( ccl_list l)

Removes the first object of the list l.

The function removes the first pair of l and returns the object that was stored in it.

Parameters
lthe list
Precondition
! ccl_list_is_empty (l)
Returns
the content of the removed pair
void** ccl_list_to_array ( const ccl_list l,
int *  p_size 
)

Return a newly allocated array containing all elements of l.

Even if the list is empty the return array is not NULL and must be deleted.

Parameters
lthe list
p_sizea pointer to an integer that should receive the size of the array (i.e. the size of the list).
Precondition
l != NULL
Postcondition
result != NULL
Returns
a newly allocated array containing all elements of l