]> git.karo-electronics.de Git - linux-beck.git/commit
drm: Track drm_mm nodes with an interval tree
authorChris Wilson <chris@chris-wilson.co.uk>
Wed, 3 Aug 2016 15:04:09 +0000 (16:04 +0100)
committerDaniel Vetter <daniel.vetter@ffwll.ch>
Mon, 8 Aug 2016 08:05:16 +0000 (10:05 +0200)
commit202b52b7fbf70858609ec20829c7d69a13ffa351
tree5d4d2383e745fdd75fffeb053974eacfbe4ccdc7
parent1d776851a6949abd85ba305514612fed16ff2459
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 <chris@chris-wilson.co.uk>
Cc: David Herrmann <dh.herrmann@gmail.com>
Cc: dri-devel@lists.freedesktop.org
Reviewed-by: David Herrmann <dh.herrmann@gmail.com>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/1470236651-678-1-git-send-email-chris@chris-wilson.co.uk
drivers/gpu/drm/drm_mm.c
include/drm/drm_mm.h