diff --git a/include/linux/grbtree.h b/include/linux/grbtree.h new file mode 100644 index 0000000..06f40cf --- /dev/null +++ b/include/linux/grbtree.h @@ -0,0 +1,597 @@ +/* + * Generic Red Black Tree Extensions + * + * Copyright (C) 2012 Daniel Santos + * + * 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 + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, + * USA. + */ + +/** + * DOC: Generic Red Black Tree Extensions + * + * Generic Red Black Tree Extensions extends upon Andrea Arcangeli's original + * rbtree implementation adding the ability to generically define + * relationships between containers and their contents (see struct + * grb_relationship) and feeding that definition to generic function + * implementations. By using a compile-time constant instance of struct + * grb_relationship and a single instantiation of the static inline find & + * insert functions, gcc will generate code that is exactly as efficient as if + * you had implemented your own find & insert functions (as explained in the + * rbtree documentation) without the source bloat and added complexity. + * Further, by wrapping calls to the generic (__always_inline) functions in + * singular (non-inline) functions, type-safety can be achieved while + * preventing the bloat of inline expansion. + * + * The struct grb_relationship object should be thought of as a database's DDL + * (Data Definition Language) that defines the relationship between two + * tables: primary & foreign keys, unique constraints, sort ordering, tuning + * hints, etc. (although in practice, some of those are specified when making + * SQL queries). It also specifies extended features you're using, like + * rather or not your container caches a pointer to the leftmost node in the + * tree -- enabling them in the generic function implementations or ensuring + * that they are compiled-out if you are not. + * + * It is important to understand that while grbtree extends upon rbtree's + * functionality, it uses a different interface paradigm: where rbtree's + * interface deals with the types struct rb_root and rb_node, grbtree is + * concerned with your containers and their objects and is designed to + * relegate the overhead for such genericity to the compiler. So rather than + * passing a pointer to the struct rb_node or rb_root member of your + * container or object, you will simply pass a pointer to your container or + * object its self, likewise for return values. + * + * Because C does not (yet) support templates, this all means that the generic + * function accept and return void *pointers, killing type safety. To + * restore type safety, its reccomeded you either wrap all calls to generic + * functions in your own type-specific function (inline or not) or use the + * unholy (but sufficient) GRB_DEFINE_INTERFACE() macro to have this done for + * you. + * + * Egg Sample: + * + * struct house { + * struct rb_root mice; + * }; + * + * struct mouse { + * struct rb_node node; + * const char* name; + * }; + * + * static __always_inline long name_cmp(const char **a, const char **b) { + * return strcmp(*a, *b); + * } + * + * static const struct grb_relationship rel_house_to_mouse = + * GRB_RELATIONHIP(struct house, mice, / * noleft * /, / * noright * /, + * struct mouse, node, name, name_cmp, + * 1, 0, 1, 0); + * + * struct mouse *find_mouse(struct house *house, const char *name) { + * return rb_find(house, name, &rel_house_to_mouse); + * } + * + * struct mouse *put_mouse_in_house(struct house *house, struct mouse *mouse) { + * return rb_insert(house, mouse, &rel_house_to_mouse); + * } + * + * + */ +#ifndef _LINUX_GRBTREE_H +#define _LINUX_GRBTREE_H + +#include + +typedef long (*rb_compare_f)(const void *a, const void *b); + +/* will submit this for include/linux/bug.h after I verify working gcc + * versions better and fully document caveats + */ +/** + * BUILD_BUG_ON_NON_CONST_STRUCT - break compile if a struct member is not a + * compile-time constant + * @exp: struct member to test for compile-time constness + * + * If you have some code that depends upon struct instance being a compile- + * time constant (or more specifically one or more of its members), then you + * can use this macro to trigger a BUILD_BUG if it is not. Note that one + * member of a struct instrance can be determined a compile-time constant by + * gcc and not another. + * + * Caveats: TODO + */ +#if defined(__OPTIMIZE__) && (__GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 1) +#define BUILD_BUG_ON_NON_CONST_STRUCT(exp) \ + BUILD_BUG_ON(!__builtin_constant_p(exp)) +#else +#define BUILD_BUG_ON_NON_CONST_STRUCT(exp) +#endif + + +#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. + * on_true: A value to expand to if test is empty. + * on_false: A value to expand to if test is non-empty. + * + * Examples: + * IFF_EMPTY(a, b, c) = c + * IFF_EMPTY( , b, c) = b + * IFF_EMPTY( , , c) = (nothing) + */ +#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. + */ +#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))) + + +/** + * struct grb_relationship - Defines relationship between a container and + * the objects it contains. + * @root_offset: Offset of container's struct rb_root member. + * @has_left: Non-zero if the container has a leftmost member, zero + * otherwise. + * @has_right: Non-zero if the container has a rightmost member, zero + * otherwise. + * @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. + * @compare: Compare function for object keys -- should be an + * inline function in the same translation unit for + * proper optimization, although this is the only field + * that isn't required to be a compile-time constant. + * The compare function should accept pointers to the key + * type and return long. + * @unique: Zero if duplicate keys are allowed, non-zero otherwise. + * @tune_many_dupes: (Used only if !unique.) Tune searches & inserts when + * not using unique keys and many duplilcates are likely. + * @ins_replace: (Used only if unique.) Rather or not the __grb_insert + * function should replace existing objects. + * @is_augmented: Rather or this is an augmented rbtree (and the + * augmented is non-null) + * @augmented: Not yet implemented (pointer to rb_augmented_f function) + * + * Instances of struct grb_relationship should be compile-time constants (or + * rather, the value of its members). + * + * Note: If your container stores the leftmost or rightmost, you must use the + * generic __rb_remove to keep them current. + */ +struct grb_relationship { + long root_offset; + int has_left; + int has_right; + long left_offset; + long right_offset; + long node_offset; + long key_offset; + rb_compare_f compare; + int unique; + int tune_many_dupes; + int ins_replace; + int is_augmented; + rb_augment_f augmented; +}; + +static __always_inline +struct rb_root *__grb_to_root(const void *ptr, const struct grb_relationship *rel) +{ + BUILD_BUG_ON_NON_CONST_STRUCT(rel->root_offset); + return (struct rb_root *)((char *)ptr + rel->root_offset); +} + +static __always_inline +struct rb_node **__grb_to_left(void *ptr, const struct grb_relationship *rel) +{ + BUILD_BUG_ON(!rel->has_left); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->left_offset); + return (struct rb_node **)((char *)ptr + rel->left_offset); +} + +static __always_inline +struct rb_node **__grb_to_right(void *ptr, const struct grb_relationship *rel) +{ + BUILD_BUG_ON(!rel->has_right); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->right_offset); + return (struct rb_node **)((char *)ptr + rel->right_offset); +} + +static __always_inline +struct rb_node *__grb_to_node(const void *ptr, const struct grb_relationship *rel) +{ + BUILD_BUG_ON_NON_CONST_STRUCT(rel->node_offset); + return (struct rb_node *)((char *)ptr + rel->node_offset); +} + +static __always_inline +const void *__grb_to_key(const void *ptr, const struct grb_relationship *rel) +{ + BUILD_BUG_ON_NON_CONST_STRUCT(rel->key_offset); + return (const void *)((const char *)ptr + rel->key_offset); +} + +static __always_inline +const void *__grb_node_to_key(const void *ptr, const struct grb_relationship *rel) +{ + BUILD_BUG_ON_NON_CONST_STRUCT(rel->node_offset); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->key_offset); + return (const void *)((const char *)ptr - rel->node_offset + rel->key_offset); +} + +static __always_inline +char *__grb_node_to_obj(const void *ptr, const struct grb_relationship *rel) +{ + BUILD_BUG_ON_NON_CONST_STRUCT(rel->node_offset); + return ((char *)ptr - rel->node_offset); +} + +/** + * grb_find_down_from - search a tree (normally) starting from the specified node + */ +static __always_inline +void *grb_find_down_from(const struct rb_node *node, + const void *key, + const struct grb_relationship *rel) +{ + while (node) { + int diff = rel->compare(__grb_node_to_key(node, rel), key); + + if (diff > 0) + node = node->rb_right; + else if (diff < 0) + node = node->rb_left; + else + return __grb_node_to_obj(node, rel); + } + + return 0; +} + +/** + * grb_find_up_from - search a tree climbing upwards, starting at the 'from' + * object and then descending (if needed) to find a + * matching object or no match. + */ +static __always_inline +void *grb_find_up_from(const void *from, + const void *key, + const struct grb_relationship *rel) +{ + const struct rb_node *node = __grb_to_node(from, rel); + long diff = rel->compare(__grb_node_to_key(node, rel), key); + int go_left = diff < 0; + + if (!diff) + return (void *)from; + + while ((node = rb_parent(node))) { + diff = rel->compare(__grb_node_to_key(node, rel), key); + + if (!diff) + return __grb_node_to_obj(node, rel); + else if (go_left ? diff > 0 : diff < 0) + return grb_find_down_from(node, key, rel); + } + + return 0; +} + +/** + * grb_find() - Searches a red black tree. + * @container: Container to search. + * @key: Pointer to the key you want to find. + * @rel: Pointer to the compile-time constant relationship definition. + * + * On success, returns a pointer to the object (not the struct rb_node), NULL + * otherwise. If rel is not a compile-time constant, a link-time error will + * be generated. + * + * If your code calls this function from more than one place, it is highly + * recommended that you wrap this function in a non-inline function to avoid + * object code bloat. You have been advised! Even if you are calling it from + * one place, wrapping it in a type-specific function (inline or otherwise) + * improves type-safety. + * + * + */ +static __always_inline +void *grb_find(const void *container, + const void *key, + const struct grb_relationship *rel) +{ + return grb_find_down_from(__grb_to_root(container, rel)->rb_node, key, + rel); +} + +/** + * grb_insert() - Inserts an object into a container. + * @container: Pointer to the container. + * @obj: Pointer to the new object to insert. + * @rel: Pointer to the compile-time constant relationship definition. + * + * If an object with the same key already exists and rel->ins_replace is non-zero, + * then it is replaced with obj; if rel->ins_replace is zero, then no change is made. + * In either case, a pointer to the existing object is returned. Note that + * return values are pointers to the objects themselves, not to the struct + * rb_node. + * + * If no object with the same key exists, then obj is inserted and NULL is + * returned. + * + * See rb_find for example. + */ +static __always_inline +void *grb_insert(void *container, + void *obj, + const struct grb_relationship *rel) +{ + struct rb_root *root = __grb_to_root(container, rel); + struct rb_node **p = &root->rb_node; + struct rb_node *parent = NULL; + struct rb_node *node = __grb_to_node(obj, rel); + void *ret = NULL; + const void *key = __grb_to_key(obj, rel); + int rightmost = 1; + int leftmost = 1; + + BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_left); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_right); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->unique); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->tune_many_dupes); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->ins_replace); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->is_augmented); + + while (*p) { + int diff = rel->compare(__grb_node_to_key(*p, rel), key); + parent = *p; + + if (diff > 0) { + p = &(*p)->rb_right; + if (rel->has_left) + leftmost = 0; + /* if keys are not unique, we can skip additional tests, + * although it will be slower if there are often duplicate + * keys, so rel->tune_many_dupes will dictate how we + * behave. + */ + } else if ((!rel->unique && !rel->tune_many_dupes) || diff < 0) { + p = &(*p)->rb_left; + if (rel->has_right) + rightmost = 0; + } else + break; + } + + if (rel->has_left && leftmost) + *__grb_to_left(container, rel) = node; + if (rel->has_right && rightmost) + *__grb_to_right(container, rel) = node; + + if (rel->unique && *p) { + ret = __grb_node_to_obj(*p, rel); + if (rel->ins_replace) + rb_replace_node(*p, node, root); + } else { + rb_link_node(node, parent, p); + rb_insert_color(node, root); + } + + if (rel->is_augmented) + rb_augment_insert(node, rel->augmented, NULL); + + return ret; +} + +static __always_inline +void grb_remove(void *container, + void *obj, + const struct grb_relationship *rel) +{ + struct rb_root *root = __grb_to_root(container, rel); + struct rb_node *node = __grb_to_node(obj, rel); + struct rb_node *deepest; + + BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_right); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_left); + BUILD_BUG_ON_NON_CONST_STRUCT(rel->is_augmented); + + if (rel->is_augmented) + deepest = rb_augment_erase_begin(node); + + if (rel->has_left) { + struct rb_node **left = __grb_to_left(container, rel); + + if (*left == node) + *left = rb_next(node); + } + + if (rel->has_right) { + struct rb_node **right = __grb_to_right(container, rel); + + if (*right == node) + *right = rb_prev(node); + } + + rb_erase(node, root); + + if (rel->is_augmented) + rb_augment_erase_end(deepest, rel->augmented, NULL); +} + +/** + * GRB_RELATIONHIP - Define the relationship bewteen a container with a + * struct rb_root member, and the objects it contains. + * cont_type: . + * root: . + * left: . + * right: . + * obj_type: . + * node: . + * key: . + * compare: . + * unique: . + * tune_many_dupes: . + * ins_replace: . + * augmented: . + */ +#define GRB_RELATIONHIP( \ + cont_type, root, left, right, \ + obj_type, node, key, _compare, \ + _unique, _tune_many_dupes, _ins_replace, _augmented) { \ + .root_offset = offsetof(cont_type, root), \ + .has_left = !IS_EMPTY(left), \ + .has_right = !IS_EMPTY(right), \ + .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), \ + .compare = (rb_compare_f)_compare, \ + .unique = _unique, \ + .tune_many_dupes = _tune_many_dupes, \ + .ins_replace = _ins_replace, \ + .is_augmented = !IS_EMPTY(left), \ + .augmented = IFF_EMPTY(_augmented, 0, _augmented), \ +} + +#define __GRB_DEFINE_INTERFACE( \ + rel_var, insert_func, find_func, remove_func, \ + cont_type, root, left, right, \ + obj_type, node, key, compare, \ + unique, tune_many_dupes, ins_replace, augmented, \ + insert_func_mod, find_func_mod) \ +static const struct grb_relationship rel_var = GRB_RELATIONHIP( \ + cont_type, root, left, right, \ + obj_type, node, key, compare, \ + unique, tune_many_dupes, ins_replace, augmented); \ + \ +insert_func_mod \ +obj_type *insert_func(cont_type *container, obj_type *obj) { \ + return (obj_type *)grb_insert(container, obj, &rel_var); \ +} \ + \ +find_func_mod \ +obj_type *find_func(const cont_type *container, \ + const typeof(((obj_type *)0)->key) *key) { \ + return (obj_type *)grb_find(container, key, &rel_var); \ +} \ + \ +static __always_inline \ +void remove_func(cont_type *container, obj_type *obj) { \ + grb_remove(container, obj, &rel_var); \ +} \ + +/** GRB_DEFINE_INTERFACE - Defines a struct grb_relationship object and + * type-safe inteface functions. + * prefix: . + * cont_type: . + * root: . + * left: . + * right: . + * obj_type: . + * node: . + * key: . + * compare: . + * unique: . + * tune_many_dupes: . + * ins_replace: . + * augmented: . + * insert_func_mod: . + * find_func_mod: . + */ +#define GRB_DEFINE_INTERFACE(prefix, ...)\ +__GRB_DEFINE_INTERFACE( \ + prefix ## rel, \ + prefix ## insert, \ + prefix ## find, \ + prefix ## remove, \ + __VA_ARGS__) + + +/** GRB_DEFINE_INTERFACE_OBJ - A cute way to contain the type-safe interface + * in a single object, but killing inline-ability. + * interface_name: name of your interface object + * cont_type: . + * root: . + * left: . + * right: . + * obj_type: . + * node: . + * key: . + * compare: . + * unique: . + * tune_many_dupes: . + * ins_replace: . + * augmented: . + */ +#define GRB_DEFINE_INTERFACE_OBJ( \ + interface_name, \ + cont_type, root, left, right, \ + obj_type, node, key, compare, \ + unique, tune_many_dupes, ins_replace, augmented) \ +static const struct { \ + struct grb_relationship rel; \ + obj_type *(*insert)(cont_type *c, obj_type *o, \ + const struct grb_relationship *rel); \ + obj_type *(*find)(const cont_type *c, \ + const typeof(((obj_type *)0)->key) *key, \ + const struct grb_relationship *rel); \ + void (*remove)(cont_type *c, obj_type *o, \ + const struct grb_relationship *rel); \ +} interface_name = { \ +.rel = GRB_RELATIONHIP( \ + cont_type, root, left, right, \ + obj_type, node, key, compare, \ + unique, tune_many_dupes, ins_replace, augmented), \ + \ +.insert = (obj_type *(*)(cont_type *, \ + obj_type *, \ + const struct grb_relationship *))grb_insert, \ +.find = (obj_type *(*)(const cont_type *, \ + const typeof(((obj_type *)0)->key) *, \ + const struct grb_relationship *))grb_find, \ +.remove = (void (*)(cont_type *, obj_type *, \ + const struct grb_relationship *))grb_remove, \ +}; + + + +#endif /* _LINUX_GRBTREE_H */