dynamically-allocated list

Data Structures
struct	__zListCell
struct	__zList

Macros
#define	zListClass(list_t, cell_t, data_t)
	generate bidirectional ring list class. More...
#define	zListCellPrev(c)   (c)->prev
	a pointer to the previous cell of c. More...
#define	zListCellNext(c)   (c)->next
	a pointer to the next cell of c. More...
#define	zListCellSetPrev(c, p)   ( zListCellPrev(c) = (p) )
	set the previous cell of c for p. More...
#define	zListCellSetNext(c, n)   ( zListCellNext(c) = (n) )
	set the next cell of c for n. More...
#define	zListCellInit(c)
	initialize a list cell c. More...
#define	zListCellBind(l, f)
	bind two list cells l and f. l is the latter, while f is the former. More...
#define	zListCellInsertNext(c, n)
	insert a list cell n to the next of c. More...
#define	zListCellInsertPrev(c, p)
	insert a list cell p to the previous of c. More...
#define	zListCellPurge(c)
	purge a cell c from a list. More...
#define	zListCellDeleteNext(c, n)
	delete the next cell of c from a list. The deleted cell is stored into n. More...
#define	zListCellDeletePrev(c, p)
	delete the previous cell from a list. The deleted cell is stored into p. More...
#define	zListCellSwap(cell_t, c1, c2)
	swap the positions of two list cells c1 and c2. cell_t is the type of list cells. More...
#define	zListCellFPrint(f, c)
	print connections around a list cell c to the file f. More...
#define	zListCellPrint(c)   zListCellFPrint( stdout, c )
	print pointing information of a list cell c to the standard output. More...
#define	zListSize(l)   (l)->size
	the size of a list l. More...
#define	zListRoot(l)   ( &(l)->root )
	the root cell of a list l. More...
#define	zListHead(l)   zListCellPrev( zListRoot( l ) )
	the head cell (the previous of the root) of a list l. More...
#define	zListTail(l)   zListCellNext( zListRoot( l ) )
	the tail cell (the next of the root) of a list l. More...
#define	zListSetSize(l, n)   ( zListSize(l) = (n) )
	set the size of a list l for n (unpreferable to be used). More...
#define	zListIncSize(l)   ( zListSize(l)++ )
	increment the size of a list l (unpreferable to be used). More...
#define	zListDecSize(l)   ( zListSize(l)-- )
	decrement the size of a list l (unpreferable to be used). More...
#define	zListIsEmpty(l)   ( zListSize(l) == 0 )
	check if a list l is empty. More...
#define	zListInit(l)
	initialize a list l. More...
#define	zListDestroy(t, l)
	destroy a list l. t is the type of list cells. More...
#define	zListInsertNext(l, c, n)
	insert a list cell n to the next of c in a list l. More...
#define	zListInsertPrev(l, c, p)
	insert a list cell p to the previous of c in a list l. More...
#define	zListInsertHead(l, c)   zListInsertPrev( l, zListRoot(l), c )
	insert a list cell c to the head of a list l. More...
#define	zListInsertTail(l, c)   zListInsertNext( l, zListRoot(l), c )
	insert a list cell c to the tail of a list l. More...
#define	zListDeleteNext(l, c, n)
	delete the next cell of c of a list l. The deleted cell is stored into n. More...
#define	zListDeletePrev(l, c, p)
	delete the previous cell of c of a list l. The deleted cell is stored into p. More...
#define	zListDeleteHead(l, c)   zListDeletePrev( l, zListRoot(l), c )
	delete the head cell of a list l. The deleted cell is stored into c. More...
#define	zListDeleteTail(l, c)   zListDeleteNext( l, zListRoot(l), c )
	delete the tail cell of a list l. The deleted cell is stored into c. More...
#define	zListPurge(l, c)
	purge a list cell c in a list l. More...
#define	zListAppendA(a, p)
	append all cells in a list p to the head of another list a. As the result, p will be empty. More...
#define	zListAppendZ(a, p)
	append all cells in a list p to the tail of another list a. As the result, p will be empty. More...
#define	zListAppend(a, p)   zListAppendZ(a,p)
#define	zListMove(src, dst)
	move a list to another. More...
#define	zListSwap(cell_t, l1, l2)
	swap two lists l1 and l2. More...
#define	zListToHead(l, c)   for( ; (c)!=zListRoot(l); (c)=zListCellNext(c) )
	succeed a process for each cell of a list l from the current c to the head. More...
#define	zListToTail(l, c)   for( ; (c)!=zListRoot(l); (c)=zListCellPrev(c) )
	succeed a process for each cell of a list l from the current c to the tail. More...
#define	zListForEach(l, c)   for( (c)=zListTail(l); (c)!=zListRoot(l); (c)=zListCellNext(c) )
	succeed a process for each cell in a list l. Each cell is pointed by c from the tail to the head. More...
