diff options
| author | Mauro Carvalho Chehab <mchehab@s-opensource.com> | 2017-09-29 05:24:10 -0400 |
|---|---|---|
| committer | Mauro Carvalho Chehab <mchehab@s-opensource.com> | 2017-09-29 05:24:10 -0400 |
| commit | cf09e3c904bf424f8b6a8203958e09bf7d9bcbc0 (patch) | |
| tree | 5e9936b3de36aa222b52a9bca366a43d98730ffd /include/linux/rbtree.h | |
| parent | d5426f4c2ebac8cf05de43988c3fccddbee13d28 (diff) | |
| parent | e19b205be43d11bff638cad4487008c48d21c103 (diff) | |
Merge tag 'v4.14-rc2' into patchwork
Linux 4.14-rc2
* tag 'v4.14-rc2': (12066 commits)
Linux 4.14-rc2
tpm: ibmvtpm: simplify crq initialization and document crq format
tpm: replace msleep() with usleep_range() in TPM 1.2/2.0 generic drivers
Documentation: tpm: add powered-while-suspended binding documentation
tpm: tpm_crb: constify acpi_device_id.
tpm: vtpm: constify vio_device_id
security: fix description of values returned by cap_inode_need_killpriv
x86/asm: Fix inline asm call constraints for Clang
objtool: Handle another GCC stack pointer adjustment bug
inet: fix improper empty comparison
net: use inet6_rcv_saddr to compare sockets
net: set tb->fast_sk_family
net: orphan frags on stand-alone ptype in dev_queue_xmit_nit
MAINTAINERS: update git tree locations for ieee802154 subsystem
SMB3: Don't ignore O_SYNC/O_DSYNC and O_DIRECT flags
SMB3: handle new statx fields
arch: remove unused *_segments() macros/functions
parisc: Unbreak bootloader due to gcc-7 optimizations
parisc: Reintroduce option to gzip-compress the kernel
apparmor: fix apparmorfs DAC access permissions
...
Diffstat (limited to 'include/linux/rbtree.h')
| -rw-r--r-- | include/linux/rbtree.h | 21 |
1 files changed, 21 insertions, 0 deletions
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index e585018498d5..d574361943ea 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -44,10 +44,25 @@ struct rb_root { struct rb_node *rb_node; }; +/* + * Leftmost-cached rbtrees. + * + * We do not cache the rightmost node based on footprint + * size vs number of potential users that could benefit + * from O(1) rb_last(). Just not worth it, users that want + * this feature can always implement the logic explicitly. + * Furthermore, users that want to cache both pointers may + * find it a bit asymmetric, but that's ok. + */ +struct rb_root_cached { + struct rb_root rb_root; + struct rb_node *rb_leftmost; +}; #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3)) #define RB_ROOT (struct rb_root) { NULL, } +#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL } #define rb_entry(ptr, type, member) container_of(ptr, type, member) #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) @@ -69,6 +84,12 @@ extern struct rb_node *rb_prev(const struct rb_node *); extern struct rb_node *rb_first(const struct rb_root *); extern struct rb_node *rb_last(const struct rb_root *); +extern void rb_insert_color_cached(struct rb_node *, + struct rb_root_cached *, bool); +extern void rb_erase_cached(struct rb_node *node, struct rb_root_cached *); +/* Same as rb_first(), but O(1) */ +#define rb_first_cached(root) (root)->rb_leftmost + /* Postorder iteration - always visit the parent after its children */ extern struct rb_node *rb_first_postorder(const struct rb_root *); extern struct rb_node *rb_next_postorder(const struct rb_node *); |