1. 06 Nov, 2018 2 commits
  2. 15 Jan, 2018 1 commit
  3. 08 Nov, 2017 1 commit
  4. 13 Apr, 2017 2 commits
    • Kirill Smelkov's avatar
      Merge pull request #8 from navytux/splitx · 6955404b
      Kirill Smelkov authored
      splitX bugfix test + simplification
      
      In the process of going through b code I've noticed that splitX bug fix (commit 5c732b36) handling logic was not covered by tests for edge cases and that this edge-handling logic itself can be simplified. Please find patches which add corresponding test and do the simplification attached.
      
      The simplified logic will be handy for upcoming work.
      
      Please see details in individual commit messages.
      
      Thanks beforehand,
      Kirill
      6955404b
    • Kirill Smelkov's avatar
      A+C: Add information about my contributions · 9fff7486
      Kirill Smelkov authored
      As requested by @cznic add information about me and my company to
      AUTHORS and CONTRIBUTORS.
      
      Btw, I'm not a lawyer and maybe there are country differences, but I
      used to think that:
      
      - author is the person who actually creates the work.
      - copyright holder is who owns the copyright on that work (i.e. the
        person, or company he is working for or someone else).
      
      The `AUTHORS` file however gets it the other way - it says to put there
      information about who is "copyright holder" which goes counterwise above
      classification.
      
      ----
      
      I understand however that the exact A+C approach is taken from the Go
      project so let's also continue following it here.
      9fff7486
  5. 12 Apr, 2017 3 commits
    • Kirill Smelkov's avatar
      Simplify "splitX bug" fix · 15a07c50
      Kirill Smelkov authored
      We are simplyfing commit 5c732b36 (Fix splitX bug.) here:
      
      By always passing to splitX i of index entry that is actually going to
      be used for traversal(*) we don't need to consider edge cases, such as
      when to move to next slot, inside splitX itself and this way there is no
      need to keep relookup logic there.
      
      So inside splitX it becomes very simple:
      
      	- i <= kx  -> go left
      	- i > kx   -> go right
      
      The logic to advance i by 1 on exact key hits was already there in Set
      and Put so it is natural for them to pass correct slot index to splitX.
      
      (*) i.e. index of next slot on exact index entry key hit - see previous
          patch for explanation
      15a07c50
    • Kirill Smelkov's avatar
      Add test for splitX bug fix covering logic handling splits on edges · 2a93ae07
      Kirill Smelkov authored
      Commit 5c732b36 (Fix splitX bug.) in particular modified splitX to redo
      the search on current level when key hits exactly kx slot in splitted X.
      
      However this is not tested at all as with current tests nothing breaks with the
      following patch:
      
      	@@ -546,10 +546,11 @@ func (t *Tree) Set(k interface{} /*K*/, v interface{} /*V*/) {
      	                i, ok := t.find(q, k)
      	                if ok {
      	                        switch x := q.(type) {
      	                        case *x:
      	                                if x.c > 2*kx {
      	+                                       panic("splitX ; ok=T")
      	                                        x, i = t.splitX(p, x, pi, i)
      	                                }
      	                                pi = i + 1
      	                                p = x
      	                                q = x.x[i+1].ch
      
      The relookup handling is needed exactly for ok=true case bacause if key is in
      xk slot there are 2 cases:
      
      1) key < x.x[xk].k  : here splitX is ok to let search follow left split child
      2) key = x.x[xk].k  : here splitX needs to let search follow right split child (*)
      
      and splitX, when knowing key comes from xk entry, does not bother itself with
      deciding which way to go (1 or 2) and for this case just follows up to make the
      search relookup current level after split.
      
      We can make existing tests cover this logic by raising N in TestSetGet2.
      However for kx=32, kd=32 N has to be increased more than 100x which, on my
      computer, increases the time to run TestSetGet2 from 0.5s to more than 200s,
      and still with it it only covers case when X does not have a parent.
      
      So instead of increasing N to be very large and slow down testing, let's add
      explicit test for this particular case.
      
      (*) reminder:
      
      `i, ok := find(q, k)` finds i corresponding to entry in q with min(k' : k <= k')
      (entry at i=q.c is always handled as with k'=∞)
      
      NOTE the "or-equal" in comparision. However keys in data (d) and index (x) page
      entries are treated differently. When find finds an entry with exact match (ok=true):
      
      - for d: d[i] is used
      
      	https://github.com/cznic/b/blob/aaaa43c9/btree.go#L409
      	https://github.com/cznic/b/blob/aaaa43c9/btree.go#L558
      
      - for x: x[i+1] is used:
      
      	https://github.com/cznic/b/blob/aaaa43c9/btree.go#L406
      	https://github.com/cznic/b/blob/aaaa43c9/btree.go#L555
      
      in other words keys located at index page entries says: all keys in child are
      strictly less than this key.
      
      This is probably so organized to help splitting - so split can pick lowest data
      entry from right data page and use its key as key in parent index entry for
      left data sibling directly.
      2a93ae07
    • Kirill Smelkov's avatar
      example: Regenerate int.go + cherry-pick corresponding all_test.go updates · 0f0644ab
      Kirill Smelkov authored
      example/int.go receives updates from aaaa43c9 (Fix Prev() to behave like
      Next() in reverse).
      
      We have to also update example/all_test.go because otherwise tests stop
      passing in example/ as the above commit changed both Prev and test
      logic.
      
      There are more missed updates to example/all_test.go - here I pick only
      minimum to keep tests passing in example/ .
      0f0644ab
  6. 29 Mar, 2017 1 commit
  7. 16 Jul, 2016 2 commits
  8. 10 Feb, 2016 1 commit
  9. 27 Oct, 2015 4 commits
  10. 21 Sep, 2015 1 commit
  11. 26 Apr, 2015 2 commits
  12. 29 Jan, 2015 1 commit
  13. 04 Sep, 2014 1 commit
  14. 18 Aug, 2014 1 commit
    • cznic's avatar
      A+C · 82d9e96a
      cznic authored
      82d9e96a
  15. 11 Aug, 2014 2 commits
  16. 10 Aug, 2014 1 commit
  17. 02 Jul, 2014 1 commit
  18. 01 Jul, 2014 1 commit
  19. 26 Jun, 2014 2 commits
  20. 22 Jun, 2014 2 commits
  21. 20 Jun, 2014 3 commits
  22. 19 Apr, 2014 1 commit
  23. 29 Jan, 2014 2 commits
  24. 23 Oct, 2013 1 commit
  25. 21 Oct, 2013 1 commit