summary refs log tree commit diff stats
path: root/lib/pure/cstrutils.nim
diff options
context:
space:
mode:
authorc-blake <c-blake@users.noreply.github.com>2020-06-10 14:53:18 -0400
committerGitHub <noreply@github.com>2020-06-10 19:53:18 +0100
commit6aa971d39f1339a27a953972cd329f9cbe791f98 (patch)
tree6e48631181605838376db4727a4e425dacb08ba8 /lib/pure/cstrutils.nim
parent8bbdb8f43fb0da04d4b75bca011662f690972bfe (diff)
downloadNim-6aa971d39f1339a27a953972cd329f9cbe791f98.tar.gz
Add `proc find` to `heapqueue` (#14628)
* Unwind just the "pseudorandom probing" (whole hash-code-keyed variable
stride double hashing) part of recent sets & tables changes (which has
still been causing bugs over a month later (e.g., two days ago
https://github.com/nim-lang/Nim/issues/13794) as well as still having
several "figure this out" implementation question comments in them (see
just diffs of this PR).

This topic has been discussed in many places:
  https://github.com/nim-lang/Nim/issues/13393
  https://github.com/nim-lang/Nim/pull/13418
  https://github.com/nim-lang/Nim/pull/13440
  https://github.com/nim-lang/Nim/issues/13794

Alternative/non-mandatory stronger integer hashes (or vice-versa opt-in
identity hashes) are a better solution that is more general (no illusion
of one hard-coded sequence solving all problems) while retaining the
virtues of linear probing such as cache obliviousness and age-less tables
under delete-heavy workloads (still untested after a month of this change).

The only real solution for truly adversarial keys is a hash keyed off of
data unobservable to attackers.  That all fits better with a few families
of user-pluggable/define-switchable hashes which can be provided in a
separate PR more about `hashes.nim`.

This PR carefully preserves the better (but still hard coded!) probing
of the  `intsets` and other recent fixes like `move` annotations, hash
order invariant tests, `intsets.missingOrExcl` fixing, and the move of
`rightSize` into `hashcommon.nim`.

* Fix `data.len` -> `dataLen` problem.

* Add neglected API call `find` to heapqueue.

* Add a changelog.md entry, `since` annotation and rename parameter to be
`heap` like all the other procs for consistency.

* Add missing import.
Diffstat (limited to 'lib/pure/cstrutils.nim')
0 files changed, 0 insertions, 0 deletions