1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#include <HtmRange.h>
#include <stdio.h>
#include <string.h>
#define INSIDE 1
#define OUTSIDE -1
#define INTERSECT 0
#define GAP_HISTO_SIZE 10000
extern "C" {
int cc_ID2name(char *name, uint64 id);
}
HtmRange::HtmRange()
{
my_los = new SkipList;
my_his = new SkipList;
}
HtmRange::~HtmRange()
{
my_los->freeRange(-1, KEY_MAX);
my_his->freeRange(-1, KEY_MAX);
delete my_los;
delete my_his;
}
InclusionType HtmRange::tinside(const Key mid) const
{
// clearly out, inside, share a boundary, off by one to some boundary
InclusionType t1, t2;
Key GH = my_his->findMAX(mid);
Key GL = my_los->findMAX(mid);
if (GH < GL)
t1 = InclInside;
else
t1 = InclOutside;
Key SH = my_his->findMIN(mid);
Key SL = my_los->findMIN(mid);
if (SH < SL)
t2 = InclInside;
else
t2 = InclOutside;
if (t1 == t2)
return t1;
if (t1 == InclInside)
return InclHi;
else
return InclLo;
}
void HtmRange::mergeRange(const Key lo, const Key hi)
{
int lo_flag = tinside(lo);
int hi_flag = tinside(hi);
// delete all nodes (key) in his and los where lo < key < hi
my_his->freeRange(lo, hi);
my_los->freeRange(lo, hi);
// add if not inside a pre-existing interval
if (lo_flag == InclHi)
{
}
else if (lo_flag == InclLo || (lo_flag == InclOutside))
{
my_los->insert(lo, 33);
}
if (hi_flag == InclLo)
{
}
else if (hi_flag == InclOutside || hi_flag == InclHi)
{
my_his->insert(hi, 33);
}
}
void HtmRange::reset()
{
my_los->reset();
my_his->reset();
}
int HtmRange::getNext(Key *lo, Key *hi)
{
*lo = my_los->getkey();
if (*lo <= (Key)0)
{
*hi = *lo = (Key)0;
return 0;
}
*hi = my_his->getkey();
my_his->step();
my_los->step();
return 1;
}
|
