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

diff --git a/gc.c b/gc.c
index 93004338..93a91267 100644
--- a/gc.c
+++ b/gc.c
@@ -266,6 +266,7 @@ static void finalize(val obj)
   case ENV:
   case FLNUM:
   case RNG:
+  case TNOD:
     return;
   case SYM:
     free(obj->s.slot_cache);
@@ -417,6 +418,10 @@ tail_call:
   case BUF:
     mark_obj(obj->b.len);
     mark_obj_tail(obj->b.size);
+  case TNOD:
+    mark_obj(obj->tn.left);
+    mark_obj(obj->tn.right);
+    mark_obj_tail(obj->tn.key);
   }
 
   assert (0 && "corrupt type field");