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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#pragma once
namespace os {
/**
* A table that contains pointer to T, and allows iterating through them in some order that is
* consistent until elements are added and removed.
*
* Automatically resizes the underlying storage as needed (both growing and shrinking).
*/
template <class T>
class Table {
public:
// Create.
Table() : capacity(0), filled(0), hint(0), data(null) {}
// Destroy.
~Table() {
delete []data;
}
// Add an element and return its current key.
size_t put(T *elem) {
if (filled == capacity)
grow();
while (data[hint]) {
if (++hint == capacity)
hint = 0;
}
filled++;
data[hint] = elem;
return hint;
}
// Remove the element 'id' and return it.
T *remove(size_t id) {
if (id >= capacity)
return null;
T *r = data[id];
data[id] = null;
if (r) {
--filled;
shrink();
}
return r;
}
// Get the element at index 'id'. May be null.
T *operator [] (size_t id) const {
return data[id];
}
// Total number of elements.
size_t size() const {
return capacity;
}
// Number of elements in here.
size_t used() const {
return filled;
}
// Find the first element's index and return it. Returns >= size() if no elements exist.
size_t first() const {
for (size_t i = 0; i < capacity; i++)
if (data[i])
return i;
return capacity;
}
// Find the next element's index and return it. Returns something >= size() if no more elements exist.
size_t next(size_t curr) const {
for (size_t i = curr + 1; i < capacity; i++)
if (data[i])
return i;
return capacity;
}
private:
Table(const Table &);
Table &operator =(const Table &);
// Total capacity.
size_t capacity;
// Number of used entries.
size_t filled;
// Last filled element. The next one is probably empty.
size_t hint;
// The actual data.
T **data;
// Grow to fit at least one more element.
void grow() {
size_t cap = max(capacity * 2, size_t(8));
T **d = new T*[cap];
hint = 0;
for (size_t i = first(); i < capacity; i = next(i))
d[hint++] == data[i];
delete []data;
data = d;
capacity = cap;
}
// Shrink if necessary.
void shrink() {
size_t cap = capacity / 4;
// Too many elements?
if (filled > cap)
return;
T **d = new T*[cap];
hint = 0;
for (size_t i = first(); i < capacity; i = next(i))
d[hint++] = data[i];
delete []data;
data = d;
capacity = cap;
}
};
}
|
