/*
 * sparse.h - Sparse arrays header file
 *
 */


/* Vanilla constants */
#define SPR_NODD 8		/* Node depth, in levels */
#define SPR_SHFC 4		/* 2 log of # of indexes per node */

/* Extract bit field */
#define SPR_I2X(C,I,F) \
  ( ((I) >> ((F) * (C)->spr_shfc)) & (C)->spr_mask )

/* Sparse array node */
typedef struct _sparse_
  {
    short
      spr_inuse;		/* # of links in use */

    struct _sparse_
      *spr_link[ 1 ];		/* Links */
  }
SPR_NODE;


/* Sparse array header */
typedef struct
 {
   char *spr_id;		/* Identifier/reference */

   short
     spr_nodd,			/* Node depth */
     spr_mask,			/* (1 << (spr_shfc)) - 1 */
     spr_shfc,			/* Shift count */
     spr_inuse;			/* Nodes in use */

   SPR_NODE
     *(*spr_create)(),		/* Node creation (malloc(3) compatible) */
     *spr_top;			/* Top node */

   void
     (*spr_destr)();		/* Node destruction (free(3) compatible) */
 }
SPR_ROOT;


/* Functions */
extern SPR_ROOT
  *spr_open();			/* Create sparse array */

extern char
  *spr_get();			/* Get value */

extern void
  spr_close(),			/* Destroy sparse array */
  spr_unbind(),			/* Unbind slot */
  spr_bind();			/* Bind slot */
