| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
* lib.c (copy): Handle tree objects via copy_search_tree.
* tree.c (deep_copy_tnode): New static function.
(copy_search_tree): New function.
(tree_init): copy-search-tree intrinsic registered.
* tree.h (copy_search_tree): Declared.
* txr.1: Documented copy-search-tree, and copy function's use
thereof.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* lisplib.c (defset_set_entries): Autoload entries for left,
right and key.
* share/txr/stdlib/defset.tl (left, right, key): New
simple-form defsets.
* tree.c (set_left, set_right, set_key): New functions.
(tree_init): Register intrinsics set-left, set-right and
set-key.
* tree.h (set_left, set_right, set_key): Declared.
* txr.1: key, left and right classified as accessors.
Documented set-key, set-left and set-right.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
* lib.c (copy): Handle TNOD casee via copy_tnode.
* tree.c (copy_tnode): New function.
(tree_init): copy-tnode intrinsic registered.
* tree.h (copy_tnode): Declared.
* txr.1: copy function documented as handling tnode type via
copy-tnode. That function is documented.
|
| |
|
|
|
|
|
| |
* tree.c (tree_clear): New function.
(tree_init): tree-clear intrinsic registered.
* tree.h (tree_clear): Declared.
|
| |
|
|
|
|
| |
* tree.c (tree_insert_node): Change to external linkage.
* tree.h (tree_insert_node): Declared.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
* 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.
|
| |
|
|
|
| |
* tree.c (treep): new function.
(tree_init): Registered treep intrinsic.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
|
|
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.
|
