stack overflow while deleting a key from the tree #56
Comments
const maxCacheSize = 3
type KCounter struct {
key string
value int
}
func (t *KCounter) Less(than btree.Item) bool {
// 1. change pointer
counter := than.(*KCounter)
if t.key < counter.key {
return true
}
return t.value < counter.value
}
func Test_B(t *testing.T) {
put := func(tree *btree.BTree, itemByKey map[string]KCounter, kc KCounter) bool {
_, ok := itemByKey[kc.key]
if ok {
//update the value by re-inserting it
// 2. no need delete
//tree.Delete(&item)
tree.ReplaceOrInsert(&kc)
itemByKey[kc.key] = kc
return true
}
if tree.Len() >= maxCacheSize {
smallestItem := tree.Min().(*KCounter)
if kc.value < smallestItem.value {
//dont add group that have values that are smaller than the smallest elem in tree
return false
}
tree.DeleteMin()
}
tree.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})
}
// 3. use debug for result.
t.Log("debug: see debug info")
} |
|
I found that there is an issue with your Less function. KCounter(9, 9) is considered less than KCounter(10, 6), but KCounter(10, 6) is also considered less than KCounter(9, 9). Because of this problem, your binary tree will contain duplicate items when you insert new items, which may lead to an indefinite recursive call. for example, if you run this test, you will get a btree with items of the root are {1 2}, {10 6}, {9 9}, {10 6} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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
the error
The text was updated successfully, but these errors were encountered: