From 22dc6014ecb09547929c45a8fb82820740230589 Mon Sep 17 00:00:00 2001
From: Carl Worth <cworth@cworth.org>
Date: Mon, 11 Mar 2013 12:14:06 -0700
Subject: [PATCH] Extend trim::CallSet with a new range-based add method.

Previously, individual calls had to be added one-at-a-time. This was
adequate for trimming functionality where one call is examined at a
time.

But I'm now wanting to use this same CallSet code to dramatically
optimize the performance of callset specifications on the apitrace
command-line, (in particular large callsets resulting from "apitrace
trim --print-callset"). In this case, we really want to add entire
call ranges rather than just one call at a time.
---
 cli/trim_callset.cpp | 90 ++++++++++++++++++++++++++------------------
 cli/trim_callset.hpp |  7 ++--
 2 files changed, 56 insertions(+), 41 deletions(-)

diff --git a/cli/trim_callset.cpp b/cli/trim_callset.cpp
index 236880a..69ed818 100644
--- a/cli/trim_callset.cpp
+++ b/cli/trim_callset.cpp
@@ -37,10 +37,10 @@ using namespace trim;
 
 #define MAX_LEVEL 16
 
-CallRange::CallRange(CallNo call_no, int level)
+CallRange::CallRange(CallNo first, CallNo last, int level)
 {
-    first = call_no;
-    last = call_no;
+    this->first = first;
+    this->last = last;
     this->level = level;
 
     next = new CallRange*[level];
@@ -52,7 +52,7 @@ CallRange::contains(CallNo call_no)
     return (first <= call_no && last >= call_no);
 }
 
-CallSet::CallSet(): head(0, MAX_LEVEL)
+CallSet::CallSet(): head(0, 0, MAX_LEVEL)
 {
     head.first = std::numeric_limits<CallNo>::max();
     head.last = std::numeric_limits<CallNo>::min();
@@ -88,64 +88,54 @@ random_level (void)
 }
 
 void
-CallSet::add(CallNo call_no)
+CallSet::add(CallNo first, CallNo last)
 {
     CallRange **update[MAX_LEVEL];
-    CallRange *node;
+    CallRange *node, *next;
     int i, level;
 
     /* Find node immediately before insertion point. */
     node = &head;
     for (i = max_level - 1; i >= 0; i--) {
-        while (node->next[i] && call_no > node->next[i]->last) {
+        while (node->next[i] && first > node->next[i]->last) {
             node = node->next[i];
         }
         update[i] = &node->next[i];
     }
 
-    /* Can we contain call_no by expanding tail of current range by 1? */
-    if (node != &head && node->last == call_no - 1) {
-
-        CallRange *next = node->next[0];
-
-        node->last = call_no;
-
-        /* Also merge with next node as needed. */
-        if (next && next->first == call_no + 1) {
-            node->last = next->last;
-
-            /* Delete node 'next' */
-            for (i = 0; i < node->level && i < next->level; i++) {
-                node->next[i] = next->next[i];
-            }
-
-            for (; i < next->level; i++) {
-                *update[i] = next->next[i];
-            }
+    /* Can we contain first by expanding tail of current range by 1? */
+    if (node != &head && node->last == first - 1) {
 
-            delete next;
-        }
+        node->last = last;
+        goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES;
 
-        return;
     }
 
-    /* Current range could not contain call_no, look at next. */
+    /* Current range could not contain first, look at next. */
+
     node = node->next[0];
 
     if (node) {
-        /* Do nothing if call_no is already contained. */
-        if (node->first <= call_no) {
+        /* Do nothing if new range is already entirely contained. */
+        if (node->first <= first && node->last >= last) {
             return;
         }
 
-        /* Can we exand head of range by 1? */
-        if (node->first == call_no + 1) {
-            node->first = call_no;
+        /* If last is already included, we can simply expand
+         * node->first to fully include the range. */
+        if (node->first <= last && node->last >= last) {
+            node->first = first;
             return;
         }
+
+        /* This is our candidate node if first is contained */
+        if (node->first <= first && node->last >= first) {
+            node->last = last;
+            goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES;
+        }
     }
 
-    /* Not possible to expand any existing node, so create new one. */
+    /* Not possible to expand any existing node, so create a new one. */
 
     level = random_level();
 
@@ -156,13 +146,39 @@ CallSet::add(CallNo call_no)
         max_level = level;
     }
 
-    node = new CallRange(call_no, level);
+    node = new CallRange(first, last, level);
 
     /* Perform insertion into all lists. */
     for (i = 0; i < level; i++) {
         node->next[i] = *update[i];
         *update[i] = node;
     }
+
+MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES:
+    next = node->next[0];
+    while (next && next->first <= node->last + 1) {
+        if (next->last > node->last)
+            node->last = next->last;
+
+        /* Delete node 'next' */
+        for (i = 0; i < node->level && i < next->level; i++) {
+            node->next[i] = next->next[i];
+        }
+
+        for (; i < next->level; i++) {
+            *update[i] = next->next[i];
+        }
+
+        delete next;
+
+        next = node->next[0];
+    }
+}
+
+void
+CallSet::add(CallNo call_no)
+{
+    this->add(call_no, call_no);
 }
 
 bool
diff --git a/cli/trim_callset.hpp b/cli/trim_callset.hpp
index 667ec5e..fb2c92a 100644
--- a/cli/trim_callset.hpp
+++ b/cli/trim_callset.hpp
@@ -40,9 +40,6 @@ namespace trim {
  *
  *   Simplifications:
  *
- *	* This supports only the addition of a single call number, not
- *	  the addition of a range.
- *
  *	* There is no support here for the 'step' and 'freq' features
  *	  supported by trace::CallSet.
  *
@@ -76,7 +73,7 @@ public:
     int level;
     CallRange **next;
 
-    CallRange(CallNo call_no, int level);
+    CallRange(CallNo first, CallNo last, int level);
 
     bool contains(CallNo call_no);
 };
@@ -88,6 +85,8 @@ public:
 
     CallSet();
 
+    void add(CallNo first, CallNo last);
+
     void add(CallNo call_no);
 
     bool contains(CallNo call_no);
-- 
2.43.0