Lines Matching refs:rb
152 INTERVAL_TREE_DEFINE(struct drm_mm_node, rb, in INTERVAL_TREE_DEFINE() argument
168 struct rb_node **link, *rb; in drm_mm_interval_tree_add_node() local
175 rb = &hole_node->rb; in drm_mm_interval_tree_add_node()
176 while (rb) { in drm_mm_interval_tree_add_node()
177 parent = rb_entry(rb, struct drm_mm_node, rb); in drm_mm_interval_tree_add_node()
182 rb = rb_parent(rb); in drm_mm_interval_tree_add_node()
185 rb = &hole_node->rb; in drm_mm_interval_tree_add_node()
186 link = &hole_node->rb.rb_right; in drm_mm_interval_tree_add_node()
189 rb = NULL; in drm_mm_interval_tree_add_node()
195 rb = *link; in drm_mm_interval_tree_add_node()
196 parent = rb_entry(rb, struct drm_mm_node, rb); in drm_mm_interval_tree_add_node()
200 link = &parent->rb.rb_left; in drm_mm_interval_tree_add_node()
202 link = &parent->rb.rb_right; in drm_mm_interval_tree_add_node()
207 rb_link_node(&node->rb, rb, link); in drm_mm_interval_tree_add_node()
208 rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost, in drm_mm_interval_tree_add_node()
215 static u64 rb_to_hole_size(struct rb_node *rb) in rb_to_hole_size() argument
217 return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; in rb_to_hole_size()
223 struct rb_node **link = &root->rb_root.rb_node, *rb = NULL; in insert_hole_size() local
228 rb = *link; in insert_hole_size()
229 if (x > rb_to_hole_size(rb)) { in insert_hole_size()
230 link = &rb->rb_left; in insert_hole_size()
232 link = &rb->rb_right; in insert_hole_size()
237 rb_link_node(&node->rb_hole_size, rb, link); in insert_hole_size()
295 static inline struct drm_mm_node *rb_hole_size_to_node(struct rb_node *rb) in rb_hole_size_to_node() argument
297 return rb_entry_safe(rb, struct drm_mm_node, rb_hole_size); in rb_hole_size_to_node()
300 static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb) in rb_hole_addr_to_node() argument
302 return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr); in rb_hole_addr_to_node()
307 struct rb_node *rb = mm->holes_size.rb_root.rb_node; in best_hole() local
312 rb_entry(rb, struct drm_mm_node, rb_hole_size); in best_hole()
316 rb = rb->rb_right; in best_hole()
318 rb = rb->rb_left; in best_hole()
320 } while (rb); in best_hole()
325 static bool usable_hole_addr(struct rb_node *rb, u64 size) in usable_hole_addr() argument
327 return rb && rb_hole_addr_to_node(rb)->subtree_max_hole >= size; in usable_hole_addr()
332 struct rb_node *rb = mm->holes_addr.rb_node; in find_hole_addr() local
335 while (rb) { in find_hole_addr()
338 if (!usable_hole_addr(rb, size)) in find_hole_addr()
341 node = rb_hole_addr_to_node(rb); in find_hole_addr()
345 rb = node->rb_hole_addr.rb_left; in find_hole_addr()
347 rb = node->rb_hole_addr.rb_right; in find_hole_addr()
493 static u64 rb_to_hole_size_or_zero(struct rb_node *rb) in rb_to_hole_size_or_zero() argument
495 return rb ? rb_to_hole_size(rb) : 0; in rb_to_hole_size_or_zero()
670 rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree); in drm_mm_replace_node()