1. 13 Jun, 2020 6 commits
  2. 05 Jun, 2020 1 commit
  3. 04 Jun, 2020 2 commits
  4. 03 Jun, 2020 2 commits
  5. 02 Jun, 2020 4 commits
  6. 01 Jun, 2020 2 commits
    • Geoff Simmons's avatar
      malloc the temp array used for sorting in .compile(). · 599fb3ac
      Geoff Simmons authored
      For large sets, workspace could be too small.
      599fb3ac
    • Geoff Simmons's avatar
      Implement perfect hashing based on universal hashing. · 278d6968
      Geoff Simmons authored
      Universal hashing has a sounder theoretical basis; in particular, it
      doesn't have the dubious minimum hash table size below which a
      perfect hash may not be possible, and which was set by trial and error.
      
      For nearly all test data, universal hashing performs at least as
      well or better. Especially better for sets with longer strings,
      since the subject string is cast as an array of uint32_t, so the
      hash is computed in fewer operations.
      
      The only exception I've noticed is /usr/share/dict/words, which now
      appears to have more collisions than under the previous approach.
      But it appears likely that this only becomes an issue for sets that
      are much larger than are probable for VCL use cases (in the 100,000
      range), and if all of the sets' elements are tested for matches
      about equally often (whereas real-world usage patterns tend to
      match a subset much more frequently).
      278d6968
  7. 31 May, 2020 2 commits
  8. 27 Mar, 2020 2 commits
    • Geoff Simmons's avatar
      afded0f5
    • Geoff Simmons's avatar
      Implement QP prefix searching without recursion. · 1ec2deee
      Geoff Simmons authored
      The new algorithm improves efficiency with iteration in place of
      recursion, and in a number of other ways:
      
      - Avoid searches into dead-end branches. The traversal of all branches
      was done because of the overlapping prefix case -- "foo" and "foobar"
      both in the set. Now we just search the tree for a match, but before
      descending into the next branch, check if there are other branches at
      which the current prefix matches a terminating node.
      
      - Only do string comparisons when we hit a terminating node.
      
      - Mark terminating nodes with a flag in the tree, so that we don't go
      looking for the null byte in the strings table during the search.
      
      While we're here, rename the flag for the nibble search as hinib --
      non-zero if and only if we inspect the most significant nibble at that
      node. Also remove some dead code from QP_Insert().
      1ec2deee
  9. 26 Mar, 2020 3 commits
  10. 24 Mar, 2020 2 commits
  11. 20 Mar, 2020 3 commits
  12. 06 Mar, 2020 3 commits
  13. 03 Mar, 2020 7 commits
  14. 28 Feb, 2020 1 commit