/* $Id: vca.h 140 1999-12-03 13:08:15Z clerger $
 * Copyright (C) 1996 Eric de la Clergerie
 * ------------------------------------------------------------
 *
 *   VCA -- Header of CLib/vca.c
 *
 * ------------------------------------------------------------
 * Description
 *
 *      struct vca        : a tree and a length
 *      struct vcatree    : binary trees
 *      struct entrytable : table of entries (and leaf of vcatree)
 *
 * Parameters
 *      USER_MALLOC       : the allocation procedure
 *      ENTRY_SHIFT       : number of entries by table 
 *      ENTRY_TYPE        : entry type
 * ------------------------------------------------------------
 */

#ifndef VCA_READ
#define VCA_READ

/***********************************************************************
 *                          Parameters
 **********************************************************************/

#ifndef USER_MALLOC
     #define USER_MALLOC( _size ) GC_MALLOC( _size )
#endif

#ifndef ENTRY_SHIFT
     #define ENTRY_SHIFT   5
#endif
    
#define ENTRY_MAX    ( 1 << ENTRY_SHIFT )
#define ENTRY_MASK   ( ENTRY_MAX - 1 )

#ifndef ENTRY_TYPE
     #define ENTRY_TYPE void
#endif

/***********************************************************************
 *                         Type declarations 
 **********************************************************************/

typedef ENTRY_TYPE *entry_t;

typedef struct vcatree {

  struct vcatree *left;
  struct vcatree *right;

} *vcatree_t;

typedef struct entrytable {
  unsigned long count;
  entry_t table[ENTRY_MAX];
} *entrytable_t;

typedef struct vca {
  unsigned long  length;
  vcatree_t      tree;
} *vca_t;

/***********************************************************************
 *                         VCA's
 **********************************************************************/

#define VCA_SIZE     (sizeof( struct vca ))

#define VCA_NEW						\
        ({ vca_t v = (vca_t) USER_MALLOC( VCA_SIZE );	\
	    v->length = 0;				\
	    v->tree   = VCATREE_NULL;			\
	    v; })

#define VCA_LENGTH( _vca )   ( _vca->length )
#define VCA_SAFE_LENGTH( _vca ) ( _vca ? _vca->length : 0 )
#define VCA_IN( _vca, n)     ( n < VCA_LENGTH( _vca ))
#define VCA_NULL_P( _vca )   ( !_vca || _vca->length == 0)

/***********************************************************************
 *                         VCATREE's
 **********************************************************************/

#define VCATREE_SIZE (sizeof( struct vcatree ))

#define VCATREE_MAKE( _t1, _t2)						\
        ({ vcatree_t node = (vcatree_t) USER_MALLOC( VCATREE_SIZE );	\
	    VCATREE_L( node ) = _t1;					\
	    VCATREE_R( node ) = _t2;					\
	    node; })

#define VCATREE_MAKE_EMPTY				\
        ( VCATREE_MAKE( VCATREE_NULL , VCATREE_NULL ) )

#define VCATREE_NULL         ( (vcatree_t) 0 )
#define VCATREE_NULL_P( _t ) ( _t ==  VCATREE_NULL )
#define VCATREE_L_P( n, h )  ( (n & h) == 0 )
#define VCATREE_R_P( n, h )  ( (n & h) != 0 )

#define VCATREE_L( t )       (  (t)->left  )
#define VCATREE_R( t )       (  (t)->right )

#define VCATREE_SEL( tree, n, h)			\
        ( VCATREE_L_P( n, h) ? VCATREE_L( tree )	\
	                     : VCATREE_R( tree ) )
  
#define VCATREE_EXTEND( n, e)				\
        ( ( n % 2) ?  VCATREE_MAKE( VCATREE_NULL, e)	\
	           : VCATREE_MAKE( e , VCATREE_NULL) )

/***********************************************************************
 *                         ENTRY TABLE's
 **********************************************************************/

#define ENTRYTAB_SIZE        (sizeof( struct entrytable ))

#define ENTRYTAB_MAKE								\
     ({ entrytable_t entrytab = (entrytable_t) USER_MALLOC( ENTRYTAB_SIZE );	\
        entrytab->count=0;							\
	entrytab; })							
 
#define ENTRYTAB_REF( _tab, i)     ((entrytable_t) _tab)->table[i]
#define ENTRYTAB_COUNT( _tab )     ((entrytable_t) _tab)->count
#define ENTRYTAB_NULL_P( _tab )    ( ENTRYTAB_COUNT( _tab ) == 0        )

#define ENTRYTAB_SET( _tab, i, o)				\
	    ({ if ( !ENTRYTAB_REF( _tab, i)) ++((entrytable_t) _tab)->count;	\
	       ENTRYTAB_REF( _tab, i) = (entry_t) o; })

#define ENTRY_UP(  k )             ((unsigned long)( k >> ENTRY_SHIFT ))
#define ENTRY_DOWN( k )            ((unsigned long)( k & ENTRY_MASK  ))

/***********************************************************************
 *                         EXPORTATIONS
 **********************************************************************/

/* extern entry_t vca_ref(   vca_t, unsigned long ); */
extern void    vca_set(   vca_t, unsigned long, entry_t );
extern void    vca_reset( vca_t, unsigned long );
extern vca_t   vca_merge( vca_t , vca_t );

extern long vca_stat_ref, vca_stat_in, vca_stat_down;

inline extern
entry_t
vca_ref( vca_t v, unsigned long n)
{
  unsigned long h,up;

  if ( v && (up = ENTRY_UP( n )) < (h = v->length) ) {

    vcatree_t tree = v->tree;

    /* WARNING: we assume that if h=1 then v->tree is not empty
       this is the case if v is correctly normalized */
    
    do 
      if ((h >>= 1) == 0)   /* leaf with non empty entry table */
	return ENTRYTAB_REF( tree, ENTRY_DOWN( n ));
    while ((tree = VCATREE_SEL(tree, up, h)));
  }

  /* no entry found */
  return 0;

}



#endif /* VCA_READ */