/* $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 */