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