199 lines
5.9 KiB
C
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
|