#define	zListForEachRew(l, c)   for( (c)=zListHead(l); (c)!=zListRoot(l); (c)=zListCellPrev(c) )
	succeed a process for each cell in a list l. Each cell is pointed by c from the head back to the tail. More...
#define	zListItem(list, i, cp)
	refer the i 'th cell of a list list, and let cp point the cell. More...
#define	zListQuickSortDef(list_t, cell_t)
	define the quick sort method for a list class. More...
#define	zListFPrint(f, l)   _zListFPrint( f, (zList *)(l) )
#define	zListPrint(l)   zListFPrint( stdout, l )
#define	zStackPush(s, v)   zListInsertHead(s,v)
	stack push operation. More...
#define	zStackPop(s, c)   zListDeleteHead(s,c)
	stack pop operation. More...
#define	zQueueEnqueue(q, v)   zListInsertTail(q,v)
	enqueue operation. More...
#define	zQueueDequeue(q, c)   zListDeleteHead(q,c)
	dequeue operation. More...

Typedefs
typedef struct __zListCell	zListCell
typedef struct __zList	zList

Functions
void	_zListFPrint (FILE *fp, zList *list)
	print connection information of a list. More...

Detailed Description

Macro Definition Documentation

zListClass

#define zListClass	(		list_t,
			cell_t,
			data_t
	)

Value:

typedef struct __##cell_t{\
  struct __##cell_t *prev, *next;\
  data_t data;\
} cell_t;\
typedef struct __##list_t{\
  int size;\
  cell_t root;\
} list_t

generate bidirectional ring list class.

A macro zListClass() simultaneously generates a new (bidirectional) list class and a new list cell class.

The list cell class, which is named cell_t has pointers to the previous and the next cells, and the data with a specified type data_t.

The list class, which is named list_t, has a root cell with the type data_t and the number of cells.

zListCellPrev

#define zListCellPrev

(

c

)

(c)->prev

a pointer to the previous cell of c.

zListCellNext

#define zListCellNext

(

c

)

(c)->next

a pointer to the next cell of c.

zListCellSetPrev

#define zListCellSetPrev	(		c,
			p
	)		( zListCellPrev(c) = (p) )

set the previous cell of c for p.

zListCellSetNext

#define zListCellSetNext	(		c,
			n
	)		( zListCellNext(c) = (n) )

set the next cell of c for n.

zListCellInit

#define zListCellInit

(

c

)

Value:

do{\
  zListCellSetNext( c, c ); \
  zListCellSetPrev( c, c ); \
} while(0)

initialize a list cell c.

zListCellBind

#define zListCellBind	(		l,
			f
	)

Value:

do{\
  zListCellSetPrev( f, l ); \
  zListCellSetNext( l, f ); \
} while(0)

bind two list cells l and f. l is the latter, while f is the former.

zListCellInsertNext

#define zListCellInsertNext	(		c,
			n
	)

Value:

do{\
  zListCellBind( n, zListCellNext(c) ); \
  zListCellBind( c, n ); \
} while(0)

insert a list cell n to the next of c.

zListCellInsertPrev

#define zListCellInsertPrev	(		c,
			p
	)

Value:

do{\
  zListCellBind( zListCellPrev(c), p ); \
  zListCellBind( p, c ); \
} while(0)

insert a list cell p to the previous of c.

zListCellPurge

#define zListCellPurge

(

c

)

Value:

do{\
  zListCellBind( zListCellPrev((c)), zListCellNext((c)) ); \
  zListCellInit( (c) ); \
} while(0)

purge a cell c from a list.

zListCellDeleteNext

#define zListCellDeleteNext	(		c,
			n
	)

Value:

do{\
  if( zListCellNext(c) != (c) ){ \
    *(n) = zListCellNext( c ); \
    zListCellPurge( *(n) );\
  } else\
    *(n) = NULL;\
} while(0)

delete the next cell of c from a list. The deleted cell is stored into n.

zListCellDeletePrev

#define zListCellDeletePrev	(		c,
			p
	)

Value:

do{\
  if( zListCellPrev(c) != (c) ){ \
    *(p) = zListCellPrev( c ); \
    zListCellPurge( *(p) );\
  } else\
    *(p) = NULL;\
} while(0)

delete the previous cell from a list. The deleted cell is stored into p.

zListCellSwap

#define zListCellSwap	(		cell_t,
			c1,
			c2
	)

Value:

do{\
  cell_t *__zlist_cell_swap_tmp; \
 \
  __zlist_cell_swap_tmp = zListCellPrev( c1 ); \
  zListCellBind( zListCellPrev(c2), c1 ); \
  zListCellBind( __zlist_cell_swap_tmp, c2 ); \
  __zlist_cell_swap_tmp = zListCellNext( c1 ); \
  zListCellBind( c1, zListCellNext(c2) ); \
  zListCellBind( c2, __zlist_cell_swap_tmp ); \
} while(0)

