/
VectorHeap.h
105 lines (85 loc) · 2.62 KB
/
VectorHeap.h
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
// @Begin License@
// This file is part of Coldest.
//
// Coldest is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Coldest is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Coldest. If not, see <http://www.gnu.org/licenses/>.
//
// Copyright 2008-2012 Ben Nemec
// @End License@
#ifndef __VECTORHEAP_H
#define __VECTORHEAP_H
#include <vector>
using std::vector;
template <class T> class VectorHeapPointer;
/**
@author Ben Nemec <cybertron@nemebean.com>
This class is designed to allow for reference counted pointer semantics where
the objects pointed to are actually contained in a vector for better cache
coherency.
Note that items are never actually removed from the vector - when their refcount
becomes 0 then that slot becomes available for reuse.
*/
template <class T>
class VectorHeap
{
friend class VectorHeapPointer<T>;
public:
VectorHeap(size_t reserve = 0);
~VectorHeap();
VectorHeapPointer<T> insert(T&);
VectorHeapPointer<T> insert();
private:
vector<T> v;
vector<size_t> refcount;
bool valid;
};
#include "VectorHeapPointer.h"
template <class T>
VectorHeap<T>::VectorHeap(size_t reserve) : valid(true)
{
if (reserve)
v.reserve(reserve);
}
// This only exists as a sanity check for the pointers pointing into us.
// We can check that valid is true before pointer operations and that way hopefully
// if this object was destroyed with pointers still pointing at it, we'll catch it.
// Theoretically we could be destroyed and overwritten with something that puts 0
// at the valid position, so it's not perfect, but I figure it's better than nothing
template <class T>
VectorHeap<T>::~VectorHeap()
{
valid = false;
}
template <class T>
VectorHeapPointer<T> VectorHeap<T>::insert(T& object)
{
size_t rsize = refcount.size();
for (size_t i = 0; i < rsize; ++i)
{
if (refcount[i] == 0)
{
v[i] = object;
return VectorHeapPointer<T>(this, i);
}
}
v.push_back(object);
refcount.push_back(0);
return VectorHeapPointer<T>(this, v.size() - 1);
}
template <class T>
VectorHeapPointer<T> VectorHeap<T>::insert()
{
T newobj;
return insert(newobj);
}
#endif