summaryrefslogtreecommitdiffstats
path: root/tree.c
Commit message (Collapse)AuthorAgeFilesLines
* tree: new functions for priority queue operation.Kaz Kylheku2021-12-181-0/+62
| | | | | | | | | | | | | | | | * tree.c (tree_min_node, tree_min, tree_del_min_node, tree_del_min): New functions. (tree_init): tree-min-node, tree-min, tree-del-min-node, tree-del-min: New intrinsics registered. * tree.h (tree_min_node, tree_min, tree_del_min_node, tree_del_min): Declared. * txr.1: Documented. * tests/010/tree.tl: New tests. * stdlib/doc-syms.tl: Updated.
* tree: bugfix wrong tree-count.Kaz Kylheku2021-12-181-2/+4
| | | | | | | | | | | | | When duplicate keys are inserted in the default way with replacement, the tree size must not be incremented. * tree.c (tr_insert): Increment the tr->size and maintain tr->max_size here. In the case of replacing an existing node, do not touch the count. * tests/010/tree.tl: Add test cases covering duplicate insertion and tree-count. (tree_insert_node): Remove unconditional size increment.
* tree: support for duplicate keys.Kaz Kylheku2021-12-171-14/+117
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * tree.c (tr_insert): New argument for allowing duplicate. If it is true, suppresses the case of replacing a node, causing the logic to fall through to traversing right, so the duplicate key effectively looks like it is greater than the existing duplicates, and gets inserted as the rightmost duplicate. (tr_do_delete_specific, tr_delete_specific): New static functions. (tree_insert_node): New parameter, passed to tr_insert. (tree_insert): New parameter, passed to tree_insert_node. (tree_delete_specific_node): New function. (tree): New parameter to allow duplicate keys in the elements sequence. (tree_construct): Pass t to tree to allow duplicate elements. (tree_init): Update registrations of tree, tree-insert and tree-insert-node. Register tree-delete-specific-node function. * tree.h (tree, tree_insert_node, tree_insert): Declarations updated. (tree_delete_specific_node): Declared. * lib.c (seq): Pass t argument to tree_insert, allowing duplicates. * parser.c (circ_backpatch): Likewise. * parser.y (tree): Pass t to new argument of tree, so duplicates are preserved in the element list of the #T literal. * y.tab.c.shipped: Updated. * tests/010/tree.tl: Test cases for duplicate keys. * txr.1: Documented. * stdlib/doc-syms.tl: Updated.
* tree-count: new function.Kaz Kylheku2021-12-171-0/+8
| | | | | | | | | | | | | * tree.c (tree_count): New function. (tree_init): tree-count intrinsic registered. * tree.h (tree_count): Declared. * lib.c (length): Support search tree argument via tree_count. * tests/010/tree.tl: Test cases for tree-count, indirectly via len. * txr.1: Documented.
* license: reformat to fit 80 columns.Kaz Kylheku2021-08-161-12/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Makefile, alloca.h, args.c, args.h, arith.c, arith.h, buf.c, buf.h, chksum.c, chksum.h, chksums/crc32.c, chksums/crc32.h, combi.c, combi.h, debug.c, debug.h, eval.c, eval.h, ffi.c, ffi.h, filter.c, filter.h, ftw.c, ftw.h, gc.c, gc.h, glob.c, glob.h, hash.c, hash.h, itypes.c, itypes.h, jmp.S, lib.c, lib.h, lisplib.c, lisplib.h, match.c, match.h, parser.c, parser.h, parser.l, parser.y, rand.c, rand.h, regex.c, regex.h, signal.c, signal.h, socket.c, socket.h, stdlib/asm.tl, stdlib/awk.tl, stdlib/build.tl, stdlib/compiler.tl, stdlib/constfun.tl, stdlib/conv.tl, stdlib/copy-file.tl, stdlib/debugger.tl, stdlib/defset.tl, stdlib/doloop.tl, stdlib/each-prod.tl, stdlib/error.tl, stdlib/except.tl, stdlib/ffi.tl, stdlib/getopts.tl, stdlib/getput.tl, stdlib/hash.tl, stdlib/ifa.tl, stdlib/keyparams.tl, stdlib/match.tl, stdlib/op.tl, stdlib/optimize.tl, stdlib/package.tl, stdlib/param.tl, stdlib/path-test.tl, stdlib/pic.tl, stdlib/place.tl, stdlib/pmac.tl, stdlib/quips.tl, stdlib/save-exe.tl, stdlib/socket.tl, stdlib/stream-wrap.tl, stdlib/struct.tl, stdlib/tagbody.tl, stdlib/termios.tl, stdlib/trace.tl, stdlib/txr-case.tl, stdlib/type.tl, stdlib/vm-param.tl, stdlib/with-resources.tl, stdlib/with-stream.tl, stdlib/yield.tl, stream.c, stream.h, struct.c, struct.h, strudel.c, strudel.h, sysif.c, sysif.h, syslog.c, syslog.h, termios.c, termios.h, time.c, time.h, tree.c, tree.h, txr.c, txr.h, unwind.c, unwind.h, utf8.c, utf8.h, vm.c, vm.h, vmop.h: License reformatted. * lex.yy.c.shipped, y.tab.c.shipped, y.tab.h.shipped: Updated.
* gc: problem in several object copying functions.Kaz Kylheku2021-07-291-3/+1
| | | | | | | | | | | | | | | | | | The functions copy-cons, copy-tree, copy-fun and copy-tnode have a problem. They copy the original object bitwise with a structure assignment, and then make some adjustments. The problem is that this inappropriately copies the object's metadata related to gc, such as its generation number or finalization count. To fix this, we introduce a copy_obj function, which is a companion to make_obj. This performs a shallow copy of an object without incorrectly propagating inappropriate metadata. * gc.c, gc.h (copy_obj): New function. * lib.c (copy_fun, copy_cons, copy_tree): Use copy_obj, instead of make_obj plus structure assignment. * tree.c (copy_tnode): Likewise.
* type: disallow structs using built-in type names.Kaz Kylheku2021-07-081-25/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a big commit motivated by the need to clean up the situation with built-in type symbols, COBJ objects and structs. The struct type system allows struct types to be defined for symbols like regex or str, which are used by built-in or cobj types. This is a bad thing. What is worse, structure instances are COBJ types which identify their type using the COBJ class symbol mechanism. There are places in the C implementation which assume that when a COBJ has a certain class symbol, it is of a certain expected type, which is totally different from and incompatible form a struct instance. User code can define a structure object which will fool that code. There are multiple things going on in this patch. The major theme is that the COBJ representation is changing. Instead of a class symbol, COBJ instances now carry a "struct cobj_class *" pointer. This pointer is obtained by registration via the cobj_register function. All modules must register their class symbols to obtain these class handles, which are then used in cobj() calls for instantiation. The CPTR type was identical to COBJ until now, except for the type tag. This is changing; CPTR objects will keep the old representation with the class symbol. commit 20fdfc6008297001491308849c17498c006fe7b4 Author: Kaz Kylheku <kaz@kylheku.com> Date: Thu Jul 8 19:17:39 2021 -0700 * ffi.h (carray_cls): Declared. * hash.h (hash_cls): Declared. (hash_early_init): Declared. * lib.h (struct cobj_class): New struct. (struct cobj): cls member changing to struct cobj_class *. (struct cptr): New struct, same as previous struct cobj. (union obj): New member cp of type struct cptr, for CPTR. (builtin_type): Declared. (class_check): Declaration moved closer to COBJ-related functions and updated. (cobj_register, cobj_register_super, cobj_class_exists): New functions declared. (cobjclassp, cobj_handle, cobj_ops): Declarations updated. * parser.h (parser_cls): Declared. * rand.h (random_state_cls): Declared. * regex.h (regex_cls): Declared. * stream.h (stream_cls, stdio_stream_cls): Declared. * struct.h (struct_cls): Declared. * tree.h (tree_cls, tree_iter_cls): Declared. * vm.h (vm_desc_cls): Declared. * buf.c (buf_strm, make_buf_stream): Pass stream_cls functions instead of stream_s class symbol. * chksum.c (sha256_ctx_cls, md5_ctx_cls): New static class handles. (sha256_begin, sha256_hash, sha256_end, md5_begin, md5_hash, md5_end): Pass class handles to instead of class symbols. (chksum_init): Initialize class handle variables. * ffi.c (ffi_type_cls, ffi_call_desc_cls, ffi_closure_cls, union_cls): New static class handles. (carray_cls): New global variable. (ffi_type_struct_checked, ffi_type_print_op, ffi_closure_struct_checked, ffi_closure_print_op, make_ffi_type_builtin, make_ffi_type_pointer, make_ffi_type_struct, make_ffi_type_union, make_ffi_type_array, make_ffi_type_enum, ffi_call_desc_checked, ffi_call_desc_print_op, ffi_make_call_desc, ffi_make_closure, carray_struct_checked, carray_print_op, make_carray, cptr_getobj, cptr_out, uni_struct_checked, make_union_common): Pass class handles instead of class symbols. (ffi_init): Initialize class handle variables. * filter.c (regex_from_trie): Use hash_cls class handle instead of hash_s. * gc.c (mark_obj): Split COBJ and CPTR cases since the representation is different. * hash.c (hash_cls, hash_iter_cls): New class handles. (make_similar_hash, copy_hash, gethash_c, gethash_e, remhash, clearhash, hash_count, get_hash_userdata, set_hash_userdata, hashp, hash_iter_init, hash_begin, hash_next, hash_peek, hash_reset, hash_reset, hash_uni, hash_diff, hash_symdiff, hash_isec): Pass class handles instead of class symbols. (hash_early_init): New function. (hash_init): Set the class symbols in the class handles that were created in hash_early_init at a time when these symbols did not exist. * lib.c (nelem): New macro. (cobj_class): New static array. (cobj_ptr): New static pointer. (cobj_hash): New static hash. (seq_iter_cls): New static class handle. (builtin_type_p): New function. (typeof): Struct instances now all carry the same symbol, struct, as their COBJ class symbol. To get their type, we must call struct_type_name. (subtypep): Rearrangement of two cases: let's make the reflexive case first. Adjust code for different location of COBJ class symbol. (seq_iter_init_with_info, seq_begin, seq_next, seq_reset, iter_begin, iter_more, iter_item, iter_step, iter_reset, make_like, list_collect, do_generic_funcall): Use class handles instead of class symbols. (class_check, cobj, cobjclassp, cobj_handle, cobj_ops): Take class handle argument instead of class symbol. (cobj_register, cobj_register_super, cobj_class_exists): New functions. (cobj_populate_hash): New static function. (cobj_print_op): Adjust for different location of class (cptr_print_op, cptr_typed, cptr_type, cptr_handle, cptr_get): cptr functions now refer to obj->cp rather than obj->co. (copy, length, sub, ref, refset, replace, dwim_set, dwim_del, obj_print): Use class handles for various COBJ types rather than class symbols. (obj_init): gc-protect cobj_hash. Initialize seq_iter_cls class symbol and cobj_hash. Populate cobj_hash as the last initialization step. (init): Call hash_early_init immediately after gc_init. diff --git a/lib.c b/lib.c * match.c (do_match_line): Refer to regex_cls class handle instead of regex_s.. * parser.c (parser_cls): New global class handle. (parse, parser_get_impl, lisp_parse_impl, txr_parse, parser_errors): Use class handles instead of class symbols. (parse_init): Initialize parser_cls. * rand.c (random_state_cls): New global class handle. (make_state, random_state_p, make_random_state, random_state_get_vec, random_fixnum, random_float, random): Use class handles instead of class symbols. (rand_init): Initialize random_state_cls. * regex.c (regex_cls): New global class handle. (chset_cls): New static class handle. (reg_compile_csets, reg_derivative, regex_compile, regexp, regex_source, regex_print, regex_run, regex_machine_init): Use class handles instead of class symbols. (regex_init): Initialize regex_cls and chset_cls. * socket.c (make_dgram_sock_stream): Use stream_cls class symbol instead of stream_s. * stream.c (stream_cls, stdio_stream_cls): New class handles. (make_null_stream, stdio_get_fd, make_stdio_stream_common, stream_fd, sock_family, sock_type, sock_peer, sock_set_peer, make_dir_stream, make_string_input_stream, make_string_byte_input_stream, make_strlist_input_stream, make_string_output_stream, make_strlist_output_stream, get_list_from_stream, make_catenated_stream, make_delegate_stream, make_delegate_stream, stream_set_prop, stream_get_prop, close_stream, get_error, get_error_str, clear_error, get_line, get_char, get_byte, get_bytes, unget_char, unget_byte, put_buf, fill_buf, fill_buf_adjust, get_line_as_buf, format, put_string, put_char, put_byte, flush_stream, seek_stream, truncate_stream, get_indent_mode, test_set_indent_mode, test_neq_set_indent_mode, set_indent_mode, get_indent, set_indent, inc_indent, width_check, force_break, set_max_length, set_max_depth): Use class handle instead of symbol. (stream_init): Initialize stream_cls and stdio_stream_cls. * struct.c (struct_type_cls, struct_cls): New class handles. (struct_init): Initialize struct_type_cls and struct_cls. (struct_handle): Static function moved to avoid forward declaration. (stype_handle): Refer to struct_type_cls class handle instead of struct_type_s symbol. Handle instance objects in addition to types. (make_struct_type): Throw error if a built-in type is being defined as a struct type. Refer to class handle instead of class symbol. (find_struct_type, allocate_struct, make_struct_impl, make_lazy_struct, copy_struct): Refer to class handle instead of class symbol. * strudel.c (make_struct_delegate_stream): Refer to stream_cls class handle instead of stream_s symbol. * sysif.c (dir_cls): New class handle. (poll_wrap): Use typep instead of subtypep, eliminating access to class symbol. (opendir_wrap, closedir_wrap, readdir_wrap): Use class handles instead of class symbols. (sysif_init): Initialize dir_cls. * syslog.c (make_syslog_stream): Refer to stream_cls class handle instead of stream_s symbol. * tree.c (tree_cls, tree_iter_cls): New class handles. (tree_insert_node, tree_lookup_node, tree_delete_node, tree_root, tree_equal_op, tree, copy_search_tree, make_similar_tree, treep, tree_begin, copy_tree_iter, replace_tree_iter, tree_reset, tree_next, tree_peek, tree_clear): Use class handle instead of class symbol. (tree_init): Initialize tree_cls and tree_iter_cls. * unwind.c (sys_cont_cls): New static class handle. (revive_cont, capture_cont): Use class handle instead of class symbol. (uw_late_init): Initialize sys_cont_cls. * vm.c (vm_desc_cls): New global class handle. (vm_closure_cls): New static class handle. (vm_desc_struct, vm_make_desc, vm_closure_struct, vm_make_closure, vm_copy_closure): Use class handle instead of class symbol. (vm_init): Initialize vm_desc_cls and vm_closure_cls.
* tree: expose missing tnodep.Kaz Kylheku2021-07-021-0/+1
| | | | | | * tree.c (tree_init): Register tnodep as intrinsic function. This is documented! Another discrepancy found thanks to the new piece of code in genman.txr.
* tree: different fix for dummy node issue.Kaz Kylheku2021-05-301-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | Let's restore the previous commit and fix it differently. The real problem is that the tn_flatten function does not need to use the set macro. When the flattened tree is rebuilt with tn_build_tree, every left and right link of every node is set at that time. That function uses the set macro, so all is well. The dummy node is not pulled into the rebuild, so it doesn't cause any problem; the dummy node is only mutated in tn_flatten. This is a better fix not only because tn_flatten is now more efficient. It is important for the dummy node to look like it is a generation zero object. The dummy node ends up as the pseudo-root of the tree, which means that it if it looks like it is in generation 1, all generation 0 below it will be wastefully checked by the garbage collector. * tree.c (tn_flatten): Do not use the set macro. Just use straight assignment to convert the tree into a linked list. (tr_rebuild): Restore dummy node to be all zeros.
* tree: gc crash due to dummy object.Kaz Kylheku2021-05-301-1/+1
| | | | | | | | | * tree.c (tr_rebuild): The dummy on-stack node we use in the rebuilding process must have its generation field set to 1 rather than 0, so it looks like a mature heap object rather than a baby object. Otherwise when its pointer is assigned to another node which happens to be gen 1, the on-stack dummy will be added to the checkobj array, and gc will try to mark it.
* tree: streamline iteration; provide high limit.Kaz Kylheku2021-05-111-50/+71
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Getting rid of tree-begin-at and tree-reset-at. Now tree-begin takes two optional parameters, for specifying high and low range. * tree.c (struct tree_diter): New members, tree and highkey. We need tree due to requiring access to the less function. If the iterator has no highkey, the iterator itself is stored in that member to indicate this. (tree_iter_mark): Mark the tree and highkey. (tree_begin): Take optional lowkey and highkey arguments, initializing iterator acordingly. (tree_begin_at): Function removed. (copy_tree_iter, replace_tree_iter): Copy tree and highkey members. The latter require special handling due to the funny convention for indicating highkey absence. (tree_reset): Take optional lowkey and highkey arguments, configuring these in the iterator being reset. (tree_reset_at): Function removed. (tree_next, tree_peek): Implement highkey semantics. (sub_tree): Simplified: from and to arguments are just passed through to tree_begin, and there is no need for a separate loop which enforces the upper limit, that now being handled by the iterator itself. (tree_begin): Update registrations of tree-begin and tree-reset; remove tree-begin-at and tree-reset-at intrinsics. * tree.h (tree_begin_at, tree_reset_at): Declarations removed. (tree_begin, tree_reset): Declarations updated. * lib.c (seq_iter_rewind, seq_iter_init_with_info, where, populate_obj_hash): Default new optional arguments in tree_begin and tree_reset calls. * parser.c (circ_backpatch): Likewise. * tests/010/tree.tl: Affected cases updated. * txr.1: Documentation updated. * share/txr/stdlib/doc-syms.tl: Regenerated.
* tree: support indexing and range extraction.Kaz Kylheku2021-05-111-0/+23
| | | | | | | | | | | | | | | | | | | * lib.c (do_generic_funcall): Support tree object invocation with one or two arguments via sub and ref. (sub): Implement for trees via sub_tree. (ref): Implement for trees via tree_lookup. * tree.c (sub_tree): New function. (tree_init): Register sub-tree intrinsic. * tree.h (sub_tree): Declared. * tests/010/tree.tl: New tests. * txr.1: Documented: DWIM bracket syntax on trees, sub and ref support for trees, sub-tree function, * share/txr/stdlib/doc-syms.tl: Regenerated.
* tree: replace-tree-iter function.Kaz Kylheku2021-05-111-0/+21
| | | | | | | | | | | | | * tree.c (replace_tree_iter): New function. (tree_init): Register replace-tree-iter intrinsic. * tree.h (tree_init): Declared. * share/txr/stdlib/doc-syms.tl: Updated. * txr.1: Documented. * tests/010/tree.tl: New test case.
* tree: copy-tree-iter function.Kaz Kylheku2021-05-101-0/+22
| | | | | | | | | | | | | | | * lib.c (copy): Handle tree_iter_s via copy_tree_iter. * tree.c (copy_tree_iter): New function. (tree_init): copy-tree-iter intrinsic registered. * tree.h (copy_tree_iter): Declared. * tests/010/tree.tl: New test case. * txr.1: Documented. * share/txr/stdlib/doc-syms.tl: Updated.
* tree: expose insert, lookup and delete functions.Kaz Kylheku2021-05-091-5/+5
| | | | | | | | | | * tree.c (tree_insert, tree_lookup_node, tree_delete_node, tree_delete): Switch internal linkage to external linkage. * tree.h (tree_insert, tree_lookup_node, tree_delete_node, tree_delete): Declared.
* tree: new tree-peek function.Kaz Kylheku2021-05-091-0/+52
| | | | | | | | | | | | | | * tree.c (tn_peek_next): New static function. (tree_peek): New function. (tree_init): Register tree-peek intrinsic. * tree.h (tree_peek): Declared. * txr.1: Documented. * tests/010/tree.c: Work tree-peek into existing test case. * share/txr/stdlib/doc-syms.tl: Updated.
* tree: new make_similar_tree unction.Kaz Kylheku2021-05-091-0/+13
| | | | | | | | | | | * tree.c (make_similar_tree): New function. (tree_init): Register make-similar-tree intrinsic * tree.h (make_similar_tree): Declared. * tests/010/tree.tl: New tests. * txr.1: Documented.
* tree: new functions for reseting iterator.Kaz Kylheku2021-04-301-0/+33
| | | | | | | | | | | | | | * tree.c (tree_reset, tree_reset_at): New functions. (tree_init): tree-reset and tree-reset-at intrinsics registered. * tree.h (tree_reset, tree_reset_at): Declared. * tests/010/tree.tl: New tests. * txr.1: Documented. * share/txr/stdlib/doc-syms.tl: Updated.
* tree: remove unused member from dynamic iter.Kaz Kylheku2021-04-301-3/+0
| | | | | | * tree.c (struct tree_diter): Remove the tr member; it is not used anywhere. (tree_begin, tree_begin_at): Remove initialization of tdi->tr.
* tree: new tree-begin-at function.Kaz Kylheku2021-04-291-2/+68
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * tree.c (enum tree_iter_state): New iterator state tr_find_low_prepared dedicated to the tree-begin-at traversal. This state indicates that tree-next should visit the starting node that it is given, and then after that, treat anything to the left of it as having been visited. In the other states, tree-next does not visit the node it is given but uses it as the starting point to find the next node. (tn_find_next): Bugfix here: when navigating the right link, the function neglected to add the node to the path. But the logic for backtracking up the path expects this: it checks whether the node from the path is the parent of a right child. Somehow this didn't cause a problem for full traversals with tree-begin; at least the existing test cases don't expose an issue. It caused a problem for tree-begin-at, though. (tn_find_low): New static function. This finds the low-key node in the tree, priming the iterator object with the correct state and path content to continue the traversal from that node on . We need the tr_find_low_prepared state in the iterator in order to visit the low node itself that was found. (tree_begin_at): New function. (tree_init): Register tree-begin-at intrinsic. * tree.h (tree_begin_at): Declared. * tests/010/tree.tl: New test cases for tree-begin-at. * txr.1: Documented. * share/txr/stdlib/doc-syms.tl: Updated.
* tree: incorrect lookup function.Kaz Kylheku2021-04-291-1/+1
| | | | | | | * tree.c (tn_lookup): The right case is incorrectly chasing the left pointer. * tests/010/tree.tl: New file.
* tree: debug massive gc problems.Kaz Kylheku2021-04-291-55/+62
| | | | | | | | | | | | | | | | | | | | | | | | | | | The tree module doesn't observe generational GC correctness; it assigns objects into other objects using ordinary assignment. * tests/010/tree.tl (tree_iter): New member, tree. This is initialized to null for iterators on the stack. dynamic iterator, we need this to be a back-pointer to the dynamic iterator. (tree_iter_init): Add parameter to initializer to set up the back-pointer. (set_left, set_right, set_key): Use set macro instead of ordinary assignment. (tn_find_next): Use set macro to add node to path. (tn_flatten, tn_build_tree): Use set macro. (tr_rebuild, tr_rebuild_scapegoat, tr_insert, tr_do_delete), tr_delete): Use set macro. Take a tree argument so we can use set macro on tr->root. (tree_insert): Use set macro. Pass 0 to tree_iter_init initializer macro. (tree_delete_node): Pass tree to tr_delete. (tree_equal_op, tree_print_op, tree_hash_op): Pass 0 to tree_iter_init initializer macro. (tree-begin): Rearrange construction for GC correctness: avoid storing pointers into not-yet-reachable structure.
* Copyright year bump 2021.Kaz Kylheku2021-01-141-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * METALICENSE: 2020 copyrights bumped to 2021. Added note about SHA-256 routines from Colin Percival. * LICENSE, LICENSE-CYG, Makefile, alloca.h, args.c, args.h, arith.c, arith.h, buf.c, buf.h, cadr.c, cadr.h, chksum.c, chksum.h, chksums/crc32.c, chksums/crc32.h, combi.c, combi.h, configure, debug.c, debug.h, eval.c, eval.h, ffi.c, ffi.h, filter.c, filter.h, ftw.c, ftw.h, gc.c, gc.h, glob.c, glob.h, hash.c, hash.h, itypes.c, itypes.h, jmp.S, lex.yy.c.shipped, lib.c, lib.h, linenoise/linenoise.c, linenoise/linenoise.h, lisplib.c, lisplib.h, match.c, match.h, parser.c, parser.h, parser.l, parser.y, protsym.c, rand.c, rand.h, regex.c, regex.h, share/txr/stdlib/asm.tl, share/txr/stdlib/awk.tl, share/txr/stdlib/build.tl, share/txr/stdlib/cadr.tl, share/txr/stdlib/compiler.tl, share/txr/stdlib/conv.tl, share/txr/stdlib/copy-file.tl, share/txr/stdlib/debugger.tl, share/txr/stdlib/defset.tl, share/txr/stdlib/doloop.tl, share/txr/stdlib/each-prod.tl, share/txr/stdlib/error.tl, share/txr/stdlib/except.tl, share/txr/stdlib/ffi.tl, share/txr/stdlib/getopts.tl, share/txr/stdlib/getput.tl, share/txr/stdlib/hash.tl, share/txr/stdlib/ifa.tl, share/txr/stdlib/keyparams.tl, share/txr/stdlib/op.tl, share/txr/stdlib/package.tl, share/txr/stdlib/param.tl, share/txr/stdlib/path-test.tl, share/txr/stdlib/place.tl, share/txr/stdlib/pmac.tl, share/txr/stdlib/quips.tl, share/txr/stdlib/save-exe.tl, share/txr/stdlib/socket.tl, share/txr/stdlib/stream-wrap.tl, share/txr/stdlib/struct.tl, share/txr/stdlib/tagbody.tl, share/txr/stdlib/termios.tl, share/txr/stdlib/trace.tl, share/txr/stdlib/txr-case.tl, share/txr/stdlib/type.tl, share/txr/stdlib/vm-param.tl, share/txr/stdlib/with-resources.tl, share/txr/stdlib/with-stream.tl, share/txr/stdlib/yield.tl, signal.c, signal.h, socket.c, socket.h, stream.c, stream.h, struct.c, struct.h, strudel.c, strudel.h, sysif.c, sysif.h, syslog.c, syslog.h, termios.c, termios.h, time.c, time.h, tree.c, tree.h, txr.1, txr.c, txr.h, unwind.c, unwind.h, utf8.c, utf8.h, vm.c, vm.h, vmop.h, win/cleansvg.txr, y.tab.c.shipped: Copyright year bumped to 2021.
* gc: add finalization count to objects.Kaz Kylheku2020-12-311-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | With the finalization count, we don't have to scan the freshobj array for duplicates when calling finalizers. However, the limited range of the counter limits how many times we can register a finalizer against an object. * gc.c (make_obj): Reset the new fincount field to zero for a newly minted object. (call_finalizers_impl): Decrement the fincount for each object. Only run the freshobj-related logic when the count hits zero. (gc_finalize): Bump the fincount of a registered object. If the counter overflows, throw an exception. * lib.h (obj_common): Add new field fincount for the finalization count. * tree.c (tr_rebuild): Fix up dummy object initializer to accommodate the new member. * txr.1: Document that there is a limit on the number of times an object can be registered for finalization.
* Remove unnecessary #include directives.Kaz Kylheku2020-04-221-7/+0
| | | | | | | | | | Time for some spring cleaning. * args.c, arith.c, buf.c, cadr.c, chksum.c, debug.c, ftw.c, gc.c, gencadr.txr, glob.c, hash.c, lisplib.c, match.c, parser.c, parser.l, parser.y, rand.c, signal.c, stream.c, strudel.c, syslog.c, tree.c, unwind.c, utf8.c, vm.c: Numerous unnecessary #include directives removed.
* warning cleanup: missing member initializers.Kaz Kylheku2020-04-051-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is the sixth round of an effort to enable GCC's -Wextra option. Warnings about uninitialized members are addressed. I am not happy with what had to be done in linenoise.c. We just need a dummy circular list node for the lino_list, which we achieved with a dummy all zero struture, with statially initialized next and prev pointers. There are way too many members to initialize, including one that has struct termios type containing a nonportable set of members. On the plus size, the lino_list structure now moves into the BSS section, reducing the executable size slightly. * lib.c (cptr_ops): Initialize using cobj_ops_init, which has all the initializers already, and should have been used for this in the first place. * linenoise/linenoise.c (lino_list): Remove initializer, which eliminates the warning about some members not being initialized. (lino_init): Initialize the next and prev pointers here. * parser.c (parser_ops): Initialize with cobj_ops_init. * stream.h (stdio_mode_init_blank, stdio_mode_init_r, stdio_mode_init_rpb): Add initializer corresponding to redir array member of struct stdio_mode. * sysif.c (cptr_dl_ops): Use cobj_ops_init. * tree.c (tree_iter_init): Add initializer for the path array member of struct tree_iter. (tr_rebuild): Initialize all fields of the dummy object. Since it's a union, we just have to deal with the any member. There are two layouts for the obj_common fields based on whether CONFIG_GEN_GC is enabled. This is ugly, but occurs in one place only.
* Copyright year bump 2020.Kaz Kylheku2019-12-311-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * LICENSE, LICENSE-CYG, METALICENSE, Makefile, alloca.h, args.c, args.h, arith.c, arith.h, buf.c, buf.h, cadr.c, cadr.h, chksum.c, chksum.h, chksums/crc32.c, chksums/crc32.h, combi.c, combi.h, configure, debug.c, debug.h, eval.c, eval.h, ffi.c, ffi.h, filter.c, filter.h, ftw.c, ftw.h, gc.c, gc.h, glob.c, glob.h, hash.c, hash.h, itypes.c, itypes.h, jmp.S, lib.c, lib.h, linenoise/linenoise.c, linenoise/linenoise.h, lisplib.c, lisplib.h, match.c, match.h, parser.c, parser.h, parser.l, parser.y, protsym.c, rand.c, rand.h, regex.c, regex.h, share/txr/stdlib/asm.tl, share/txr/stdlib/awk.tl, share/txr/stdlib/build.tl, share/txr/stdlib/cadr.tl, share/txr/stdlib/compiler.tl, share/txr/stdlib/conv.tl, share/txr/stdlib/debugger.tl, share/txr/stdlib/defset.tl, share/txr/stdlib/doloop.tl, share/txr/stdlib/error.tl, share/txr/stdlib/except.tl, share/txr/stdlib/ffi.tl, share/txr/stdlib/getopts.tl, share/txr/stdlib/getput.tl, share/txr/stdlib/hash.tl, share/txr/stdlib/ifa.tl, share/txr/stdlib/keyparams.tl, share/txr/stdlib/op.tl, share/txr/stdlib/package.tl, share/txr/stdlib/param.tl, share/txr/stdlib/path-test.tl, share/txr/stdlib/place.tl, share/txr/stdlib/pmac.tl, share/txr/stdlib/save-exe.tl, share/txr/stdlib/socket.tl, share/txr/stdlib/stream-wrap.tl, share/txr/stdlib/struct.tl, share/txr/stdlib/tagbody.tl, share/txr/stdlib/termios.tl, share/txr/stdlib/trace.tl, share/txr/stdlib/txr-case.tl, share/txr/stdlib/type.tl, share/txr/stdlib/vm-param.tl, share/txr/stdlib/with-resources.tl, share/txr/stdlib/with-stream.tl, share/txr/stdlib/yield.tl, signal.c, signal.h, socket.c, socket.h, stream.c, stream.h, struct.c, struct.h, strudel.c, strudel.h, sysif.c, sysif.h, syslog.c, syslog.h, termios.c, termios.h, tree.c, tree.h, txr.1, txr.c, txr.h, unwind.c, unwind.h, utf8.c, utf8.h, vm.c, vm.h, vmop.h, win/cleansvg.txr: Extended copyright notices to 2020.
* tree: printing: handle unnamed functions.Kaz Kylheku2019-10-161-3/+7
| | | | | | | * tree.c (tree): If the tree abstraction functions don't have a name, then use the functions themselves as the names, rather than nil. Otherwise the printed representation of the tree will look like it has the default abstraction functions.
* tree: copy-search-tree function.Kaz Kylheku2019-10-161-0/+22
| | | | | | | | | | | | | * 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.
* tree: node set functions and syntactic places.Kaz Kylheku2019-10-161-0/+24
| | | | | | | | | | | | | | | | | * 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.
* tree: introduce copy-tnode.Kaz Kylheku2019-10-161-0/+8
| | | | | | | | | | | | * 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: api: harmonize deletion with insertion.Kaz Kylheku2019-10-151-2/+9
| | | | | | | | | * tree.c (tree_delete): Renamed to tree_delete_node. (tree_delete): New function which returns element rather than node. (tree_root): Registered tree-delete-node intrinsic. * txr.1: Documented.
* tree: add tree-clear function.Kaz Kylheku2019-10-071-0/+11
| | | | | | | * tree.c (tree_clear): New function. (tree_init): tree-clear intrinsic registered. * tree.h (tree_clear): Declared.
* tree: make node insertion external.Kaz Kylheku2019-10-071-1/+1
| | | | | | * tree.c (tree_insert_node): Change to external linkage. * tree.h (tree_insert_node): Declared.
* tree: insert must clear left/right links.Kaz Kylheku2019-10-071-0/+3
| | | | | * tree.c (tree_insert_node): A node being inserted might not have null left and right links; we must clear them.
* tree: tree iterators.Kaz Kylheku2019-10-031-1/+54
| | | | | | | | | | | | * 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: bug in key handling in insertion.Kaz Kylheku2019-10-011-16/+17
| | | | | | | | | | | | | * tree.c (tr_insert): We must apply the key_fn to the key of the node which we are inserting, not only to the tree node being searched. This is different from delete, where the key argument is just the key value to be searched for, not a key object from which the key function extracts the key value. Variable naming is hereby adjusted: let's use tr_key for the key from the tree, and tn_key for the key extracted from the argument node. (tn_lookup, tr_delete): Rename the tn_key local variable to tr_key, for consistency with the naming inside tr_insert.
* tree: crash when root is to be replaced.Kaz Kylheku2019-10-011-4/+9
| | | | | | | | * tree.c (tr_insert): When the inserted key matches the root node, then there is nothing in ti->path and ti->depth is zero. We are accessing ti->path[-1] to get a root node. We must test for zero depth and install the new node as the tree root in that case.
* tree: add treep predicate.Kaz Kylheku2019-09-301-0/+6
| | | | | * tree.c (treep): new function. (tree_init): Registered treep intrinsic.
* tree: allow quasiquoting into #T syntax.Kaz Kylheku2019-09-281-0/+25
| | | | | | | | | | | | | | | | | * eval.c (tree_lit_s, tree_construct_s): New symbol variables. (expand_qquote_rec): Handle sys:tree-lit syntax generated by quasi-quoted #T notaton by expanding and converting to sys:tree-constuct call. (eval_init): Initialize tree_lit_s and tree_construct_s. * eval.h (tree_lit_s, tree_construct_s): Declared. * parser.y (tree): Produce sys:tree-lit syntax when #T is quasi-quoted, and unquotes occur inside it. * tree.c (tree_construct_fname, tree_construct): New static functions. (tree_init): Register sys:tree-construct intrinsic function.
* New data structure: binary search trees.Kaz Kylheku2019-09-251-0/+492
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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.
* New data type: tnode.Kaz Kylheku2019-09-221-0/+91
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.
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-18 01:28:37 +0000