- 12 Apr, 2017 2 commits
-
-
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.
-
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/ .
-
- 29 Mar, 2017 1 commit
-
-
Andrey Elenskiy authored
Enumerator.Prev() would return the next item if there was no hit. This fix instead changes Prev to return previous item as expected. Resolving issue https://github.com/cznic/b/issues/6.
-
- 16 Jul, 2016 2 commits
- 10 Feb, 2016 1 commit
-
-
Jan Mercl authored
-
- 27 Oct, 2015 4 commits
- 21 Sep, 2015 1 commit
-
-
Jan Mercl authored
-
- 26 Apr, 2015 2 commits
- 29 Jan, 2015 1 commit
-
-
Jan Mercl authored
-
- 04 Sep, 2014 1 commit
-
-
Jan Mercl authored
-
- 18 Aug, 2014 1 commit
-
-
Jan Mercl authored
-
- 11 Aug, 2014 2 commits
- 10 Aug, 2014 1 commit
-
-
kortschak authored
-
- 02 Jul, 2014 1 commit
-
-
Jan Mercl authored
-
- 01 Jul, 2014 1 commit
-
-
Jan Mercl authored
-
- 26 Jun, 2014 2 commits
- 22 Jun, 2014 2 commits
- 20 Jun, 2014 3 commits
- 19 Apr, 2014 1 commit
-
-
Jan Mercl authored
-
- 29 Jan, 2014 2 commits
-
-
cznic authored
clarify documentation
-
Brian Fallik authored
Clean up some of the documentation text for readability.
-
- 23 Oct, 2013 1 commit
-
-
Jan Mercl authored
-
- 21 Oct, 2013 1 commit
-
-
Jan Mercl authored
-
- 20 Oct, 2013 1 commit
-
-
Jan Mercl authored
-
- 29 Aug, 2013 1 commit
-
-
Jan Mercl authored
-
- 22 Jul, 2013 5 commits