drm: Track drm_mm nodes with an interval tree

In addition to the last-in/first-out stack for accessing drm_mm nodes,
we occasionally and in the future often want to find a drm_mm_node by an
address. To do so efficiently we need to track the nodes in an interval
tree - lookups for a particular address will then be O(lg(N)), where N
is the number of nodes in the range manager as opposed to O(N).
Insertion however gains an extra O(lg(N)) step for all nodes
irrespective of whether the interval tree is in use. For future i915
patches, eliminating the linear walk is a significant improvement.

v2: Use generic interval-tree template for u64 and faster insertion.

Signed-off-by: Chris Wilson <[email protected]>
Cc: David Herrmann <[email protected]>
Cc: [email protected]
Reviewed-by: David Herrmann <[email protected]>
Signed-off-by: Daniel Vetter <[email protected]>
Link: http://patchwork.freedesktop.org/patch/msgid/[email protected]

0 files changed, 0 insertions, 0 deletions