StarPU Internal Handbook
Loading...
Searching...
No Matches
rbtree_i.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2010, 2011 Richard Braun.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef _KERN_RBTREE_I_H
27#define _KERN_RBTREE_I_H
28
29#include <assert.h>
30
48{
49 uintptr_t parent;
50 struct starpu_rbtree_node *children[2];
51};
52
57{
58 struct starpu_rbtree_node *root;
59};
60
65#define STARPU_RBTREE_COLOR_MASK ((uintptr_t) 0x1)
66#define STARPU_RBTREE_PARENT_MASK (~((uintptr_t) 0x3))
67
71#define STARPU_RBTREE_COLOR_RED 0
72#define STARPU_RBTREE_COLOR_BLACK 1
73
78#define STARPU_RBTREE_SLOT_INDEX_MASK ((uintptr_t) 0x1)
79#define STARPU_RBTREE_SLOT_PARENT_MASK (~STARPU_RBTREE_SLOT_INDEX_MASK)
80
84static inline int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
85{
86 return ((uintptr_t)node & (~STARPU_RBTREE_PARENT_MASK)) == 0;
87}
88
92static inline int starpu_rbtree_check_index(int index)
93{
94 return index == (index & 1);
95}
96
103static inline int starpu_rbtree_d2i(int diff)
104{
105 return !(diff <= 0);
106}
107
111static inline struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
112{
113 return (struct starpu_rbtree_node *)(node->parent & STARPU_RBTREE_PARENT_MASK);
114}
115
119static inline uintptr_t starpu_rbtree_slot(struct starpu_rbtree_node *parent, int index)
120{
121 assert(starpu_rbtree_check_alignment(parent));
122 assert(starpu_rbtree_check_index(index));
123 return (uintptr_t)parent | index;
124}
125
129static inline struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
130{
131 return (struct starpu_rbtree_node *)(slot & STARPU_RBTREE_SLOT_PARENT_MASK);
132}
133
137static inline int starpu_rbtree_slot_index(uintptr_t slot)
138{
139 return slot & STARPU_RBTREE_SLOT_INDEX_MASK;
140}
141
151 int index, struct starpu_rbtree_node *node);
152
161 int direction);
162
169struct starpu_rbtree_node * starpu_rbtree_firstlast(const struct starpu_rbtree *tree, int direction);
170
177struct starpu_rbtree_node * starpu_rbtree_walk(struct starpu_rbtree_node *node, int direction);
178
184
189
190#endif /* _KERN_RBTREE_I_H */
struct starpu_rbtree_node * starpu_rbtree_postwalk_deepest(const struct starpu_rbtree *tree)
static int starpu_rbtree_check_index(int index)
Definition rbtree_i.h:92
static int starpu_rbtree_slot_index(uintptr_t slot)
Definition rbtree_i.h:137
static struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
Definition rbtree_i.h:129
struct starpu_rbtree_node * starpu_rbtree_walk(struct starpu_rbtree_node *node, int direction)
struct starpu_rbtree_node * starpu_rbtree_nearest(struct starpu_rbtree_node *parent, int index, int direction)
static int starpu_rbtree_d2i(int diff)
Definition rbtree_i.h:103
static uintptr_t starpu_rbtree_slot(struct starpu_rbtree_node *parent, int index)
Definition rbtree_i.h:119
static int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
Definition rbtree_i.h:84
void starpu_rbtree_insert_rebalance(struct starpu_rbtree *tree, struct starpu_rbtree_node *parent, int index, struct starpu_rbtree_node *node)
static struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
Definition rbtree_i.h:111
struct starpu_rbtree_node * starpu_rbtree_firstlast(const struct starpu_rbtree *tree, int direction)
#define STARPU_RBTREE_SLOT_INDEX_MASK
Definition rbtree_i.h:78
struct starpu_rbtree_node * starpu_rbtree_postwalk_unlink(struct starpu_rbtree_node *node)
Definition rbtree_i.h:57
Definition rbtree_i.h:48