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 *********************************************************************/
34 #include "trim_callset.hpp"
40 CallRange::CallRange(CallNo call_no, int level)
46 next = new CallRange*[level];
50 CallRange::contains(CallNo call_no)
52 return (first <= call_no && last >= call_no);
55 CallSet::CallSet(): head(0, MAX_LEVEL)
57 head.first = std::numeric_limits<CallNo>::max();
58 head.last = std::numeric_limits<CallNo>::min();
60 for (int i = 0; i < MAX_LEVEL; i++)
67 * Generate a random level number, distributed
68 * so that each level is 1/4 as likely as the one before
70 * Note that level numbers run 1 <= level < MAX_LEVEL
75 /* tricky bit -- each bit is '1' 75% of the time */
76 long int bits = random() | random();
79 while (level < MAX_LEVEL)
91 CallSet::add(CallNo call_no)
93 CallRange **update[MAX_LEVEL];
97 /* Find node immediately before insertion point. */
99 for (i = max_level - 1; i >= 0; i--) {
100 while (node->next[i] && call_no > node->next[i]->last) {
101 node = node->next[i];
103 update[i] = &node->next[i];
106 /* Can we contain call_no by expanding tail of current range by 1? */
107 if (node != &head && node->last == call_no - 1) {
109 CallRange *next = node->next[0];
111 node->last = call_no;
113 /* Also merge with next node as needed. */
114 if (next && next->first == call_no + 1) {
115 node->last = next->last;
117 /* Delete node 'next' */
118 for (i = 0; i < node->level && i < next->level; i++) {
119 node->next[i] = next->next[i];
122 for (; i < next->level; i++) {
123 *update[i] = next->next[i];
132 /* Current range could not contain call_no, look at next. */
133 node = node->next[0];
136 /* Do nothing if call_no is already contained. */
137 if (node->first <= call_no) {
141 /* Can we exand head of range by 1? */
142 if (node->first == call_no + 1) {
143 node->first = call_no;
148 /* Not possible to expand any existing node, so create new one. */
150 level = random_level();
152 /* Handle first node of this level. */
153 if (level > max_level) {
154 level = max_level + 1;
155 update[max_level] = &head.next[max_level];
159 node = new CallRange(call_no, level);
161 /* Perform insertion into all lists. */
162 for (i = 0; i < level; i++) {
163 node->next[i] = *update[i];
169 CallSet::contains(CallNo call_no)
175 for (i = max_level - 1; i >= 0; i--) {
176 while (node->next[i] && call_no > node->next[i]->last) {
177 node = node->next[i];
181 node = node->next[0];
186 return node->contains(call_no);