]> git.cworth.org Git - apitrace/blob - cli/trim_callset.cpp
trim: Use custom skiplist for required list (instead of std::set<unsigned>)
[apitrace] / cli / trim_callset.cpp
1 /*********************************************************************
2  *
3  * Copyright 2006 Keith Packard and Carl Worth
4  * Copyright 2012 Intel Corporation
5  * Copyright 2012 VMware, Inc.
6  * All Rights Reserved.
7  *
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:
15  *
16  * The above copyright notice and this permission notice shall be
17  * included in all copies or substantial portions of the Software.
18  *
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
26  * SOFTWARE.
27  *
28  *********************************************************************/
29
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <limits>
33
34 #include "trim_callset.hpp"
35
36 using namespace trim;
37
38 #define MAX_LEVEL 16
39
40 CallRange::CallRange(CallNo call_no, int level)
41 {
42     first = call_no;
43     last = call_no;
44     this->level = level;
45
46     next = new CallRange*[level];
47 }
48
49 bool
50 CallRange::contains(CallNo call_no)
51 {
52     return (first <= call_no && last >= call_no);
53 }
54
55 CallSet::CallSet(): head(0, MAX_LEVEL)
56 {
57     head.first = std::numeric_limits<CallNo>::max();
58     head.last = std::numeric_limits<CallNo>::min();
59
60     for (int i = 0; i < MAX_LEVEL; i++)
61         head.next[i] = NULL;
62
63     max_level = 0;
64 }
65
66 /*
67  * Generate a random level number, distributed
68  * so that each level is 1/4 as likely as the one before
69  *
70  * Note that level numbers run 1 <= level < MAX_LEVEL
71  */
72 static int
73 random_level (void)
74 {
75     /* tricky bit -- each bit is '1' 75% of the time */
76     long int bits = random() | random();
77     int level = 1;
78
79     while (level < MAX_LEVEL)
80     {
81         if (bits & 1)
82             break;
83         level++;
84         bits >>= 1;
85     }
86
87     return level;
88 }
89
90 void
91 CallSet::add(CallNo call_no)
92 {
93     CallRange **update[MAX_LEVEL];
94     CallRange *node;
95     int i, level;
96
97     /* Find node immediately before insertion point. */
98     node = &head;
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];
102         }
103         update[i] = &node->next[i];
104     }
105
106     /* Can we contain call_no by expanding tail of current range by 1? */
107     if (node != &head && node->last == call_no - 1) {
108
109         CallRange *next = node->next[0];
110
111         node->last = call_no;
112
113         /* Also merge with next node as needed. */
114         if (next && next->first == call_no + 1) {
115             node->last = next->last;
116
117             /* Delete node 'next' */
118             for (i = 0; i < node->level && i < next->level; i++) {
119                 node->next[i] = next->next[i];
120             }
121
122             for (; i < next->level; i++) {
123                 *update[i] = next->next[i];
124             }
125
126             delete next;
127         }
128
129         return;
130     }
131
132     /* Current range could not contain call_no, look at next. */
133     node = node->next[0];
134
135     if (node) {
136         /* Do nothing if call_no is already contained. */
137         if (node->first <= call_no) {
138             return;
139         }
140
141         /* Can we exand head of range by 1? */
142         if (node->first == call_no + 1) {
143             node->first = call_no;
144             return;
145         }
146     }
147
148     /* Not possible to expand any existing node, so create new one. */
149
150     level = random_level();
151
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];
156         max_level = level;
157     }
158
159     node = new CallRange(call_no, level);
160
161     /* Perform insertion into all lists. */
162     for (i = 0; i < level; i++) {
163         node->next[i] = *update[i];
164         *update[i] = node;
165     }
166 }
167
168 bool
169 CallSet::contains(CallNo call_no)
170 {
171     CallRange *node;
172     int i;
173
174     node = &head;
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];
178         }
179     }
180
181     node = node->next[0];
182
183     if (node == NULL)
184         return false;
185
186     return node->contains(call_no);
187 }