treetrie-2015/treetrie.h
2017-06-14 10:36:21 +01:00

199 lines
5.9 KiB
C

#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