]> git.proxmox.com Git - mirror_ubuntu-kernels.git/commit
lib/rbtree: avoid generating code twice for the cached versions
authorMichel Lespinasse <walken@google.com>
Tue, 16 Jul 2019 23:27:45 +0000 (16:27 -0700)
committerLinus Torvalds <torvalds@linux-foundation.org>
Wed, 17 Jul 2019 02:23:22 +0000 (19:23 -0700)
commit9f973cb38088e0cf42e0bae97ff140813e623f13
treeeee4545125e037873c8bf29ec1d5ff6064d2e456
parent4ab7ace465466d25c12cee9854e7140077e208cb
lib/rbtree: avoid generating code twice for the cached versions

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 implmentation, 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.

   text    data     bss     dec     hex filename
   5405     120       0    5525    1595 lib/rbtree.o-vanilla
   3827      96       0    3923     f53 lib/rbtree.o-patch

[dave@stgolabs.net: changelog addition]
Link: http://lkml.kernel.org/r/20190628171416.by5gdizl3rcxk5h5@linux-r8p5
[akpm@linux-foundation.org: coding-style fixes]
Link: http://lkml.kernel.org/r/20190628045008.39926-1-walken@google.com
Signed-off-by: Michel Lespinasse <walken@google.com>
Acked-by: Davidlohr Bueso <dbueso@suse.de>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
include/linux/rbtree.h
include/linux/rbtree_augmented.h
lib/rbtree.c