zeda_list.h

Go to the documentation of this file.

/* ZEDA - Elementary Data and Algorithms
 * Copyright (C) 1998 Tomomichi Sugihara (Zhidao)
 */
#ifndef __ZEDA_LIST_H__
#define __ZEDA_LIST_H__

#include <zeda/zeda_misc.h>

__BEGIN_DECLS

/* ********************************************************** *//* ************************************************** */

/* ********************************************************** *//* ******************************************************* */

#ifdef __cplusplus
#define zListClass(list_t,cell_t,data_t) \
struct cell_t{\
  cell_t *prev, *next;\
  data_t data;\
  cell_t(){ prev = next = this; };\
};\
struct list_t{\
  int size;\
  cell_t root;\
  list_t(){ size = 0; };\
}
#else
#define zListClass(list_t,cell_t,data_t) \
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
#endif /* __cplusplus */

/* dummy list cell class */
zListClass(zList, zListCell, void*);

#define zListCellPrev(c)       (c)->prev

#define zListCellNext(c)       (c)->next

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

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

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

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

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

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

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

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

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

#define zListCellSwap(cell_t,c1,c2) 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)

#ifndef __KERNEL__

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

#define zListCellPrint(c)  zListCellFPrint( stdout, c )
#else
#define zListCellPrint(c) do{\
  printk( "cell [%p] ", c ); \
  printk( "%p <- prev | next-> %p\n", \
    zListCellPrev(c), zListCellNext(c) ); \
} while(0)
#endif /* __KERNEL__ */

/* ********************************************************** */
/* bidirectional ring list structure
 * ********************************************************** */

#define zListSize(l)     (l)->size

#define zListRoot(l)     ( &(l)->root )

#define zListHead(l)     zListCellPrev( zListRoot( l ) )

#define zListTail(l)     zListCellNext( zListRoot( l ) )

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

#define zListIncSize(l)   ( zListSize(l)++ )

#define zListDecSize(l)   ( zListSize(l)-- )

#define zListIsEmpty(l)   ( zListSize(l) == 0 )

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

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

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

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

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

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

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

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

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

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

#define zListPurge(l,c) do{\
  zListCellPurge( c );\
  zListDecSize(l);\
} while(0)

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

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

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

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

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

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

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

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

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

#define zListItem(list,i,cp) 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)

#define zListQuickSortDef(list_t, cell_t) \
static void _##list_t##InnerQuickSort(cell_t *head, cell_t *tail, int (*cmp)(void*,void*,void*), void *priv);\
void _##list_t##InnerQuickSort(cell_t *head, cell_t *tail, int (*cmp)(void*,void*,void*), void *priv)\
{\
  cell_t *hp, *tp, *pivot, *p;\
\
  for( pivot=hp=head, tp=tail; ; ){\
    /* choose a pivot for the head value */\
    while( cmp( (void *)hp, (void *)pivot, priv ) > 0 && hp != tail )\
      hp = zListCellPrev( hp );\
    while( cmp( (void *)tp, (void *)pivot, priv ) < 0 && tp != head )\
      tp = zListCellNext( tp );\
    if( hp == tp || hp == zListCellPrev( tp ) )\
      break;\
    zListCellSwap( cell_t, hp, tp );\
    /* if head or tail is swapped, it should be renewed. */\
    if( hp == head ) head = tp;\
    if( tail == tp ) tail = hp;\
    p = zListCellNext( hp );\
    hp = zListCellPrev( tp );\
    tp = p;\
  }\
  if( hp != head )\
    _##list_t##InnerQuickSort( head, zListCellNext(hp), cmp, priv );\
  if( tp != tail )\
    _##list_t##InnerQuickSort( zListCellPrev(tp), tail, cmp, priv );\
}\
\
list_t *list_t##QuickSort(list_t *list, int (* cmp)(void*,void*,void*), void *priv)\
{\
  _##list_t##InnerQuickSort( zListHead(list), zListTail(list), cmp, priv );\
  return list;\
}

#ifndef __KERNEL__
__EXPORT void _zListFPrint(FILE *fp, zList *list);
#define zListFPrint(f,l) _zListFPrint( f, (zList *)(l) )
#define zListPrint(l)    zListFPrint( stdout, l )
#else
void zListPrint(zList *list);
#endif /* __KERNEL__ */

/* zStack/zQueue alias */

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

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

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

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

zListClass(zIntList, zIntListCell, int);

__EXPORT bool zIntListAdd(zIntList *list, int i);

__END_DECLS

#endif /* __ZEDA_LIST_H__ */