From 12b41a836a136c6fa7004c364c9cd2cbcfa9f90d Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Mon, 11 Mar 2013 13:05:52 -0700 Subject: 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). --- cli/CMakeLists.txt | 1 - cli/cli_trim.cpp | 2 +- cli/trace_analyzer.cpp | 2 +- cli/trace_analyzer.hpp | 6 +- cli/trim_callset.cpp | 203 ------------------------------------------------- cli/trim_callset.hpp | 97 ----------------------- 6 files changed, 5 insertions(+), 306 deletions(-) delete mode 100644 cli/trim_callset.cpp delete mode 100644 cli/trim_callset.hpp (limited to 'cli') 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 #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 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 -#include -#include - -#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::max(); - head.last = std::numeric_limits::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 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_ */ -- cgit v1.2.3