BTree provides a simple, ordered, in-memory data structure for Go programs.
License: Apache License 2.0
This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure.
The API is based off of the wonderful http://godoc.org/github.com/petar/GoLLRB/llrb, and is meant to allow btree to act as a drop-in replacement for gollrb trees.
See http://godoc.org/github.com/google/btree for documentation.
This isn't an issue per se, but more of a reaching out to the btree maintainer(s) to talk about a another module that might work well with btree since PR #43 is switching btree to use generics.
I have this module at https://github.com/keep94/consume2 documentation at https://pkg.go.dev/github.com/keep94/consume2 that I use primarily to read from databases. The main actor in this module is the Consumer interface that serves a similar purpose as ItemIterator in the btree module. The Consumer interface is used to collect values out of a database query just like the ItemIterator is used to collect values out of a btree. With this consume2 module, one can build more complicated Consumers out of simpler ones ultimately constructing complex pipelines to gather various results while executing the database query just once.
I would like users of the btree module to have the option of leveraging the consume2 module when iterating over a btree.
The following code can be used to convert a Consumer instance into an ItemIterator
func AsItemIterator[T Item[T]](consumer Consumer[T]) ItemIterator[T] {
return func(value T) bool {
consumer.Consume(value)
return consumer.CanConsume()
}
}
As you can see the Consumer interface has a CanConsume() method and a Consume() method whereas the ItemIterator is a simple function that returns false when consumption is done.
I thought about changing my Consumer interface to have just one method Consume() that returns a bool, like ItemIterator, but I am not sure if that would be better or worse than what I have now. The advantage of having a CanConsume() method is you can test to see if a Consumer can Consume a value without needing to consume a value. That may offer some advantages over just having one Consume() method that returns a bool indicating whether it can accept more values. The disadvantage of having a CanConsume() method is that the Consume() method has to repeat the logic of CanConsume() in case the caller decides to call Consume() without calling CanConsume() first.
So I have three choices:
I think option 3 would be kind of confusing since I also have functions that accept a T value and return a bool that act as filters. I am leaning toward option 1 or option 2.
What do you think would be best for the community?
Thank you for your feedback.
Line 204 in be84af9
I'm curious if this bounds issue is important? I'm using this implementation as a learning opportunity for Go and ran into this while studying the code.
The check whether the index is less than the length seems like it would prevent an unnecessary copy. But instead, this would result in a bounds error when attempting to set the item.
I'm using btree to provide an in-memory key-value store for use as a non-persistent substitute for other key-value databases in a cacheing application. The interface that I need to implement using this package requires that I provide an iterator which exposes Next() and Prev() methods.
I have done this using the AscendGreaterOrEqual and DescendLessOrEqual methods as follows: I store a pointer to the current item, and use it as a reference to ascend or descend from, when Next() or Prev() are called, respectively.
While, I believe that internally, iteration within the provided method calls is O(1), in my case, I believe that the lookup of the current item is always O(logN). Since there is not another obvious, O(1) way (to me at least) to restart iteration from a given Item, and move forward or backward one position in the manner I need, and which is common in most key-value store interfaces, I was wondering if the authors thought it might be useful to expose another way to control iteration in a step-by-step manner - O(1) - which keeps track of the current item.
In go doc ,says "Write operations are not safe for concurrent mutation by multiple goroutines, but Read operations are."
But I don`t kown is this safe : "only one goroutine put and some other goroutines get" ,should I lock it ?
Wrote some test codes but got fatal error
bt := btree.New(32)
var wg sync.WaitGroup
//var lock sync.Mutex
for i:=1;i<10000;i++ {
wg.Add(1)
go func(n int) {
//lock.Lock()
bt.ReplaceOrInsert(btree.Int(n))
bt.Delete(btree.Int(n))
//lock.Unlock()
wg.Done()
}(i)
}
wg.Wait()
t.Log(bt.Len())
bt.Clear(true)
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x18 pc=0x5264b1]
goroutine 94 [running]:
github.com/google/btree.items.find(0xc000050010, 0x1, 0x1, 0x7a6820, 0xc00008e1e0, 0x0, 0x0)
/mnt/d/develop/go/pkg/mod/github.com/google/[email protected]/btree.go:191 +0xc1
With support for generics, we can replace interfaces with generic types.
The use of generics avoids variables escaping to heap when calling the B-tree functions yielding 20-30% improvement.
Below are some comparisons between benchmarks (taken from original repository) done with benchstat:
name old time/op new time/op delta
Insert-8 121ns ± 1% 89ns ± 1% -27.04% (p=0.008 n=5+5)
Seek-8 115ns ± 1% 78ns ± 0% -31.56% (p=0.008 n=5+5)
DeleteInsert-8 248ns ± 0% 185ns ± 1% -25.51% (p=0.008 n=5+5)
DeleteInsertCloneEachTime-8 1.10µs ± 5% 0.61µs ± 1% -44.45% (p=0.008 n=5+5)
Delete-8 138ns ± 1% 101ns ± 1% -26.62% (p=0.008 n=5+5)
Get-8 102ns ± 1% 71ns ± 0% -30.46% (p=0.008 n=5+5)
Ascend-8 40.2µs ± 1% 31.7µs ± 0% -21.18% (p=0.008 n=5+5)
Descend-8 39.3µs ± 1% 30.7µs ± 1% -21.91% (p=0.008 n=5+5)
AscendRange-8 72.3µs ± 1% 57.6µs ± 1% -20.39% (p=0.008 n=5+5)
DescendRange-8 92.9µs ± 1% 77.6µs ± 1% -16.45% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Insert-8 35.6B ± 4% 18.4B ± 3% -48.31% (p=0.008 n=5+5)
Seek-8 7.00B ± 0% 0.00B -100.00% (p=0.008 n=5+5)
DeleteInsert-8 0.00B 0.00B ~ (all equal)
DeleteInsertCloneEachTime-8 2.98kB ± 5% 1.91kB ± 1% -36.16% (p=0.008 n=5+5)
Delete-8 0.00B 0.00B ~ (all equal)
Get-8 0.00B 0.00B ~ (all equal)
Ascend-8 0.00B 0.00B ~ (all equal)
Descend-8 0.00B 0.00B ~ (all equal)
AscendRange-8 0.00B 0.00B ~ (all equal)
DescendRange-8 0.00B 0.00B ~ (all equal)
name old allocs/op new allocs/op delta
Insert-8 0.00 0.00 ~ (all equal)
Seek-8 0.00 0.00 ~ (all equal)
DeleteInsert-8 0.00 0.00 ~ (all equal)
DeleteInsertCloneEachTime-8 11.0 ± 0% 11.0 ± 0% ~ (all equal)
Delete-8 0.00 0.00 ~ (all equal)
Get-8 0.00 0.00 ~ (all equal)
Ascend-8 0.00 0.00 ~ (all equal)
Descend-8 0.00 0.00 ~ (all equal)
AscendRange-8 0.00 0.00 ~ (all equal)
DescendRange-8 0.00 0.00 ~ (all equal)
In case of plain Insert Benchmark, the results are even better:
name old time/op new time/op delta
Insert-8 200ns ± 2% 137ns ± 1% -31.20% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Insert-8 60.0B ± 0% 27.0B ± 0% -55.00% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
Insert-8 1.00 ± 0% 0.00 -100.00% (p=0.008 n=5+5)
func BenchmarkInsert(b *testing.B) {
b.StopTimer()
tr := btree.New(32)
b.StartTimer()
for i := 0; i < b.N; i++ {
tr.ReplaceOrInsert(btree.Int(i))
}
}Unfortunately the functions that return nil do not work ex. func (t *BTree) Delete(item Item) Item.
We can't simply return zero value for generic type, because it's still a valid value, so I decided to change the API, so that:
func (t *BTree[T]) Delete(item T) (T, bool) { ... }we also return bool which indicates whether anything was really deleted.
Of course, we can implement B-tree on pointers to generic types, but it harms performance in many cases (like having B-tree for numeric types).
Changes of API destroy backward compatibility, but because of reasons mentioned above, I believe that this approach is justified.
Here is link to forked repository with generic B-tree:
https://github.com/Michal-Leszczynski/btree
How do you suggest we further proceed with this effort.
when calling DescendRange methods, an iteration is performed.
All items between [lessOrEqual, greaterThan ) are iterated.
Suppose there're n items in the range, I though Less function is called log(n) times.
However, Less is called more than n times as a matter of
if stop != nil && !n.items[i].Less(stop) {
return hit, false
}
Why make comparisons this way? I though if parent node can decide all its children are in the range, most Less(stop) call can be optimized out.
Are there anything wrong with this idea?
https://forum.golangbridge.org/t/how-to-use-github-com-google-btree/4086/3
For example, I want to insert into the btree, and the btree is sorted by v2, without modifying the source code of btree library
So basically I want to do CRUD on the btree(Create a node and then insert, Retrieve the node, Update the node by changing the v2,Delete the node by v1)
It will be better if it can generalize to arbitrary item and sort by certain element.
I'm hitting a Index error using Ascend to walk the tree.
panic: runtime error: index out of range
goroutine 20 [running]:
github.com/google/btree.(*node).iterate(0xc420115d00, 0x1, 0x0, 0x0, 0x0, 0x0, 0x440000, 0xc42008ef00, 0x300000002)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:524 +0x7df
github.com/google/btree.(*node).iterate(0xc4201780c0, 0x1, 0x0, 0x0, 0x0, 0x0, 0xc420030000, 0xc42008ef00, 0xc4200b00d8)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc4201f4e00, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0xc42008ed08)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc420382900, 0x1, 0x0, 0x0, 0x0, 0x0, 0xc420080000, 0xc42008ef00, 0xc4200100a0)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc4207c14c0, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0xc420103200)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc420d11e40, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0x0)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc423456040, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0x0)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*BTree).Ascend(0xc420132020, 0xc42008ef00)
/media/scratch/demo/go/src/github.com/google/btree/btree.go:777 +0x5b
main.stage.func1(0xc420018330, 0xc4201280c0, 0x5a6520, 0xc4201180c0, 0xc420128060, 0xc420116100)
/media/scratch/demo/demo.go:166 +0x28a
created by main.stage
/media/scratch/demo/demo.go:130 +0xd3My stage function is putting O(0.5M) object pointers into the BTree:
Sketched implementation:
const (
BTREE_DEGREE = 7
)
type myTreeItem struct {
Object *myObject
Order int
}
func (a myTreeItem) Less(b btree.Item) bool {
return a.Order < b.Order
}
processChannel := make(chan *myObject, 1000)
bt := btree.New(BTREE_DEGREE)
// Insert Objects
order := 0
for obj := range objects {
ci := &myTreeItem{
Object: obj,
Order: order,
}
i := bt.ReplaceOrInsert(ci)
order += 1
}
// Traverse
bt.Ascend(func (i btree.Item) bool {
processChannel <- i.(*myTreeItem).Object
return true
})Any ideas?
Hey there Google Team!
Are there any plans to support the BinaryMarshaler interface? This would be super useful if someone want's to store B-Tree's to disk.
My case: I have always two clones, one for updating and the other for read traversal, every time a "transaction" is done I clone again the tree to force the next update to copy the nodes.
The problem with cow: even for this case it may occur that the reader traverses a subtree that's sill being modified (i.e. and incomplete). The cause is that mutableFor() changes t.root immediately and the changes are applied to the new root. The same happens for children derived from mutableChildren() that changes the also n.children[i].
The solution is to delay the change to the original pointer (root or children) until all changes in the subtree are finished.
I prepared a first patch wit the idea, only for t.root: master...gallir:cow
If it's correct and you agree I can prepare a patch for children and items if needed.
i'm writing a kind of MFU cache
i'm using the KCounter where the KCounter.value is the frequency of the KCounter.key
the tree holds only N keys with the highest frequency , when there is no more room left the key with the minimal frequency will be dropped
running this code will result in runtime error
const maxCacheSize = 3
type KCounter struct {
key string
value int
}
func (t KCounter) Less(than btree.Item) bool {
counter := than.(KCounter)
if t.key < counter.key {
return true
}
return t.value < counter.value
}
func Test_B(t *testing.T) {
put := func(t *btree.BTree, itemByKey map[string]KCounter, kc KCounter) bool {
item, ok := itemByKey[kc.key]
if ok {
//update the value by re-inserting it
t.Delete(item)
t.ReplaceOrInsert(kc)
itemByKey[kc.key] = kc
return true
}
if t.Len() >= maxCacheSize {
smallestItem := t.Min().(KCounter)
if kc.value < smallestItem.value {
//dont add group that have values that are smaller than the smallest elem in tree
return false
}
t.DeleteMin()
}
t.ReplaceOrInsert(kc)
itemByKey[kc.key] = kc
return true
}
itemByKey := make(map[string]KCounter)
tree := btree.New(15)
for i := 0; i < 100000; i++ {
put(tree, itemByKey, KCounter{strconv.Itoa(i % 20), i % 10})
}
}
the error
/opt/homebrew/opt/go/libexec/bin/go tool test2json -t /Users/igadassi/Library/Caches/JetBrains/GoLand2023.3/tmp/GoLand/___Test_B_in_xdr_panw_ipl_internal_dml_cronus_throttler.test -test.v -test.paniconexit0 -test.run ^\QTest_B\E$
=== RUN Test_B
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0x140202e0350 stack=[0x140202e0000, 0x140402e0000]
fatal error: stack overflow
runtime stack:
runtime.throw({0x10532ec2f?, 0x200000008?})
/opt/homebrew/opt/go/libexec/src/runtime/panic.go:1077 +0x40 fp=0x16ae62690 sp=0x16ae62660 pc=0x104fd6af0
runtime.newstack()
/opt/homebrew/opt/go/libexec/src/runtime/stack.go:1107 +0x458 fp=0x16ae62840 sp=0x16ae62690 pc=0x104ff1f38
runtime.morestack()
/opt/homebrew/opt/go/libexec/src/runtime/asm_arm64.s:316 +0x70 fp=0x16ae62840 sp=0x16ae62840 pc=0x10500b7b0
goroutine 22 [running]:
sort.Search(0x8?, 0x140202e0398)
/opt/homebrew/opt/go/libexec/src/sort/search.go:58 +0x8c fp=0x140202e0350 sp=0x140202e0350 pc=0x10503af7c
github.com/google/btree.items[...].find(0x0, {0x1054aa628, 0x14000285f98?}, 0x1054a7a78?)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:215 +0x78 fp=0x140202e03e0 sp=0x140202e0350 pc=0x1052e8118
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:384 +0x1cc fp=0x140202e0470 sp=0x140202e03e0 pc=0x1052e697c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e05b0 sp=0x140202e0470 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e0640 sp=0x140202e05b0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e0780 sp=0x140202e0640 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e0810 sp=0x140202e0780 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e0950 sp=0x140202e0810 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e09e0 sp=0x140202e0950 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e0b20 sp=0x140202e09e0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e0bb0 sp=0x140202e0b20 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e0cf0 sp=0x140202e0bb0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e0d80 sp=0x140202e0cf0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e0ec0 sp=0x140202e0d80 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e0f50 sp=0x140202e0ec0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e1090 sp=0x140202e0f50 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e1120 sp=0x140202e1090 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e1260 sp=0x140202e1120 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e12f0 sp=0x140202e1260 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e1430 sp=0x140202e12f0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e14c0 sp=0x140202e1430 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e1600 sp=0x140202e14c0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e1690 sp=0x140202e1600 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e17d0 sp=0x140202e1690 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e1860 sp=0x140202e17d0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e19a0 sp=0x140202e1860 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e1a30 sp=0x140202e19a0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e1b70 sp=0x140202e1a30 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e1c00 sp=0x140202e1b70 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e1d40 sp=0x140202e1c00 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e1dd0 sp=0x140202e1d40 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e1f10 sp=0x140202e1dd0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e1fa0 sp=0x140202e1f10 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e20e0 sp=0x140202e1fa0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e2170 sp=0x140202e20e0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e22b0 sp=0x140202e2170 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e2340 sp=0x140202e22b0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e2480 sp=0x140202e2340 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e2510 sp=0x140202e2480 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e2650 sp=0x140202e2510 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e26e0 sp=0x140202e2650 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e2820 sp=0x140202e26e0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e28b0 sp=0x140202e2820 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e29f0 sp=0x140202e28b0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e2a80 sp=0x140202e29f0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e2bc0 sp=0x140202e2a80 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e2c50 sp=0x140202e2bc0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e2d90 sp=0x140202e2c50 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140202e2e20 sp=0x140202e2d90 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140202e2f60 sp=0x140202e2e20 pc=0x1052e663c
...2314001 frames elided...
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402dd7b0 sp=0x140402dd670 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dd840 sp=0x140402dd7b0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402dd980 sp=0x140402dd840 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dda10 sp=0x140402dd980 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402ddb50 sp=0x140402dda10 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402ddbe0 sp=0x140402ddb50 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402ddd20 sp=0x140402ddbe0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dddb0 sp=0x140402ddd20 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402ddef0 sp=0x140402dddb0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402ddf80 sp=0x140402ddef0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402de0c0 sp=0x140402ddf80 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402de150 sp=0x140402de0c0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402de290 sp=0x140402de150 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402de320 sp=0x140402de290 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402de460 sp=0x140402de320 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402de4f0 sp=0x140402de460 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402de630 sp=0x140402de4f0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402de6c0 sp=0x140402de630 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402de800 sp=0x140402de6c0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402de890 sp=0x140402de800 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402de9d0 sp=0x140402de890 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dea60 sp=0x140402de9d0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402deba0 sp=0x140402dea60 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dec30 sp=0x140402deba0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402ded70 sp=0x140402dec30 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dee00 sp=0x140402ded70 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402def40 sp=0x140402dee00 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402defd0 sp=0x140402def40 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402df110 sp=0x140402defd0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402df1a0 sp=0x140402df110 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402df2e0 sp=0x140402df1a0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402df370 sp=0x140402df2e0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402df4b0 sp=0x140402df370 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402df540 sp=0x140402df4b0 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402df680 sp=0x140402df540 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402df710 sp=0x140402df680 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402df850 sp=0x140402df710 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402df8e0 sp=0x140402df850 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x0, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402dfa20 sp=0x140402df8e0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dfab0 sp=0x140402dfa20 pc=0x1052e6c0c
github.com/google/btree.(*node[...]).growChildAndRemove(0x1054b56c0, 0x1, {0x1054aa628, 0x14000285f98}, 0xe, 0x1054a7a78)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:471 +0xd3c fp=0x140402dfbf0 sp=0x140402dfab0 pc=0x1052e663c
github.com/google/btree.(*node[...]).remove(0x1054b56c0, {0x1054aa628, 0x14000285f98}, 0xe, 0x0)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:396 +0x45c fp=0x140402dfc80 sp=0x140402dfbf0 pc=0x1052e6c0c
github.com/google/btree.(*BTreeG[...]).deleteItem(0x1054b5400, {0x1054aa628, 0x14000285f98}, 0x14000285f98)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:734 +0xa4 fp=0x140402dfce0 sp=0x140402dfc80 pc=0x1052e8864
github.com/google/btree.(*BTreeG[...]).Delete(...)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:712
github.com/google/btree.(*BTree).Delete(0x105459520?, {0x1054aa628?, 0x14000285f98?})
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/google/[email protected]/btree_generic.go:956 +0x40 fp=0x140402dfd20 sp=0x140402dfce0 pc=0x1052e5020
xdr.panw/ipl/internal/dml/cronus/throttler.Test_B.func1(0x140001fc9e0, 0x0?, {{0x10534714c, 0x2}, 0x5})
/Users/igadassi/gonzo/src/xdr.panw/ipl/internal/dml/cronus/throttler/throttler_test.go:361 +0xa8 fp=0x140402dfd70 sp=0x140402dfd20 pc=0x105328e58
xdr.panw/ipl/internal/dml/cronus/throttler.Test_B(0x14000268001?)
/Users/igadassi/gonzo/src/xdr.panw/ipl/internal/dml/cronus/throttler/throttler_test.go:384 +0x1bc fp=0x140402dff60 sp=0x140402dfd70 pc=0x105328d7c
testing.tRunner(0x140001a7860, 0x1054a6fa8)
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1595 +0xe8 fp=0x140402dffb0 sp=0x140402dff60 pc=0x1050b7908
testing.(*T).Run.func1()
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1648 +0x2c fp=0x140402dffd0 sp=0x140402dffb0 pc=0x1050b871c
runtime.goexit()
/opt/homebrew/opt/go/libexec/src/runtime/asm_arm64.s:1197 +0x4 fp=0x140402dffd0 sp=0x140402dffd0 pc=0x10500dca4
created by testing.(*T).Run in goroutine 1
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1648 +0x33c
goroutine 1 [chan receive]:
runtime.gopark(0x1400024d9b8?, 0x104fac00c?, 0x78?, 0xaf?, 0x18?)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:398 +0xc8 fp=0x1400024d940 sp=0x1400024d920 pc=0x104fd97b8
runtime.chanrecv(0x140002383f0, 0x1400024da3f, 0x1)
/opt/homebrew/opt/go/libexec/src/runtime/chan.go:583 +0x414 fp=0x1400024d9c0 sp=0x1400024d940 pc=0x104fa52a4
runtime.chanrecv1(0x10577c9e0?, 0x10540bcc0?)
/opt/homebrew/opt/go/libexec/src/runtime/chan.go:442 +0x14 fp=0x1400024d9f0 sp=0x1400024d9c0 pc=0x104fa4e54
testing.(*T).Run(0x140001a76c0, {0x10532b6d3?, 0x90133395fa5?}, 0x1054a6fa8)
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1649 +0x350 fp=0x1400024dab0 sp=0x1400024d9f0 pc=0x1050b85e0
testing.runTests.func1(0x14000265d70?)
/opt/homebrew/opt/go/libexec/src/testing/testing.go:2054 +0x48 fp=0x1400024db00 sp=0x1400024dab0 pc=0x1050ba408
testing.tRunner(0x140001a76c0, 0x1400024dc28)
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1595 +0xe8 fp=0x1400024db50 sp=0x1400024db00 pc=0x1050b7908
testing.runTests(0x1400025e8c0?, {0x105775000, 0x6, 0x6}, {0x40?, 0x10546faa0?, 0x0?})
/opt/homebrew/opt/go/libexec/src/testing/testing.go:2052 +0x3b4 fp=0x1400024dc50 sp=0x1400024db50 pc=0x1050ba304
testing.(*M).Run(0x1400025e8c0)
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1925 +0x538 fp=0x1400024dea0 sp=0x1400024dc50 pc=0x1050b8fd8
main.main()
_testmain.go:67 +0x1a8 fp=0x1400024df30 sp=0x1400024dea0 pc=0x10532a648
runtime.main()
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:267 +0x2bc fp=0x1400024dfd0 sp=0x1400024df30 pc=0x104fd935c
runtime.goexit()
/opt/homebrew/opt/go/libexec/src/runtime/asm_arm64.s:1197 +0x4 fp=0x1400024dfd0 sp=0x1400024dfd0 pc=0x10500dca4
goroutine 2 [force gc (idle)]:
runtime.gopark(0x0?, 0x0?, 0x0?, 0x0?, 0x0?)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:398 +0xc8 fp=0x1400005af90 sp=0x1400005af70 pc=0x104fd97b8
runtime.goparkunlock(...)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:404
runtime.forcegchelper()
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:322 +0xb8 fp=0x1400005afd0 sp=0x1400005af90 pc=0x104fd9618
runtime.goexit()
/opt/homebrew/opt/go/libexec/src/runtime/asm_arm64.s:1197 +0x4 fp=0x1400005afd0 sp=0x1400005afd0 pc=0x10500dca4
created by runtime.init.6 in goroutine 1
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:310 +0x24
goroutine 3 [GC sweep wait]:
runtime.gopark(0x0?, 0x0?, 0x0?, 0x0?, 0x0?)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:398 +0xc8 fp=0x1400005b760 sp=0x1400005b740 pc=0x104fd97b8
runtime.goparkunlock(...)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:404
runtime.bgsweep(0x0?)
/opt/homebrew/opt/go/libexec/src/runtime/mgcsweep.go:280 +0xa0 fp=0x1400005b7b0 sp=0x1400005b760 pc=0x104fc3f50
runtime.gcenable.func1()
/opt/homebrew/opt/go/libexec/src/runtime/mgc.go:200 +0x28 fp=0x1400005b7d0 sp=0x1400005b7b0 pc=0x104fb8a48
runtime.goexit()
/opt/homebrew/opt/go/libexec/src/runtime/asm_arm64.s:1197 +0x4 fp=0x1400005b7d0 sp=0x1400005b7d0 pc=0x10500dca4
created by runtime.gcenable in goroutine 1
/opt/homebrew/opt/go/libexec/src/runtime/mgc.go:200 +0x6c
goroutine 4 [GC scavenge wait]:
runtime.gopark(0x1400007c000?, 0x1053d12f8?, 0x1?, 0x0?, 0x140000031e0?)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:398 +0xc8 fp=0x1400005bf50 sp=0x1400005bf30 pc=0x104fd97b8
runtime.goparkunlock(...)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:404
runtime.(*scavengerState).park(0x10577d520)
/opt/homebrew/opt/go/libexec/src/runtime/mgcscavenge.go:425 +0x5c fp=0x1400005bf80 sp=0x1400005bf50 pc=0x104fc17fc
runtime.bgscavenge(0x0?)
/opt/homebrew/opt/go/libexec/src/runtime/mgcscavenge.go:653 +0x44 fp=0x1400005bfb0 sp=0x1400005bf80 pc=0x104fc1d54
runtime.gcenable.func2()
/opt/homebrew/opt/go/libexec/src/runtime/mgc.go:201 +0x28 fp=0x1400005bfd0 sp=0x1400005bfb0 pc=0x104fb89e8
runtime.goexit()
/opt/homebrew/opt/go/libexec/src/runtime/asm_arm64.s:1197 +0x4 fp=0x1400005bfd0 sp=0x1400005bfd0 pc=0x10500dca4
created by runtime.gcenable in goroutine 1
/opt/homebrew/opt/go/libexec/src/runtime/mgc.go:201 +0xac
goroutine 18 [finalizer wait]:
runtime.gopark(0xf780ec6195be80e2?, 0xa83c30d5eadc8e8f?, 0xc2?, 0xc6?, 0xb54ad9c0557f2d16?)
/opt/homebrew/opt/go/libexec/src/runtime/proc.go:398 +0xc8 fp=0x1400005a580 sp=0x1400005a560 pc=0x104fd97b8
runtime.runfinq()
/opt/homebrew/opt/go/libexec/src/runtime/mfinal.go:193 +0x108 fp=0x1400005a7d0 sp=0x1400005a580 pc=0x104fb7af8
runtime.goexit()
/opt/homebrew/opt/go/libexec/src/runtime/asm_arm64.s:1197 +0x4 fp=0x1400005a7d0 sp=0x1400005a7d0 pc=0x10500dca4
created by runtime.createfing in goroutine 1
/opt/homebrew/opt/go/libexec/src/runtime/mfinal.go:163 +0x80
Process finished with the exit code 1
can't load package: package go: downloading github.com/google/btree v1.0.0: malformed module path "go: downloading github.com/google/btree v1.0.0": invalid char ':'
What is the meaning of copyOnWriteContext ?
Only when tree is created, the only one copyOnWriteContext is initiated. There is no other time that create a newcopyOnWriteContext.
In function mutableFor, the n.cow always equals cow.
Suppose I have a simple set of intervals whose end time (endx) is stored in a btree. Lets say the interval represents the time a user's compute job completed, so I store the userid and a jobid with it too. I'll use the jobid (assume they are all unique) to break ties so that all records stick around.
Then I want to delete all those records with time <= some end time. Here's what I try:
package main
import (
"fmt"
"github.com/google/btree"
)
type job struct {
endx int64
user string
jobid string
}
func (a *job) Less(than btree.Item) bool {
b := than.(*job)
if a.endx == b.endx {
// simply distinguish the order,
// so we get to keep both in the tree.
return a.jobid < b.jobid
}
return a.endx < b.endx
}
func main() {
tree := btree.New(2)
tree.ReplaceOrInsert(&job{endx: 1, jobid: "hij"})
tree.ReplaceOrInsert(&job{endx: 1, jobid: "abc"})
tree.ReplaceOrInsert(&job{endx: 1, jobid: "def"})
tree.ReplaceOrInsert(&job{endx: 2, jobid: "hij"})
tree.ReplaceOrInsert(&job{endx: 2, jobid: "abc"})
tree.ReplaceOrInsert(&job{endx: 2, jobid: "def"})
tree.ReplaceOrInsert(&job{endx: 3, jobid: "hij"})
tree.ReplaceOrInsert(&job{endx: 3, jobid: "abc"})
tree.ReplaceOrInsert(&job{endx: 3, jobid: "def"})
fmt.Printf("len = %v\n", tree.Len())
// delete through the 2s
tree.AscendGreaterOrEqual(&job{endx: 0}, func(item btree.Item) bool {
j := item.(*job)
if j.endx <= 2 {
fmt.Printf("delete pass deletes %#v\n", item)
tree.Delete(j)
return true
}
fmt.Printf("delete pass ignores %#v\n", item)
return false
})
fmt.Printf("\n\n tree after deleting everything with "+
"endx <=2, is size %v; should be size 3\n",
tree.Len())
tree.AscendGreaterOrEqual(&job{endx: 0}, func(item btree.Item) bool {
fmt.Printf("%#v\n", item)
return true
})
}
here's what I get. This strange result presents in the upstream petar/gollrb as well.
go run ex1.go
len = 9
delete pass deletes &main.job{endx:1, user:"", jobid:"abc"}
delete pass deletes &main.job{endx:1, user:"", jobid:"hij"}
delete pass deletes &main.job{endx:2, user:"", jobid:"abc"}
delete pass ignores &main.job{endx:3, user:"", jobid:"abc"}
tree after deleting everything with endx <=2, is size 6; should be size 3
&main.job{endx:1, user:"", jobid:"def"}
&main.job{endx:2, user:"", jobid:"def"}
&main.job{endx:2, user:"", jobid:"hij"}
&main.job{endx:3, user:"", jobid:"abc"}
&main.job{endx:3, user:"", jobid:"def"}
&main.job{endx:3, user:"", jobid:"hij"}
Description
Deletion process produces unexpected result based on current implementation.
Steps to reproduce the issue:
1 Prepare the following test case in btree_test.go
package btree
import (
"flag"
"fmt"
"testing"
"os"
)
var btreeDegree = flag.Int("degree", 3, "B-Tree degree")
func TestForBTreeDeletion(t *testing.T) {
tree := New(*btreeDegree)
fmt.Println(tree)
for i := 0; i < 21; i++ {
if x := tree.ReplaceOrInsert(Int(i)); x != nil {
t.Fatal("insert found item", i)
}
}
fmt.Println("Before deletion")
tree.Print(os.Stdout)
for i := 0; i < 3; i++ {
if x := tree.Delete(Int(i)); x == nil {
t.Fatal("insert didn't find item", i)
}
fmt.Println("After deleting ", i)
tree.Print(os.Stdout)
}
}
2 Add a tree.Print method for debugging purpose in btree.go
// Print is for debugging purpose on CLI
func (t *BTree) Print(w io.Writer) {
t.root.print(w, 0)
}
3 Run the test suite
go test -v
Describe the results you received:
Before deletion *[<===== This is the original tree with degree of 3 after inserting 0 to 20]*
NODE:[8]
NODE:[2 5]
NODE:[0 1]
NODE:[3 4]
NODE:[6 7]
NODE:[11 14 17]
NODE:[9 10]
NODE:[12 13]
NODE:[15 16]
NODE:[18 19 20]
After deleting 0 *[<====== After deleting 0, `NODE[0 1]` underflows and causes redistribution ]*
NODE:[11]
NODE:[5 8]
NODE:[1 2 3 4] **[<====== This NODE has enough items so that deleting 1 shouldn't cause an underflow]**
NODE:[6 7]
NODE:[9 10]
NODE:[14 17]
NODE:[12 13]
NODE:[15 16]
NODE:[18 19 20]
After deleting 1 [<===== WRONG: The underlying B-tree is redistributed]
NODE:[5 8 11 14 17]
NODE:[2 3 4]
NODE:[6 7]
NODE:[9 10]
NODE:[12 13]
NODE:[15 16]
NODE:[18 19 20]
After deleting 2
NODE:[5 8 11 14 17]
NODE:[3 4]
NODE:[6 7]
NODE:[9 10]
NODE:[12 13]
NODE:[15 16]
NODE:[18 19 20]
Describe the results you expected:
See my comment inline in the above section.
To double check the behavior, try to run a visualized b-tree insertion from this website.
1 Selecting max degree as 6
2 Manually insert 0 to 20 (inclusively). [Same underlying tree as above]
3 Manually delete 0 [Correct: Underflow causes redistribution]
4 Delete 1 [Correct: No redistribution. Whereas in the issue reported, the tree is redistributed]
Additional information you deem important (e.g. issue happens only occasionally):
Output of go version:
go version go1.6.2 linux/amd64
Additional environment details (AWS, VirtualBox, physical, etc.):
from the code, it looks like a b+tree
Hi,
As Go moves towards semantic versioning and vendoring, it would be really helpful to have a tagged release of btree following semantic versioning. For instance, you could run:
git checkout master; git tag v1.0.0; git push v1.0.0
Which would define the current version to be v1.0.0.
deleteMin calls remoteAt(0). This code
https://github.com/google/btree/blob/master/btree.go#L153
makes it look like every deleteMin will therefore be O(n) in the size of the tree n, as it does a full copy of the entire tree.
This is really, really, not what I would expect from a balanced binary tree implementation. Deleting the entire tree becomes an O(n*n) operation.
is it b+ tree??
This btree data structure is an ephemeral data structure. Changes to a particular btree instance are destructive. Would be nice if there was a persistent, immutable counter part to this data structure. Adding to or deleting from, the persistent version of btree creates a new btree with the original intact. We could have the ability to batch together mutations to cut down on the creation of intermediate instances.
A persistent version of btree would make transactional processing very easy as one could quickly revert to an older version. A persistent, immutable btree helps with concurrency too. On goroutine could read the btree while another is modifying it. A persistent btree helps with undo / redo operations too.
I figure the persistent version would be almost like the ephemeral version except instead of mutating nodes in place, we do copy-on-write. Doing a single mutation to a persistent btree, one add or one delete, would be cheap. The old and new versions would share many of the same nodes. Only log(n) nodes would be different.
With the persistent version of btree, there would be no free list or recycling of nodes. Each node in the btree would be immutable as it could be shared by many different versions of the same btree.
If this sounds interesting to you, I'd be willing to take on the work.
Line 621 in 4030bb1
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.