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
103
104
|
#include "stdafx.h"
#include "ObjMap.h"
namespace storm {
RawObjMap::RawObjMap(Gc &gc) : gc(gc), root(null), data(null), capacity(0), filled(0) {}
RawObjMap::~RawObjMap() {
clear();
}
void RawObjMap::clear() {
Gc::destroyRoot(root);
root = null;
delete []data;
data = null;
capacity = 0;
filled = 0;
}
void RawObjMap::put(void *from, void *to) {
if (capacity == filled)
grow();
Item i = { from, to };
data[filled++] = i;
}
void RawObjMap::grow() {
nat nCap = capacity * 2;
if (capacity == 0)
nCap = 8;
Item *nData = new Item[nCap];
memset(nData, 0, sizeof(Item)*nCap);
Gc::Root *nRoot = gc.createRoot(nData, nCap*2);
if (data) {
for (nat i = 0; i < filled; i++)
nData[i] = data[i];
gc.destroyRoot(root);
delete []data;
}
data = nData;
capacity = nCap;
root = nRoot;
}
struct RawObjMap::Predicate {
bool operator()(const Item &a, const Item &b) const {
return size_t(a.from) < size_t(b.from);
}
bool operator()(const Item &a, void *b) const {
return size_t(a.from) < size_t(b);
}
};
void RawObjMap::sort() {
if (data) {
std::sort(data, data + filled, Predicate());
// Handle transitive dependencies. O(n log n) assuming we don't have very long chains
// (which are not very common).
for (nat i = 0; i < filled; i++) {
void *p = data[i].to;
while (void *next = find(p))
p = next;
data[i].to = p;
}
}
}
void *RawObjMap::find(void *obj) {
Item *end = data + filled;
Item *found = std::lower_bound(data, end, obj, Predicate());
if (found == end)
return null;
if (found->from == obj)
return found->to;
else
return null;
}
RawObjMap::Item RawObjMap::findBefore(void *obj) {
Item *end = data + filled;
Item *found = std::lower_bound(data, end, obj, Predicate());
// Exact match?
if (found != end && found->from == obj)
return *found;
// Otherwise, look at the previous element if there is one:
if (found != data)
return *(found - 1);
Item empty = { null, null };
return empty;
}
}
|
