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 /*
21 Description:
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 */
33 class ON_CLASS ON_SerialNumberMap
34 {
35 public:
36   ON_SerialNumberMap( ON_MEMORY_POOL* pool = 0 );
37   ~ON_SerialNumberMap();
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 
50   struct SN_ELEMENT
51   {
52     ////////////////////////////////////////////////////////////
53     //
54     // ID
55     //
56     ON_UUID m_id;
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   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   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   size_t GetElements(
314           unsigned int sn0,
315           unsigned int sn1,
316           size_t max_count,
317           ON_SimpleArray<SN_ELEMENT>& elements
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 
339 private:
340   // prohibit copy construction and operator=
341   // no implementation
342   ON_SerialNumberMap(const ON_SerialNumberMap&);
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     size_t m_count;  // used elements in m_sn[]
358     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,size_t* active_id_count) const;
367     struct SN_ELEMENT* BinarySearchBlockHelper(unsigned int sn);
368     static int CompareMaxSN(const void*,const void*);
369     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   size_t m_sn_count;   // total number of elements
381   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   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   size_t m_snblk_list_capacity; // capacity of m_blk_list[]
402   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   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   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
435