Delete during Ascend in thread-safe tree

[tidwall]

Delete during Ascend in thread-safe tree

[tidwall]

Would this work in your case?

var list []interface{}
bt.Ascend(start, func(item interface{}) bool {
    if filter(item) {
       list = append(list, item)
    }
})
var hint btree.PathHint
for _, item := range list {
    bt.DeleteHint(item, &hint)
}

[tommie]

Thanks for the reply. That would work in my case, yes. I wanted to avoid the accumulation, but you're probably right that's the most reasonable thing to do. Closing for now.

I do think it would make sense to have Ascend/Descend being able to start where it left off without redoing the full search.

[tidwall]

I wanted to avoid the accumulation

What I've done in the past is something like:

var list []interface{}
var next interface{}
var hint btree.PathHint
for {
    list = list[:0]
    more := false
    bt.Ascend(next, func(item interface{}) bool{
        if len(list) == 256 {
            next = item
            more = true
            return false
        }
        if filter(item) {
            list = append(list, item)
        }
        return true
    })
    for _, item := range list {
        bt.DeleteHint(item, &hint)
    }
    if !more {
        break
    }
}

Which accumulates in chunks of no more than a predetermined size, in this case 256 items.

Ascend/Descend being able to start where it left off without redoing the full search.

Yeah. A AscendHint and DescendHint would be nice. Or even a Cursor type with Cursor.Next() and Cursor.Prev()

[tommie]

That's an interesting hybrid. It would be interesting to see how that benchmarkas against a non-batching AscendHint/DeleteHint. Since you would seem to accept a PR for AscendHint, I might code something up for that.

Or even a Cursor type with Cursor.Next() and Cursor.Prev()

If Delete-in-Ascend is unsafe, I think it's actually better to just cause a deadlock if you try, so I'd suggest keeping only the callback API.

[tommie]

To loop back: I ran some benchmarks, and in the scenarios I tried to conjure up, I couldn't see any performance improvement over batch-slice-delete. So I don't think it's worth pursuing until someone comes up with a case where it does matter.