On Fri, Apr 27, 2018 at 01:53:35PM +0800, Jason Wang wrote: [...]
> > + /* Merge right adjacent range */ > > + overlap = it_tree_find_value(tree, end + 1); > > + if (overlap) { > > + range->end = overlap->end; > > + g_tree_remove(gtree, overlap); > > + } > > + > > + /* Key and value are sharing the same range data */ > > + it_tree_insert_internal(gtree, range); > > A small optimization here is to delay the allocation until you're sure > there's not overlapping. Yes I can. [...] > > +int it_tree_remove(ITTree *tree, ITValue start, ITValue end) > > +{ > > + ITRange range = { .start = start, .end = end }, *overlap, and; > > + GTree *gtree; > > + > > + g_assert(tree); > > + > > + gtree = tree->tree; > > + while ((overlap = g_tree_lookup(gtree, &range))) { > > + if (it_range_equal(overlap, &range)) { > > + /* Exactly what we want to remove; done */ > > + g_tree_remove(gtree, overlap); > > + break; > > + } else if (it_range_cover(overlap, &range)) { > > + /* Split existing range into two; done */ > > + it_tree_remove_subset(gtree, overlap, &range); > > + break; > > + } else if (it_range_cover(&range, overlap)) { > > + /* Drop this range and continue */ > > + g_tree_remove(gtree, overlap); > > + } else { > > + /* > > + * The range to remove has intersection with existing > > + * ranges. Remove part of the range and continue > > + */ > > + it_range_and(&and, overlap, &range); > > + g_assert(and.start <= and.end); > > + it_tree_remove_subset(gtree, overlap, &and); > > + } > > + } > > + > > Looks like what we need here is just calculate the intersection part the > remove it. Yes. Will fix that. Thanks, -- Peter Xu