From a88cc108f6f39e56577793f66ac69eb0e18ae099 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Mon, 17 Mar 2014 12:21:54 +0000 Subject: lib: Export interval_tree lib/interval_tree.c provides a simple interface for an interval-tree (an augmented red-black tree) but is only built when testing the generic macros for building interval-trees. For drivers with modest needs, export the simple interval-tree library as is. v2: Lots of help from Michel Lespinasse to only compile the code as required: - make INTERVAL_TREE a config option - make INTERVAL_TREE_TEST select the library functions and sanitize the filenames & Makefile - prepare interval_tree for being built as a module if required Signed-off-by: Chris Wilson Cc: Michel Lespinasse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Cc: Andrew Morton Reviewed-by: Michel Lespinasse [Acked for inclusion via drm/i915 by Andrew Morton.] [danvet: switch to _GPL as per the mailing list discussion.] Signed-off-by: Daniel Vetter --- lib/Kconfig | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'lib/Kconfig') diff --git a/lib/Kconfig b/lib/Kconfig index 4771fb3f4da4..334f7722a999 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -331,6 +331,20 @@ config TEXTSEARCH_FSM config BTREE boolean +config INTERVAL_TREE + boolean + help + Simple, embeddable, interval-tree. Can find the start of an + overlapping range in log(n) time and then iterate over all + overlapping nodes. The algorithm is implemented as an + augmented rbtree. + + See: + + Documentation/rbtree.txt + + for more information. + config ASSOCIATIVE_ARRAY bool help -- cgit v1.2.3