| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <4FD0715C.4070906@att.net>
Date: Thu, 07 Jun 2012 04:16:12 -0500
From: Daniel Santos <danielfsantos@....net>
To: linux-kernel@...r.kernel.org
Subject: [PATCHv3 5/6] [RFC] rbtree.h: generic search, insert & remove
Signed-off-by: Daniel Santos <daniel.santos@...ox.com>
---
include/linux/rbtree.h | 659 ++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 659 insertions(+), 0 deletions(-)
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 033b507..66e59cb 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -1,6 +1,7 @@
/*
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@...e.de>
+ (C) 2012 Daniel Santos <daniel.santos@...ox.com>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -96,6 +97,8 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
#include <linux/kernel.h>
#include <linux/stddef.h>
+#include <linux/typecheck.h>
+#include <linux/bug.h>
struct rb_node
{
@@ -148,6 +151,7 @@ extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
typedef void (*rb_augment_f)(struct rb_node *node, void *data);
+typedef long (*rb_compare_f)(const void *a, const void *b);
extern void rb_augment_insert(struct rb_node *node,
rb_augment_f func, void *data);
@@ -174,4 +178,659 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
*rb_link = node;
}
+
+#define __JUNK junk,
+#define _iff_empty(test_or_junk, t, f) __iff_empty(test_or_junk, t, f)
+#define __iff_empty(__ignored1, __ignored2, result, ...) result
+
+/**
+ * IFF_EMPTY() - Expands to the second argument when the first is empty, the
+ * third if non-empty.
+ * @test: An argument to test for emptiness.
+ * @t: A value to expand to if test is empty.
+ * @f: A value to expand to if test is non-empty.
+ *
+ * Caveats:
+ * IFF_EMPTY isn't perfect. The test parmater must either be empty or a valid
+ * pre-processor token as well as result in a valid token when pasted to the
+ * end of a word.
+ *
+ * Valid Examples:
+ * IFF_EMPTY(a, b, c) = c
+ * IFF_EMPTY( , b, c) = b
+ * IFF_EMPTY( , , c) = (nothing)
+ *
+ * Invalid Examples:
+ * IFF_EMPTY(., b, c)
+ * IFF_EMPTY(+, b, c)
+ */
+#define IFF_EMPTY(test, t, f) _iff_empty(__JUNK##test, t, f)
+
+/**
+ * IS_EMPTY() - test if a pre-processor argument is empty.
+ * @arg: An argument (empty or non-empty)
+ *
+ * If empty, expands to 1, 0 otherwise. See IFF_EMPTY() for caveats &
+ * limitations.
+ */
+#define IS_EMPTY(arg) IFF_EMPTY(arg, 1, 0)
+
+/**
+ * OPT_OFFSETOF() - return the offsetof for the supplied expression, or zero
+ * if m is an empty argument.
+ * @type: struct/union type
+ * @m: (optional) struct member name
+ *
+ * Since any offsetof can return zero if the specified member is the first in
+ * the struct/union, you should also check if the argument is empty separately
+ * with IS_EMPTY(m).
+ */
+#define OPT_OFFSETOF(type, m) ((size_t) &((*((type *)0)) IFF_EMPTY(m, , .m)))
+
+
+enum rb_flags {
+RB_HAS_LEFTMOST = 0x00000001, /* The container has a struct rb_node *leftmost
+ member that will receive a pointer to the
+ leftmost (smallest) object in the tree that
+ is updated during inserts & deletions */
+RB_HAS_RIGHTMOST = 0x00000002, /* same as above (for right side of tree) */
+RB_UNIQUE_KEYS = 0x00000004, /* the tree contains only unique values. */
+RB_INSERT_REPLACES = 0x00000008, /* when set, the rb_insert() will replace a
+ value if it matches the supplied one (valid
+ only when RB_UNIQUE_KEYS is set). */
+RB_IS_AUGMENTED = 0x00000010,
+RB_ALL_FLAGS = RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST
+ | RB_UNIQUE_KEYS | RB_INSERT_REPLACES
+ | RB_IS_AUGMENTED,
+};
+
+/**
+ * struct rb_relationship - Defines relationship between a container and
+ * the objects it contains.
+ * @root_offset: Offset of container's struct rb_root member.
+ * @left_offset: (Used only if has_left.) Offset of the container's struct
+ * rb_node *leftmost member for storing a pointer to the
+ * leftmost node in the tree, which is kept updated as inserts
+ * and deletions are made.
+ * @right_offset: Same as left_offset, except for right side of tree.
+ * @node_offset: Offset of object's struct rb_node member.
+ * @key_offset: Offset of object's key member.
+ * @flags: TODO
+ * @compare: Pointer to key rb_compare_f function to compare keys.
+ * Although it will be cast to and called as type long (*)(const
+ * void *a, const void *b), you should delcare it as accepting
+ * pointers to your key members, or sanity checks will fail.
+ * Further, it is optimial if the function is declared inline.
+ * @augment: Pointer to the rb_augment_f or zero if tree is not augmented.
+ *
+ * Instances of struct rb_relationship should be compile-time constants (or
+ * rather, the value of its members).
+ */
+struct rb_relationship {
+ long root_offset;
+ long left_offset;
+ long right_offset;
+ long node_offset;
+ long key_offset;
+ int flags;
+ const rb_compare_f compare;
+ const rb_augment_f augment;
+};
+
+static __always_inline
+struct rb_root *__rb_to_root(const void *ptr,
+ const struct rb_relationship *rel)
+{
+ BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+ return (struct rb_root *)((char *)ptr + rel->root_offset);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_left(struct rb_root *root,
+ const struct rb_relationship *rel)
+{
+ BUILD_BUG_ON(!(rel->flags & RB_HAS_LEFTMOST));
+ BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+ BUILD_BUG_ON_NON_CONST2(rel->left_offset);
+ return (struct rb_node **)((char *)root - rel->root_offset
+ + rel->left_offset);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_right(struct rb_root *root,
+ const struct rb_relationship *rel)
+{
+ BUILD_BUG_ON(!(rel->flags & RB_HAS_RIGHTMOST));
+ BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+ BUILD_BUG_ON_NON_CONST2(rel->right_offset);
+ return (struct rb_node **)((char *)root - rel->root_offset
+ + rel->right_offset);
+}
+
+static __always_inline
+const void *__rb_node_to_key(const struct rb_node *node,
+ const struct rb_relationship *rel)
+{
+ BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+ BUILD_BUG_ON_NON_CONST2(rel->key_offset);
+ return (const void *)((const char *)node - rel->node_offset
+ + rel->key_offset);
+}
+
+static __always_inline
+char *__rb_node_to_obj(const void *ptr, const struct rb_relationship *rel)
+{
+ BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+ return (char *)ptr - rel->node_offset;
+}
+
+/* not used anymore */
+#if 0
+static __always_inline
+struct rb_node *__rb_to_node(const void *ptr, const struct rb_relationship *rel)
+{
+ BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+ return (struct rb_node *)((char *)ptr + rel->node_offset);
+}
+
+static __always_inline
+const void *__rb_to_key(const void *ptr, const struct rb_relationship *rel)
+{
+ BUILD_BUG_ON_NON_CONST2(rel->key_offset);
+ return (const void *)((const char *)ptr + rel->key_offset);
+}
+
+#endif
+
+/** __rb_find - Perform a (normal) search of rbtree starting at the specified
+ * node, traversing downward.
+ *
+ */
+static __always_inline __flatten
+struct rb_node *__rb_find(
+ struct rb_node *node,
+ const void *key,
+ const struct rb_relationship *rel)
+{
+ while (node) {
+ long diff = rel->compare(key, __rb_node_to_key(node, rel));
+
+ if (diff > 0)
+ node = node->rb_right;
+ else if (diff < 0)
+ node = node->rb_left;
+ else
+ return node;
+ }
+
+ return 0;
+}
+
+static __always_inline __flatten
+struct rb_node *rb_find(
+ struct rb_root *root,
+ const void *key,
+ const struct rb_relationship *rel)
+{
+ return __rb_find(root->rb_node, key, rel);
+}
+
+
+enum rb_find_subtree_match {
+ RB_MATCH_NONE = 0,
+ RB_MATCH_IMMEDIATE = 2,
+ RB_MATCH_LEFT = -1,
+ RB_MATCH_RIGHT = 1,
+};
+
+/**
+ * rb_find_subtree - Locate the subtree that contains the specified key (if it
+ * exists) starting from a specific node traversing upwards.
+ *
+ */
+static __always_inline __flatten
+struct rb_node *__rb_find_subtree(
+ struct rb_node *from,
+ const void *key,
+ int *matched,
+ const struct rb_relationship *rel)
+{
+ struct rb_node *prev = from;
+ struct rb_node *node = rb_parent(from);
+ long diff;
+
+ if (!node) {
+ *matched = RB_MATCH_NONE;
+ return prev;
+ }
+
+ diff = rel->compare(key, __rb_node_to_key(node, rel));
+
+ if (diff > 0) {
+ while (1) {
+ prev = node;
+ node = rb_parent(prev);
+ if (!node)
+ break;
+
+ diff = rel->compare(key, __rb_node_to_key(node, rel));
+ if (diff < 0)
+ break;
+ else if (!diff) {
+ *matched = RB_MATCH_LEFT;
+ return node;
+ }
+ }
+ *matched = RB_MATCH_NONE;
+ return prev->rb_left;
+ } else if (diff < 0) {
+ while (1) {
+ prev = node;
+ node = rb_parent(prev);
+ if (!node)
+ break;
+
+ diff = rel->compare(key, __rb_node_to_key(node, rel));
+ if (diff > 0)
+ break;
+ else if (!diff) {
+ *matched = RB_MATCH_RIGHT;
+ return node;
+ }
+ }
+ *matched = RB_MATCH_NONE;
+ return prev->rb_right;
+ } else {
+ *matched = RB_MATCH_IMMEDIATE;
+ return node;
+ }
+}
+
+static __always_inline __flatten
+struct rb_node *rb_find_near(
+ struct rb_node *from,
+ const void *key,
+ const struct rb_relationship *rel)
+{
+ int matched;
+ struct rb_node *subtree;
+
+ subtree = __rb_find_subtree(from, key, &matched, rel);
+
+ if (matched)
+ return subtree;
+
+ return __rb_find(subtree, key, rel);
+}
+
+/* common insert epilogue used by rb_insert() and rb_insert_near() */
+static __always_inline __flatten
+struct rb_node *__rb_insert_epilogue(
+ struct rb_root *root,
+ struct rb_node *parent,
+ struct rb_node *node,
+ struct rb_node *found,
+ struct rb_node **rb_link,
+ const struct rb_relationship *rel)
+{
+ if ((rel->flags & RB_UNIQUE_KEYS) && found) {
+ /* if replacing, we will still need to call do augment */
+ if (rel->flags & RB_INSERT_REPLACES)
+ rb_replace_node(found, node, root);
+ /* otherwise, we can bail */
+ else
+ goto exit;
+ } else {
+ rb_link_node(node, parent, rb_link);
+ rb_insert_color(node, root);
+ }
+
+ if (rel->augment)
+ rb_augment_insert(node, rel->augment, NULL);
+
+exit:
+ return found;
+}
+
+
+/**
+ * rb_insert() - Inserts an object into a container.
+ * @root: Pointer to struct rb_root.
+ * @node: Pointer to the node of the new object to insert.
+ * @rel: Pointer to the compile-time constant relationship definition.
+ * @compare: Compare function
+ * @augmented: Augmented function (if using an augmented rbtree)
+ *
+ * If an object with the same key already exists and RB_INSERT_REPLACES is set
+ * then it is replaced with new object node; if RB_INSERT_REPLACES is not set,
+ * then no change is made. In either case, a pointer to the existing object
+ * node is returned.
+ *
+ * If no object with the same key exists, then the new object node is inserted
+ * and NULL is returned.
+ */
+static __always_inline __flatten
+struct rb_node *rb_insert(
+ struct rb_root *root,
+ struct rb_node *node,
+ const struct rb_relationship *rel)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ const void *key = __rb_node_to_key(node, rel);
+ int leftmost = 1;
+ int rightmost = 1;
+
+ BUILD_BUG_ON_NON_CONST2(rel->flags);
+ BUG_ON((rel->flags & RB_INSERT_REPLACES)
+ && !(rel->flags & RB_UNIQUE_KEYS));
+
+ while (*p) {
+ long diff = rel->compare(key, __rb_node_to_key(*p, rel));
+ parent = *p;
+
+ if (diff > 0) {
+ p = &(*p)->rb_right;
+ if (rel->flags & RB_HAS_LEFTMOST)
+ leftmost = 0;
+ } else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0) {
+ p = &(*p)->rb_left;
+ if (rel->flags & RB_HAS_RIGHTMOST)
+ rightmost = 0;
+ } else
+ break;
+ }
+
+ if ((rel->flags & RB_HAS_LEFTMOST) && leftmost) {
+ struct rb_node **left = __rb_root_to_left(root, rel);
+
+ if (!(rel->flags & RB_INSERT_REPLACES) || !(*p) || *left == *p)
+ *left = node;
+ }
+ if ((rel->flags & RB_HAS_RIGHTMOST) && rightmost) {
+ struct rb_node **right = __rb_root_to_right(root, rel);
+
+ if (!(rel->flags & RB_INSERT_REPLACES) || !(*p) || *right == *p)
+ *right = node;
+ }
+
+ return __rb_insert_epilogue(root, parent, node, *p, p, rel);
+}
+
+static __always_inline __flatten
+struct rb_node *rb_insert_near(
+ struct rb_root *root,
+ struct rb_node *start,
+ struct rb_node *node,
+ const struct rb_relationship *rel)
+{
+#if 0
+
+ return 0;
+/* TODO: not yet finished */
+#endif
+ const void *key = __rb_node_to_key(node, rel);
+ struct rb_node **p = &start;
+ struct rb_node *parent = NULL;
+ struct rb_node *ret;
+ int matched;
+ long diff;
+
+ BUILD_BUG_ON_NON_CONST2(rel->flags);
+
+ ret = __rb_find_subtree(start, key, &matched, rel);
+
+ if (!matched) {
+ while (*p) {
+ diff = rel->compare(__rb_node_to_key(*p, rel), key);
+ parent = *p;
+
+ if (diff > 0)
+ p = &(*p)->rb_right;
+ else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0)
+ p = &(*p)->rb_left;
+ else
+ break;
+ }
+ ret = *p;
+ } else {
+ /* FIXME: p will not be correctly set to point to the parent's
+ * rb_left or rb_right member here when it's passed as
+ * __rb_insert_epilogue()'s rb_link parameter.
+ */
+ if (rel->flags & (RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST)) {
+ if ((rel->flags & RB_HAS_LEFTMOST)) {
+ struct rb_node **left =
+ __rb_root_to_left(root, rel);
+ if (*left == ret)
+ *left = node;
+ }
+
+ if ((rel->flags & RB_HAS_RIGHTMOST)) {
+ struct rb_node **right =
+ __rb_root_to_right(root, rel);
+ if (*right == ret)
+ *right = node;
+ }
+ }
+ }
+
+ if (rel->flags & (RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST)) {
+
+ }
+
+ if ((rel->flags & RB_HAS_LEFTMOST)) {
+ struct rb_node **left = __rb_root_to_left(root, rel);
+ if (!*left || (*left == parent && diff < 0))
+ *left = node;
+ }
+
+ if ((rel->flags & RB_HAS_RIGHTMOST)) {
+ struct rb_node **right = __rb_root_to_right(root, rel);
+ if ((*right == parent && diff > 0) || !*right)
+ *right = node;
+ }
+
+ return __rb_insert_epilogue(root, parent, node, ret, p, rel);
+}
+
+static __always_inline __flatten
+void rb_remove(
+ struct rb_root *root,
+ struct rb_node *node,
+ const struct rb_relationship *rel)
+{
+ struct rb_node *uninitialized_var(deepest);
+
+ BUILD_BUG_ON_NON_CONST2(rel->flags);
+
+ if (rel->augment)
+ deepest = rb_augment_erase_begin(node);
+
+ if (rel->flags & RB_HAS_LEFTMOST) {
+ struct rb_node **left = __rb_root_to_left(root, rel);
+
+ if (*left == node)
+ *left = rb_next(node);
+ }
+
+ if (rel->flags & RB_HAS_RIGHTMOST) {
+ struct rb_node **right = __rb_root_to_right(root, rel);
+
+ if (*right == node)
+ *right = rb_prev(node);
+ }
+
+ rb_erase(node, root);
+
+ if (rel->augment)
+ rb_augment_erase_end(deepest, rel->augment, NULL);
+}
+
+
+/**
+ * RB_RELATIONHIP - Define the relationship bewteen a container with a
+ * struct rb_root member, and the objects it contains.
+ * @cont_type: container type
+ * @root: container's struct rb_root member name
+ * @left: (optional) if the container needs a pointer to the tree's
+ * leftmost (smallest) object, then specify the container's struct
+ * rb_node *leftmost member. Otherwise, leave this parameter
+ * empty.
+ * @right: (optional) same as left, but for the rightmost (largest)
+ * @obj_type: the type of object stored in container
+ * @node: the struct rb_node memeber of the object
+ * @key: the key member of the object
+ * @flags see rb_flags. Note: you do not have to specify RB_HAS_LEFTMOST
+ * or RB_HAS_RIGHTMOST as these will be added automatically if the
+ * left or right parameter (respectively) is non-empty
+ * @compare: Pointer to key rb_compare_f function to compare keys.
+ * Although it will be cast to and called as type long (*)(const
+ * void *a, const void *b), you should delcare it as accepting
+ * pointers to your key members, or sanity checks will fail.
+ * Further, it is optimial if the function is declared inline.
+ * @_augment: pointer to the rb_augment_f or zero if tree is not augmented.
+ */
+#define RB_RELATIONSHIP( \
+ cont_type, root, left, right, \
+ obj_type, node, key, \
+ _flags, _compare, _augment) { \
+ .root_offset = offsetof(cont_type, root), \
+ .left_offset = OPT_OFFSETOF(cont_type, left), \
+ .right_offset = OPT_OFFSETOF(cont_type, right), \
+ .node_offset = offsetof(obj_type, node), \
+ .key_offset = offsetof(obj_type, key), \
+ .flags = (_flags) \
+ | IFF_EMPTY(left , 0, RB_HAS_LEFTMOST) \
+ | IFF_EMPTY(right, 0, RB_HAS_RIGHTMOST) \
+ | (!(_augment) ? 0 : RB_IS_AUGMENTED), \
+ .compare = (const rb_compare_f) (_compare), \
+ .augment = _augment, \
+}
+
+/**
+ * RB_DEFINE_INTERFACE - Defines a complete interface for a relationship
+ * between container and object including a struct
+ * rb_relationship and an interface of type-safe wrapper
+ * functions.
+ * @prefix: name for the relationship (see explanation below)
+ * @cont_type: container type
+ * @root: container's struct rb_root member name
+ * @left: (optional) if the container needs a pointer to the tree's
+ * leftmost (smallest) object, then specify the container's struct
+ * rb_node *leftmost member. Otherwise, leave this parameter
+ * empty.
+ * @right: (optional) same as left, but for the rightmost (largest)
+ * @obj_type: the type of object stored in container
+ * @node: the struct rb_node memeber of the object
+ * @key: the key member of the object
+ * @flags see rb_flags. Note: you do not have to specify RB_HAS_LEFTMOST
+ * or RB_HAS_RIGHTMOST as these will be added automatically if the
+ * left or right parameter (respectively) is non-empty
+ * @compare: Pointer to key rb_compare_f function to compare keys.
+ * Although it will be cast to and called as type long (*)(const
+ * void *a, const void *b), you should delcare it as accepting
+ * pointers to your key members, or sanity checks will fail.
+ * Further, it is optimial if the function is declared inline.
+ * @augment: pointer to the rb_augment_f or zero if tree is not augmented.
+ *
+ * This macro can be delcared in the global scope of either a source or header
+ * file and will generate a static const struct rb_relationship variable named
+ * prefix##_rel as well as similarly named (i.e., prefix##_##func_name)
+ * type-safe wrapper functions for find, find_near, insert, insert_near and
+ * remove. If these function names are not sufficient, you can use the
+ * __RB_DEFINE_INTERFACE macro to specify them explicitly.
+ *
+ * The compare function will be passed pointers to the key members of two
+ * objects. If your compare function needs access to other members of your
+ * struct (e.g., compound keys, etc.) , you can use the rb_entry macro to
+ * access other members. However, if you use this mechanism, your find
+ * function must always pass it's key parameter as a pointer to the key member
+ * of an object of type obj_type, since the compare function is used for both
+ * inserts and lookups (else, you'll be screwed).
+ */
+#define RB_DEFINE_INTERFACE(prefix, ...)\
+__RB_DEFINE_INTERFACE( \
+ prefix ## _rel, \
+ prefix ## _insert, \
+ prefix ## _insert_near, \
+ prefix ## _find, \
+ prefix ## _find_near, \
+ prefix ## _remove, \
+ __VA_ARGS__)
+
+
+#define __RB_DEFINE_INTERFACE( \
+ rel_var, insert, insert_near, find, find_near, remove, \
+ cont_type, root, left, right, \
+ obj_type, node, key, \
+ flags, compare, augment) \
+ \
+/* Define __sanity_check function first, so errors will (hopefully) */ \
+/* get caught here where the error message will be less confusing */ \
+/* then a failure in the RB_RELATIONSHIP macro expansion. You need */ \
+/* not call this function for validation to occur. */ \
+static inline __always_unused \
+void __sanity_check_##rel_var(cont_type *cont, obj_type *obj) \
+{ \
+ const struct rb_node *nodeptr; \
+ long diff; \
+ \
+ /* compare function should accept pointer to key member */ \
+ diff = (compare)(&obj->key, &obj->key); \
+ \
+ /* object node member should be struct rb_node */ \
+ nodeptr = &obj->node; \
+ \
+ /* leftmost & rightmost should be (const) struct rb_node* */ \
+ nodeptr = IFF_EMPTY(left , 0, cont->left); \
+ nodeptr = IFF_EMPTY(right , 0, cont->right); \
+} \
+ \
+static const struct rb_relationship rel_var = RB_RELATIONSHIP( \
+ cont_type, root, left, right, \
+ obj_type, node, key, \
+ flags, compare, augment); \
+ \
+static __always_inline \
+obj_type *insert(cont_type *cont, obj_type *obj) \
+{ \
+ struct rb_node *ret = rb_insert( \
+ &cont->root, &obj->node, &rel_var); \
+ return ret ? rb_entry(ret, obj_type, node) : 0; \
+} \
+ \
+static __always_inline \
+obj_type *insert_near(cont_type *cont, obj_type *near, obj_type *obj) \
+{ \
+ struct rb_node * ret = rb_insert_near( \
+ &cont->root, &near->node, &obj->node, &rel_var);\
+ return ret ? rb_entry(ret, obj_type, node) : 0; \
+} \
+ \
+static __always_inline \
+obj_type *find(cont_type *cont, \
+ const typeof(((obj_type *)0)->key) *_key) \
+{ \
+ struct rb_node * ret = rb_find( \
+ &cont->root, _key, &rel_var); \
+ return ret ? rb_entry(ret, obj_type, node) : 0; \
+} \
+ \
+static __always_inline \
+obj_type *find_near(obj_type *near, \
+ const typeof(((obj_type *)0)->key) *_key) \
+{ \
+ struct rb_node *ret = rb_find_near( \
+ &near->node, _key, &rel_var); \
+ return ret ? rb_entry(ret, obj_type, node) : 0; \
+} \
+ \
+static __always_inline \
+void remove(cont_type *cont, obj_type *obj) \
+{ \
+ rb_remove(&cont->root, &obj->node, &rel_var); \
+}
+
+
#endif /* _LINUX_RBTREE_H */
--
1.7.3.4
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists