diff options
author | Kaz Kylheku <kaz@kylheku.com> | 2019-10-03 17:31:01 -0700 |
---|---|---|
committer | Kaz Kylheku <kaz@kylheku.com> | 2019-10-03 17:31:01 -0700 |
commit | 8660816e37a7a169ec41d50d9067b3889c9a6186 (patch) | |
tree | 466ec77e369115cd6f3831158f66c8262fa3a1fd | |
parent | f58f6224e6276f729a4d29732543530d561e2020 (diff) | |
download | txr-8660816e37a7a169ec41d50d9067b3889c9a6186.tar.gz txr-8660816e37a7a169ec41d50d9067b3889c9a6186.tar.bz2 txr-8660816e37a7a169ec41d50d9067b3889c9a6186.zip |
tree: tree iterators.
* tree.c (struct tree_diter): New struct type.
(tree_iter_s): New symbol variable.
(tree_iter_mark): New static function.
(tree_iter_ops): New static struct.
(tree_begin, tree_next): New functions.
(tree_init): Initialize tree_iter_s; register tree-begin and
tree-next intrinsics.
* tree.h (tree_begin, tree_next): Declared.
-rw-r--r-- | tree.c | 55 | ||||
-rw-r--r-- | tree.h | 2 |
2 files changed, 56 insertions, 1 deletions
@@ -76,9 +76,15 @@ struct tree_iter { val path[TREE_DEPTH_MAX]; }; +struct tree_diter { + struct tree_iter ti; + struct tree *tr; + val lastnode; +}; + #define tree_iter_init() { 0, tr_visited_nothing } -val tree_s, tree_fun_whitelist_s; +val tree_s, tree_iter_s, tree_fun_whitelist_s; val tnode(val key, val left, val right) { @@ -599,9 +605,54 @@ val treep(val obj) return tnil(type(obj) == COBJ && obj->co.cls == tree_s); } +static void tree_iter_mark(val tree_iter) +{ + struct tree_diter *tdi = coerce(struct tree_diter *, tree_iter->co.handle); + int i; + + for (i = 0; i < tdi->ti.depth; i++) + gc_mark(tdi->ti.path[i]); + + gc_mark(tdi->lastnode); +} + +static struct cobj_ops tree_iter_ops = cobj_ops_init(eq, + cobj_print_op, + cobj_destroy_free_op, + tree_iter_mark, + cobj_eq_hash_op); + +val tree_begin(val tree) +{ + val self = lit("tree-begin"); + struct tree *tr = coerce(struct tree *, cobj_handle(self, tree, tree_s)); + struct tree_diter *tdi = coerce(struct tree_diter *, + chk_calloc(1, sizeof *tdi)); + tdi->tr = tr; + tdi->lastnode = tr->root; + + return cobj(coerce(mem_t *, tdi), tree_iter_s, &tree_iter_ops); +} + +val tree_next(val iter) +{ + val self = lit("tree-next"); + struct tree_diter *tdi = coerce(struct tree_diter *, + cobj_handle(self, iter, tree_iter_s)); + + if (tdi->lastnode) { + val node = tn_find_next(tdi->lastnode, &tdi->ti); + set(mkloc(tdi->lastnode, iter), node); + return node; + } + + return nil; +} + void tree_init(void) { tree_s = intern(lit("tree"), user_package); + tree_iter_s = intern(lit("tree-iter"), user_package); tree_fun_whitelist_s = intern(lit("*tree-fun-whitelist*"), user_package); reg_fun(tnode_s, func_n3(tnode)); reg_fun(intern(lit("left"), user_package), func_n1(left)); @@ -616,5 +667,7 @@ void tree_init(void) reg_fun(intern(lit("tree-lookup"), user_package), func_n2(tree_lookup)); reg_fun(intern(lit("tree-delete"), user_package), func_n2(tree_delete)); reg_fun(intern(lit("tree-root"), user_package), func_n1(tree_root)); + reg_fun(intern(lit("tree-begin"), user_package), func_n1(tree_begin)); + reg_fun(intern(lit("tree-next"), user_package), func_n1(tree_next)); reg_var(tree_fun_whitelist_s, list(identity_s, equal_s, less_s, nao)); } @@ -36,4 +36,6 @@ val right(val node); val key(val node); val tree(val keys, val key_fn, val less_fn, val equal_fn); val treep(val obj); +val tree_begin(val tree); +val tree_next(val iter); void tree_init(void); |