projects
/
fio.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
zbd: Improve random zone index generation logic
[fio.git]
/
lib
/
rbtree.c
diff --git
a/lib/rbtree.c
b/lib/rbtree.c
index 883bc7231d0905b114e45fb57c9a0b525e252b98..6f0feae3a54b7f00f72a853a539a93c0ea8e9397 100644
(file)
--- a/
lib/rbtree.c
+++ b/
lib/rbtree.c
@@
-15,17
+15,17
@@
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
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., 5
9 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ Foundation, Inc., 5
1 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
linux/lib/rbtree.c
*/
#include "rbtree.h"
linux/lib/rbtree.c
*/
#include "rbtree.h"
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+static void __rb_rotate_left(struct
fio_
rb_node *node, struct rb_root *root)
{
{
- struct rb_node *right = node->rb_right;
- struct rb_node *parent = rb_parent(node);
+ struct
fio_
rb_node *right = node->rb_right;
+ struct
fio_
rb_node *parent = rb_parent(node);
if ((node->rb_right = right->rb_left))
rb_set_parent(right->rb_left, node);
if ((node->rb_right = right->rb_left))
rb_set_parent(right->rb_left, node);
@@
-45,10
+45,10
@@
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
rb_set_parent(node, right);
}
rb_set_parent(node, right);
}
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+static void __rb_rotate_right(struct
fio_
rb_node *node, struct rb_root *root)
{
{
- struct rb_node *left = node->rb_left;
- struct rb_node *parent = rb_parent(node);
+ struct
fio_
rb_node *left = node->rb_left;
+ struct
fio_
rb_node *parent = rb_parent(node);
if ((node->rb_left = left->rb_right))
rb_set_parent(left->rb_right, node);
if ((node->rb_left = left->rb_right))
rb_set_parent(left->rb_right, node);
@@
-68,9
+68,9
@@
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
rb_set_parent(node, left);
}
rb_set_parent(node, left);
}
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
+void rb_insert_color(struct
fio_
rb_node *node, struct rb_root *root)
{
{
- struct rb_node *parent, *gparent;
+ struct
fio_
rb_node *parent, *gparent;
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
@@
-79,7
+79,7
@@
void rb_insert_color(struct rb_node *node, struct rb_root *root)
if (parent == gparent->rb_left)
{
{
if (parent == gparent->rb_left)
{
{
- register struct rb_node *uncle = gparent->rb_right;
+ register struct
fio_
rb_node *uncle = gparent->rb_right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
@@
-92,7
+92,7
@@
void rb_insert_color(struct rb_node *node, struct rb_root *root)
if (parent->rb_right == node)
{
if (parent->rb_right == node)
{
- register struct rb_node *tmp;
+ register struct
fio_
rb_node *tmp;
__rb_rotate_left(parent, root);
tmp = parent;
parent = node;
__rb_rotate_left(parent, root);
tmp = parent;
parent = node;
@@
-104,7
+104,7
@@
void rb_insert_color(struct rb_node *node, struct rb_root *root)
__rb_rotate_right(gparent, root);
} else {
{
__rb_rotate_right(gparent, root);
} else {
{
- register struct rb_node *uncle = gparent->rb_left;
+ register struct
fio_
rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
@@
-117,7
+117,7
@@
void rb_insert_color(struct rb_node *node, struct rb_root *root)
if (parent->rb_left == node)
{
if (parent->rb_left == node)
{
- register struct rb_node *tmp;
+ register struct
fio_
rb_node *tmp;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
@@
-133,10
+133,11
@@
void rb_insert_color(struct rb_node *node, struct rb_root *root)
rb_set_black(root->rb_node);
}
rb_set_black(root->rb_node);
}
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+static void __rb_erase_color(struct fio_rb_node *node,
+ struct fio_rb_node *parent,
struct rb_root *root)
{
struct rb_root *root)
{
- struct rb_node *other;
+ struct
fio_
rb_node *other;
while ((!node || rb_is_black(node)) && node != root->rb_node)
{
while ((!node || rb_is_black(node)) && node != root->rb_node)
{
@@
-161,7
+162,7
@@
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
{
if (!other->rb_right || rb_is_black(other->rb_right))
{
{
if (!other->rb_right || rb_is_black(other->rb_right))
{
- struct rb_node *o_left;
+ struct
fio_
rb_node *o_left;
if ((o_left = other->rb_left))
rb_set_black(o_left);
rb_set_red(other);
if ((o_left = other->rb_left))
rb_set_black(o_left);
rb_set_red(other);
@@
-198,7
+199,7
@@
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
{
if (!other->rb_left || rb_is_black(other->rb_left))
{
{
if (!other->rb_left || rb_is_black(other->rb_left))
{
- register struct rb_node *o_right;
+ register struct
fio_
rb_node *o_right;
if ((o_right = other->rb_right))
rb_set_black(o_right);
rb_set_red(other);
if ((o_right = other->rb_right))
rb_set_black(o_right);
rb_set_red(other);
@@
-219,9
+220,9
@@
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
rb_set_black(node);
}
rb_set_black(node);
}
-void rb_erase(struct rb_node *node, struct rb_root *root)
+void rb_erase(struct
fio_
rb_node *node, struct rb_root *root)
{
{
- struct rb_node *child, *parent;
+ struct
fio_
rb_node *child, *parent;
int color;
if (!node->rb_left)
int color;
if (!node->rb_left)
@@
-230,7
+231,7
@@
void rb_erase(struct rb_node *node, struct rb_root *root)
child = node->rb_left;
else
{
child = node->rb_left;
else
{
- struct rb_node *old = node, *left;
+ struct
fio_
rb_node *old = node, *left;
node = node->rb_right;
while ((left = node->rb_left) != NULL)
node = node->rb_right;
while ((left = node->rb_left) != NULL)
@@
-289,9
+290,9
@@
void rb_erase(struct rb_node *node, struct rb_root *root)
/*
* This function returns the first node (in sort order) of the tree.
*/
/*
* This function returns the first node (in sort order) of the tree.
*/
-struct rb_node *rb_first(struct rb_root *root)
+struct
fio_
rb_node *rb_first(struct rb_root *root)
{
{
- struct
rb_node
*n;
+ struct
fio_rb_node
*n;
n = root->rb_node;
if (!n)
n = root->rb_node;
if (!n)
@@
-301,9
+302,9
@@
struct rb_node *rb_first(struct rb_root *root)
return n;
}
return n;
}
-struct
rb_node *rb_next(const struct
rb_node *node)
+struct
fio_rb_node *rb_next(const struct fio_
rb_node *node)
{
{
- struct rb_node *parent;
+ struct
fio_
rb_node *parent;
if (RB_EMPTY_NODE(node))
return NULL;
if (RB_EMPTY_NODE(node))
return NULL;
@@
-316,7
+317,7
@@
struct rb_node *rb_next(const struct rb_node *node)
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
- return (struct rb_node *)node;
+ return (struct
fio_
rb_node *)node;
}
/*
}
/*