treetrie-2015/treetrie.h

#ifndef TREETRIE_H_f55a3f6d_ef43_45d3_bec3_496a196b5db1
#define TREETRIE_H_f55a3f6d_ef43_45d3_bec3_496a196b5db1

#ifdef __cplusplus
extern "C" {
#endif

typedef enum tt_tag_t {
  TT_TAG_INVALID = 0, /* an invalid pointer - should only be used with 0 as index. */
  /* Trie things */
  TT_TAG_TAIL,
  TT_TAG_OK,
  TT_TAG_BRANCH,
  /* Dict things */
  TT_TAG_LEAF, /* node b points to atom, not node */
  TT_TAG_NODE,
  TT_TAG_DICT, /* node b is just an integer */
  /* Generic things */
  TT_TAG_SPECIAL, /* immediate special - all others are pointerlike */
} tt_tag_t;

typedef enum tt_special_idx_t {
  TT_EMPTY_IDX, /* empty treetrie */
  TT_EMPTY_DICT_IDX, /* empty dict */
} tt_special_idx_t;

#define TT_STYLE_UNSTYLED	0x00000000
#define TT_STYLE_TEXT_LABELS	0x00000001
#define TT_STYLE_HIDE_DETAILS	0x00000002

typedef uint32_t tt_node_idx_t; /* N.B. tt_special_idx_t; and 0 is reserved. */
typedef uint32_t tt_node_ptr_t; /* An index shifted left 3 with tag or'd in low bits */

#define TT_NO_IDX		((tt_node_idx_t) (0))
#define TT_NO_PTR		((tt_node_ptr_t) (0))

#define TT_EMPTY		(tt_mkptr(TT_EMPTY_IDX, TT_TAG_SPECIAL))
#define TT_EMPTY_DICT		(tt_mkptr(TT_EMPTY_DICT_IDX, TT_TAG_SPECIAL))

#define TT_NO_PTR_P(x)		((x) == TT_NO_PTR)
#define TT_EMPTY_P(x)		((x) == TT_EMPTY)
#define TT_EMPTY_DICT_P(x)	((x) == TT_EMPTY_DICT)

#define RET_VAL_IF_NO_PTR(v,rv)	\
  ({ tt_node_ptr_t ___w = (v); if (TT_NO_PTR_P(___w)) return (rv); ___w; })

#define RET_IF_NO_PTR(v)	RET_VAL_IF_NO_PTR(v,TT_NO_PTR)

typedef uint32_t tt_atom_t; /* Atom number 0 is the wildcard atom. */

typedef uint32_t tt_hash_t;

typedef union tt_header_t {
  tt_node_idx_t next_free;
  struct {
    uint32_t refcount : 24;
    uint32_t index : 8; /* this really doesn't need to be more than 5 or 6 bits wide */
  } inuse;
} tt_header_t;

#define TT_REFCOUNT_LIMIT ((1 << 24) - 1)

typedef struct tt_node_t {
  tt_node_ptr_t a; /* always a real node ptr */
  tt_node_ptr_t b; /* usually a real node ptr; see definition of tt_tag_t */
} tt_node_t;

typedef struct tt_free_chain_t {
  tt_node_idx_t head; /* remove links from here */
  tt_node_idx_t tail; /* append links here */
} tt_free_chain_t;

typedef struct tt_hashtable_entry_t {
  tt_hash_t hash;
  tt_node_ptr_t ptr;
} tt_hashtable_entry_t;

typedef struct tt_arena_t {
  void *atom_context;
  void (*atom_incref)(void *atom_context, struct tt_arena_t *a, tt_atom_t atom);
  void (*atom_decref)(void *atom_context, struct tt_arena_t *a, tt_atom_t atom);

  /* Fields for the Robin Hood hashset used for hashconsing of tt_nodes */
  unsigned int max_probe;
  unsigned int table_length;
  tt_hashtable_entry_t *table;

  tt_header_t *headers;
  tt_node_t *nodes;

  unsigned int free_count;
  tt_free_chain_t free_chain;
} tt_arena_t;

static inline tt_node_ptr_t tt_mkptr(tt_node_idx_t i, tt_tag_t tag) {
  return (i << 3) | tag;
}

static inline tt_node_idx_t tt_ptr_idx(tt_node_ptr_t p) {
  return p >> 3;
}

static inline tt_tag_t tt_ptr_tag(tt_node_ptr_t p) {
  return p & 7;
}

extern int tt_arena_init(tt_arena_t *a,
			 void *atom_context,
			 void (*atom_incref)(void *atom_context, tt_arena_t *a, tt_atom_t atom),
			 void (*atom_decref)(void *atom_context, tt_arena_t *a, tt_atom_t atom));

extern void tt_arena_done(tt_arena_t *a);

extern void tt_dump_arena_summary(tt_arena_t *a);
extern void tt_dump_arena(tt_arena_t *a, int show_free_chain);
extern void tt_dump_arena_dot_styled(char const *rootlabel,
				     tt_node_ptr_t rootptr,
				     tt_arena_t *a,
				     int flags);
extern void tt_dump_arena_dot(char const *rootlabel, tt_node_ptr_t rootptr, tt_arena_t *a);

extern void tt_arena_flush(tt_arena_t *a);

/* Returns TT_NO_PTR if consing failed (because of out-of-memory).
   Grabs na and nb (according to tag) IF it needs to allocate a new node, otherwise does not.
   DOES NOT increase the reference count of the returned node. */
extern tt_node_ptr_t tt_arena_cons(tt_arena_t *a,
				   uint32_t tag,
				   uint32_t index,
				   tt_node_ptr_t na,
				   tt_node_ptr_t nb);

extern tt_node_ptr_t tt_grab(tt_arena_t *a, tt_node_ptr_t i);
extern void tt_drop(tt_arena_t *a, tt_node_ptr_t i);

static inline tt_node_ptr_t tt_cons_tail(tt_arena_t *a, tt_node_ptr_t p) {
  /* p should point to a trie */
  return tt_arena_cons(a, TT_TAG_TAIL, 0, p, TT_NO_PTR);
}

static inline tt_node_ptr_t tt_cons_ok(tt_arena_t *a, tt_node_ptr_t p) {
  /* p should point to a dict */
  return tt_arena_cons(a, TT_TAG_OK, 0, p, TT_NO_PTR);
}

static inline tt_node_ptr_t tt_cons_branch(tt_arena_t *a,
					   tt_node_ptr_t wildcard, /* trie */
					   tt_node_ptr_t others) /* dict */
{
  return tt_arena_cons(a, TT_TAG_BRANCH, 0, wildcard, others);
}

static inline tt_node_ptr_t tt_cons_leaf(tt_arena_t *a, tt_node_ptr_t p, tt_atom_t atom) {
  return tt_arena_cons(a, TT_TAG_LEAF, 0, p, atom);
}

static inline tt_node_ptr_t tt_cons_node(tt_arena_t *a,
					 unsigned int index,
					 tt_node_ptr_t zero,
					 tt_node_ptr_t one)
{
  return tt_arena_cons(a, TT_TAG_NODE, index, zero, one);
}

static inline tt_node_ptr_t tt_cons_dict(tt_arena_t *a, tt_node_ptr_t p, uint32_t size) {
  return tt_arena_cons(a, TT_TAG_DICT, 0, p, size);
}

static inline tt_node_ptr_t tt_left(tt_arena_t *a, tt_node_ptr_t p) {
  return a->nodes[tt_ptr_idx(p)].a;
}

static inline tt_node_ptr_t tt_right(tt_arena_t *a, tt_node_ptr_t p) {
  return a->nodes[tt_ptr_idx(p)].b;
}

#define TT_TAIL_TRIE(a,p) tt_left(a,p)
#define TT_OK_DICT(a,p) tt_left(a,p)
#define TT_BRANCH_WILDCARD(a,p) tt_left(a,p)
#define TT_BRANCH_OTHERS(a,p) tt_right(a,p)
#define TT_LEAF_TRIE(a,p) tt_left(a,p)
#define TT_LEAF_ATOM(a,p) ((tt_atom_t) tt_right(a,p))
#define TT_NODE_INDEX(a,p) (a->headers[tt_ptr_idx(p)].inuse.index)
#define TT_NODE_ZERO(a,p) tt_left(a,p)
#define TT_NODE_ONE(a,p) tt_right(a,p)
#define TT_DICT_ROOT(a,p) tt_left(a,p)
#define TT_DICT_SIZE(a,p) ((uint32_t) tt_right(a,p))

static inline void tt_replace(tt_arena_t *a, tt_node_ptr_t *target, tt_node_ptr_t newval) {
  tt_grab(a, newval);
  tt_drop(a, *target);
  *target = newval;
}

#ifdef __cplusplus
}
#endif

#endif