New data structure: binary search trees.

Adding binary search trees based on the new tnode cell.  The
scapegoat algorithm is used, which requires no additional
storage in a cell. In the future we may go to something else,
like red-black trees, and carve out a bit in the tag field
of the cell for the red/black color.

Tree cells store only single key objects, not key/value pairs.

However, which part of the key object is compared is
determined by a custom key function stored in the tree
container. For instance, tree nodes can be cons cells, and car
can be used as the key function; the cdr then stores an
associated value.

Trees have a printed notation

  #T(<props> <key>*)

where <props> is a list of up to three items:

  <props> ::= ([<key-fn> [<less-fn> [<equal-fn>]]])

key-fn, less-fn and equal-fn are function names.
If they are missing or nil, they default, respectively, to
identity, less and equal.

For security, the printed notation is machine-readable only if
these options are symbols, not lambda expressions.
Furthermore, the symbols must be listed in the special
variable *tree-fun-whitelist*.

* eval.c (less_s): New symbol variable.
(eval_init): Initialize less_s.

* eval.h (less_s): Declard.

* parser.h (grammar): New #T token recognized, mapped to
HASH_T.

* parser.y (HASH_T): New terminal symbol.
(tree): New non-terminal symbol.
(i_expr, n_expr): Add tree to productions.
(fname_helper): New static function.
(yybadtoken): Map HASH_T to "#T".

* protsym.c: Tweaked accidentally; remove.

* tree.c (TREE_DEPTH_MAX): New macro.
(struct tree): New struct type.
(enum tree_iter_state): New enumeration.
(struct tree_iter): New struct type.
(tree_iter_init): New macro.
(tree_s, tree_fun_whitelist_s): New symbol variables.
(tn_size, tn_size_one_child, tn_lookup, tn_find_next,
tn_flatten, tn_build_tree, tr_rebuild,
tr_find_rebuild_scapegoat, tr_insert, tr_lookup, tr_do_delete,
tr_delete, tree_insert_node, tree_insert, tree_lookup_node,
tree_lookup, tree_delete, tree_root, tree_equal_op,
tree_print_op, tree_mark, tree_hash_op): New static functions.
(tree_ops): New static struct.
(tree): New function.
(tree_init): Initialize tree_s and tree_fun_whitelist_s symbol
variables.  Register intrinsic functions tree,
tree-insert-node, tree-insert, tree-lookup-node, tree-lookup,
tree-delete, tree-root. Register special variable
*tree-fun-whitelist*.

* tree.h (tree_s, tree_fun_whitelist_s, tree): Declared.
(tree_fun_whitelist): New macro.

1 files changed, 2 insertions, 1 deletions

diff --git a/eval.c b/eval.c
index a2b60120..0530b476 100644
--- a/eval.c
+++ b/eval.c
@@ -81,7 +81,7 @@ val sys_mark_special_s;
 val caseq_s, caseql_s, casequal_s;
 val caseq_star_s, caseql_star_s, casequal_star_s;
 val memq_s, memql_s, memqual_s;
-val eq_s, eql_s, equal_s;
+val eq_s, eql_s, equal_s, less_s;
 val car_s, cdr_s, not_s, vecref_s;
 val setq_s, setqf_s, sys_lisp1_value_s, sys_lisp1_setq_s;
 val sys_l1_val_s, sys_l1_setq_s;
@@ -6165,6 +6165,7 @@ void eval_init(void)
   eq_s = intern(lit("eq"), user_package);
   eql_s = intern(lit("eql"), user_package);
   equal_s = intern(lit("equal"), user_package);
+  less_s = intern(lit("less"), user_package);
   if_s = intern(lit("if"), user_package);
   when_s = intern(lit("when"), user_package);
   usr_var_s = intern(lit("var"), user_package);