On Thu, Oct 27, 2016 at 02:59:07PM +0200, Peter Zijlstra wrote: > On Wed, Oct 26, 2016 at 09:18:01PM +0200, David Herrmann wrote: > > +/* insert slice into the free tree */ > > +static void bus1_pool_slice_link_free(struct bus1_pool_slice *slice, > > + struct bus1_pool *pool) > > +{ > > + struct rb_node **n, *prev = NULL; > > + struct bus1_pool_slice *ps; > > + > > + n = &pool->slices_free.rb_node; > > + while (*n) { > > + prev = *n; > > + ps = container_of(prev, struct bus1_pool_slice, rb); > > + if (slice->size < ps->size) > > + n = &prev->rb_left; > > + else > > + n = &prev->rb_right; > > + } > > + > > + rb_link_node(&slice->rb, prev, n); > > + rb_insert_color(&slice->rb, &pool->slices_free); > > +} > > If you only sort free slices by size, how do you merge contiguous free > slices?
Ah, I see, you also keep an ordered list of slices and use that one function up from here.