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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
/* SPDX-License-Identifier: GPL-2.0-or-later */
/** \file
* \ingroup bke
*
* Tree hash for the outliner space.
*/
#include <cstdlib>
#include <cstring>
#include "BLI_mempool.h"
#include "BLI_utildefines.h"
#include "BLI_vector.hh"
#include "DNA_outliner_types.h"
#include "BKE_outliner_treehash.hh"
#include "MEM_guardedalloc.h"
namespace blender::bke::outliner::treehash {
/* -------------------------------------------------------------------- */
/** \name #TseGroup
* \{ */
class TseGroup {
public:
blender::Vector<TreeStoreElem *> elems;
/* Index of last used #TreeStoreElem item, to speed up search for another one. */
int lastused = 0;
/* Counter used to reduce the amount of 'rests' of `lastused` index, otherwise search for unused
* item is exponential and becomes critically slow when there are a lot of items in the group. */
int lastused_reset_count = -1;
void add_element(TreeStoreElem &elem);
void remove_element(TreeStoreElem &elem);
};
/* Only allow reset of #TseGroup.lastused counter to 0 once every 1k search. */
#define TSEGROUP_LASTUSED_RESET_VALUE 10000
void TseGroup::add_element(TreeStoreElem &elem)
{
const int64_t idx = elems.append_and_get_index(&elem);
lastused = idx;
}
void TseGroup::remove_element(TreeStoreElem &elem)
{
const int64_t idx = elems.first_index_of(&elem);
elems.remove(idx);
}
/** \} */
/* -------------------------------------------------------------------- */
/** \name #TreeStoreElemKey
* \{ */
TreeStoreElemKey::TreeStoreElemKey(const TreeStoreElem &elem)
: id(elem.id), type(elem.type), nr(elem.nr)
{
}
TreeStoreElemKey::TreeStoreElemKey(ID *id, short type, short nr) : id(id), type(type), nr(nr)
{
}
uint64_t TreeStoreElemKey::hash() const
{
return get_default_hash_3(id, type, nr);
}
bool operator==(const TreeStoreElemKey &a, const TreeStoreElemKey &b)
{
return (a.id == b.id) && (a.type == b.type) && (a.nr == b.nr);
}
/** \} */
/* -------------------------------------------------------------------- */
/** \name #TreeHash
* \{ */
TreeHash::~TreeHash() = default;
std::unique_ptr<TreeHash> TreeHash::create_from_treestore(BLI_mempool &treestore)
{
/* Can't use `make_unique()` here because of private constructor. */
std::unique_ptr<TreeHash> tree_hash{new TreeHash()};
tree_hash->fill_treehash(treestore);
return tree_hash;
}
void TreeHash::fill_treehash(BLI_mempool &treestore)
{
TreeStoreElem *tselem;
BLI_mempool_iter iter;
BLI_mempool_iternew(&treestore, &iter);
while ((tselem = static_cast<TreeStoreElem *>(BLI_mempool_iterstep(&iter)))) {
add_element(*tselem);
}
}
void TreeHash::clear_used()
{
for (auto &group : elem_groups_.values()) {
group->lastused = 0;
group->lastused_reset_count = 0;
}
}
void TreeHash::rebuild_from_treestore(BLI_mempool &treestore)
{
elem_groups_.clear();
fill_treehash(treestore);
}
void TreeHash::add_element(TreeStoreElem &elem)
{
std::unique_ptr<TseGroup> &group = elem_groups_.lookup_or_add_cb(
TreeStoreElemKey(elem), []() { return std::make_unique<TseGroup>(); });
group->add_element(elem);
}
void TreeHash::remove_element(TreeStoreElem &elem)
{
TseGroup *group = lookup_group(elem);
BLI_assert(group != nullptr);
if (group->elems.size() <= 1) {
/* One element -> remove group completely. */
elem_groups_.remove(TreeStoreElemKey(elem));
}
else {
group->remove_element(elem);
}
}
TseGroup *TreeHash::lookup_group(const TreeStoreElemKey &key) const
{
const auto *group = elem_groups_.lookup_ptr(key);
if (group) {
return group->get();
}
return nullptr;
}
TseGroup *TreeHash::lookup_group(const TreeStoreElem &key_elem) const
{
return lookup_group(TreeStoreElemKey(key_elem));
}
TseGroup *TreeHash::lookup_group(const short type, const short nr, ID *id) const
{
TreeStoreElemKey key(id, type, nr);
if (type == TSE_SOME_ID) {
key.nr = 0; /* we're picky! :) */
}
return lookup_group(key);
}
TreeStoreElem *TreeHash::lookup_unused(const short type, const short nr, ID *id) const
{
TseGroup *group = lookup_group(type, nr, id);
if (!group) {
return nullptr;
}
/* Find unused element, with optimization to start from previously
* found element assuming we do repeated lookups. */
const int size = group->elems.size();
int offset = group->lastused;
for (int i = 0; i < size; i++, offset++) {
/* Once at the end of the array of items, in most cases it just means that all items are
* used, so only check the whole array once every TSEGROUP_LASTUSED_RESET_VALUE times. */
if (offset >= size) {
if (LIKELY(group->lastused_reset_count <= TSEGROUP_LASTUSED_RESET_VALUE)) {
group->lastused_reset_count++;
group->lastused = group->elems.size() - 1;
break;
}
group->lastused_reset_count = 0;
offset = 0;
}
if (!group->elems[offset]->used) {
group->lastused = offset;
return group->elems[offset];
}
}
return nullptr;
}
TreeStoreElem *TreeHash::lookup_any(const short type, const short nr, ID *id) const
{
const TseGroup *group = lookup_group(type, nr, id);
return group ? group->elems[0] : nullptr;
}
/** \} */
} // namespace blender::bke::outliner::treehash
|
