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
|
/*
* This program 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 2
* of the License, or (at your option) any later version.
*
* This program 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 this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#pragma once
/** \file
* \ingroup bli
*
* This file contains slot types that are supposed to be used with blender::VectorSet.
*
* Every slot type has to be able to hold an integer index and state information.
* A vector set slot has three possible states: empty, occupied and removed.
*
* A vector slot type has to implement a couple of methods that are explained in
* SimpleVectorSetSlot.
* A vector slot type is assumed to be trivially destructible, when it is in empty or removed
* state.
*
* Possible Improvements:
* - Implement a slot type that stores the hash.
* - Implement a slot type that stores the key. That means that the key would be stored in two
* places: the key vector and the slot itself. Maybe storing the key in the slot as well, can
* result in better performance, due to better cache utilization.
*/
#include "BLI_sys_types.h"
namespace blender {
/**
* The simplest possible vector set slot. It stores the index and state in a signed integer. If the
* value is negative, it represents empty or occupied state. Otherwise it represents the index.
*/
template<typename Key> class SimpleVectorSetSlot {
private:
#define s_is_empty -1
#define s_is_removed -2
/**
* After the default constructor has run, the slot has to be in the empty state.
*/
int64_t state_ = s_is_empty;
public:
/**
* Return true if this slot contains an index to a key.
*/
bool is_occupied() const
{
return state_ >= 0;
}
/**
* Return true if the slot is empty, i.e. it does not contain an index.
*/
bool is_empty() const
{
return state_ == s_is_empty;
}
/**
* Return the stored index. It is assumed that the slot is occupied.
*/
int64_t index() const
{
BLI_assert(this->is_occupied());
return state_;
}
/**
* Return true if the slot contains the given key, i.e. its index points to a key that compares
* equal to it. The hash can be used by other implementations to determine inequality faster.
*/
template<typename ForwardKey, typename IsEqual>
bool contains(const ForwardKey &key,
const IsEqual &is_equal,
uint64_t UNUSED(hash),
const Key *keys) const
{
if (state_ >= 0) {
return is_equal(key, keys[state_]);
}
return false;
}
/**
* Change the state of this slot from empty/removed to occupied. The hash can be used by other
* slot implementations.
*/
void occupy(int64_t index, uint64_t UNUSED(hash))
{
BLI_assert(!this->is_occupied());
state_ = index;
}
/**
* The key has changed its position in the vector, so the index has to be updated. This method
* can assume that the slot is currently occupied.
*/
void update_index(int64_t index)
{
BLI_assert(this->is_occupied());
state_ = index;
}
/**
* Change the state of this slot from occupied to removed.
*/
void remove()
{
BLI_assert(this->is_occupied());
state_ = s_is_removed;
}
/**
* Return true if this slot is currently occupied and its corresponding key has the given index.
*/
bool has_index(int64_t index) const
{
return state_ == index;
}
/**
* Return the hash of the currently stored key. In this simple set slot implementation, we just
* compute the hash here. Other implementations might store the hash in the slot instead.
*/
template<typename Hash> uint64_t get_hash(const Key &key, const Hash &hash) const
{
BLI_assert(this->is_occupied());
return hash(key);
}
#undef s_is_empty
#undef s_is_removed
};
template<typename Key> struct DefaultVectorSetSlot;
template<typename Key> struct DefaultVectorSetSlot {
using type = SimpleVectorSetSlot<Key>;
};
} // namespace blender
|
