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")
} |
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: