diff options
author | Ben Skeggs <bskeggs@redhat.com> | 2015-08-20 14:54:16 +1000 |
---|---|---|
committer | Ben Skeggs <bskeggs@redhat.com> | 2015-08-28 12:37:37 +1000 |
commit | e59f3bfd6f1fdb8390ddcd9a1db93f03da5a5c08 (patch) | |
tree | a4ff683f7e007b6241030b11867aa39b8506aa6c /lib | |
parent | 33b1104b25f0e58ca56d6dd13ce917371a9115fe (diff) | |
download | nouveau-e59f3bfd6f1fdb8390ddcd9a1db93f03da5a5c08.tar.gz |
nvif: replace path-based object identification
Signed-off-by: Ben Skeggs <bskeggs@redhat.com>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Makefile | 1 | ||||
-rw-r--r-- | lib/include/nvif/os.h | 22 | ||||
-rw-r--r-- | lib/rb.c | 92 |
3 files changed, 115 insertions, 0 deletions
diff --git a/lib/Makefile b/lib/Makefile index ca3be266d..b4ac32765 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -31,6 +31,7 @@ srcs := $(lib)/bit.o \ $(lib)/intr.o \ $(lib)/main.o \ $(lib)/null.o \ + $(lib)/rb.o \ $(lib)/work.o outp := $(lib)/libnvif.so diff --git a/lib/include/nvif/os.h b/lib/include/nvif/os.h index 01b648d6c..58f71c535 100644 --- a/lib/include/nvif/os.h +++ b/lib/include/nvif/os.h @@ -552,6 +552,28 @@ struct lock_class_key { #include "list.h" /****************************************************************************** + * rbtree + *****************************************************************************/ +struct rb_root { + struct rb_node *rb_node; +}; + +#define RB_ROOT (struct rb_root) {} + +struct rb_node { + struct rb_node *parent; + struct rb_node *rb_left; + struct rb_node *rb_right; +}; + +#define RB_EMPTY_NODE(a) ((a)->parent == (a)) +#define RB_CLEAR_NODE(a) ((a)->parent = (a)) + +void rb_link_node(struct rb_node *, struct rb_node *, struct rb_node **); +void rb_insert_color(struct rb_node *, struct rb_root *); +void rb_erase(struct rb_node *, struct rb_root *); + +/****************************************************************************** * io space *****************************************************************************/ #define __iomem diff --git a/lib/rb.c b/lib/rb.c new file mode 100644 index 000000000..68be227a1 --- /dev/null +++ b/lib/rb.c @@ -0,0 +1,92 @@ +/* + * Copyright 2015 Red Hat Inc. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR + * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, + * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + * + * Authors: Ben Skeggs <bskeggs@redhat.com> + */ +#include <core/os.h> + +/*XXX: this is just an unbalanced bst with linux's rbtree interface */ + +void +rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **ptr) +{ + node->parent = parent; + *ptr = node; +} + +void +rb_insert_color(struct rb_node *node, struct rb_root *root) +{ +} + +void +rb_erase(struct rb_node *node, struct rb_root *root) +{ + struct rb_node **ptr; + + /* determine which parent pointer needs replacing */ + if (node->parent) { + if (node == node->parent->rb_left) + ptr = &node->parent->rb_left; + else + ptr = &node->parent->rb_right; + } else { + ptr = &root->rb_node; + } + + if (node->rb_left && node->rb_right) { + /* find the largest value to the left of the deleted + * node, this will take its place in the tree + */ + struct rb_node *lr = node->rb_left; + while (lr->rb_right) + lr = lr->rb_right; + /* if this isn't the immediate left of the deleted node, + * search down to find the smallest value and link the + * immediate left of the deleted node there + */ + if (node->rb_left != lr) { + struct rb_node *lrl = lr; + while (lrl->rb_left) + lrl = lrl->rb_left; + lrl->rb_left = node->rb_left; + lrl->rb_left->parent = lrl; + lr->parent->rb_right = NULL; + } + /* link into the deleted node's position */ + lr->parent = node->parent; + lr->rb_right = node->rb_right; + lr->rb_right->parent = lr; + *ptr = lr; + } else + if (node->rb_left) { + /* move left node into the deleted node's position */ + node->rb_left->parent = node->parent; + *ptr = node->rb_left; + } else + if (node->rb_right) { + /* move right node into the deleted node's position */ + node->rb_right->parent = node->parent; + *ptr = node->rb_right; + } else { + *ptr = NULL; + } +} |