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, 25 insertions, 0 deletions

diff --git a/parser.c b/parser.c
index 584a923a..d8619832 100644
--- a/parser.c
+++ b/parser.c
@@ -336,6 +336,31 @@ tail:
       obj = e;
       goto tail;
     }
+  case TNOD:
+    {
+      val k = obj->tn.key;
+      val l = obj->tn.left;
+      val r = obj->tn.right;
+      val rk = patch_ref(p, k);
+      val rl = patch_ref(p, l);
+      val rr = patch_ref(p, r);
+
+      if (rl)
+        set(mkloc(obj->tn.left, obj), rl);
+      else
+        circ_backpatch(p, &cs, l);
+
+      if (rr)
+        set(mkloc(obj->tn.right, obj), rr);
+      else
+        circ_backpatch(p, &cs, r);
+
+      if (rk)
+        set(mkloc(obj->tn.key, obj), rk);
+
+      obj = k;
+      goto tail;
+    }
   case COBJ:
     if (hashp(obj)) {
       val u = get_hash_userdata(obj);