[tcf-dev] Speedup compute_reverse_lookup_indices.

["Rafal Hibner" <Rafal.Hibner@xxxxxxxxxxxx>]

Hello everyone. This is my first contributiuon here.

Inefficient implementation of mStatesIndex creation results in long
startup of debug context. This patch changes O(N^2) complexity to O(N).
It vastly speeds up startup with big symbol files (>300MB).

---
 agent/tcf/services/dwarfcache.c | 33
++++++++++++++++++---------------
 1 file changed, 18 insertions(+), 15 deletions(-)

diff --git a/agent/tcf/services/dwarfcache.c
b/agent/tcf/services/dwarfcache.c
index f073a08..8b2942a 100644
--- a/agent/tcf/services/dwarfcache.c
+++ b/agent/tcf/services/dwarfcache.c
@@ -2373,22 +2373,25 @@ static int state_text_pos_comparator(const void
* x1, const void * x2) {
 }
 
 static void compute_reverse_lookup_indices(DWARFCache * Cache,
CompUnit * Unit) {
-    U4_T i;
+    U4_T i,j;
     qsort(Unit->mStates, Unit->mStatesCnt, sizeof(LineNumbersState),
state_address_comparator);
-    Unit->mStatesIndex = (LineNumbersState
**)loc_alloc(sizeof(LineNumbersState *) * Unit->mStatesCnt);
-    for (i = 0; i < Unit->mStatesCnt; i++) {
-        LineNumbersState * s1 = Unit->mStates + i;
-        while (i + 1 < Unit->mStatesCnt) {
-            LineNumbersState * s2 = s1 + 1;
-            if (s1->mFile != s2->mFile ||
-                s1->mLine != s2->mLine || s1->mColumn != s2->mColumn
||
-                s1->mFlags != s2->mFlags || s1->mISA != s2->mISA ||
-                s1->mOpIndex != s2->mOpIndex || s1->mDiscriminator !=
s2->mDiscriminator) break;
-            memmove(s2, s2 + 1, sizeof(LineNumbersState) *
(Unit->mStatesCnt - i - 2));
-            Unit->mStatesCnt--;
-        }
-        Unit->mStatesIndex[i] = s1;
-    }
+    Unit->mStatesIndex =
(LineNumbersState**)loc_alloc(sizeof(LineNumbersState*) *
Unit->mStatesCnt);
+    LineNumbersState* s2 = Unit->mStates;
+    for (i = 1, j = 0; i < Unit->mStatesCnt; i++) {
+        LineNumbersState* s1 = Unit->mStates + i;
+        if (s1->mLine != s2->mLine || s1->mColumn != s2->mColumn ||
+            s1->mFile != s2->mFile ||
+            s1->mFlags != s2->mFlags || s1->mISA != s2->mISA ||
+            s1->mOpIndex != s2->mOpIndex || s1->mDiscriminator !=
s2->mDiscriminator) {
+            Unit->mStatesIndex[j++] = s2;
+        }
+        s2 = s1;
+    }
+    for (i = 0; i < j; i++) {
+        memmove(Unit->mStates + i, Unit->mStatesIndex[i],
sizeof(LineNumbersState));
+        Unit->mStatesIndex[i] = Unit->mStates + i;
+    }
+    Unit->mStatesCnt = j;
     qsort(Unit->mStatesIndex, Unit->mStatesCnt,
sizeof(LineNumbersState *), state_text_pos_comparator);
     for (i = 0; i < Unit->mStatesCnt; i++)
Unit->mStatesIndex[i]->mStatesIndexPos = i;
     if (Cache->mFileInfoHash == NULL) {
--