swap the positions of two list cells c1 and c2. cell_t is the type of list cells.

zListCellFPrint

#define zListCellFPrint	(		f,
			c
	)

Value:

do{\
  fprintf( f, "cell [%p] ", c ); \
  fprintf( f, "%p <- prev | next-> %p\n", \
    zListCellPrev(c), zListCellNext(c) ); \
} while(0)

print connections around a list cell c to the file f.

zListCellPrint

#define zListCellPrint

(

c

)

zListCellFPrint( stdout, c )

print pointing information of a list cell c to the standard output.

zListSize

#define zListSize

(

l

)

(l)->size

the size of a list l.

zListRoot

#define zListRoot

(

l

)

( &(l)->root )

the root cell of a list l.

zListHead

#define zListHead

(

l

)

zListCellPrev( zListRoot( l ) )

the head cell (the previous of the root) of a list l.

zListTail

#define zListTail

(

l

)

zListCellNext( zListRoot( l ) )

the tail cell (the next of the root) of a list l.

zListSetSize

#define zListSetSize	(		l,
			n
	)		( zListSize(l) = (n) )

set the size of a list l for n (unpreferable to be used).

zListIncSize

#define zListIncSize

(

l

)

( zListSize(l)++ )

increment the size of a list l (unpreferable to be used).

zListDecSize

#define zListDecSize

(

l

)

( zListSize(l)-- )

decrement the size of a list l (unpreferable to be used).

zListIsEmpty

#define zListIsEmpty

(

l

)

( zListSize(l) == 0 )

check if a list l is empty.

zListInit

#define zListInit

(

l

)

Value:

do{\
  zListSetSize( l, 0 ); \
  zListCellInit( zListRoot( l ) ); \
} while(0)

initialize a list l.

zListDestroy

#define zListDestroy	(		t,
			l
	)

Value:

do{\
  t *__zlist_destroy_cell = NULL; \
 \
  while( !zListIsEmpty( l ) ){ \
    zListDeleteHead( l, &__zlist_destroy_cell ); \
    zFree( __zlist_destroy_cell ); \
  } \
} while(0)

destroy a list l. t is the type of list cells.

zListInsertNext

#define zListInsertNext	(		l,
			c,
			n
	)

Value:

do{\
  zListCellInsertNext( c, n ); \
  zListIncSize(l); \
} while(0)

insert a list cell n to the next of c in a list l.

zListInsertPrev

#define zListInsertPrev	(		l,
			c,
			p
	)

Value:

do{\
  zListCellInsertPrev( c, p ); \
  zListIncSize(l); \
} while(0)

insert a list cell p to the previous of c in a list l.

zListInsertHead

#define zListInsertHead	(		l,
			c
	)		zListInsertPrev( l, zListRoot(l), c )

insert a list cell c to the head of a list l.

zListInsertTail

#define zListInsertTail	(		l,
			c
	)		zListInsertNext( l, zListRoot(l), c )

insert a list cell c to the tail of a list l.

zListDeleteNext

#define zListDeleteNext	(		l,
			c,
			n
	)

Value:

do{\
  zListCellDeleteNext( c, n ); \
  zListDecSize(l); \
} while(0)

delete the next cell of c of a list l. The deleted cell is stored into n.

zListDeletePrev

#define zListDeletePrev	(		l,
			c,
			p
	)

Value:

do{\
  zListCellDeletePrev( c, p ); \
  zListDecSize(l); \
} while(0)

delete the previous cell of c of a list l. The deleted cell is stored into p.

zListDeleteHead

#define zListDeleteHead	(		l,
			c
	)		zListDeletePrev( l, zListRoot(l), c )

delete the head cell of a list l. The deleted cell is stored into c.

zListDeleteTail

#define zListDeleteTail	(		l,
			c
	)		zListDeleteNext( l, zListRoot(l), c )

delete the tail cell of a list l. The deleted cell is stored into c.

zListPurge

#define zListPurge	(		l,
			c
	)

Value:

do{\
  zListCellPurge( c );\
  zListDecSize(l);\
} while(0)

purge a list cell c in a list l.

zListAppendA

#define zListAppendA	(		a,
			p
	)

Value:

do{\
  if( !zListIsEmpty(p) ){\
    zListCellBind( zListHead(a), zListTail(p) );\
    zListCellBind( zListHead(p), zListRoot(a) );\
    zListSize(a) += zListSize(p);\
    zListInit(p);\
  }\
} while(0)

append all cells in a list p to the head of another list a. As the result, p will be empty.

zListAppendZ

#define zListAppendZ	(		a,
			p
	)

Value:

