Rename trim::CallSet to trace::FastCallSet

This is in preparation for being able to use this code to optimize the common
cases in trace::CallSet, (callsets without step or freq).

6 files changed, 5 insertions, 306 deletions

diff --git a/cli/CMakeLists.txt b/cli/CMakeLists.txt
index 939019b3..713222fc 100644
--- a/cli/CMakeLists.txt
+++ b/cli/CMakeLists.txt
@@ -24,7 +24,6 @@ add_executable (apitrace
     cli_trim.cpp
     cli_resources.cpp
     trace_analyzer.cpp
-    trim_callset.cpp
 )
 
 target_link_libraries (apitrace
diff --git a/cli/cli_trim.cpp b/cli/cli_trim.cpp
index 6694737a..342e66b0 100644
--- a/cli/cli_trim.cpp
+++ b/cli/cli_trim.cpp
@@ -203,7 +203,7 @@ trim_trace(const char *filename, struct trim_options *options)
     trace::ParseBookmark beginning;
     trace::Parser p;
     TraceAnalyzer analyzer(options->trim_flags);
-    trim::CallSet *required;
+    trace::FastCallSet *required;
     unsigned frame;
     int call_range_first, call_range_last;
 
diff --git a/cli/trace_analyzer.cpp b/cli/trace_analyzer.cpp
index febeadb1..374e6cef 100644
--- a/cli/trace_analyzer.cpp
+++ b/cli/trace_analyzer.cpp
@@ -760,7 +760,7 @@ TraceAnalyzer::require(trace::Call *call)
 /* Return a set of all the required calls, (both those calls added
  * explicitly with require() and those implicitly depended
  * upon. */
-trim::CallSet *
+trace::FastCallSet *
 TraceAnalyzer::get_required(void)
 {
     return &required;
diff --git a/cli/trace_analyzer.hpp b/cli/trace_analyzer.hpp
index 3c1d3f7d..c344fb6a 100644
--- a/cli/trace_analyzer.hpp
+++ b/cli/trace_analyzer.hpp
@@ -29,7 +29,7 @@
 #include <GL/glext.h>
 
 #include "trace_callset.hpp"
-#include "trim_callset.hpp"
+#include "trace_fast_callset.hpp"
 #include "trace_parser.hpp"
 
 typedef unsigned TrimFlags;
@@ -59,7 +59,7 @@ private:
 
     std::map<GLenum, unsigned> texture_map;
 
-    trim::CallSet required;
+    trace::FastCallSet required;
 
     bool transformFeedbackActive;
     bool framebufferObjectActive;
@@ -110,5 +110,5 @@ public:
     /* Return a set of all the required calls, (both those calls added
      * explicitly with require() and those implicitly depended
      * upon. */
-    trim::CallSet *get_required(void);
+    trace::FastCallSet *get_required(void);
 };
diff --git a/cli/trim_callset.cpp b/cli/trim_callset.cpp
deleted file mode 100644
index 69ed8180..00000000
--- a/cli/trim_callset.cpp
+++ /dev/null
@@ -1,203 +0,0 @@
-/*********************************************************************
- *
- * Copyright 2006 Keith Packard and Carl Worth
- * Copyright 2012 Intel Corporation
- * Copyright 2012 VMware, Inc.
- * All Rights Reserved.
- *
- * Permission is hereby granted, free of charge, to any person
- * obtaining a copy of this software and associated documentation
- * files (the "Software"), to deal in the Software without
- * restriction, including without limitation the rights to use, copy,
- * modify, merge, publish, distribute, sublicense, and/or sell copies
- * of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be
- * included in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
- * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
- * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
- * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- *
- *********************************************************************/
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <limits>
-
-#include "trim_callset.hpp"
-
-using namespace trim;
-
-#define MAX_LEVEL 16
-
-CallRange::CallRange(CallNo first, CallNo last, int level)
-{
-    this->first = first;
-    this->last = last;
-    this->level = level;
-
-    next = new CallRange*[level];
-}
-
-bool
-CallRange::contains(CallNo call_no)
-{
-    return (first <= call_no && last >= call_no);
-}
-
-CallSet::CallSet(): head(0, 0, MAX_LEVEL)
-{
-    head.first = std::numeric_limits<CallNo>::max();
-    head.last = std::numeric_limits<CallNo>::min();
-
-    for (int i = 0; i < MAX_LEVEL; i++)
-        head.next[i] = NULL;
-
-    max_level = 0;
-}
-
-/*
- * Generate a random level number, distributed
- * so that each level is 1/4 as likely as the one before
- *
- * Note that level numbers run 1 <= level < MAX_LEVEL
- */
-static int
-random_level (void)
-{
-    /* tricky bit -- each bit is '1' 75% of the time */
-    long int bits = random() | random();
-    int	level = 1;
-
-    while (level < MAX_LEVEL)
-    {
-	if (bits & 1)
-	    break;
-        level++;
-	bits >>= 1;
-    }
-
-    return level;
-}
-
-void
-CallSet::add(CallNo first, CallNo last)
-{
-    CallRange **update[MAX_LEVEL];
-    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] && first > node->next[i]->last) {
-            node = node->next[i];
-        }
-        update[i] = &node->next[i];
-    }
-
-    /* Can we contain first by expanding tail of current range by 1? */
-    if (node != &head && node->last == first - 1) {
-
-        node->last = last;
-        goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES;
-
-    }
-
-    /* Current range could not contain first, look at next. */
-
-    node = node->next[0];
-
-    if (node) {
-        /* Do nothing if new range is already entirely contained. */
-        if (node->first <= first && node->last >= last) {
-            return;
-        }
-
-        /* 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 a new one. */
-
-    level = random_level();
-
-    /* Handle first node of this level. */
-    if (level > max_level) {
-        level = max_level + 1;
-        update[max_level] = &head.next[max_level];
-        max_level = 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
-CallSet::contains(CallNo call_no)
-{
-    CallRange *node;
-    int i;
-
-    node = &head;
-    for (i = max_level - 1; i >= 0; i--) {
-        while (node->next[i] && call_no > node->next[i]->last) {
-            node = node->next[i];
-        }
-    }
-
-    node = node->next[0];
-
-    if (node == NULL)
-        return false;
-
-    return node->contains(call_no);
-}
diff --git a/cli/trim_callset.hpp b/cli/trim_callset.hpp
deleted file mode 100644
index fb2c92a4..00000000
--- a/cli/trim_callset.hpp
+++ /dev/null
@@ -1,97 +0,0 @@
-/*********************************************************************
- *
- * Copyright 2012 Intel Corporation
- * Copyright 2012 VMware, Inc.
- * All Rights Reserved.
- *
- * Permission is hereby granted, free of charge, to any person
- * obtaining a copy of this software and associated documentation
- * files (the "Software"), to deal in the Software without
- * restriction, including without limitation the rights to use, copy,
- * modify, merge, publish, distribute, sublicense, and/or sell copies
- * of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be
- * included in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
- * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
- * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
- * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- *
- *********************************************************************/
-
-#ifndef _TRIM_CALLSET_HPP_
-#define _TRIM_CALLSET_HPP_
-
-namespace trim {
-
-/* A set of call numbers.
- *
- * This is designed as a more efficient replacement for
- * std::set<unsigned> which is used heavily within the trim code's
- * TraceAnalyzer. This is quite similar to the trace::CallSet with the
- * following differences:
- *
- *   Simplifications:
- *
- *	* There is no support here for the 'step' and 'freq' features
- *	  supported by trace::CallSet.
- *
- *   Sophistications:
- *
- *	* This callset is implemented with a skip list for
- *	  (probabilistically) logarithmic lookup times for
- *	  out-of-order lookups.
- *
- *	* This callset optimizes the addition of new calls which are
- *        within or adjacent to existing ranges, (by either doing
- *        nothing, expanding the limits of an existing range, or also
- *        merging two ranges). This keeps the length of the list down
- *        when succesively adding individual calls that could be
- *        efficiently expressed with a range.
- *
- * It would not be impossible to extend this code to support the
- * missing features of trace::CallSet, (though the 'step' and 'freq'
- * features would prevent some range-extending and merging
- * optimizations in some cases). Currently, trace::CallSet is not used
- * in any performance-critical areas, so it may not be important to
- * provide the performance imrpovements to it.
- */
-
-typedef unsigned CallNo;
-
-class CallRange {
-public:
-    CallNo first;
-    CallNo last;
-    int level;
-    CallRange **next;
-
-    CallRange(CallNo first, CallNo last, int level);
-
-    bool contains(CallNo call_no);
-};
-
-class CallSet {
-public:
-    CallRange head;
-    int max_level;
-
-    CallSet();
-
-    void add(CallNo first, CallNo last);
-
-    void add(CallNo call_no);
-
-    bool contains(CallNo call_no);
-};
-
-} /* namespace trim */
-
-#endif /* _TRIM_CALLSET_HPP_ */