Panda3D
Loading...
Searching...
No Matches
pointerSlotStorage.h
1/**
2 *
3 * RenderPipeline
4 *
5 * Copyright (c) 2014-2016 tobspr <tobias.springer1@gmail.com>
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 * THE SOFTWARE.
24 *
25 */
26
27#ifndef POINTERSLOTSTORAGE_H
28#define POINTERSLOTSTORAGE_H
29
30
31#ifdef CPPPARSER
32
33// Dummy implementation for interrogate
34template <typename T, int SIZE>
35class PointerSlotStorage {};
36
37#else // CPPPARSER
38
39
40#include "pandabase.h"
41
42// Apple has an outdated libstdc++, so pull the class from TR1.
43#if defined(__GLIBCXX__) && __GLIBCXX__ <= 20070719
44#include <tr1/array>
45using std::tr1::array;
46#else
47#include <array>
48using std::array;
49#endif
50
51/**
52 * @brief Class to keep a list of pointers and nullpointers.
53 * @details This class stores a fixed size list of pointers, whereas pointers
54 * may be a nullptr as well. It provides functionality to find free slots,
55 * and also to find free consecutive slots, as well as taking care of reserving slots.
56 *
57 * @tparam T* Pointer-Type
58 * @tparam SIZE Size of the storage
59 */
60template <typename T, int SIZE>
62public:
63 /**
64 * @brief Constructs a new PointerSlotStorage
65 * @details This constructs a new PointerSlotStorage, with all slots
66 * initialized to a nullptr.
67 */
69#if defined(__GLIBCXX__) && __GLIBCXX__ <= 20070719
70 _data.assign(nullptr);
71#else
72 _data.fill(nullptr);
73#endif
74 _max_index = 0;
75 _num_entries = 0;
76 }
77
78 /**
79 * @brief Returns the maximum index of the container
80 * @details This returns the greatest index of any element which is not zero.
81 * This can be useful for iterating the container, since all elements
82 * coming after the returned index are guaranteed to be a nullptr.
83 *
84 * If no elements are in this container, -1 is returned.
85 * @return Maximum index of the container
86 */
87 int get_max_index() const {
88 return _max_index;
89 }
90
91 /**
92 * @brief Returns the amount of elements of the container
93 * @details This returns the amount of elements in the container which are
94 * no nullptr.
95 * @return Amount of elements
96 */
97 size_t get_num_entries() const {
98 return _num_entries;
99 }
100
101 /**
102 * @brief Finds a free slot
103 * @details This finds the first slot which is a nullptr and returns it.
104 * This is most likely useful in combination with reserve_slot.
105 *
106 * When no slot found was found, slot will be undefined, and false will
107 * be returned.
108 *
109 * @param slot Output-Variable, slot will be stored there
110 * @return true if a slot was found, otherwise false
111 */
112 bool find_slot(size_t &slot) const {
113 for (size_t i = 0; i < SIZE; ++i) {
114 if (_data[i] == nullptr) {
115 slot = i;
116 return true;
117 }
118 }
119 return false;
120 }
121
122 /**
123 * @brief Finds free consecutive slots
124 * @details This behaves like find_slot, but it tries to find a slot
125 * after which <num_consecutive-1> free slots follow as well.
126 *
127 * When no slot found was found, slot will be undefined, and false will
128 * be returned.
129 *
130 * @param slot Output-Variable, index of the first slot of the consecutive
131 * slots will be stored there.
132 * @param num_consecutive Amount of consecutive slots to find, including the
133 * first slot.
134 *
135 * @return true if consecutive slots were found, otherwise false.
136 */
137 bool find_consecutive_slots(size_t &slot, size_t num_consecutive) const {
138 nassertr(num_consecutive > 0, false);
139
140 // Fall back to default search algorithm in case the parameters are equal
141 if (num_consecutive == 1) {
142 return find_slot(slot);
143 }
144
145 // Try to find consecutive slots otherwise
146 for (size_t i = 0; i < SIZE; ++i) {
147 bool any_taken = false;
148 for (size_t k = 0; !any_taken && k < num_consecutive; ++k) {
149 any_taken = _data[i + k] != nullptr;
150 }
151 if (!any_taken) {
152 slot = i;
153 return true;
154 }
155 }
156 return false;
157 }
158
159 /**
160 * @brief Frees an allocated slot
161 * @details This frees an allocated slot. If the slot was already freed
162 * before, this method throws an assertion.
163 *
164 * @param slot Slot to free
165 */
166 void free_slot(size_t slot) {
167 nassertv(slot >= 0 && slot < SIZE);
168 nassertv(_data[slot] != nullptr); // Slot was already empty!
169 _data[slot] = nullptr;
170 _num_entries--;
171
172 // Update maximum index
173 if ((int)slot == _max_index) {
174 while (_max_index >= 0 && !_data[_max_index--]);
175 }
176 }
177
178 /**
179 * @brief Frees consecutive allocated slots
180 * @details This behaves like PointerSlotStorage::free_slot, but deletes
181 * consecutive slots.
182 *
183 * @param slot Start of the consecutive slots to free
184 * @param num_consecutive Number of consecutive slots
185 */
186 void free_consecutive_slots(size_t slot, size_t num_consecutive) {
187 for (size_t i = slot; i < slot + num_consecutive; ++i) {
188 free_slot(i);
189 }
190 }
191
192 /**
193 * @brief Reserves a slot
194 * @details This reserves a slot by storing a pointer in it. If the slot
195 * was already taken, throws an assertion.
196 * If the ptr is a nullptr, also throws an assertion.
197 * If the slot was out of bounds, also throws an assertion.
198 *
199 * @param slot Slot to reserve
200 * @param ptr Pointer to store
201 */
202 void reserve_slot(size_t slot, T ptr) {
203 nassertv(slot >= 0 && slot < SIZE);
204 nassertv(_data[slot] == nullptr); // Slot already taken!
205 nassertv(ptr != nullptr); // nullptr passed as argument!
206 _max_index = std::max(_max_index, (int)slot);
207 _data[slot] = ptr;
208 _num_entries++;
209 }
210
211 typedef array<T, SIZE> InternalContainer;
212
213 /**
214 * @brief Returns an iterator to the begin of the container
215 * @details This returns an iterator to the beginning of the container
216 * @return Begin-Iterator
217 */
218 typename InternalContainer::iterator begin() {
219 return _data.begin();
220 }
221
222 /**
223 * @brief Returns an iterator to the end of the container
224 * @details This returns an iterator to the end of the iterator. This only
225 * iterates to PointerSlotStorage::get_max_index()
226 * @return [description]
227 */
228 typename InternalContainer::iterator end() {
229 return _data.begin() + _max_index + 1;
230 }
231
232private:
233 int _max_index;
234 size_t _num_entries;
235 InternalContainer _data;
236};
237
238#endif // CPPPARSER
239
240#endif // POINTERSLOTSTORAGE_H
Class to keep a list of pointers and nullpointers.
void free_slot(size_t slot)
Frees an allocated slot.
void free_consecutive_slots(size_t slot, size_t num_consecutive)
Frees consecutive allocated slots.
int get_max_index() const
Returns the maximum index of the container.
InternalContainer::iterator begin()
Returns an iterator to the begin of the container.
PointerSlotStorage()
Constructs a new PointerSlotStorage.
bool find_slot(size_t &slot) const
Finds a free slot.
size_t get_num_entries() const
Returns the amount of elements of the container.
bool find_consecutive_slots(size_t &slot, size_t num_consecutive) const
Finds free consecutive slots.
InternalContainer::iterator end()
Returns an iterator to the end of the container.
void reserve_slot(size_t slot, T ptr)
Reserves a slot.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.