rbtree_i.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.
*/
#ifndef _KERN_RBTREE_I_H
#define _KERN_RBTREE_I_H
#include <assert.h>
struct starpu_rbtree_node {
uintptr_t parent;
struct starpu_rbtree_node *children[2];
};
struct starpu_rbtree {
struct starpu_rbtree_node *root;
};
#define STARPU_RBTREE_COLOR_MASK ((uintptr_t) 0x1)
#define STARPU_RBTREE_PARENT_MASK (~((uintptr_t) 0x3))
#define STARPU_RBTREE_COLOR_RED 0
#define STARPU_RBTREE_COLOR_BLACK 1
#define STARPU_RBTREE_SLOT_INDEX_MASK ((uintptr_t) 0x1)
#define STARPU_RBTREE_SLOT_PARENT_MASK (~STARPU_RBTREE_SLOT_INDEX_MASK)
static inline int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
{
return ((uintptr_t)node & (~STARPU_RBTREE_PARENT_MASK)) == 0;
}
static inline int starpu_rbtree_check_index(int index)
{
return index == (index & 1);
}
static inline int starpu_rbtree_d2i(int diff)
{
return !(diff <= 0);
}
static inline struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
{
return (struct starpu_rbtree_node *)(node->parent & STARPU_RBTREE_PARENT_MASK);
}
static inline uintptr_t starpu_rbtree_slot(struct starpu_rbtree_node *parent, int index)
{
assert(starpu_rbtree_check_alignment(parent));
assert(starpu_rbtree_check_index(index));
return (uintptr_t)parent | index;
}
static inline struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
{
return (struct starpu_rbtree_node *)(slot & STARPU_RBTREE_SLOT_PARENT_MASK);
}
static inline int starpu_rbtree_slot_index(uintptr_t slot)
{
return slot & STARPU_RBTREE_SLOT_INDEX_MASK;
}
void starpu_rbtree_insert_rebalance(struct starpu_rbtree *tree, struct starpu_rbtree_node *parent,
int index, struct starpu_rbtree_node *node);
struct starpu_rbtree_node * starpu_rbtree_nearest(struct starpu_rbtree_node *parent, int index,
int direction);
struct starpu_rbtree_node * starpu_rbtree_firstlast(const struct starpu_rbtree *tree, int direction);
struct starpu_rbtree_node * starpu_rbtree_walk(struct starpu_rbtree_node *node, int direction);
struct starpu_rbtree_node * starpu_rbtree_postwalk_deepest(const struct starpu_rbtree *tree);
struct starpu_rbtree_node * starpu_rbtree_postwalk_unlink(struct starpu_rbtree_node *node);
#endif /* _KERN_RBTREE_I_H */
starpu_rbtree_postwalk_deepest
struct starpu_rbtree_node * starpu_rbtree_postwalk_deepest(const struct starpu_rbtree *tree)
starpu_rbtree_check_index
static int starpu_rbtree_check_index(int index)
Definition: rbtree_i.h:90
starpu_rbtree_slot_index
static int starpu_rbtree_slot_index(uintptr_t slot)
Definition: rbtree_i.h:135
starpu_rbtree_slot_parent
static struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
Definition: rbtree_i.h:127
starpu_rbtree_walk
struct starpu_rbtree_node * starpu_rbtree_walk(struct starpu_rbtree_node *node, int direction)
starpu_rbtree_nearest
struct starpu_rbtree_node * starpu_rbtree_nearest(struct starpu_rbtree_node *parent, int index, int direction)
starpu_rbtree_d2i
static int starpu_rbtree_d2i(int diff)
Definition: rbtree_i.h:101
starpu_rbtree_slot
static uintptr_t starpu_rbtree_slot(struct starpu_rbtree_node *parent, int index)
Definition: rbtree_i.h:117
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_parent
static struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:109
starpu_rbtree_firstlast
struct starpu_rbtree_node * starpu_rbtree_firstlast(const struct starpu_rbtree *tree, int direction)
STARPU_RBTREE_SLOT_INDEX_MASK
#define STARPU_RBTREE_SLOT_INDEX_MASK
Definition: rbtree_i.h:76
starpu_rbtree_postwalk_unlink
struct starpu_rbtree_node * starpu_rbtree_postwalk_unlink(struct starpu_rbtree_node *node)
starpu_rbtree
Definition: rbtree_i.h:55
starpu_rbtree_node
Definition: rbtree_i.h:47