gpu/drm/drm_mm.c

152 INTERVAL_TREE_DEFINE(struct drm_mm_node, rb,
168 	struct rb_node **link, *rb;
175 		rb = &hole_node->rb;
176 		while (rb) {
177 			parent = rb_entry(rb, struct drm_mm_node, rb);
182 			rb = rb_parent(rb);
185 		rb = &hole_node->rb;
186 		link = &hole_node->rb.rb_right;
189 		rb = NULL;
195 		rb = *link;
196 		parent = rb_entry(rb, struct drm_mm_node, rb);
200 			link = &parent->rb.rb_left;
202 			link = &parent->rb.rb_right;
207 	rb_link_node(&node->rb, rb, link);
208 	rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost,
215 static u64 rb_to_hole_size(struct rb_node *rb)
217 	return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size;
223 	struct rb_node **link = &root->rb_root.rb_node, *rb = NULL;
228 		rb = *link;
229 		if (x > rb_to_hole_size(rb)) {
230 			link = &rb->rb_left;
232 			link = &rb->rb_right;
237 	rb_link_node(&node->rb_hole_size, rb, link);
295 static inline struct drm_mm_node *rb_hole_size_to_node(struct rb_node *rb)
297 	return rb_entry_safe(rb, struct drm_mm_node, rb_hole_size);
300 static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb)
302 	return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr);
307 	struct rb_node *rb = mm->holes_size.rb_root.rb_node;
312 			rb_entry(rb, struct drm_mm_node, rb_hole_size);
316 			rb = rb->rb_right;
318 			rb = rb->rb_left;
320 	} while (rb);
325 static bool usable_hole_addr(struct rb_node *rb, u64 size)
327 	return rb && rb_hole_addr_to_node(rb)->subtree_max_hole >= size;
332 	struct rb_node *rb = mm->holes_addr.rb_node;
335 	while (rb) {
338 		if (!usable_hole_addr(rb, size))
341 		node = rb_hole_addr_to_node(rb);
345 			rb = node->rb_hole_addr.rb_left;
347 			rb = node->rb_hole_addr.rb_right;
381  * @first: first rb member to traverse (either rb_left or rb_right).
382  * @last: last rb member to traverse (either rb_right or rb_left).
384  * This macro declares a function to return the next hole of the addr rb tree.
493 static u64 rb_to_hole_size_or_zero(struct rb_node *rb)
495 	return rb ? rb_to_hole_size(rb) : 0;
670 	rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree);