| /********************************************************************* |
| * |
| * 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 _TRACE_FAST_CALLSET_HPP_ |
| #define _TRACE_FAST_CALLSET_HPP_ |
| |
| #include "trace_model.hpp" |
| |
| namespace trace { |
| |
| /* A set of call numbers. |
| * |
| * This was originally designed as a more efficient replacement for |
| * std::set<unsigned> which was 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 or more ranges). |
| * |
| * 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). |
| */ |
| |
| class FastCallRangePtr; |
| |
| class FastCallRange { |
| public: |
| CallNo first; |
| CallNo last; |
| int level; |
| std::vector<FastCallRangePtr> next; |
| |
| // (NOTE: Initalize ref_counter to 0 in all constructors) |
| FastCallRange(CallNo first, CallNo last, int level); |
| |
| bool contains(CallNo call_no) const; |
| |
| private: |
| friend class FastCallRangePtr; |
| size_t ref_counter; |
| // ref_counter must be initialized to 0 by all constructors |
| // ref_counter is the number of FastCallRangePtr objects that point at this |
| }; |
| |
| class FastCallRangePtr { |
| public: |
| FastCallRange* operator-> () { return this->ptr; } |
| FastCallRange& operator * () { return *this->ptr; } |
| FastCallRange* operator ()() { return this->ptr; } // get pointer |
| |
| |
| FastCallRangePtr () : ptr(0) {} |
| FastCallRangePtr(FastCallRange* _ptr) : ptr(_ptr) |
| { if (this->ptr) ++this->ptr->ref_counter; } |
| |
| ~FastCallRangePtr() { if (this->ptr) |
| if (--this->ptr->ref_counter == 0) |
| delete this->ptr; |
| } |
| |
| FastCallRangePtr(FastCallRangePtr const& _ptr) : ptr(_ptr.ptr) |
| { if (this->ptr) ++this->ptr->ref_counter; } |
| |
| FastCallRangePtr& operator= (FastCallRangePtr const& new_ptr) |
| { // DO NOT CHANGE THE ORDER OF THESE STATEMENTS! |
| // (This order properly handles self-assignment) |
| // (This order also properly handles recursion, e.g., |
| // if a FastCallRange contains FastCallRangePtrs) |
| FastCallRange* const old_ptr = this->ptr; |
| this->ptr = new_ptr.ptr; |
| if (this->ptr) |
| ++this->ptr->ref_counter; |
| if (old_ptr) { |
| if (--old_ptr->ref_counter == 0) |
| delete old_ptr; |
| } |
| return *this; |
| } |
| private: |
| FastCallRange* ptr; |
| }; |
| |
| class FastCallSet { |
| public: |
| FastCallRange head; |
| int max_level; |
| |
| FastCallSet(); |
| |
| bool empty(void) const; |
| |
| void add(CallNo first, CallNo last); |
| |
| void add(CallNo call_no); |
| |
| bool contains(CallNo call_no) const; |
| }; |
| |
| } /* namespace trace */ |
| |
| #endif /* _TRACE_FAST_CALLSET_HPP_ */ |