Generic simple linked list. More...

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

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_list *	ccl_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_list *	ccl_list_dup (const ccl_list *l)
	Duplicates the list l. More...

ccl_list *	ccl_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

l the list

Precondition: l != NULL

Returns: the number of elements in the list.

Definition at line 176 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

l the list

Precondition: l != NULL

Returns: the number of elements in the list.

Definition at line 168 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

l the list

Precondition: l != NULL

Returns: a non null value if l is empty

Definition at line 184 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

l	the list
obj	the 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

l1	the first list
l2	the 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

l	the list
del	a 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

l	the list
del	a 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

l1	the first list
l2	the second list
cmp	the 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

l	the list to duplicate
dup	the 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

l the 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

l	the 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

l1	the first list
l2	the 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

l	the list
index	the 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

l	the list
ptr	the object to find in the list
cmp	the 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

l	the list
obj	the 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

l the 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

l	the list
h	the 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

l	the list
obj	the object to insert into l
cmp	the 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

l	the list
obj	the 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

l	the list
p	the 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

l	the list
cmp	the 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

l1	the first list
l2	the 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

l the 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

l	the list
p_size	a 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

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation