linux/lib/interval_tree_test.c, branch v4.14

lib/interval_tree: fast overlap detection

2017-09-09T01:26:49Z

Allow interval trees to quickly check for overlaps to avoid unnecesary tree lookups in interval_tree_iter_first(). As of this patch, all interval tree flavors will require using a 'rb_root_cached' such that we can have the leftmost node easily available. While most users will make use of this feature, those with special functions (in addition to the generic insert, delete, search calls) will avoid using the cached option as they can do funky things with insertions -- for example, vma_interval_tree_insert_after(). [jglisse@redhat.com: fix deadlock from typo vm_lock_anon_vma()] Link: http://lkml.kernel.org/r/20170808225719.20723-1-jglisse@redhat.com Link: http://lkml.kernel.org/r/20170719014603.19029-12-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Jérôme Glisse Acked-by: Christian König Acked-by: Peter Zijlstra (Intel) Acked-by: Doug Ledford Acked-by: Michael S. Tsirkin Cc: David Airlie Cc: Jason Wang Cc: Christian Benvenuti Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/interval_tree_test.c: allow full tree search

2017-07-10T23:32:35Z

... such that a user can specify visiting all the nodes in the tree (intersects with the world). This is a nice opposite from the very basic default query which is a single point. Link: http://lkml.kernel.org/r/20170518174936.20265-5-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/interval_tree_test.c: allow users to limit scope of endpoint

2017-07-10T23:32:35Z

Add a 'max_endpoint' parameter such that users may easily limit the size of the intervals that are randomly generated. Link: http://lkml.kernel.org/r/20170518174936.20265-4-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/interval_tree_test.c: make test options module parameters

2017-07-10T23:32:35Z

Allows for more flexible debugging. Link: http://lkml.kernel.org/r/20170518174936.20265-3-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib: Export interval_tree

2014-05-05T07:09:14Z

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