1/* -*-c++-*- */ 2/* osgEarth - Geospatial SDK for OpenSceneGraph 3* Copyright 2019 Pelican Mapping 4* http://osgearth.org 5* 6* osgEarth is free software; you can redistribute it and/or modify 7* it under the terms of the GNU Lesser General Public License as published by 8* the Free Software Foundation; either version 2 of the License, or 9* (at your option) any later version. 10* 11* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 12* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 13* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 14* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 15* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 16* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 17* IN THE SOFTWARE. 18* 19* You should have received a copy of the GNU Lesser General Public License 20* along with this program. If not, see <http://www.gnu.org/licenses/> 21*/ 22#ifndef OSGEARTH_CONTAINERS_H 23#define OSGEARTH_CONTAINERS_H 1 24 25#include <osgEarth/Common> 26#include <osgEarth/ThreadingUtils> 27#include <osg/ref_ptr> 28#include <osg/observer_ptr> 29#include <osg/State> 30#include <list> 31#include <vector> 32#include <set> 33#include <map> 34 35namespace osgEarth 36{ 37 template<typename DATA> 38 struct fast_set 39 { 40 typedef DATA entry_t; 41 typedef std::vector<entry_t> container_t; 42 43 container_t _data; 44 45 typedef typename container_t::iterator iterator; 46 typedef typename container_t::const_iterator const_iterator; 47 48 iterator find(const DATA& value) { 49 for( iterator i = _data.begin(); i != _data.end(); ++i ) { 50 if ( (*i) == value ) { 51 return i; 52 } 53 } 54 return _data.end(); 55 } 56 57 const_iterator find(const DATA& value) const { 58 for( const_iterator i = _data.begin(); i != _data.end(); ++i ) { 59 if ( (*i) == value ) { 60 return i; 61 } 62 } 63 return _data.end(); 64 } 65 66 std::pair<iterator,bool> insert(const DATA& value) { 67 for( iterator i = _data.begin(); i != _data.end(); ++i ) { 68 if ( (*i) == value ) { 69 *i = value; 70 return std::make_pair(i, false); 71 } 72 } 73 _data.push_back(value); 74 iterator n = _data.end(); --n; 75 return std::make_pair(n, true); 76 } 77 78 const_iterator begin() const { return _data.begin(); } 79 const_iterator end() const { return _data.end(); } 80 iterator begin() { return _data.begin(); } 81 iterator end() { return _data.end(); } 82 bool empty() const { return _data.empty(); } 83 void clear() { _data.clear(); } 84 void erase(iterator i) { _data.erase(i); } 85 void erase(const DATA& data) { iterator i = find(data); if (i != _data.end()) _data.erase(i); } 86 int size() const { return _data.size(); } 87 }; 88 89 /** 90 * A std::map-like map that uses a vector and a getUID method for keying. 91 * DATA must have a getUID() method. 92 */ 93 template<typename KEY,typename DATA> 94 struct vector_map 95 { 96 struct ENTRY { 97 inline const KEY& key() const { return _key; } 98 inline const DATA& data() const { return _data; } 99 inline DATA& data() { return _data; } 100 KEY _key; 101 DATA _data; 102 }; 103 typedef std::vector<ENTRY> container_t; 104 105 //typedef std::vector<KEY> keys_t; 106 //typedef std::vector<DATA> container_t; 107 108 typedef typename container_t::iterator iterator; 109 typedef typename container_t::const_iterator const_iterator; 110 111 container_t _container; 112 113 inline DATA& operator[](const KEY& key) { 114 for(unsigned i=0; i<_container.size(); ++i) { 115 if (_container[i]._key == key) { 116 return _container[i]._data; 117 } 118 } 119 _container.resize(_container.size()+1); 120 _container.back()._key = key; 121 return _container.back()._data; 122 } 123 124 inline DATA* find(const KEY& key) { 125 for(unsigned i=0; i<_container.size(); ++i) { 126 if (_container[i]._key == key) { 127 return &_container[i]._data; 128 } 129 } 130 return 0L; 131 } 132 133 inline const DATA* find(const KEY& key) const { 134 for(unsigned i=0; i<_container.size(); ++i) { 135 if (_container[i]._key == key) { 136 return &_container[i]._data; 137 } 138 } 139 return 0L; 140 } 141 142 inline const_iterator begin() const { return _container.begin(); } 143 inline const_iterator end() const { return _container.end(); } 144 inline iterator begin() { return _container.begin(); } 145 inline iterator end() { return _container.end(); } 146 147 inline bool empty() const { return _container.empty(); } 148 149 inline void clear() { _container.clear(); } 150 151 inline void erase(const KEY& key) { 152 for(unsigned i=0; i<_container.size(); ++i) { 153 if (_container[i]._key == key) { 154 if (i+1 < _container.size()) { 155 _container[i] = _container[_container.size()-1]; 156 } 157 _container.resize(_container.size()-1); 158 break; 159 } 160 } 161 } 162 163 inline int size() const { return _container.size(); } 164 165 template<typename InputIterator> 166 void insert(InputIterator a, InputIterator b) { 167 for(InputIterator i = a; i != b; ++i) (*this)[i->first] = i->second; 168 } 169 }; 170 171 /** 172 * A std::map-like container that is faster than std::map for small amounts 173 * of data accessed by a single user 174 */ 175 template<typename KEY, typename DATA> 176 struct fast_map 177 { 178 typedef std::pair<KEY,DATA> entry_t; 179 typedef std::list<entry_t> container_t; 180 181 typedef typename container_t::iterator iterator; 182 typedef typename container_t::const_iterator const_iterator; 183 184 container_t _data; 185 KEY _lastKey; 186 187 DATA& operator[] (const KEY& key) { 188 for( iterator i = _data.begin(); i != _data.end(); ++i ) { 189 if ( i->first == key ) { 190 return i->second; 191 } 192 } 193 _data.push_back(entry_t(key,DATA())); 194 return _data.back().second; 195 } 196 197 iterator find( const KEY& key ) { 198 for( iterator i = _data.begin(); i != _data.end(); ++i ) { 199 if ( i->first == key ) { 200 return i; 201 } 202 } 203 return end(); 204 } 205 206 const_iterator find( const KEY& key ) const { 207 for( const_iterator i = _data.begin(); i != _data.end(); ++i ) { 208 if ( i->first == key ) { 209 return i; 210 } 211 } 212 return end(); 213 } 214 215 const_iterator begin() const { return _data.begin(); } 216 const_iterator end() const { return _data.end(); } 217 iterator begin() { return _data.begin(); } 218 iterator end() { return _data.end(); } 219 220 bool empty() const { return _data.empty(); } 221 222 void clear() { 223 _data.clear(); 224 } 225 226 iterator erase(iterator i) { 227 return _data.erase( i ); 228 } 229 230 iterator erase(iterator i0, iterator i1) { 231 return _data.erase(i0, i1); 232 } 233 234 void erase(const KEY& key) { 235 iterator i = find(key); 236 if ( i != end() ) { 237 erase( i ); 238 } 239 } 240 241 // Note: std::list::size() can be O(n) 242 int size() const { return _data.size(); } 243 244 template<typename InputIterator> 245 void insert(InputIterator a, InputIterator b) { 246 for(InputIterator i = a; i != b; ++i) (*this)[i->first] = i->second; 247 } 248 }; 249 250 //------------------------------------------------------------------------ 251 252 struct CacheStats 253 { 254 public: 255 CacheStats( unsigned entries, unsigned maxEntries, unsigned queries, float hitRatio ) 256 : _entries(entries), _maxEntries(maxEntries), _queries(queries), _hitRatio(hitRatio) { } 257 258 /** dtor */ 259 virtual ~CacheStats() { } 260 261 unsigned _entries; 262 unsigned _maxEntries; 263 unsigned _queries; 264 float _hitRatio; 265 }; 266 267 //------------------------------------------------------------------------ 268 269 /** 270 * Least-recently-used cache class. 271 * K = key type, T = value type 272 * 273 * usage: 274 * LRUCache<K,T> cache; 275 * cache.insert( key, value ); 276 * LRUCache<K,T>::Record rec; 277 * if ( cache.get( key, rec ) ) 278 * const T& value = rec.value(); 279 */ 280 template<typename K, typename T, typename COMPARE=std::less<K> > 281 class LRUCache 282 { 283 public: 284 struct Record { 285 Record() : _valid(false) { } 286 Record(const T& value) : _value(value), _valid(true) { } 287 bool valid() const { return _valid; } 288 const T& value() const { return _value; } 289 private: 290 bool _valid; 291 T _value; 292 friend class LRUCache; 293 }; 294 295 struct Functor { 296 virtual void operator()(const K& key, const T& value) =0; 297 }; 298 299 protected: 300 typedef typename std::list<K>::iterator lru_iter; 301 typedef typename std::list<K> lru_type; 302 typedef typename std::pair<T, lru_iter> map_value_type; 303 typedef typename std::map<K, map_value_type> map_type; 304 typedef typename map_type::iterator map_iter; 305 typedef typename map_type::const_iterator map_const_iter; 306 307 map_type _map; 308 lru_type _lru; 309 unsigned _max; 310 unsigned _buf; 311 unsigned _queries; 312 unsigned _hits; 313 bool _threadsafe; 314 mutable Threading::Mutex _mutex; 315 316 public: 317 LRUCache( unsigned max =100 ) : _max(max), _threadsafe(false) { 318 _queries = 0; 319 _hits = 0; 320 setMaxSize_impl(max); 321 } 322 LRUCache( bool threadsafe, unsigned max =100 ) : _max(max), _threadsafe(threadsafe) { 323 _queries = 0; 324 _hits = 0; 325 setMaxSize_impl(max); 326 } 327 328 /** dtor */ 329 virtual ~LRUCache() { } 330 331 void insert( const K& key, const T& value ) { 332 if ( _threadsafe ) { 333 Threading::ScopedMutexLock lock(_mutex); 334 insert_impl( key, value ); 335 } 336 else { 337 insert_impl( key, value ); 338 } 339 } 340 341 bool get( const K& key, Record& out ) { 342 if ( _threadsafe ) { 343 Threading::ScopedMutexLock lock(_mutex); 344 get_impl( key, out ); 345 } 346 else { 347 get_impl( key, out ); 348 } 349 return out.valid(); 350 } 351 352 bool has( const K& key ) { 353 if ( _threadsafe ) { 354 Threading::ScopedMutexLock lock(_mutex); 355 return has_impl( key ); 356 } 357 else { 358 return has_impl( key ); 359 } 360 } 361 362 void erase( const K& key ) { 363 if ( _threadsafe ) { 364 Threading::ScopedMutexLock lock(_mutex); 365 erase_impl( key ); 366 } 367 else { 368 erase_impl( key ); 369 } 370 } 371 372 void clear() { 373 if ( _threadsafe ) { 374 Threading::ScopedMutexLock lock(_mutex); 375 clear_impl(); 376 } 377 else { 378 clear_impl(); 379 } 380 } 381 382 void setMaxSize( unsigned max ) { 383 if ( _threadsafe ) { 384 Threading::ScopedMutexLock lock(_mutex); 385 setMaxSize_impl( max ); 386 } 387 else { 388 setMaxSize_impl( max ); 389 } 390 } 391 392 unsigned getMaxSize() const { 393 return _max; 394 } 395 396 CacheStats getStats() const { 397 return CacheStats( 398 _map.size(), _max, _queries, _queries > 0 ? (float)_hits/(float)_queries : 0.0f ); 399 } 400 401 void iterate(Functor& functor) const { 402 if (_threadsafe) { 403 Threading::ScopedMutexLock lock(_mutex); 404 iterate_impl(functor); 405 } 406 else { 407 iterate_impl(functor); 408 } 409 } 410 411 private: 412 413 void insert_impl( const K& key, const T& value ) { 414 map_iter mi = _map.find( key ); 415 if ( mi != _map.end() ) { 416 _lru.erase( mi->second.second ); 417 mi->second.first = value; 418 _lru.push_back( key ); 419 mi->second.second = _lru.end(); 420 mi->second.second--; 421 } 422 else { 423 _lru.push_back( key ); 424 lru_iter last = _lru.end(); last--; 425 _map[key] = std::make_pair(value, last); 426 } 427 428 if ( _map.size() > _max ) { 429 for( unsigned i=0; i < _buf; ++i ) { 430 const K& key = _lru.front(); 431 _map.erase( key ); 432 _lru.pop_front(); 433 } 434 } 435 } 436 437 void get_impl( const K& key, Record& result ) { 438 _queries++; 439 map_iter mi = _map.find( key ); 440 if ( mi != _map.end() ) { 441 _lru.erase( mi->second.second ); 442 _lru.push_back( key ); 443 lru_iter new_iter = _lru.end(); new_iter--; 444 mi->second.second = new_iter; 445 _hits++; 446 result._value = mi->second.first; 447 result._valid = true; 448 } 449 } 450 451 bool has_impl( const K& key ) { 452 return _map.find( key ) != _map.end(); 453 } 454 455 void erase_impl( const K& key ) { 456 map_iter mi = _map.find( key ); 457 if ( mi != _map.end() ) { 458 _lru.erase( mi->second.second ); 459 _map.erase( mi ); 460 } 461 } 462 463 void clear_impl() { 464 _lru.clear(); 465 _map.clear(); 466 _queries = 0; 467 _hits = 0; 468 } 469 470 void setMaxSize_impl( unsigned max ) { 471 _max = osg::maximum(max,10u); 472 _buf = _max/10u; 473 while( _map.size() > _max ) { 474 const K& key = _lru.front(); 475 _map.erase( key ); 476 _lru.pop_front(); 477 } 478 } 479 480 void iterate_impl(Functor& f) const { 481 for (map_const_iter i = _map.begin(); i != _map.end(); ++i) { 482 f(i->first, i->second.first); 483 } 484 } 485 }; 486 487 //-------------------------------------------------------------------- 488 489 /** 490 * Same of osg::MixinVector, but with a superclass template parameter. 491 */ 492 template<class ValueT, class SuperClass> 493 class MixinVector : public SuperClass 494 { 495 typedef typename std::vector<ValueT> vector_type; 496 public: 497 typedef typename vector_type::allocator_type allocator_type; 498 typedef typename vector_type::value_type value_type; 499 typedef typename vector_type::const_pointer const_pointer; 500 typedef typename vector_type::pointer pointer; 501 typedef typename vector_type::const_reference const_reference; 502 typedef typename vector_type::reference reference; 503 typedef typename vector_type::const_iterator const_iterator; 504 typedef typename vector_type::iterator iterator; 505 typedef typename vector_type::const_reverse_iterator const_reverse_iterator; 506 typedef typename vector_type::reverse_iterator reverse_iterator; 507 typedef typename vector_type::size_type size_type; 508 typedef typename vector_type::difference_type difference_type; 509 510 explicit MixinVector() : _impl() 511 { 512 } 513 514 explicit MixinVector(size_type initial_size, const value_type& fill_value = value_type()) 515 : _impl(initial_size, fill_value) 516 { 517 } 518 519 template<class InputIterator> 520 MixinVector(InputIterator first, InputIterator last) 521 : _impl(first, last) 522 { 523 } 524 525 MixinVector(const vector_type& other) 526 : _impl(other) 527 { 528 } 529 530 MixinVector(const MixinVector& other) 531 : _impl(other._impl) 532 { 533 } 534 535 MixinVector& operator=(const vector_type& other) 536 { 537 _impl = other; 538 return *this; 539 } 540 541 MixinVector& operator=(const MixinVector& other) 542 { 543 _impl = other._impl; 544 return *this; 545 } 546 547 virtual ~MixinVector() {} 548 549 void clear() { _impl.clear(); } 550 void resize(size_type new_size, const value_type& fill_value = value_type()) { _impl.resize(new_size, fill_value); } 551 void reserve(size_type new_capacity) { _impl.reserve(new_capacity); } 552 553 void swap(vector_type& other) { _impl.swap(other); } 554 void swap(MixinVector& other) { _impl.swap(other._impl); } 555 556 bool empty() const { return _impl.empty(); } 557 size_type size() const { return _impl.size(); } 558 size_type capacity() const { return _impl.capacity(); } 559 size_type max_size() const { return _impl.max_size(); } 560 allocator_type get_allocator() const { return _impl.get_allocator(); } 561 562 const_iterator begin() const { return _impl.begin(); } 563 iterator begin() { return _impl.begin(); } 564 const_iterator end() const { return _impl.end(); } 565 iterator end() { return _impl.end(); } 566 567 const_reverse_iterator rbegin() const { return _impl.rbegin(); } 568 reverse_iterator rbegin() { return _impl.rbegin(); } 569 const_reverse_iterator rend() const { return _impl.rend(); } 570 reverse_iterator rend() { return _impl.rend(); } 571 572 const_reference operator[](size_type index) const { return _impl[index]; } 573 reference operator[](size_type index) { return _impl[index]; } 574 575 const_reference at(size_type index) const { return _impl.at(index); } 576 reference at(size_type index) { return _impl.at(index); } 577 578 void assign(size_type count, const value_type& value) { _impl.assign(count, value); } 579 template<class Iter> 580 void assign(Iter first, Iter last) { _impl.assign(first, last); } 581 582 void push_back(const value_type& value) { _impl.push_back(value); } 583 void pop_back() { _impl.pop_back(); } 584 585 iterator erase(iterator where) { return _impl.erase(where); } 586 iterator erase(iterator first, iterator last) { return _impl.erase(first, last); } 587 588 iterator insert(iterator where, const value_type& value) { return _impl.insert(where, value); } 589 590 template<class InputIterator> 591 void insert(iterator where, InputIterator first, InputIterator last) 592 { 593 _impl.insert(where, first, last); 594 } 595 596 void insert(iterator where, size_type count, const value_type& value) 597 { 598 _impl.insert(where, count, value); 599 } 600 601 const_reference back() const { return _impl.back(); } 602 reference back() { return _impl.back(); } 603 const_reference front() const { return _impl.front(); } 604 reference front() { return _impl.front(); } 605 606 vector_type& asVector() { return _impl; } 607 const vector_type& asVector() const { return _impl; } 608 609 friend inline bool operator==(const MixinVector<ValueT,SuperClass>& left, const MixinVector<ValueT,SuperClass>& right) { return left._impl == right._impl; } 610 friend inline bool operator==(const MixinVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl == right; } 611 friend inline bool operator==(const std::vector<ValueT>& left, const MixinVector<ValueT,SuperClass>& right) { return left == right._impl; } 612 613 friend inline bool operator!=(const MixinVector<ValueT,SuperClass>& left, const MixinVector<ValueT,SuperClass>& right) { return left._impl != right._impl; } 614 friend inline bool operator!=(const MixinVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl != right; } 615 friend inline bool operator!=(const std::vector<ValueT>& left, const MixinVector<ValueT,SuperClass>& right) { return left != right._impl; } 616 617 friend inline bool operator<(const MixinVector<ValueT,SuperClass>& left, const MixinVector<ValueT,SuperClass>& right) { return left._impl < right._impl; } 618 friend inline bool operator<(const MixinVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl < right; } 619 friend inline bool operator<(const std::vector<ValueT>& left, const MixinVector<ValueT,SuperClass>& right) { return left < right._impl; } 620 621 friend inline bool operator>(const MixinVector<ValueT,SuperClass>& left, const MixinVector<ValueT,SuperClass>& right) { return left._impl > right._impl; } 622 friend inline bool operator>(const MixinVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl > right; } 623 friend inline bool operator>(const std::vector<ValueT>& left, const MixinVector<ValueT,SuperClass>& right) { return left > right._impl; } 624 625 friend inline bool operator<=(const MixinVector<ValueT,SuperClass>& left, const MixinVector<ValueT,SuperClass>& right) { return left._impl <= right._impl; } 626 friend inline bool operator<=(const MixinVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl <= right; } 627 friend inline bool operator<=(const std::vector<ValueT>& left, const MixinVector<ValueT,SuperClass>& right) { return left <= right._impl; } 628 629 friend inline bool operator>=(const MixinVector<ValueT,SuperClass>& left, const MixinVector<ValueT,SuperClass>& right) { return left._impl >= right._impl; } 630 friend inline bool operator>=(const MixinVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl >= right; } 631 friend inline bool operator>=(const std::vector<ValueT>& left, const MixinVector<ValueT,SuperClass>& right) { return left >= right._impl; } 632 633 private: 634 vector_type _impl; 635 }; 636 637 638 /** Template for per-thread data storage */ 639 template<typename T> 640 struct PerThread 641 { 642 T& get() { 643 Threading::ScopedMutexLock lock(_mutex); 644 return _data[Threading::getCurrentThreadId()]; 645 } 646 private: 647 std::map<unsigned,T> _data; 648 Threading::Mutex _mutex; 649 }; 650 651 652 /** Template for thread safe per-object data storage */ 653 template<typename KEY, typename DATA> 654 struct PerObjectMap 655 { 656 DATA& get(KEY k) 657 { 658 { 659 osgEarth::Threading::ScopedReadLock readLock(_mutex); 660 typename std::map<KEY,DATA>::iterator i = _data.find(k); 661 if ( i != _data.end() ) 662 return i->second; 663 } 664 { 665 osgEarth::Threading::ScopedWriteLock lock(_mutex); 666 typename std::map<KEY,DATA>::iterator i = _data.find(k); 667 if ( i != _data.end() ) 668 return i->second; 669 else 670 return _data[k]; 671 } 672 } 673 674 void remove(KEY k) 675 { 676 osgEarth::Threading::ScopedWriteLock exclusive(_mutex); 677 _data.erase( k ); 678 } 679 680 private: 681 std::map<KEY,DATA> _data; 682 osgEarth::Threading::ReadWriteMutex _mutex; 683 }; 684 685 /** Template for thread safe per-object data storage */ 686 template<typename KEY, typename DATA> 687 struct PerObjectFastMap 688 { 689 struct Functor { 690 virtual void operator()(DATA& data) =0; 691 }; 692 693 struct ConstFunctor { 694 virtual void operator()(const DATA& data) const =0; 695 }; 696 697 DATA& get(KEY k) 698 { 699 osgEarth::Threading::ScopedMutexLock lock(_mutex); 700 typename osgEarth::fast_map<KEY,DATA>::iterator i = _data.find(k); 701 if ( i != _data.end() ) 702 return i->second; 703 else 704 return _data[k]; 705 } 706 707 void remove(KEY k) 708 { 709 osgEarth::Threading::ScopedMutexLock lock(_mutex); 710 _data.erase( k ); 711 } 712 713 void forEach(Functor& functor) 714 { 715 osgEarth::Threading::ScopedMutexLock lock(_mutex); 716 for (typename fast_map<KEY, DATA>::iterator i = _data.begin(); i != _data.end(); ++i) 717 functor.operator()(i->second); 718 } 719 720 void forEach(ConstFunctor& functor) const 721 { 722 osgEarth::Threading::ScopedMutexLock lock(_mutex); 723 for (typename fast_map<KEY, DATA>::const_iterator i = _data.begin(); i != _data.end(); ++i) 724 functor.operator()(i->second); 725 } 726 727 unsigned size() const 728 { 729 osgEarth::Threading::ScopedMutexLock lock(_mutex); 730 return _data.size(); 731 } 732 733 void clear() 734 { 735 osgEarth::Threading::ScopedMutexLock lock(_mutex); 736 _data.clear(); 737 } 738 739 private: 740 osgEarth::fast_map<KEY,DATA> _data; 741 mutable osgEarth::Threading::Mutex _mutex; 742 }; 743 744 /** Template for thread safe per-object data storage */ 745 template<typename KEY, typename DATA> 746 struct PerObjectRefMap 747 { 748 DATA* get(KEY k) 749 { 750 osgEarth::Threading::ScopedReadLock lock(_mutex); 751 typename std::map<KEY,osg::ref_ptr<DATA > >::const_iterator i = _data.find(k); 752 if ( i != _data.end() ) 753 return i->second.get(); 754 755 return 0L; 756 } 757 758 DATA* getOrCreate(KEY k, DATA* newDataIfNeeded) 759 { 760 osg::ref_ptr<DATA> _refReleaser = newDataIfNeeded; 761 { 762 osgEarth::Threading::ScopedReadLock lock(_mutex); 763 typename std::map<KEY,osg::ref_ptr<DATA> >::const_iterator i = _data.find(k); 764 if ( i != _data.end() ) 765 return i->second.get(); 766 } 767 768 { 769 osgEarth::Threading::ScopedWriteLock lock(_mutex); 770 typename std::map<KEY,osg::ref_ptr<DATA> >::iterator i = _data.find(k); 771 if ( i != _data.end() ) 772 return i->second.get(); 773 774 _data[k] = newDataIfNeeded; 775 return newDataIfNeeded; 776 } 777 } 778 779 void remove(KEY k) 780 { 781 osgEarth::Threading::ScopedWriteLock exclusive(_mutex); 782 _data.erase( k ); 783 } 784 785 void remove(DATA* data) 786 { 787 osgEarth::Threading::ScopedWriteLock exclusive(_mutex); 788 for( typename std::map<KEY,osg::ref_ptr<DATA> >::iterator i = _data.begin(); i != _data.end(); ++i ) 789 { 790 if ( i->second.get() == data ) 791 { 792 _data.erase( i ); 793 break; 794 } 795 } 796 } 797 798 private: 799 std::map<KEY,osg::ref_ptr<DATA> > _data; 800 osgEarth::Threading::ReadWriteMutex _mutex; 801 }; 802 803 /** Template for thread safe per-object data storage */ 804 template<typename KEY, typename DATA> 805 struct PerObjectObsMap 806 { 807 DATA* get(KEY k) 808 { 809 osgEarth::Threading::ScopedReadLock lock(_mutex); 810 typename std::map<KEY, osg::observer_ptr<DATA> >::const_iterator i = _data.find(k); 811 if ( i != _data.end() ) 812 return i->second.get(); 813 814 return 0L; 815 } 816 817 DATA* getOrCreate(KEY k, DATA* newDataIfNeeded) 818 { 819 osg::ref_ptr<DATA> _refReleaser = newDataIfNeeded; 820 { 821 osgEarth::Threading::ScopedReadLock lock(_mutex); 822 typename std::map<KEY,osg::observer_ptr<DATA> >::const_iterator i = _data.find(k); 823 if ( i != _data.end() ) 824 return i->second.get(); 825 } 826 827 { 828 osgEarth::Threading::ScopedWriteLock lock(_mutex); 829 typename std::map<KEY,osg::observer_ptr<DATA> >::iterator i = _data.find(k); 830 if ( i != _data.end() ) 831 return i->second.get(); 832 833 _data[k] = newDataIfNeeded; 834 return newDataIfNeeded; 835 } 836 } 837 838 void remove(KEY k) 839 { 840 osgEarth::Threading::ScopedWriteLock exclusive(_mutex); 841 _data.erase( k ); 842 } 843 844 void remove(DATA* data) 845 { 846 osgEarth::Threading::ScopedWriteLock exclusive(_mutex); 847 for( typename std::map<KEY,osg::observer_ptr<DATA> >::iterator i = _data.begin(); i != _data.end(); ++i ) 848 { 849 if ( i->second.get() == data ) 850 { 851 _data.erase( i ); 852 break; 853 } 854 } 855 } 856 857 private: 858 std::map<KEY,osg::observer_ptr<DATA> > _data; 859 osgEarth::Threading::ReadWriteMutex _mutex; 860 }; 861 862 863 /** Template for thread safe observer set */ 864 template<typename T> 865 struct ThreadSafeObserverSet 866 { 867 typedef void (*Functor)(T*); 868 typedef void (*ConstFunctor)(const T*); 869 870 void iterate( const Functor& f ) 871 { 872 osgEarth::Threading::ScopedWriteLock lock(_mutex); 873 for( typename std::set<T>::iterator i = _data.begin(); i != _data.end(); ) 874 { 875 if ( i->valid() ) 876 { 877 f( i->get() ); 878 ++i; 879 } 880 else 881 { 882 i = _data.erase( i ); 883 } 884 } 885 } 886 887 void iterate( const ConstFunctor& f ) 888 { 889 osgEarth::Threading::ScopedReadLock lock(_mutex); 890 for( typename std::set<osg::observer_ptr<T> >::iterator i = _data.begin(); i != _data.end(); ) 891 { 892 if ( i->valid() ) 893 { 894 f( i->get() ); 895 ++i; 896 } 897 else 898 { 899 i = _data.erase( i ); 900 } 901 } 902 } 903 904 void insert(T* obj) 905 { 906 osgEarth::Threading::ScopedWriteLock lock(_mutex); 907 _data.insert( obj ); 908 } 909 910 void remove(T* obj) 911 { 912 osgEarth::Threading::ScopedWriteLock lock(_mutex); 913 _data.erase( obj ); 914 } 915 916 private: 917 std::set<osg::observer_ptr<T> > _data; 918 osgEarth::Threading::ReadWriteMutex _mutex; 919 }; 920 921 922 // borrowed from osg::buffered_object. Auto-resizing array. 923 template<class T> 924 class AutoArray 925 { 926 public: 927 inline AutoArray() { } 928 929 inline AutoArray(unsigned int size) : _array(size) { } 930 931 AutoArray& operator = (const AutoArray& rhs) 932 { 933 _array = rhs._array; 934 return *this; 935 } 936 937 inline void setAllElementsTo(const T& t) { std::fill(_array.begin(), _array.end(), t); } 938 inline void clear() { _array.clear(); } 939 inline bool empty() const { return _array.empty(); } 940 inline unsigned int size() const { return _array.size(); } 941 inline void resize(unsigned int newSize) { _array.resize(newSize); } 942 943 inline T& operator[] (unsigned int pos) 944 { 945 if (_array.size() <= pos) 946 _array.resize(pos + 1); 947 948 return _array[pos]; 949 } 950 951 inline const T& operator[] (unsigned int pos) const 952 { 953 // automatically resize array. 954 if (_array.size() <= pos) 955 _array.resize(pos + 1); 956 957 return _array[pos]; 958 } 959 960 inline T& back() { return _array[size()-1]; } 961 inline const T& back() const { return _array[size()-1]; } 962 963 protected: 964 965 mutable std::vector<T> _array; 966 }; 967 968} 969 970#endif // OSGEARTH_CONTAINERS_H 971