StarPU Internal Handbook
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  uintptr_t parent;
49  struct starpu_rbtree_node *children[2];
50 };
51 
55 struct starpu_rbtree {
56  struct starpu_rbtree_node *root;
57 };
58 
63 #define STARPU_RBTREE_COLOR_MASK ((uintptr_t) 0x1)
64 #define STARPU_RBTREE_PARENT_MASK (~((uintptr_t) 0x3))
65 
69 #define STARPU_RBTREE_COLOR_RED 0
70 #define STARPU_RBTREE_COLOR_BLACK 1
71 
76 #define STARPU_RBTREE_SLOT_INDEX_MASK ((uintptr_t) 0x1)
77 #define STARPU_RBTREE_SLOT_PARENT_MASK (~STARPU_RBTREE_SLOT_INDEX_MASK)
78 
82 static inline int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
83 {
84  return ((uintptr_t)node & (~STARPU_RBTREE_PARENT_MASK)) == 0;
85 }
86 
90 static inline int starpu_rbtree_check_index(int index)
91 {
92  return index == (index & 1);
93 }
94 
101 static inline int starpu_rbtree_d2i(int diff)
102 {
103  return !(diff <= 0);
104 }
105 
109 static inline struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
110 {
111  return (struct starpu_rbtree_node *)(node->parent & STARPU_RBTREE_PARENT_MASK);
112 }
113 
117 static inline uintptr_t starpu_rbtree_slot(struct starpu_rbtree_node *parent, int index)
118 {
119  assert(starpu_rbtree_check_alignment(parent));
120  assert(starpu_rbtree_check_index(index));
121  return (uintptr_t)parent | index;
122 }
123 
127 static inline struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
128 {
129  return (struct starpu_rbtree_node *)(slot & STARPU_RBTREE_SLOT_PARENT_MASK);
130 }
131 
135 static inline int starpu_rbtree_slot_index(uintptr_t slot)
136 {
137  return slot & STARPU_RBTREE_SLOT_INDEX_MASK;
138 }
139 
149  int index, struct starpu_rbtree_node *node);
150 
159  int direction);
160 
167 struct starpu_rbtree_node * starpu_rbtree_firstlast(const struct starpu_rbtree *tree, int direction);
168 
175 struct starpu_rbtree_node * starpu_rbtree_walk(struct starpu_rbtree_node *node, int direction);
176 
182 
187 
188 #endif /* _KERN_RBTREE_I_H */
static struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:109
static int starpu_rbtree_check_index(int index)
Definition: rbtree_i.h:90
static int starpu_rbtree_slot_index(uintptr_t slot)
Definition: rbtree_i.h:135
struct starpu_rbtree_node * starpu_rbtree_postwalk_unlink(struct starpu_rbtree_node *node)
struct starpu_rbtree_node * starpu_rbtree_postwalk_deepest(const struct starpu_rbtree *tree)
static struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
Definition: rbtree_i.h:127
static int starpu_rbtree_d2i(int diff)
Definition: rbtree_i.h:101
static uintptr_t starpu_rbtree_slot(struct starpu_rbtree_node *parent, int index)
Definition: rbtree_i.h:117
static int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:82
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_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_nearest(struct starpu_rbtree_node *parent, int index, int direction)
#define STARPU_RBTREE_SLOT_INDEX_MASK
Definition: rbtree_i.h:76
Definition: rbtree_i.h:55
Definition: rbtree_i.h:47