summaryrefslogtreecommitdiffstats
path: root/hash.c
Commit message (Collapse)AuthorAgeFilesLines
...
* hash: use ucnum for hash values everywhere.Kaz Kylheku2019-10-121-11/+11
| | | | | | | | | | | | | | | | | | | One consequence of this is that we no longer pass negative values to vecref; that functon was protecting us from the consequences of this signed/unsigned mixup, at the cost of cyles. * hash.c (struct hash_ops): hash parameter in assoc_fun and acons_new_c_fun pointers changes from cnum to ucnum. (hash_assoc, hash_assql, hash_assq): hash parameter changes to ucnum. (hash_acons_new_c, hash_aconsql_new_c, hash_aconsq_new_c): Likewise. (gethash_c, gethash_e, remhash): Variable which captures the output of the hashing function is now ucnum instead of cnum. * lib.h (struct cons_hash_entry): Member hash changes from cnum to ucnum.
* hash: strengthen type mutual exclusion check.Kaz Kylheku2019-10-111-8/+13
| | | | | | | | | | * hash.c (equal_based_p): Take additional argument eq indicating that :eq-based has been specified. Check all three exclusive combinations. (hashv): Call equal_based_p unconditionally, even when :eq-based is specified and we don't use this function's return value so we benefit from that function's exclusion check. Pass the eq boolean, as required.
* hash: implement :eq-based.Kaz Kylheku2019-10-111-7/+117
| | | | | | | | | | | | | | | | | | | | | We need eq based hash tables to fix a problem in *print-circle*. * hash.c (enum hash_type, hash_type_t): New enum type. (eq_based_k): New keyword variable. (eq_hash, eq_hash_op): New static functions. (hash_print_op): Ensure we print eq-based hashes with the correct keyword. (hash_assq, hash_aconsq_new_c): New static functions. (hash_eq_ops): New static structure. (do_make_hash): New function, made from previous contents of make_seeded_hash. (make_seeded_hash): Wrapper around do_make_hash now. (make_eq_hash): New function. (hashv): Parse out :eq-based argument. Use make_eq_hash if it is present. (hash_init): Initialize eq_based_k. * hash.h (eq_based_k, make_eq_hash): Declared.
* safety: fix type tests that code can subvert.Kaz Kylheku2019-09-301-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch fixes numerous instances of a safety hole which involves the type of a COBJ object being tested to be of a given class using logic that can be subverted by the definition of a like-named struct. Specifically logic like (typeof(obj) == hash_s) is broken, because if a struct type called hash is defined, then the test will yield true for instances of that struct type. Those instances can then be passed into code that only works on COBJ hashes, and relies on this test to reject invalid objects. * ffi.c (make_carray): Replace fragile test with strong one, using new cobjclassp function. * hash.c (hashp): Likewise. * lib.c (class_check): The expression used here for the type test moves into the new function cobjclassp and so is replaced by a call to that function. (cobjclassp): New function. * lib.h (cobjclassp): Declared. * rand.c (random_state_p): Replace fragile test using cobjclassp. * regex.c (char_set_compile): Replace fragile typeof tests for character type with is_chr. (reg_derivative, regexp): Replace fragile test with cobjclassp. * struct.c (struct_type_p): Replace fragile test with cobjclassp.
* Use put_char for single character output.Kaz Kylheku2019-09-261-5/+5
| | | | | | | * hash.c (hash_print_op): Replace length 1 put_string calls with put_char. * lib.c (obj_print_impl): Likewise.
* New data type: tnode.Kaz Kylheku2019-09-221-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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.
* hashing: take advantage of seed when hashing aggregates.Kaz Kylheku2019-09-201-11/+12
| | | | | | | | | | * hash.c (equal_hash): When hashing conses and ranges, perturb the seed going into the hash for the second element, rather than hashing it the same way, and then multiplying it. When hashing the elements of a vector, perturb the seed of each one by multiplying by the index. For the CHR, NUM, BGNUM, FLNUM and several types hashed like pointers, we now mix the seed into the hash.
* New function: hash-zip.Kaz Kylheku2019-07-171-0/+17
| | | | | | | | | * hash.c (hash_zip): New function. (hash_init): hash-zip intrinsic registered. * hash.h (hash_zip): Declared. * txr.1: Documented.
* New function: hash-peek.Kaz Kylheku2019-06-111-0/+26
| | | | | | | | | * hash.c (hash_peek): New function. (hash_init): hash-peek intrinsic registered. * hash.h (hash_peek): Declared. * txr.1: Documented.
* hash: remove unnecessary test.Kaz Kylheku2019-06-111-1/+1
| | | | | | * hash.c (hash_next): We know after the loop that hi->cons is not nil, because the loop contains no break, and is guarded by hi->cons being nil.
* C99: get rid of useless inline instantiations.Kaz Kylheku2019-05-021-5/+0
| | | | | | | | | | | * hash.c, lib.c, parser.y, unwind.c: Remove useless declarations that were believed to be C99 inline instantiations. This was mistakenly added at the time the Solaris issue was discovered that _XOPEN_SOURCE values of 600 or greater require compiling in C99 mode. We use "static inline" under C99 for inline functions; instantiation is not applicable at all to inline functions that don't have external linkage.
* Support max length and depth for object printing.Kaz Kylheku2019-04-181-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * hash.c (hash_print_op): Implement max length. * lib.c (lazy_str_put, out_lazy_str): Take struct strm_base * parameter and implement max length. (out_quasi_str_sym): Don't use obj_print_impl for symbol's name string; just put_string. The use of obj_print_impl causes symbols appearing as variables in quasiliterals to be truncated when max length is imposed. (out_quasi_str): Implement max length. (obj_print_impl): Implement max length and depth. Note that there is now always a non-null ctx pointer. (obj_print): Always set up context pointer for obj_print_impl. Context now has pointer to low-level stream structure, where we can access max_length and max_depth. It also carries the recursion depth. * lib.h (lazy_str_put): Declaration updated. * stream.c (strm_base_init): Add initializers for max_length and max_depth. (put_string): Pass stream structure to lazy_str_put. (set_max_length, set_max_depth): New functions. (stream_init): set-max-length and set-max-depth intrinsics registered. * stream.h (struct strm_ctx): New members depth and strm. (struct strm_base): New members max_length and max_depth. (set_max_length, set_max_depth): Declared. * txr.1: Documented.
* lib: use accessor for lcons function.Kaz Kylheku2019-03-121-4/+4
| | | | | | | | * hash.c (hash_keys_lazy, hash_values_lazy, hash_pairs_lazy, hash_alist_lazy): Use us_lcons_fun instead of direct lcons->lc.fun access. * lib.c (simple_lazy_stream_func, lazy_stream_func): Likewise.
* lib: rename make_half_lazy_cons.Kaz Kylheku2019-03-121-12/+12
| | | | | | | | | | | * lib.h (make_half_lazy_cons): Renamed to make make_lazy_cons_car. * lib.c (rem_lazy_rec, make_half_lazy_cons): Follow rename. * hash.c (hash_keys_lazy, hash_keys, hash_values_lazy, hash_values, hash_pairs_lazy, hash_pairs, hash_alist_lazy, hash_alist): Follow rename.
* hash: gc issue in clearhash.Kaz Kylheku2019-02-241-0/+1
| | | | | | * hash.c (clearhash): Assignment of new table into hash requires setcheck, because it's putting a new object into an old one.
* hash: remove redundant assignment from hash_grow.Kaz Kylheku2019-02-241-1/+1
| | | | | | * hash.c (hash_grow): The new_table value is stored in h->table twice. First directly and then via the set macro. Let's just use setcheck, which avoids the intermediate loc object.
* hashing: provide unsafe hash count.Kaz Kylheku2019-02-221-0/+6
| | | | | | | * hash.c (us_hash_count): New function. Blindly assumes that the argument is a hash. * hash.h (us_hash_count): Declared.
* Optimize hash operation with unsafe car/cdr.Kaz Kylheku2019-02-141-94/+97
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The associative lists that make up the chains of a hash table are guaranteed to be made of conses. We can use unsafe versions of car, cdr, rplaca and rplacd to speed up hash operations. * eval.c (op_dohash): Use unsafe operations on hash cell. * filter.c (trie_compress, regex_from_trie): Likewise. * hash.c (hash_equal_op, hash_print_op, hash_mark, hash_grow, hash_assoc, hash_assql, copy_hash_chain, gethash, inhash, gethash_n, sethash, remhash, hash_next, maphash, do_weak_tables, group_by, group_reduce, hash_keys_lazy, hash_keys, hash_values_lazy, hash_values, hash_pairs_lazy, hash_pairs, hash_alist_lazy, hash_uni, hash_diff, hash_symdiff, hash_isec, hash_subset, hash_update, hash_update_1, hash_revget): Likewise. * lib.c (us_rplaca, us_rplacd): New functions. (package_local_symbols, package_foreign_symbols, where, populate_obj_hash, obj_hash_merge): Use unsafe operations on hash cell * lib.h (us_rplaca, us_rplacd): Declared. * parser.c (circ_backpatch, get_visible_syms): Use unsafe operations on hash cell. * struct.c (method_name, get_slot_syms): Likewise.
* gethash_c: review uses and improve or replace.Kaz Kylheku2019-02-141-8/+7
| | | | | | | | | | | | | | | | | | | | * eval.c (env_fbind, env_vbind, reg_symacro): Use gethash_l instead of gethash_c to eliminate repeated cdr operations on the same cell. * hash.c (sethash): Since new_p is never used, eliminated it and use nulloc. (group_reduce): Use gethash_l instead of gethash_c. * lib.c (obj_init): Replace rplacd(gethash_c(...)) pattern whose return value is not used with with sethash. We lose some diagnosability here since sethash doesn't take a "self" argument. (obj_print_impl, obj_hash_merge): Use gethash_l instead of gethash_c. * parser.y (ensure_parser, parser_circ_def, get_visible_syms, rlset): Use gethash_l instead of gethash_c.
* gethash_f: removing function.Kaz Kylheku2019-02-141-16/+7
| | | | | | | | | | | | | | | | Uses of gethash_f can be replaced with gethash_e, which returns the hash cell directly rather than through a loc argument. Code that needs the value can call cdr itself. * hash.c (inhash, hash_isec, hash_update_1): Replace gethash_f with gethash_e. (gethash_f): Function removed. * hash.h (gethash_f): Declaration removed. * lib.c (use_sym, unuse_sym, find_symbol, unintern, intern_fallback, in, sel, populate_obj_hash): Replace gethash_f with gethash_e.
* hash-from-alist: new function.Kaz Kylheku2019-02-131-0/+15
| | | | | | | | | * hash.c (hash_from_alist_v): New function. (hash_init): Register hash-from-alist intrinsic. * hash.h (hash_from_alist_v): Declared. * txr.1: Documented.
* hash-symdiff: new function.Kaz Kylheku2019-02-131-0/+35
| | | | | | | | | * hash.c (hash_symdiff): New function. (hash_init): hash-symdiff intrinsic registered. * hash.h (hash_symdiff): Declared. * txr.1: Documented.
* hash-uni: bugfix.Kaz Kylheku2019-02-131-2/+6
| | | | | | | | * hash.c (hash_uni): The join function must only be called for the values of keys that exist in both hashes. The broken logic here unconditionally calls the join function for all keys in the left hash (using nil as the right join value when the key doesn't exist in the right hash).
* copy-hash: showstopper: seed must be copied.Kaz Kylheku2019-01-281-0/+1
| | | | | | * hash.c (copy_hash): Fix failure to initialize seed member in the duplicated hash structure. This regression was introduced along with seeded hashing.
* Fix some instances of 4 bytes = 32 bits assumption.Kaz Kylheku2019-01-231-15/+15
| | | | | | | | | | | | | | | | | * hash.c (equal_hash, eql_hash, cobj_eq_hash_op, hash_hash_op): Multiply object size by CHAR_BIT and switch on number of bits, rather than bytes. * sysif.c (off_t_num): Likewise. * arith.c, ffi.c, itypes.c, rand.c: In numerous #if directive, fix size tests from bytes to bits. * configure: in the test that detects integer types, and in the test for enabling large file offsets, detect one more variable from the system: the value of CHAR_BIT. This turns into SIZEOF_BYTE. We use that value instead of a hard-coded 8.
* Copyright year bump 2019.Kaz Kylheku2019-01-161-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * LICENSE, LICENSE-CYG, METALICENSE, Makefile, args.c, args.h, arith.c, arith.h, buf.c, buf.h, cadr.c, cadr.h, combi.c, combi.h, configure, debug.c, debug.h, eval.c, eval.h, ffi.c, ffi.h, filter.c, filter.h, 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, 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/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/path-test.tl, share/txr/stdlib/place.tl, share/txr/stdlib/pmac.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, 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 line to 2018.
* Eliminate ALLOCA_H.Kaz Kylheku2018-12-311-1/+1
| | | | | | | | | | | | | * configure: Instead of generating a definition of ALLOCA_H, generate the variable HAVE_ALLOCA_<name> with a value of 1, where <name> is one of stdlib, alloca or malloc. * alloca.h: New header. * args.c, eval.c, ffi.c ffi.c, ftw.c, hash.c, lib.c, match.c, parser.c, parser.y, regex.c, socket.c, stream.c, struct.c, sysif.c, syslog.c, termios.c, unwind.c, vm.c: Include "alloca.h" instead of ALLOCA_H.
* Eliminate various unneeded header inclusions.Kaz Kylheku2018-12-121-1/+0
| | | | | | | | | | * hash.c: Don't include "cadr.h". * stream.c: Don't include "struct.h". * strudel.c: No <syslog.h>, ALLOCA_H, "args.h" or "utf8.h". * vm.c: No "hash.h".
* Drastically reduce inclusion of <dirent.h>.Kaz Kylheku2018-12-111-1/+0
| | | | | | | | | | | | | | | | | | | The <dirent.h> header is included all over the place because it is needed by a single declaration in stream.h. That declaration is for a function that is only called within stream.c, so we make it internal. Now only stream.c has to include <dirent.h>. * buf.c, debug.c, eval.c, ffi.c, filter.c, gc.c, gencadr.txr, hash.c, lib.c, lisplib.c, match.c, parser.c, regex.c, socket.c, struct.c, strudel.c, sysif.c, syslog.c, termios.c, txr.c, unwind.c, vm.c: Remove #include <dirent.h>. * cadr.c: Regenerated. * stream.c (make_dir_stream): Make external function static. * stream.h (make_dir_stream): Declaration updated.
* gethash_l: C99 fix for Solaris.txr-201Kaz Kylheku2018-11-071-1/+1
| | | | | * hash.c (gethash_l): C99 inline instantiation updated to match new type signature.
* Better identify functions that misuse COBJ-s and hashes.Kaz Kylheku2018-11-071-36/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In this patch, the cobj_handle, cobj_ops and variants of gethash get an additional argument to identify the caller. Many functions are updated to pass this down. * buf.c (buf_strm): Pass self name to cobj_handle. * eval.c (env_fbind, env_vbind, rt_defvarl, me_case): Pass self name to gethash_c or gethash_e. (load): Pass self name to read_eval_stream and read_compiled_file. (reg_symacro): Pass situation-identifying string to gethash_c. * ffi.c (ffi_type_struct_checked, ffi_closure_struct_checked, ffi_call_desc_checked, uni_struct_checked): Take self name parameter, and pass down to cobj_handle. (ffi_get_type, ffi_get_lisp_type): Take self name and pass down to ffi_type_struct_checked. (union_get_ptr): Take self name and pass to uni_struct_checked. (ffi_union_in, ffi_union_put): Pass self name to union_get_ptr. (ffi_type_compile): Pass self name to ffi_get_lisp_type. (ffi_make_call_desc): Pass self name to ffi_type_struct_checked, ffi_get_type and ffi_call_desc_checked. (ffi_make_closure): Pass self name to ffi_call_desc_checked. (ffi_closure_get_fptr): Take self name, pass to ffi_closure_struct_checked. (ffi_typedef, ffi_size, ffi_alignof, ffi_offsetof, ffi_arraysize, ffi_elemsize, ffi_elemtype, ffi_put_into, ffi_put, ffi_in, ffi_get, ffi_out, make_carray): Pass self name to ffi_closure_struct_checked. (carray_struct_checked): Take self name, pass to cobj_handle. (carray_set_length, carray_dup, carray_own, carray_free, carray_type, length_carray, copy_carray, carray_ptr, buf_carray, vec_carray, list_carray, carray_ref, carray_refset, carray_sub, carray_replace, carray_get_common, carray_put_common, unum_carray, num_carray, put_carray, fill_carray): Pass self name to carray_struct_checked. (carray_blank, carray_buf, carray_cptr): Pass self name ffi_type_struct_checked. (carray_pun): Pass self name to carray_struct_checked and ffi_type_struct_checked. (make_union): Pass self name to ffi_type_struct_checked. (union_members, union_get, union_put, union_in, union_out): Pass self name to uni_struct_checked. (make_zstruct, zero_fill, put_obj, get_obj, fill_obj): Pass self-name to ffi_type_struct_checked. * ffi.h (ffi_closure_get_fptr, union_get_ptr): Declarations updated. * filter.c (trie_add): Pass self-name to gethash_l. * hash.c (make_similar_hash, copy_hash, hash_count, get_hash_userdata, set_hash_userdata, hash_begin, hash_next, hash_uni, hash_diff, hash_isec): Pass self name to cobj_handle. (gethash_c, gethash_e): Take self name parameter and pass down to cobj_handle. (gethash_f): Take self parameter and pass down to gethash_e. (gethash, inhash, gethash_n, sethash, pushhash, remhash, clearhash, hash_update_1): Pass self name to gethash_e or gethash_c. * hash.h (gethash_c, gethash_e, gethash_f): Declarations updated. (gethash_l): Take self name, and pass down to gethash_c. * lib.c (class_check): Take self name parameter and use in type mismatch diagnostic. (use_sym, unuse_sym, symbol_needs_prefix, find_symbol, intern, unintern, intern_fallback, unique, in, sel, obj_print_impl, populate_obj_hash, obj_hash_merge): Pass self name to gethash_f or gethash_l. (symbol_visible, obj_init): Pass situation-identifying string to gethash_e. (cobj_handle, cobj_ops): Take self name parameter and pass down to class_check. * lib.h (class_check, cobj_handle, cobj_ops): Declarations updated. * match.c (v_load): Pass self name to read_compiled_file and read_eval_stream. * parser.c (get_parser_impl): Take self name and pass to cobj_handle. (ensure_parser): Pass situation-identifying string to gethash_c. (parser_circ_def): Pass self-name to gethash_c. (lisp_parser_impl): Pass self name to get_parser_impl and class_check. (lisp_parse, nread, iread): Pass self-name to lisp_parser_impl. (read_file_common): Take self name parameter and pass down to get_parser_impl. (read_eval_stream, read_compiled_file): Take self name and pass down to read_file_common. (load_rcfile): Pass situation-identifying string to read_eval_streem. (get_visible_syms): Pass situation-identifying string to gethash_c. (parser_errors, parser_eof): Pass self name to cobj_handle. * parser.h (read_eval_stream, read_compiled_file): Declarations updated. * parser.y (rlset): Pass self name to gethash_c. * rand.c (make_random_state, random_state_get_vec,l random_fixnum, random_float): Pass self name to cobj_handle. * regex.c (regex_source, regex_print, regex_run): Pass self-name to cobj_handle. (regex_machine_init): Take self name param and pass to cobj_handle. (search_regex, match_regex, match_regex_right, regex_prefix_match, read_until_match): Pass self-name to regex_machine_init. * stream.c (stdio_get_fd): Pass self name to cobj_handle. (generic_get_line): Get COBJ operations via unsafe, diret object access rather than cobj_ops. (set_mode_props): Get object handle via unsafe, direct object access. (stream_fd, sock_family, sock_type, sock_peer, set_sock_peer, get_string_from_stream, get_list_from_stream, stream_set_prop, stream_get_prop, close_stream, get_error, get_error_str, clear_error, get_line, get_char, get_byte, unget_char, unget_byte, put_buf, fill_buf, put_string, put_char, put_byte, flush_stream, seek_stream, truncate_stream, get_indent_mode, test_set_indent_mode, set_indent_mode, get_indent, set_indent, inc_indent, width_check, force_break, get_set_ctx, get_ctx): Pass self name to cobj_ops. (make_delegate_stream): Take self name parameter, pass down to cobj_ops. (record_adapter): Pass self name down to make_delegate_stream. (format): Pass self name to class_check. * struct.c (stype_handle): Pass self name to cobj_handle. (make_struct_type): Pass self name to class_check. * txr.c (read_eval_stream_noerr): Take self name parameter, pass to read_eval_stream. (txr_main): Pass istuation-identifying string to read_compiled_file and read_eval_stream_noerr. * unwind.c (revive_cont): Pass self-name to cobj_handle. * vm.c (vm_desc_struct): Take self name parameter, pass to cobj_handle. (vm_desc_nlevels, vm_desc_nregs, vm_desc_bytecode, vm_desc_datavec, vm_desc_symvec, vm_execute_toplevel, vm_execute_closure, vm_closure_entry): Pass self name to vm_desc_struct. (vm_closure_struct): Take self name parameter, pass to cobj_handle.
* hash: gnu C++ signed/unsigned warning.Kaz Kylheku2018-10-281-1/+1
| | | | | * hash.c (hash_double): Fix comparison warning between signed loop variable and unsigned limit expression.
* hash: replace hashing function for doubles.Kaz Kylheku2018-07-171-5/+8
| | | | | * hash.c (hash_double): Rewrite silly byte rotation with union aliased against ucnum array.
* hash: use full width unsigned type for hash values.Kaz Kylheku2018-07-061-52/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Throughout the hashing framework, hashes are reduced into the fixnum range, and returned as cnum. This is not necessary; only the hash-eql and hash-equal functions need to reduce hashes to fixnums. Let's make it ucnum everywhere else, using its full range (no reduction into the [0, NUM_MAX) range). * hash.c (struct hash_ops): hash_fun function pointer returns ucnum instead of cnum. (hash_double): Return unreduced ucnum. Obsolete #ifdef-s removed; the ucnum type gives us a pointer-wide unsigned integer on all platforms. (equal_hash, eql_hash): Return ucnum. Don't reduce values to fixnum range. Some of the way we combine hashes from recursive calls changes; we multiply by at most 2 not to lose too many bits. (eql_hash_op, cobj_eq_hash_op, hash_hash_op): Return ucnum. * hash.h (equal_hash): Declaration updated. * lib.c (cobj_handle_hash_op): Return value changes to ucnum. * lib.h (struct cobj_ops): Hash function pointer's return type changes. (cobj_eq_hash_op, cobj_handle_hash_op): Declarations updated. * struct.c (struct_inst_hash): Return value changes to ucnum.
* hash: C++ maintenance.Kaz Kylheku2018-07-061-2/+2
| | | | | | | | * hash.c (hash_buf): Make size parameter unsigned. This eliminates a signed/unsigned comparison error from the GNU C++ compiler. (equal_hash): Use c_unum to get the buffer length. Should that be negative, c_unum will throw.
* hashing: overhaul part 2.Kaz Kylheku2018-07-051-6/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | | In this commit we feature-complete the seeded hashing implementation. The *hash-seed* special variable is provided from which newly created hashes take their seed. The make-hash and hash-equal functions get an optional seed argument. A function called gen-hash-seed is provided for obtaining a randomized seed. * hash.c (hash_seed): New macro. (hash_seed_s): New symbol variable. (make_seeded_hash): New function, made from make_hash. (make_hash): Reduced to wrapper around make_seeded_hash. (hash-equal): Take seed argument. (gen_hash_seed): New function. (hash_init): Initialize hash_seed_s and register *hash-seed* special variable. Re-register make-hash with new optional parameter, with regard to make_seeded_hash. Re-register hash-equal with new optional parameter. Register gen-hash-seed. * hash.h (make_seeded_hash): Declared. (hash_equal): Declaration updated. * txr.1: Documented optional seed arguments of make-hash and hash-equal. Documented new *hash-seed* variable and gen-hash-seed function.
* hashing: overhaul part 1.Kaz Kylheku2018-07-041-67/+95
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Hashing of buffers and character strings is being replaced with a seedable hash, providing a tool against denial of service attacks against hash tables. This commit lays most of the groundwork: most of the internal interface changes, and a new hashing implementation. What is missing is the mechanisms to do the seeding. * hash.c (struct hash_ops): Hash operation now takes a seed argument of type ucnum. (struct hash): New member, seed. (hash_str_limit): Default value changed to INT_MAX. A short value opens the gateway to an obvious collision attack whereby strings sharing the same 128 character prefix are entered into the same hash table, which will defeat any seedings strategy. (randbox): New static array. Values come from the Kazlib hash module, but are not used in exactly the same way. (hash_c_str, hash_buf): Now take a seed argument, and are rewritten. (equal_hash): Takes a seed, and passes it to hash_c_str, hash_buf and to recursive self calls. (eql_hash_op): New static function. Adapts the eql_hash operation, which doesn't take a seed, to the new interface that calls for a seed. (obj_eq_hash_op): Take a seed; ignore it. (hash_hash_op): Take a seed, pass it down to equal_hash. (hash_eql_ops): Wire hash functiono pointer to eql_hash_op instead of eql_hash. (make_hash): For now, intialize the hash's seed to zero. (make_similar_hash): Copy original hash's seed. (gethash_c, gethash_e, remhash): Pass hash table's seed to the hashing function. (hash_equal): Pass a seed of zero to equal_hash for now; this function will soon acquire an optional parameter for the seed. * hash.h (equal_hash): Declaration updated. * lib.c (cobj_handle_hash_op): Take seed argument, pass down. * lib.h (cobj_ops): Hash operation now takes seed. (cobj_eq_hash_op, cobj_handle_hash_op): Declarations updated. * struct.c (struct_inst_hash): Take seed argument, pass down. * tests/009/json.expected: Updated, because the hash table included in this output is now printed in a different order.
* hash: move ops into static structure + bug found.Kaz Kylheku2018-06-221-32/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The four hash operations (hash, equal, assoc and acons) are moved out of the hash instance and into a static table of operations. This means we have to go through one more indirection when calling them, but we save some space and shorten initialization. A bug is fixed here: the copy_hash function was only copying three out of these four functions; the equal operation was left uninitialized eposing the hash equality operation to corrupt behavior. Now that function just copies the hops pointer, so all is well. * hash.c (struct hash_ops): New struct type. (hash_ops_init): New macro. (struct hash): hash_fun, equal_fun, assoc_fun and assoc_new_c fun members removed. New member hops. (hash_eql_ops, hash_equal_ops): New static structures. (hash_equal_op): Compare the hops pointers rather than just the hash_fun: if two hashes have different hops pointers, they are different, period. Indirect through ops for calling equal fun and others. (hash_hash_op): Include the hops pointer in the hash, rather than the hash_fun pointer. (hash_print_op): Test for hash type (equal based or eql based) now done by comparing the hops pointer to one of the two static structures, rather than hash_fun to one of two functions. (make_hash, make_similar_hash, copy_hash): Initialize hops; remove initializations for the four functions. (gethash_c, gethash_e, remhash): Indirect through hops to invoke hash operations. (hash_uni, hash_diff, hash_isec): Incompatible hash check based on comparing hops pointer rather than hash_fun.
* hash: fix broken equality-of-two-hashes test.Kaz Kylheku2018-06-221-2/+2
| | | | | * hash.c (hash_equal_op): Fix broken logic that is supposed to push a cell onto the pending list: rplaca should be rplacd.
* printer: improve object formatting.Kaz Kylheku2018-04-051-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There is an issue with the printer in that it produces output whereby objects continue on the same line after a multi-line object, e.g: (foo (foobly bar xyzzy quux) (oops same line)) rather than: (foo (foobly bar xyzzy quux) (oops same line)) There is a simple fix for this: set a flag to force a line break on the next width-check operation whenever an object has been broken into multiple lines. width-check can return a Boolean indication whether it generated a line break, and so aggregate object printing routines can tell whether their object has been broken into lines, and set the flag. * stream.h (struct strm_base): New member, force_break. (force_break): Declared. * stream.c (strm_base_init): Extent initializer to cover force_break flag. (put_string, put_char): Clear the force_break flag whenever we hit column zero. (width_check): If indent mode is on, and force_break is true, generate a break. Clear force_break. (force_break): New function. (stream_init): Register force-break intrinsic. * buf.c (buf_print): Set the force break flag if the buffer was broken into multiple lines. * hash.c (hash_print_op): Set the force break flag if the hash was broken into multiple lines. * lib.c (obj_print_impl): Same logic for lists. * struct.c (struct_inst_print): Same logic for structs. * tests/009/json.expected, tests/011/macros-2.expected, tests/012/struct.tl, tests/017/glob-zarray.expected: Update expected textual output to reflect new formatting.
* Copyright year bump 2018.Kaz Kylheku2018-02-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * LICENSE, LICENSE-CYG, METALICENSE, Makefile, args.c, args.h, arith.c, arith.h, buf.c, buf.h, cadr.c, cadr.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, 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/awk.tl, share/txr/stdlib/build.tl, share/txr/stdlib/cadr.tl, share/txr/stdlib/conv.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/path-test.tl, share/txr/stdlib/place.tl, share/txr/stdlib/pmac.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/txr-case.tl, share/txr/stdlib/type.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, txr.1, txr.c, txr.h, unwind.c, unwind.h, utf8.c, utf8.h, win/cleansvg.txr: Extended Copyright line to 2018.
* Use rplaca and rplacd instead of set over car_l/cdr_l.Kaz Kylheku2018-01-011-4/+4
| | | | | | | | | | | | | | | | | | | | | | | This reduces the proliferation of car_l and cdr_l. With this change, nreverse should work on chains of objects that implement rplacd. * combi.c (comb_gen_fun_common, rcomb_gen_fun_common): Use rplaca. * eval.c (mappendv, mapdov): Likewise * hash.c (hash_equal_op): Likewise. * lib.c (nreverse, acons_new, aconsql_new, sort_list): Use rplaca and rplacd. * match.c (dest_set, v_gather, v_collect, v_flatten, v_cat, v_output, v_filter): Likewise * parser.c (ensure_parser): Use sys_rplacd. * unwind.c (uw_register_subtype): Use rplacd.
* hash: read/print consistency regression.Kaz Kylheku2017-12-281-2/+8
| | | | | | | | | | | | | | | | | | | | | | TXR 188 makes a slight mess of the #H notation. An :eql-based hash table prints as #H(() ...), but when that notation is read, it produces an :equal-based hash table. No aspect of this situation was intended; the intent was that the notation stays the same as before, and just the hash function changes to make :equal-based the default. Let's just go with this and have #H(() ...) denote :equal-based tables. * hash.c (hash_print_op): Print an :eql-based for eql-based hash tables, and nothing for equal-based ones. In compatibility mode with 188 and older, reproduce the old behavior, rendering equal-based tables with :equal-based and the absence of a symbol for eql-based. * txr.1: Updated places that touch on :equal-based and added compatibility notes. * tests/009/json.expected: updated, since equal-based hash tables now print without :equal-based keyword.
* hash tables: now default to :equal-based.Kaz Kylheku2017-12-061-3/+28
| | | | | | | | | | | | | | * hash.c (eql_based_k): New keyword variable. (equal_based_p): New static function. (hashv): Use eql_based_p to determine whether to make an equal-based hash table. Subject to opt_compat relative to version 187. (hash_init): Intern :eql-based keyword and store in new variable. * hash.h (eql_based_k, userdata_k): Declared. * txr.1: Documentation updated, with compat notes too.
* args: redesign args extractor to just use array.Kaz Kylheku2017-12-041-6/+7
| | | | | | | | | | | | | | | | | | | * args.c (struct args_bool_key): Structure moved to header file. (struct args_bool_ctx): One more piece of context information, the array size. (args_check_key_store): Work with array of args_bool_key structs rather than linked list. Remove useless local variable "store". (args_key_extract_vl): Function removed. (args_key_extract): Takes array instead of va_list. * args.h (struct args_bool_key): Structure declared here. Loses the next pointer since not used for a linked list. (args_key_extract_vl): Function removed. (args_key_extract): Redeclared. * hash.c (hashv): Adapt to new args_key_extract function.
* hash: use new args keyword extraction mechanism.Kaz Kylheku2017-12-011-6/+8
| | | | * hash.c (hashv): Switch over to args_keys_extract.
* hash: optimization in remhash.Kaz Kylheku2017-10-231-4/+8
| | | | | | | | | | | | * hash.c (remhash): Walk chain to splice out to-be-removed entry using an approach similar to what is done in do_weak_tables to splice out lapsed weak entries. This eliminates one extra traversal of the chain as well as consing due to the ldiff call. We use raw pointers obtained using valptr, and direct assignment through *pchain because later cells in a chain are strictly older objects than earlier cells and so so the *pchain = cdr(*pchain) assignment cannot make a generation 1 object point to a generation 0 object.
* hash: fix broken copy_hash.Kaz Kylheku2017-10-231-1/+15
| | | | | | | | | | | | | | | | Impact assessment: this bug affects the correctness of all programs which rely on copying hash tables. Direct reliance means the use of copy-hash, or using the generic copy function on hash objects. Indirect reliance occurs through hash-diff which uses copy-hash. Nothing in TXR itself calls hash-diff. The the listener's Tab completion relies on copy-hash for package-sensitive symbol visibility calculation. Since that is an interactive feature, the impact is low. * hash.c (copy_hash_chain): New static function. (copy_hash): Use copy_hash_chain instead of copy_alist, since the pairs are hash conses and not regular conses: they have a hash value field that must be copied.
* hash: remove pointless nullify ops.Kaz Kylheku2017-10-231-4/+0
| | | | | | | * hash.c (hash_assoc, hash_assql): Remove useless nullify calls. These are copy and paste leftovers, since these functions were based on assoc and assql, which handle sequences other than lists.
* bugfix: fixnum crackdown.Kaz Kylheku2017-09-131-4/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The purpose of this commit is to address certain situations in which code is wrongly relying on a cnum value being in the fixnum range (NUM_MIN to NUM_MAX), so that num_fast can safely be used on it. One wrong pattern is that c_num is applied to some Lisp value, and that value (or one derived from it arithmetically) is then passed to num_fast. The problem is that c_num succeeds on integers outside of the fixnum range. Some bignum values convert to a cnum successfully. Thus either num has to be used instead of num_fast, or else the original c_num attempt must be replaced with something that will fail if the original value isn't a fixnum. (In the latter case, any arithmetic on the fixnum cannot produce value outside of that range). * buf.c (buf_put_bytes): The size argument here is not guaranteed to be in fixnum range: use num. * combi.c (perm_init_common): Throw if the sequence length isn't a fixnum. Thus the num_fast in perm_while_fun is correct, since the ci value is bounded by k, which is bounded by n. * hash.c (hash_grow): Remove dubious assertion which aborts the run-time if the hash table doubling overflows. Simply don't allow the modulus to grow beyond NUM_MAX. If doubling it makes it larger than NUM_MAX, then just don't grow the table. We need the modulus to be in fixnum range, so that uses of num_fast on the modulus value elsewhere are correct. (group_by, group_reduce): Use c_fixnum rather than c_num to extract a value that is later assumed to be a fixnum. * lib.c (c_fixnum): New function. (nreverse, reverse, remove_if, less, window_map_list, sort_vec, unique): Use c_fixnum rather than c_num to extract a value that is later assumed to be a fixnum. (string_extend): Use c_fixnum rather than c_num to extract a value that is later assumed to be a fixnum. Cap the string allocation size to fixnum range rather than INT_PTR_MAX. (cmp_str): The wcscmp function could return values outside of the fixnum range, so we must use num, not num_fast. * lib.h (c_fixnum): Declared.
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-18 07:10:50 +0000