do{\
  if( !zListIsEmpty(p) ){\
    zListCellBind( zListHead(p), zListTail(a) );\
    zListCellBind( zListRoot(a), zListTail(p) );\
    zListSize(a) += zListSize(p);\
    zListInit(p);\
  }\
} while(0)

append all cells in a list p to the tail of another list a. As the result, p will be empty.

zListAppend

#define zListAppend	(		a,
			p
	)		zListAppendZ(a,p)

zListMove

#define zListMove	(		src,
			dst
	)

Value:

do{\
  zListCellBind( zListRoot(dst), zListTail(src) );\
  zListCellBind( zListHead(src), zListRoot(dst) );\
  zListSetSize( dst, zListSize(src) );\
  zListInit( src );\
} while(0)

move a list to another.

zListSwap

#define zListSwap	(		cell_t,
			l1,
			l2
	)

Value:

do{\
  int __tmpsize;\
  zListCellSwap( cell_t, zListRoot(l1), zListRoot(l2) );\
  __tmpsize = zListSize(l1);\
  zListSetSize( l1, zListSize(l2) );\
  zListSetSize( l2, __tmpsize );\
} while(0)

swap two lists l1 and l2.

zListToHead

#define zListToHead	(		l,
			c
	)		for( ; (c)!=zListRoot(l); (c)=zListCellNext(c) )

succeed a process for each cell of a list l from the current c to the head.

zListToTail

#define zListToTail	(		l,
			c
	)		for( ; (c)!=zListRoot(l); (c)=zListCellPrev(c) )

succeed a process for each cell of a list l from the current c to the tail.

zListForEach

#define zListForEach	(		l,
			c
	)		for( (c)=zListTail(l); (c)!=zListRoot(l); (c)=zListCellNext(c) )

succeed a process for each cell in a list l. Each cell is pointed by c from the tail to the head.

zListForEachRew

#define zListForEachRew	(		l,
			c
	)		for( (c)=zListHead(l); (c)!=zListRoot(l); (c)=zListCellPrev(c) )

succeed a process for each cell in a list l. Each cell is pointed by c from the head back to the tail.

zListItem

#define zListItem	(		list,
			i,
			cp
	)

Value:

do{\
  int __z_list_item_tmp;\
  *(cp) = NULL;\
  if( (i) >= 0 && (i) < zListSize(list) ){\
    if( (i) <= zListSize(list) - (i) ){\
      __z_list_item_tmp = 0;\
      zListForEach( list, *(cp) )\
        if( __z_list_item_tmp++ == (i) ) break;\
    } else{\
      __z_list_item_tmp = zListSize( list );\
      zListForEachRew( list, *(cp) )\
        if( --__z_list_item_tmp == (i) ) break;\
    }\
  }\
} while(0)

refer the i 'th cell of a list list, and let cp point the cell.

zListQuickSortDef

#define zListQuickSortDef	(		list_t,
			cell_t
	)

define the quick sort method for a list class.

zListQuickSortDef() defines a quick sort function for a given list class list_t and a list cell class cell_t. list_t class must stand upon cell_t class.

The function defined will be named 'list_t'QuickSort() with the following prototype.

list_t list_tQuickSort(list_t *list, int (*cmp)(void,void*,void*), void *priv);

The cells of list will be sorted in ascending order according to the comparison function cmp. (The factor a in the list is put after another factor b if cmp(a,b,p) > 0. p is for programmer's utility, given by priv.)

zListFPrint

#define zListFPrint	(		f,
			l
	)		_zListFPrint( f, (zList *)(l) )

zListPrint

#define zListPrint

(

l

)

zListFPrint( stdout, l )

zStackPush

#define zStackPush	(		s,
			v
	)		zListInsertHead(s,v)

stack push operation.

zStackPop

#define zStackPop	(		s,
			c
	)		zListDeleteHead(s,c)

stack pop operation.

zQueueEnqueue

#define zQueueEnqueue	(		q,
			v
	)		zListInsertTail(q,v)

enqueue operation.

zQueueDequeue

#define zQueueDequeue	(		q,
			c
	)		zListDeleteHead(q,c)

dequeue operation.

Typedef Documentation

zListCell

typedef struct __zListCell zListCell

zList

typedef struct __zList zList

Function Documentation

_zListFPrint()

void _zListFPrint	(	FILE *	fp,
		zList *	list
	)

print connection information of a list.

zListFPrint() prints the connection information of a list list to the current position of a file fp with the following form.

number = X

<0> cell [0xXXXXXXXXX]

0xXXXXXXXXA <- prev | next -> 0xXXXXXXXXB

<1> cell [0xXXXXXXXXB]

0xXXXXXXXXX <- prev | next -> 0xXXXXXXXXC

...

zListPrint() is also available to print the information to the standard output.

See also

zListCellFPrint, zListCellPrint