Merge branch 'akpm' (patches from Andrew)

[cascardo/linux.git] / include / drm / drm_mm.h

diff --git a/include/drm/drm_mm.h b/include/drm/drm_mm.h
index fc65118..205ddcf 100644 (file)
--- a/include/drm/drm_mm.h
+++ b/include/drm/drm_mm.h
@@ -37,6 +37,7 @@
  * Generic range manager structs
  */
 #include <linux/bug.h>
+#include <linux/rbtree.h>
 #include <linux/kernel.h>
 #include <linux/list.h>
 #include <linux/spinlock.h>
@@ -61,6 +62,7 @@ enum drm_mm_allocator_flags {
 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;
@@ -70,6 +72,7 @@ struct drm_mm_node {
        unsigned long color;
        u64 start;
        u64 size;
+       u64 __subtree_last;
        struct drm_mm *mm;
 };
 
@@ -79,6 +82,9 @@ struct drm_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;
@@ -295,6 +301,12 @@ void drm_mm_init(struct drm_mm *mm,
 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,