KDDockWidgets API Documentation 2.0
Loading...
Searching...
No Matches
genindex_array.h
Go to the documentation of this file.
1/*
2This code has been adapted from MIT licensed code, originally by Jeremy burns and available at
3https://gist.github.com/jaburns/ca72487198832f6203e831133ffdfff4.
4The original license is provided below:
5
6Copyright 2021 Jeremy Burns
7
8Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files
9(the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge,
10publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
11subject to the following conditions:
12
13The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
14
15THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
16OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
17LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
18IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19*/
20
21#pragma once
22
23#include <functional>
24#include <vector>
25#include <cstdint>
26#include <optional>
27#include <cassert>
28#include <limits>
29#include <stdexcept>
30#include <string>
31
32namespace KDBindings {
33
34namespace Private {
35
40
42{
43 struct AllocatorEntry {
44 bool isLive = false;
45 uint32_t generation = 0;
46 };
47
48 std::vector<AllocatorEntry> m_entries;
49 std::vector<uint32_t> m_freeIndices;
50
51public:
53 {
54 if (m_freeIndices.size() > 0) {
55 uint32_t index = m_freeIndices.back();
56 m_freeIndices.pop_back();
57
58 m_entries[index].generation += 1;
59 m_entries[index].isLive = true;
60
61 return { index, m_entries[index].generation };
62 } else {
63 // check that we are still within the bounds of uint32_t
64 if (m_entries.size() + 1 >= std::numeric_limits<uint32_t>::max()) {
65 throw std::length_error(std::string("Maximum number of values inside GenerationalIndexArray reached: ") + std::to_string(m_entries.size()));
66 }
67
68 m_entries.push_back({ true, 0 });
69 return { static_cast<uint32_t>(m_entries.size()) - 1, 0 };
70 }
71 }
72
74 {
75 if (isLive(index)) {
76 m_entries[index.index].isLive = false;
77 m_freeIndices.emplace_back(index.index);
78 return true;
79 }
80
81 return false;
82 }
83
84 bool isLive(GenerationalIndex index) const noexcept
85 {
86 return index.index < m_entries.size() &&
87 m_entries[index.index].generation == index.generation &&
88 m_entries[index.index].isLive;
89 }
90};
91
92// A GenerationalIndexArray stores elements in contiguous memory just like an std::vector
93// and also allows items to be retrieved in constant time through indexed access, but it keeps
94// track of the "version"/generation of values at indices so that it can inform an accessor
95// when the item at the index it is trying to access is no longer the item that it wants.
96template<typename T>
98{
99 struct Entry {
100 uint32_t generation;
101 T value;
102 };
103
104 // TODO: m_entries never shrinks after an entry has been deleted, it might be
105 // a good idea to add a "trim" function at some point if this becomes an issue
106
107 std::vector<std::optional<Entry>> m_entries;
108 GenerationalIndexAllocator m_allocator;
109
110public:
111 // Sets the value at a specific index inside the array
112 void set(const GenerationalIndex index, T &&value)
113 {
114 while (m_entries.size() <= index.index)
115 m_entries.emplace_back(std::nullopt);
116
117#ifndef NDEBUG
119
120 const auto &previousEntry = m_entries[index.index];
121 if (previousEntry)
122 previousGeneration = previousEntry->generation;
123
125#endif
126
127 m_entries[index.index] = std::optional<Entry>{ { index.generation, std::move(value) } };
128 }
129
130 // Insert a value at the first free index and get the index back
132 {
133 const auto index = m_allocator.allocate();
134 set(index, std::move(value));
135 return index;
136 }
137
138 // Erase the value at the specified index and free up the index again
140 {
141 if (m_allocator.deallocate(index))
142 m_entries[index.index] = std::nullopt;
143 }
144
145 // Get a pointer to the value at the specified index
147 {
148 if (index.index >= m_entries.size())
149 return nullptr;
150
151 auto &entry = m_entries[index.index];
152 if (entry && entry->generation == index.generation) {
153 return &entry->value;
154 }
155
156 return nullptr;
157 }
158
159 // Get a const pointer to the value at the specified index
160 const T *get(GenerationalIndex index) const noexcept
161 {
162 return const_cast<const T *>(const_cast<GenerationalIndexArray *>(this)->get(index));
163 }
164
165 // Erase all the values in the array and thus free up all indices too
166 void clear()
167 {
168 const auto numEntries = entriesSize();
169
170 for (auto i = decltype(numEntries){ 0 }; i < numEntries; ++i) {
171 const auto index = indexAtEntry(i);
172
173 if (index != std::nullopt)
174 erase(*index);
175 }
176 }
177
178 // The number entries currently in the array, not all necessarily correspond to valid indices,
179 // use "indexAtEntry" to translate from an entry index to a optional GenerationalIndex
181 {
182 // this cast is safe because the allocator checks that we never exceed the capacity of uint32_t
183 return static_cast<uint32_t>(m_entries.size());
184 }
185
186 // Convert an entry index into a GenerationalIndex, if possible otherwise returns nullopt
187 std::optional<GenerationalIndex> indexAtEntry(uint32_t entryIndex) const
188 {
189 if (entryIndex >= entriesSize())
190 return std::nullopt;
191
192 const auto &entry = m_entries[entryIndex];
193 if (!entry)
194 return std::nullopt;
195
197
198 if (m_allocator.isLive(index))
199 return index;
200
201 return std::nullopt;
202 }
203};
204
205} //namespace Private
206
207} // namespace KDBindings
bool isLive(GenerationalIndex index) const noexcept
std::optional< GenerationalIndex > indexAtEntry(uint32_t entryIndex) const
const T * get(GenerationalIndex index) const noexcept
void set(const GenerationalIndex index, T &&value)
typename operator_node_result< Operator, Ts... >::type operator_node_result_t
Definition make_node.h:57
The main namespace of the KDBindings library.
Definition binding.h:21

© Klarälvdalens Datakonsult AB (KDAB)
"The Qt, C++ and OpenGL Experts"
https://www.kdab.com/
KDDockWidgets
Advanced Dock Widget Framework for Qt
https://www.kdab.com/development-resources/qt-tools/kddockwidgets/
Generated by doxygen 1.9.8