* Generic range manager structs
*/
#include <linux/bug.h>
+#include <linux/rbtree.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/spinlock.h>
struct drm_mm_node {
struct list_head node_list;
struct list_head hole_stack;
+ struct rb_node rb;
unsigned hole_follows : 1;
unsigned scanned_block : 1;
unsigned scanned_prev_free : 1;
unsigned long color;
u64 start;
u64 size;
+ u64 __subtree_last;
struct drm_mm *mm;
};
/* head_node.node_list is the list of all memory nodes, ordered
* according to the (increasing) start address of the memory node. */
struct drm_mm_node head_node;
+ /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
+ struct rb_root interval_tree;
+
unsigned int scan_check_range : 1;
unsigned scan_alignment;
unsigned long scan_color;
void drm_mm_takedown(struct drm_mm *mm);
bool drm_mm_clean(struct drm_mm *mm);
+struct drm_mm_node *
+drm_mm_interval_first(struct drm_mm *mm, u64 start, u64 last);
+
+struct drm_mm_node *
+drm_mm_interval_next(struct drm_mm_node *node, u64 start, u64 last);
+
void drm_mm_init_scan(struct drm_mm *mm,
u64 size,
unsigned alignment,