Point Cloud Library (PCL) 1.15.0
Loading...
Searching...
No Matches
opennurbs_lookup.h
1/* $NoKeywords: $ */
2/*
3//
4// Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
5// OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
6// McNeel & Associates.
7//
8// THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
9// ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
10// MERCHANTABILITY ARE HEREBY DISCLAIMED.
11//
12// For complete openNURBS copyright information see <http://www.opennurbs.org>.
13//
14////////////////////////////////////////////////////////////////
15*/
16
17#if !defined(OPENNURBS_MAP_INC_)
18#define OPENNURBS_MAP_INC_
19
20/*
21Description:
22 ON_SerialNumberMap provides a way to map set of unique
23 serial number - uuid pairs to application defined values
24 so that adding, finding and removing serial numbers is
25 fast and efficient. The class is designed to handle
26 several millions of unique serial numbers. There are no
27 restrictions on what order numbers are added and removed.
28 The minimum memory footprint is less than 150KB and doesn't
29 increase until you have more than 8000 serial numbers.
30 It is possible to have an active serial number and an
31 inactive id.
32*/
33class ON_CLASS ON_SerialNumberMap
34{
35public:
36 ON_SerialNumberMap( ON_MEMORY_POOL* pool = 0 );
38
39 struct MAP_VALUE
40 {
41 ON__UINT32 m_u_type;
42 union
43 {
44 void* ptr;
45 unsigned int ui;
46 int i;
47 } m_u;
48 };
49
51 {
52 ////////////////////////////////////////////////////////////
53 //
54 // ID
55 //
57 struct SN_ELEMENT* m_next; // id hash table linked list
58
59 ////////////////////////////////////////////////////////////
60 //
61 // Serial number:
62 //
63 unsigned int m_sn;
64
65 ////////////////////////////////////////////////////////////
66 //
67 // Status flags:
68 //
69 // If m_id_active is 1, then m_sn_active must be 1.
70 // If m_sn_active = 1, then m_id_active can be 0 or 1.
71 //
72 unsigned char m_sn_active; // 1 = serial number is active
73 unsigned char m_id_active; // 1 = id is active
74 unsigned char m_reserved1;
75 unsigned char m_reserved2;
76
77 ////////////////////////////////////////////////////////////
78 //
79 // User information:
80 //
81 // ON_SerialNumberMap does not use the m_value field.
82 // When a new element is added, m_value is memset to
83 // zero. Other than that, m_value is not changed by
84 // this class. The location of m_value in memory,
85 // (&m_value) may change at any time.
86 struct MAP_VALUE m_value;
87
88 void Dump(ON_TextLog&) const;
89 };
90
91 /*
92 Returns:
93 Number of active serial numbers in the list.
94 */
95 std::size_t ActiveSerialNumberCount() const;
96
97 /*
98 Returns:
99 Number of active ids in the list. This number
100 is less than or equal to ActiveSerialNumberCount().
101 */
102 std::size_t ActiveIdCount() const;
103
104 /*
105 Returns:
106 The active element with the smallest serial number,
107 or null if the list is empty.
108 Restrictions:
109 The returned pointer may become invalid after any
110 subsequent calls to any function in this class.
111 If you need to save information in the returned
112 SN_ELEMENT for future use, you must copy the
113 information into storage you are managing.
114
115 You may change the value of the SN_ELEMENT's m_value
116 field. You must NEVER change any other SN_ELEMENT
117 fields or you will break searching and possibly cause
118 crashes.
119 */
120 struct SN_ELEMENT* FirstElement() const;
121
122 /*
123 Returns:
124 The active element with the biggest serial number,
125 or null if the list is empty.
126 Restrictions:
127 The returned pointer may become invalid after any
128 subsequent calls to any function in this class.
129 If you need to save information in the returned
130 SN_ELEMENT for future use, you must copy the
131 information into storage you are managing.
132
133 You may change the value of the SN_ELEMENT's m_value
134 field. You must NEVER change any other SN_ELEMENT
135 fields or you will break searching and possibly cause
136 crashes.
137 */
138 struct SN_ELEMENT* LastElement() const;
139
140 /*
141 Parameters:
142 sn - [in] serial number to search for.
143 Returns:
144 If the serial number is active, a pointer to
145 its element is returned.
146 Restrictions:
147 The returned pointer may become invalid after any
148 subsequent calls to any function in this class.
149 If you need to save information in the returned
150 SN_ELEMENT for future use, you must copy the
151 information into storage you are managing.
152
153 You may change the value of the SN_ELEMENT's m_value
154 field. You must NEVER change any other SN_ELEMENT
155 fields or you will break searching and possibly cause
156 crashes.
157 */
158 struct SN_ELEMENT* FindSerialNumber(unsigned int sn) const;
159
160 /*
161 Parameters:
162 id - [in] id number to search for.
163 Returns:
164 If the id is active, a pointer to
165 its element is returned.
166 Restrictions:
167 The returned pointer may become invalid after any
168 subsequent calls to any function in this class.
169 If you need to save information in the returned
170 SN_ELEMENT for future use, you must copy the
171 information into storage you are managing.
172
173 You may change the value of the SN_ELEMENT's m_value
174 field. You must NEVER change any other SN_ELEMENT
175 fields or you will break searching and possibly cause
176 crashes.
177 */
178 struct SN_ELEMENT* FindId(ON_UUID) const;
179
180 /*
181 Description:
182 Add a serial number to the map.
183 Parameters:
184 sn - [in] serial number to add.
185 Returns:
186 If the serial number is valid (>0), a pointer to its
187 element is returned. When a new element is added,
188 every byte of the m_value field is set to 0.
189 If the serial number was already active, its element is
190 also returned. If you need to distinguish between new
191 and previously existing elements, then change
192 m_value.m_u_type to something besides 0 after you add
193 a new serial number. The id associated with this
194 serial number will be zero and cannot be found using
195 FindId().
196 Restrictions:
197 The returned pointer may become invalid after any
198 subsequent calls to any function in this class.
199 If you need to save information in the returned
200 SN_ELEMENT for future use, you must copy the
201 information into storage you are managing.
202
203 You may change the value of the SN_ELEMENT's m_value
204 field. You must NEVER change any other SN_ELEMENT
205 fields or you will break searching and possibly cause
206 crashes.
207 */
208 struct SN_ELEMENT* AddSerialNumber(unsigned int sn);
209
210 /*
211 Parameters:
212 sn - [in] serial number to add.
213 id - [in] suggested id to add. If id is zero or
214 already in use, another id will be assigned
215 to the element.
216 Returns:
217 If the serial number is valid (>0), a pointer to its
218 element is returned. When a new element is added,
219 every byte of the m_value field is set to 0.
220 If the serial number was already active, its element is
221 also returned. If you need to distinguish between new
222 and previously existing elements, then change
223 m_value.m_u_type to something besides 0 after you add
224 a new serial number.
225 If the id parameter is zero, then a new uuid is created
226 and added. If the id parameter is non zero but is active
227 on another element, a new uuid is created and added.
228 You can inspect the value of m_id on the returned element
229 to determine the id AddSerialNumberAndId() assigned to
230 the element.
231 Restrictions:
232 The returned pointer may become invalid after any
233 subsequent calls to any function in this class.
234 If you need to save information in the returned
235 SN_ELEMENT for future use, you must copy the
236 information into storage you are managing.
237
238 You may change the value of the SN_ELEMENT's m_value
239 field. You must NEVER change any other SN_ELEMENT
240 fields or you will break searching and possibly cause
241 crashes.
242 */
243 struct SN_ELEMENT* AddSerialNumberAndId(unsigned int sn, ON_UUID id);
244
245 /*
246 Parameters:
247 sn - [in] serial number of the element to remove.
248 Returns:
249 If the serial number was active, it is removed
250 and a pointer to its element is returned. If
251 the element's id was active, the id is also removed.
252 Restrictions:
253 The returned pointer may become invalid after any
254 subsequent calls to any function in this class.
255 If you need to save information in the returned
256 SN_ELEMENT for future use, you must copy the
257 information into storage you are managing.
258
259 You may change the value of the SN_ELEMENT's m_value
260 field. You must NEVER change any other SN_ELEMENT
261 fields or you will break searching and possibly cause
262 crashes.
263 */
264 struct SN_ELEMENT* RemoveSerialNumberAndId(unsigned int sn);
265
266 /*
267 Parameters:
268 sn - [in] If > 0, this is the serial number
269 of the element with the id. If 0, the
270 field is ignored.
271 id - [in] id to search for.
272 Returns:
273 If the id was active, it is removed and a pointer
274 to its element is returned. The element's serial
275 remains active. To remove both the id and serial number,
276 use RemoveSerialNumberAndId().
277 Restrictions:
278 The returned pointer may become invalid after any
279 subsequent calls to any function in this class.
280 If you need to save information in the returned
281 SN_ELEMENT for future use, you must copy the
282 information into storage you are managing.
283
284 You may change the value of the SN_ELEMENT's m_value
285 field. You must NEVER change any other SN_ELEMENT
286 fields or you will break searching and possibly cause
287 crashes.
288 */
289 struct SN_ELEMENT* RemoveId(unsigned int sn, ON_UUID id);
290
291 /*
292 Description:
293 Finds all the elements whose serial numbers are
294 in the range sn0 <= sn <= sn1 and appends them
295 to the elements[] array. If max_count > 0, it
296 specifies the maximum number of elements to append.
297 Parameters:
298 sn0 - [in]
299 Minimum serial number.
300 sn1 - [in]
301 Maximum serial number
302 max_count - [in]
303 If max_count > 0, this parameter specifies the
304 maximum number of elements to append.
305 elements - [out]
306 Elements are appended to this array
307 Returns:
308 Number of elements appended to elements[] array.
309 Remarks:
310 When many elements are returned, GetElements() can be
311 substantially faster than repeated calls to FindElement().
312 */
313 std::size_t GetElements(
314 unsigned int sn0,
315 unsigned int sn1,
316 std::size_t max_count,
318 ) const;
319
320 /*
321 Description:
322 Empties the list.
323 */
324 void EmptyList();
325
326 /*
327 Description:
328 Returns true if the map is valid. Returns false if the
329 map is not valid. If an error is found and textlog
330 is not null, then a description of the problem is sent
331 to textlog.
332 Returns:
333 true if the list if valid.
334 */
335 bool IsValid(ON_TextLog* textlog) const;
336
337 void Dump(ON_TextLog& text_log) const;
338
339private:
340 // prohibit copy construction and operator=
341 // no implementation
343 ON_SerialNumberMap& operator=(const ON_SerialNumberMap&);
344
345 enum
346 {
347 // These numbers are chosen so the ON_SerialNumberMap
348 // will be computationally efficient for up to
349 // 10 million entries.
350 SN_BLOCK_CAPACITY = 8192,
351 SN_PURGE_RATIO = 16,
352 ID_HASH_TABLE_COUNT = 8192
353 };
354
355 struct SN_BLOCK
356 {
357 std::size_t m_count; // used elements in m_sn[]
358 std::size_t m_purged; // number of purged elements in m_sn[]
359 unsigned int m_sorted; // 0 = no, 1 = yes
360 unsigned int m_sn0; // minimum sn in m_sn[]
361 unsigned int m_sn1; // maximum sn in m_sn[]
362 struct SN_ELEMENT m_sn[SN_BLOCK_CAPACITY];
363 void EmptyBlock();
364 void CullBlockHelper();
365 void SortBlockHelper();
366 bool IsValidBlock(ON_TextLog* textlog,struct SN_ELEMENT*const* hash_table,std::size_t* active_id_count) const;
367 struct SN_ELEMENT* BinarySearchBlockHelper(unsigned int sn);
368 static int CompareMaxSN(const void*,const void*);
369 std::size_t ActiveElementEstimate(unsigned int sn0, unsigned int sn1) const;
370 void Dump(ON_TextLog&) const;
371 };
372
373 unsigned int m_maxsn; // largest sn stored anywhere
374 unsigned int m_reserved;
375
376 // All heap used in this class is allocated from this pool.
377 ON_MEMORY_POOL* m_pool;
378
379 // Serial Number list counts
380 std::size_t m_sn_count; // total number of elements
381 std::size_t m_sn_purged; // total number of purged elements
382
383 // ID hash table counts (all ids in the hash table are active)
384 bool m_bHashTableIsValid; // true if m_hash_table[] is valid
385 std::size_t m_active_id_count; // number of active ids in the hash table
386 ON_UUID m_inactive_id; // frequently and id is removed and
387 // then added back. m_inactive_id
388 // records the most recently removed
389 // id so we don't have to waste time
390 // searching the hash table for
391 // an id that is not there.
392
393
394 // The blocks in m_sn_list[] are alwasy sorted, disjoint,
395 // and in increasing order. m_sn_list is used when
396 // m_sn_block0.m_sn[] is not large enough.
397 // The sn list is partitioned into blocks to avoid
398 // requiring large amounts of contiguous memory for
399 // situations with millions of serial numbers.
400 struct SN_BLOCK** m_snblk_list;
401 std::size_t m_snblk_list_capacity; // capacity of m_blk_list[]
402 std::size_t m_snblk_list_count; // used elements in m_snblk_list[]
403
404 // If FindElementHelper() returns a non-null pointer
405 // to an element, then m_e_blk points to the SN_BLOCK
406 // that contains the returned element. In all other
407 // situations the value in m_e_blk is undefined and
408 // m_e_blk must not be dereferenced.
409 struct SN_BLOCK* m_e_blk;
410
411 // m_sn_block0 is where the new additions are added.
412 // When serial numbers are not added in increasing
413 // order, m_sn_block0.m_sn[] may not be sorted.
414 SN_BLOCK m_sn_block0;
415
416 struct SN_ELEMENT* FindElementHelper(unsigned int sn);
417 void UpdateMaxSNHelper();
418 void GarbageCollectHelper();
419 std::size_t GarbageCollectMoveHelper(SN_BLOCK* dst,SN_BLOCK* src);
420
421 // When m_bHashTableIsValid is true, then m_hash_table[i] is
422 // a linked list of elements whose id satisfies
423 // i = HashIndex(&e->m_id). When m_bHashTableIsValid is false,
424 // m_hash_table[] is identically zero.
425 struct SN_ELEMENT* m_hash_table[ID_HASH_TABLE_COUNT];
426 std::size_t HashIndex(const ON_UUID*) const;
427 void InvalidateHashTableHelper(); // marks table as dirty
428 bool RemoveBlockFromHashTableHelper(const struct SN_BLOCK* blk);
429 void AddBlockToHashTableHelper(struct SN_BLOCK* blk);
430 void BuildHashTableHelper(); // prepares table for use
431};
432
433
434#endif
struct SN_ELEMENT * LastElement() const
struct SN_ELEMENT * AddSerialNumber(unsigned int sn)
std::size_t ActiveSerialNumberCount() const
ON_SerialNumberMap(ON_MEMORY_POOL *pool=0)
struct SN_ELEMENT * FirstElement() const
struct SN_ELEMENT * RemoveSerialNumberAndId(unsigned int sn)
bool IsValid(ON_TextLog *textlog) const
struct SN_ELEMENT * RemoveId(unsigned int sn, ON_UUID id)
std::size_t ActiveIdCount() const
struct SN_ELEMENT * FindId(ON_UUID) const
std::size_t GetElements(unsigned int sn0, unsigned int sn1, std::size_t max_count, ON_SimpleArray< SN_ELEMENT > &elements) const
struct SN_ELEMENT * FindSerialNumber(unsigned int sn) const
struct SN_ELEMENT * AddSerialNumberAndId(unsigned int sn, ON_UUID id)
void Dump(ON_TextLog &text_log) const
void Dump(ON_TextLog &) const