Tracking: Re-write marker request function

There are two main things.

First, remove the marker index caching. Thins makes it possible to
safely use function from a threaded environment.

Second, replace linear search with binary search, which speeds up
random lookup.

There is no measurable difference in the stabilization which had a
comment about caching nature of track lookup. The random lookup
complexity changed from O(N) to O(log N). In practice this also
unlikely to be measurable, but thread-safety worth it.

1 files changed, 45 insertions, 11 deletions

diff --git a/source/blender/blenkernel/intern/tracking_test.cc b/source/blender/blenkernel/intern/tracking_test.cc
index 6afcf6872eb..6c3cf89a03f 100644
--- a/source/blender/blenkernel/intern/tracking_test.cc
+++ b/source/blender/blenkernel/intern/tracking_test.cc
@@ -22,24 +22,58 @@ class TrackingTest : public ::testing::Test {
 
 TEST_F(TrackingTest, BKE_tracking_marker_get)
 {
-  MovieTrackingTrack track = {nullptr};
+  {
+    MovieTrackingTrack track = {nullptr};
 
-  addMarkerToTrack(&track, 1);
-  addMarkerToTrack(&track, 10);
+    addMarkerToTrack(&track, 10);
 
-  {
-    const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 1);
-    EXPECT_NE(marker, nullptr);
-    EXPECT_EQ(marker->framenr, 1);
+    EXPECT_EQ(BKE_tracking_marker_get(&track, 0), &track.markers[0]);
+    EXPECT_EQ(BKE_tracking_marker_get(&track, 10), &track.markers[0]);
+    EXPECT_EQ(BKE_tracking_marker_get(&track, 20), &track.markers[0]);
+
+    BKE_tracking_track_free(&track);
   }
 
   {
-    const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 5);
-    EXPECT_NE(marker, nullptr);
-    EXPECT_EQ(marker->framenr, 1);
+    MovieTrackingTrack track = {nullptr};
+
+    addMarkerToTrack(&track, 1);
+    addMarkerToTrack(&track, 10);
+
+    {
+      const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 1);
+      EXPECT_NE(marker, nullptr);
+      EXPECT_EQ(marker->framenr, 1);
+    }
+
+    {
+      const MovieTrackingMarker *marker = BKE_tracking_marker_get(&track, 5);
+      EXPECT_NE(marker, nullptr);
+      EXPECT_EQ(marker->framenr, 1);
+    }
+
+    BKE_tracking_track_free(&track);
   }
 
-  BKE_tracking_track_free(&track);
+  {
+    {
+      MovieTrackingTrack track = {nullptr};
+
+      addMarkerToTrack(&track, 1);
+      addMarkerToTrack(&track, 2);
+      addMarkerToTrack(&track, 10);
+
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 0), &track.markers[0]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 1), &track.markers[0]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 2), &track.markers[1]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 3), &track.markers[1]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 9), &track.markers[1]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 10), &track.markers[2]);
+      EXPECT_EQ(BKE_tracking_marker_get(&track, 11), &track.markers[2]);
+
+      BKE_tracking_track_free(&track);
+    }
+  }
 }
 
 TEST_F(TrackingTest, BKE_tracking_marker_get_exact)