Lely core libraries  2.3.4
rbtree.c File Reference

This file is part of the utilities library; it contains the implementation of the red-black tree. More...

#include "util.h"
#include <lely/util/rbtree.h>
#include <assert.h>
Include dependency graph for rbtree.c:

Go to the source code of this file.

Functions

static struct rbnoderbnode_get_parent (const struct rbnode *node)
 Returns the parent of node. node MUST NOT be NULL.
 
static void rbnode_set_parent (struct rbnode *node, const struct rbnode *parent)
 Sets the parent of node to parent. More...
 
static int rbnode_get_color (const struct rbnode *node)
 Returns the color of node, or 0 (black) if node is NULL.
 
static void rbnode_set_color (struct rbnode *node, int color)
 Sets the color of node to 0 (black) if color is 0, or to 1 (red) otherwise. More...
 
static struct rbnoderbnode_min (struct rbnode *node)
 Returns the leftmost descendant of node.
 
static struct rbnoderbnode_max (struct rbnode *node)
 Returns the rightmost descendant of node.
 
static void rbtree_rol (struct rbtree *tree, struct rbnode *node)
 Rotates node counter-clockwise (left), i.e., it is replaced in the tree by its right child, while becoming that child's left child.
 
static void rbtree_ror (struct rbtree *tree, struct rbnode *node)
 Rotates node clockwise (right), i.e., it is replaced in the tree by its left child, while becoming that child's right child.
 
static void rbtree_replace (struct rbtree *tree, struct rbnode *old_node, struct rbnode *new_node)
 Replaces old_node by new_node in tree by updating its parent.
 
struct rbnoderbnode_prev (const struct rbnode *node)
 Returns a pointer to the previous (in-order) node in a red-black tree with respect to node. More...
 
struct rbnoderbnode_next (const struct rbnode *node)
 Returns a pointer to the next (in-order) node in a red-black tree with respect to node. More...
 
void rbtree_insert (struct rbtree *tree, struct rbnode *node)
 Inserts a node into a red-black tree. More...
 
void rbtree_remove (struct rbtree *tree, struct rbnode *node)
 Removes a node from a red-black tree. More...
 
struct rbnoderbtree_find (const struct rbtree *tree, const void *key)
 Finds a node in a red-black tree. More...
 
int rbtree_contains (const struct rbtree *tree, const struct rbnode *node)
 Checks if a node is part of a red-black tree. More...
 
struct rbnoderbtree_first (const struct rbtree *tree)
 Returns a pointer to the first (leftmost) node in a red-black tree. More...
 
struct rbnoderbtree_last (const struct rbtree *tree)
 Returns a pointer to the last (rightmost) node in a red-black tree. More...
 

Detailed Description

This file is part of the utilities library; it contains the implementation of the red-black tree.

See also
lely/util/rbtree.h
Author
J. S. Seldenthuis jseld.nosp@m.enth.nosp@m.uis@l.nosp@m.ely..nosp@m.com

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Definition in file rbtree.c.

Function Documentation

◆ rbnode_set_parent()

static void rbnode_set_parent ( struct rbnode node,
const struct rbnode parent 
)
static

Sets the parent of node to parent.

If node is NULL, this function has no effect.

Definition at line 359 of file rbtree.c.

◆ rbnode_set_color()

static void rbnode_set_color ( struct rbnode node,
int  color 
)
inlinestatic

Sets the color of node to 0 (black) if color is 0, or to 1 (red) otherwise.

If node is NULL, this function has no effect.

Definition at line 374 of file rbtree.c.

◆ rbnode_prev()

struct rbnode* rbnode_prev ( const struct rbnode node)

Returns a pointer to the previous (in-order) node in a red-black tree with respect to node.

This is, at worst, an O(log(n)) operation.

See also
rbnode_next()

Definition at line 74 of file rbtree.c.

◆ rbnode_next()

struct rbnode* rbnode_next ( const struct rbnode node)

Returns a pointer to the next (in-order) node in a red-black tree with respect to node.

This is, at worst, an O(log(n)) operation. However, visiting all nodes in order is an O(n) operation, and therefore, on average, O(1) for each node.

See also
rbnode_prev()

Definition at line 91 of file rbtree.c.

◆ rbtree_insert()

void rbtree_insert ( struct rbtree tree,
struct rbnode node 
)

Inserts a node into a red-black tree.

This is an O(log(n)) operation. This function does not check whether a node with the same key already exists, or whether the node is already part of another tree.

See also
rbtree_remove(), rbtree_find()

Definition at line 108 of file rbtree.c.

◆ rbtree_remove()

void rbtree_remove ( struct rbtree tree,
struct rbnode node 
)

Removes a node from a red-black tree.

This is an O(log(n)) operation.

See also
rbtree_insert()

Definition at line 187 of file rbtree.c.

◆ rbtree_find()

struct rbnode* rbtree_find ( const struct rbtree tree,
const void *  key 
)

Finds a node in a red-black tree.

This is an O(log(n)) operation.

Returns
a pointer to the node if found, or NULL if not.
See also
rbtree_insert()

Definition at line 306 of file rbtree.c.

◆ rbtree_contains()

int rbtree_contains ( const struct rbtree tree,
const struct rbnode node 
)

Checks if a node is part of a red-black tree.

Returns
1 if the node was found in the tree, and 0 if not.

Definition at line 322 of file rbtree.c.

◆ rbtree_first()

struct rbnode* rbtree_first ( const struct rbtree tree)

Returns a pointer to the first (leftmost) node in a red-black tree.

This is an O(log(n)) operation.

See also
rbtree_last()

Definition at line 335 of file rbtree.c.

◆ rbtree_last()

struct rbnode* rbtree_last ( const struct rbtree tree)

Returns a pointer to the last (rightmost) node in a red-black tree.

This is an O(log(n)) operation.

See also
rbtree_first()

Definition at line 343 of file rbtree.c.