New data type: tnode.

Binary search tree nodes are being added as a basic heap data
type. The C type tag is TNOD, and the Lisp type is tnode.

Binary search tree nodes have three elements: a key, a left
child and a right child.

The printed notation is #N(key left right). Quasiquoting
is supported: ^#N(,foo ,bar) but not splicing.

Because tnodes have three elements, they they fit into TXR's
four-word heap cell, not requiring any additional memory
allocation.

These nodes are going to be the basis for a binary search tree
container, which will use the scapegoat tree algorithm for
maintaining balance.

* tree.c, tree.h: New files.

* Makefile (OBJS): Adding tree.o.

* eval.c (expand_qquote_rec): Recurse through tnode cells,
so unquotes work inside #N syntax.

* gc.c (finalize): Add TNOD to no-op case in switch; tnodes
don't require finalization.
(mark_obj): Traverse tnode cell.

* hash.c (equal_hash): Add TNOD case.

* lib.c (tnode_s): New symbol variable.
(seq_kind_tab): New entry for TNOD, mapping to SEQ_NOTSEQ.
(code2type, equal): Handle TNOD.
(obj_init): Initialize tnode_s variable.
(obj_print_impl, populate_obj_hash): Handle TNOD.
(init): Call tree_init function in tree.c.

* lib.h (enum type, type_t): New enumeration TNOD.
(struct tnod): New struct type.
(union obj, obj_t): New union member tn of type struct tnod.
(tnode_s): Declard.

* parserc.c (circ_backpatch): Handle TNOD, so circular
notation works through tnode cells.

* parser.l (grammar): Recognize #N prefix, mapping to
HASH_N token.

* parser.y (HASH_N): New grammar terminal symbol.
(tnode): New nonterminal symbol.
(i_expr, n_expr): Add tnode cases to productions.
(yybadtoken): Map HASH_N to "#N" string.

1 files changed, 6 insertions, 0 deletions

diff --git a/eval.c b/eval.c
index 0058b961..a2b60120 100644
--- a/eval.c
+++ b/eval.c
@@ -54,6 +54,7 @@
 #include "struct.h"
 #include "cadr.h"
 #include "filter.h"
+#include "tree.h"
 #include "vm.h"
 #include "eval.h"
 
@@ -3464,6 +3465,11 @@ static val expand_qquote_rec(val qquoted_form, val qq, val unq, val spl)
     val frexp = expand_qquote(from(qquoted_form), qq, unq, spl);
     val toexp = expand_qquote(to(qquoted_form), qq, unq, spl);
     return rlcp(list(rcons_s, frexp, toexp, nao), qquoted_form);
+  } else if (tnodep(qquoted_form)) {
+    val kyexp = expand_qquote(key(qquoted_form), qq, unq, spl);
+    val leexp = expand_qquote(left(qquoted_form), qq, unq, spl);
+    val riexp = expand_qquote(right(qquoted_form), qq, unq, spl);
+    return rlcp(list(tnode_s, kyexp, leexp, riexp, nao), qquoted_form);
   } else if (atom(qquoted_form)) {
     return cons(quote_s, cons(qquoted_form, nil));
   } else {