On Thu, Jun 27, 2019 at 09:50:08PM -0700, Michel Lespinasse wrote: > As was already noted in rbtree.h, the logic to cache rb_first (or rb_last) > can easily be implemented externally to the core rbtree api. > > Change the implementation to do just that. Previously the update of > rb_leftmost was wired deeper into the implemntation, but there were > some disadvantages to that - mostly, lib/rbtree.c had separate > instantiations for rb_insert_color() vs rb_insert_color_cached(), as well > as rb_erase() vs rb_erase_cached(), which were doing exactly the same > thing save for the rb_leftmost update at the start of either function. >
> Signed-off-by: Michel Lespinasse <wal...@google.com> > --- > include/linux/rbtree.h | 70 +++++++++++++++++++++----------- > include/linux/rbtree_augmented.h | 27 +++++------- > lib/rbtree.c | 40 ++---------------- > 3 files changed, 59 insertions(+), 78 deletions(-) Acked-by: Peter Zijlstra (Intel) <pet...@infradead.org>
