rbtree.h
Go to the documentation of this file.
/*
* Copyright (c) 2010, 2011 Richard Braun.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*
* Red-black tree.
*/
#ifndef _KERN_RBTREE_H
#define _KERN_RBTREE_H
#include <stddef.h>
#include <assert.h>
#include <stdint.h>
#include <sys/types.h>
#define MACRO_BEGIN ({
#define MACRO_END })
/*
* Indexes of the left and right nodes in the children array of a node.
*/
#define STARPU_RBTREE_LEFT 0
#define STARPU_RBTREE_RIGHT 1
struct starpu_rbtree_node;
struct starpu_rbtree;
#define STARPU_RBTREE_INITIALIZER { NULL }
#include "rbtree_i.h"
static inline void starpu_rbtree_init(struct starpu_rbtree *tree)
{
tree->root = NULL;
}
static inline void starpu_rbtree_node_init(struct starpu_rbtree_node *node)
{
assert(starpu_rbtree_check_alignment(node));
node->parent = (uintptr_t)node | STARPU_RBTREE_COLOR_RED;
node->children[STARPU_RBTREE_LEFT] = NULL;
node->children[STARPU_RBTREE_RIGHT] = NULL;
}
/*
* Return true if node is in no tree.
*/
static inline int starpu_rbtree_node_unlinked(const struct starpu_rbtree_node *node)
{
return starpu_rbtree_parent(node) == node;
}
#define starpu_rbtree_entry(node, type, member) structof(node, type, member)
static inline int starpu_rbtree_empty(const struct starpu_rbtree *tree)
{
return tree->root == NULL;
}
#define starpu_rbtree_lookup(tree, key, cmp_fn) \
MACRO_BEGIN \
struct starpu_rbtree_node *___cur; \
int ___diff; \
\
___cur = (tree)->root; \
\
while (___cur != NULL) { \
___diff = cmp_fn(key, ___cur); \
\
if (___diff == 0) \
break; \
\
___cur = ___cur->children[starpu_rbtree_d2i(___diff)]; \
} \
\
___cur; \
MACRO_END
#define starpu_rbtree_lookup_nearest(tree, key, cmp_fn, dir) \
MACRO_BEGIN \
struct starpu_rbtree_node *___cur, *___prev; \
int ___diff, ___index; \
\
___prev = NULL; \
___index = -1; \
___cur = (tree)->root; \
\
while (___cur != NULL) { \
___diff = cmp_fn(key, ___cur); \
\
if (___diff == 0) \
break; \
\
___prev = ___cur; \
___index = starpu_rbtree_d2i(___diff); \
___cur = ___cur->children[___index]; \
} \
\
if (___cur == NULL) \
___cur = starpu_rbtree_nearest(___prev, ___index, dir); \
\
___cur; \
MACRO_END
#define starpu_rbtree_insert(tree, node, cmp_fn) \
MACRO_BEGIN \
struct starpu_rbtree_node *___cur, *___prev; \
int ___diff, ___index; \
\
___prev = NULL; \
___index = -1; \
___cur = (tree)->root; \
\
while (___cur != NULL) { \
___diff = cmp_fn(node, ___cur); \
assert(___diff != 0); \
___prev = ___cur; \
___index = starpu_rbtree_d2i(___diff); \
___cur = ___cur->children[___index]; \
} \
\
starpu_rbtree_insert_rebalance(tree, ___prev, ___index, node); \
MACRO_END
#define starpu_rbtree_lookup_slot(tree, key, cmp_fn, slot) \
MACRO_BEGIN \
struct starpu_rbtree_node *___cur, *___prev; \
int ___diff, ___index; \
\
___prev = NULL; \
___index = 0; \
___cur = (tree)->root; \
\
while (___cur != NULL) { \
___diff = cmp_fn(key, ___cur); \
\
if (___diff == 0) \
break; \
\
___prev = ___cur; \
___index = starpu_rbtree_d2i(___diff); \
___cur = ___cur->children[___index]; \
} \
\
(slot) = starpu_rbtree_slot(___prev, ___index); \
___cur; \
MACRO_END
static inline void starpu_rbtree_insert_slot(struct starpu_rbtree *tree, uintptr_t slot,
struct starpu_rbtree_node *node)
{
struct starpu_rbtree_node *parent;
int index;
parent = starpu_rbtree_slot_parent(slot);
index = starpu_rbtree_slot_index(slot);
starpu_rbtree_insert_rebalance(tree, parent, index, node);
}
void starpu_rbtree_remove(struct starpu_rbtree *tree, struct starpu_rbtree_node *node);
/* TODO: optimize by maintaining the first node of the tree */
#define starpu_rbtree_first(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_LEFT)
/* TODO: optimize by maintaining the first node of the tree */
/* TODO: could be useful to optimize the case when the key being inserted is
* bigger that the biggest node */
#define starpu_rbtree_last(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_RIGHT)
#define starpu_rbtree_prev(node) starpu_rbtree_walk(node, STARPU_RBTREE_LEFT)
#define starpu_rbtree_next(node) starpu_rbtree_walk(node, STARPU_RBTREE_RIGHT)
#define starpu_rbtree_for_each_remove(tree, node, tmp) \
for (node = starpu_rbtree_postwalk_deepest(tree), \
tmp = starpu_rbtree_postwalk_unlink(node); \
node != NULL; \
node = tmp, tmp = starpu_rbtree_postwalk_unlink(node)) \
#endif /* _KERN_RBTREE_H */
starpu_rbtree_remove
void starpu_rbtree_remove(struct starpu_rbtree *tree, struct starpu_rbtree_node *node)
starpu_rbtree_init
static void starpu_rbtree_init(struct starpu_rbtree *tree)
Definition: rbtree.h:67
starpu_rbtree_insert_slot
static void starpu_rbtree_insert_slot(struct starpu_rbtree *tree, uintptr_t slot, struct starpu_rbtree_node *node)
Definition: rbtree.h:256
starpu_rbtree_empty
static int starpu_rbtree_empty(const struct starpu_rbtree *tree)
Definition: rbtree.h:103
starpu_rbtree_node_init
static void starpu_rbtree_node_init(struct starpu_rbtree_node *node)
Definition: rbtree.h:77
rbtree_i.h
starpu_rbtree_parent
static struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:109
starpu_rbtree_slot_index
static int starpu_rbtree_slot_index(uintptr_t slot)
Definition: rbtree_i.h:135
STARPU_RBTREE_COLOR_RED
#define STARPU_RBTREE_COLOR_RED
Definition: rbtree_i.h:69
starpu_rbtree_slot_parent
static struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
Definition: rbtree_i.h:127
starpu_rbtree_check_alignment
static int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:82
starpu_rbtree_insert_rebalance
void starpu_rbtree_insert_rebalance(struct starpu_rbtree *tree, struct starpu_rbtree_node *parent, int index, struct starpu_rbtree_node *node)
starpu_rbtree
Definition: rbtree_i.h:55
starpu_rbtree_node
Definition: rbtree_i.h:47