1 /*********************************************************************
3 * Copyright 2006 Keith Packard and Carl Worth
4 * Copyright 2012 Intel Corporation
5 * Copyright 2012 VMware, Inc.
8 * Permission is hereby granted, free of charge, to any person
9 * obtaining a copy of this software and associated documentation
10 * files (the "Software"), to deal in the Software without
11 * restriction, including without limitation the rights to use, copy,
12 * modify, merge, publish, distribute, sublicense, and/or sell copies
13 * of the Software, and to permit persons to whom the Software is
14 * furnished to do so, subject to the following conditions:
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
23 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
24 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
25 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28 *********************************************************************/
35 #include "trace_fast_callset.hpp"
37 using namespace trace;
41 FastCallRange::FastCallRange(CallNo first, CallNo last, int level)
47 next = new FastCallRange*[level];
51 FastCallRange::contains(CallNo call_no) const
53 return (first <= call_no && last >= call_no);
57 FastCallSet::empty(void) const
59 return max_level == 0;
62 FastCallSet::FastCallSet(): head(0, 0, MAX_LEVEL)
64 head.first = std::numeric_limits<CallNo>::max();
65 head.last = std::numeric_limits<CallNo>::min();
67 for (int i = 0; i < MAX_LEVEL; i++)
74 * Generate a random level number, distributed
75 * so that each level is 1/4 as likely as the one before
77 * Note that level numbers run 1 <= level < MAX_LEVEL
82 /* tricky bit -- each bit is '1' 75% of the time */
83 long int bits = os::random() | os::random();
86 while (level < MAX_LEVEL)
98 FastCallSet::add(CallNo first, CallNo last)
100 FastCallRange **update[MAX_LEVEL];
101 FastCallRange *node, *next;
104 /* Find node immediately before insertion point. */
106 for (i = max_level - 1; i >= 0; i--) {
107 while (node->next[i] && first > node->next[i]->last) {
108 node = node->next[i];
110 update[i] = &node->next[i];
113 /* Can we contain first by expanding tail of current range by 1? */
114 if (node != &head && node->last == first - 1) {
117 goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES;
121 /* Current range could not contain first, look at next. */
122 node = node->next[0];
125 /* Do nothing if new range is already entirely contained. */
126 if (node->first <= first && node->last >= last) {
130 /* If last is already included, we can simply expand
131 * node->first to fully include the range. */
132 if (node->first <= last && node->last >= last) {
137 /* This is our candidate node if first is contained */
138 if (node->first <= first && node->last >= first) {
140 goto MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES;
144 /* Not possible to expand any existing node, so create a new one. */
146 level = random_level();
148 /* Handle first node of this level. */
149 if (level > max_level) {
150 level = max_level + 1;
151 update[max_level] = &head.next[max_level];
155 node = new FastCallRange(first, last, level);
157 /* Perform insertion into all lists. */
158 for (i = 0; i < level; i++) {
159 node->next[i] = *update[i];
163 MERGE_NODE_WITH_SUBSEQUENT_COVERED_NODES:
164 next = node->next[0];
165 while (next && next->first <= node->last + 1) {
166 if (next->last > node->last)
167 node->last = next->last;
169 /* Delete node 'next' */
170 for (i = 0; i < node->level && i < next->level; i++) {
171 node->next[i] = next->next[i];
174 for (; i < next->level; i++) {
175 *update[i] = next->next[i];
180 next = node->next[0];
185 FastCallSet::add(CallNo call_no)
187 this->add(call_no, call_no);
191 FastCallSet::contains(CallNo call_no) const
193 const FastCallRange *node;
197 for (i = max_level - 1; i >= 0; i--) {
198 while (node->next[i] && call_no > node->next[i]->last) {
199 node = node->next[i];
203 node = node->next[0];
208 return node->contains(call_no);