git.cworth.org Git - apitrace/blob - cli/trim_callset.hpp

   1 /*********************************************************************
   2  *
   3  * Copyright 2012 Intel Corporation
   4  * Copyright 2012 VMware, Inc.
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person
   8  * obtaining a copy of this software and associated documentation
   9  * files (the "Software"), to deal in the Software without
  10  * restriction, including without limitation the rights to use, copy,
  11  * modify, merge, publish, distribute, sublicense, and/or sell copies
  12  * of the Software, and to permit persons to whom the Software is
  13  * furnished to do so, subject to the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be
  16  * included in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  22  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  23  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  25  * SOFTWARE.
  26  *
  27  *********************************************************************/
  28
  29 #ifndef _TRIM_CALLSET_HPP_
  30 #define _TRIM_CALLSET_HPP_
  31
  32 namespace trim {
  33
  34 /* A set of call numbers.
  35  *
  36  * This is designed as a more efficient replacement for
  37  * std::set<unsigned> which is used heavily within the trim code's
  38  * TraceAnalyzer. This is quite similar to the trace::CallSet with the
  39  * following differences:
  40  *
  41  *   Simplifications:
  42  *
  43  *      * This supports only the addition of a single call number, not
  44  *        the addition of a range.
  45  *
  46  *      * There is no support here for the 'step' and 'freq' features
  47  *        supported by trace::CallSet.
  48  *
  49  *   Sophistications:
  50  *
  51  *      * This callset is implemented with a skip list for
  52  *        (probabilistically) logarithmic lookup times for
  53  *        out-of-order lookups.
  54  *
  55  *      * This callset optimizes the addition of new calls which are
  56  *        within or adjacent to existing ranges, (by either doing
  57  *        nothing, expanding the limits of an existing range, or also
  58  *        merging two ranges). This keeps the length of the list down
  59  *        when succesively adding individual calls that could be
  60  *        efficiently expressed with a range.
  61  *
  62  * It would not be impossible to extend this code to support the
  63  * missing features of trace::CallSet, (though the 'step' and 'freq'
  64  * features would prevent some range-extending and merging
  65  * optimizations in some cases). Currently, trace::CallSet is not used
  66  * in any performance-critical areas, so it may not be important to
  67  * provide the performance imrpovements to it.
  68  */
  69
  70 typedef unsigned CallNo;
  71
  72 class CallRange {
  73 public:
  74     CallNo first;
  75     CallNo last;
  76     int level;
  77     CallRange **next;
  78
  79     CallRange(CallNo call_no, int level);
  80
  81     bool contains(CallNo call_no);
  82 };
  83
  84 class CallSet {
  85 public:
  86     CallRange head;
  87     int max_level;
  88
  89     CallSet();
  90
  91     void add(CallNo call_no);
  92
  93     bool contains(CallNo call_no);
  94 };
  95
  96 } /* namespace trim */
  97
  98 #endif /* _TRIM_CALLSET_HPP_ */