1 /*********************************************************************
3 * Copyright 2012 Intel Corporation
4 * Copyright 2012 VMware, Inc.
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:
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
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
27 *********************************************************************/
29 #ifndef _TRIM_CALLSET_HPP_
30 #define _TRIM_CALLSET_HPP_
34 /* A set of call numbers.
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:
43 * * This supports only the addition of a single call number, not
44 * the addition of a range.
46 * * There is no support here for the 'step' and 'freq' features
47 * supported by trace::CallSet.
51 * * This callset is implemented with a skip list for
52 * (probabilistically) logarithmic lookup times for
53 * out-of-order lookups.
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.
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.
70 typedef unsigned CallNo;
79 CallRange(CallNo call_no, int level);
81 bool contains(CallNo call_no);
91 void add(CallNo call_no);
93 bool contains(CallNo call_no);
96 } /* namespace trim */
98 #endif /* _TRIM_CALLSET_HPP_ */