929 lines
31 KiB
Plaintext
929 lines
31 KiB
Plaintext
|
/* -*-c++-*- */
|
||
|
|
/* osgEarth - Geospatial SDK for OpenSceneGraph
|
||
|
|
* Copyright 2020 Pelican Mapping
|
||
|
|
* http://osgearth.org
|
||
|
|
*
|
||
|
|
* osgEarth is free software; you can redistribute it and/or modify
|
||
|
|
* it under the terms of the GNU Lesser General Public License as published by
|
||
|
|
* the Free Software Foundation; either version 2 of the License, or
|
||
|
|
* (at your option) any later version.
|
||
|
|
*
|
||
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
||
|
|
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
||
|
|
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
||
|
|
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
||
|
|
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
|
||
|
|
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
|
||
|
|
* IN THE SOFTWARE.
|
||
|
|
*
|
||
|
|
* You should have received a copy of the GNU Lesser General Public License
|
||
|
|
* along with this program. If not, see <http://www.gnu.org/licenses/>
|
||
|
|
*/
|
||
|
|
#pragma once
|
||
|
|
#include <osgEarth/Common>
|
||
|
|
#include <osgEarth/Threading>
|
||
|
|
#include <osg/ref_ptr>
|
||
|
|
#include <osg/observer_ptr>
|
||
|
|
#include <osg/Math>
|
||
|
|
#include <list>
|
||
|
|
#include <vector>
|
||
|
|
#include <unordered_set>
|
||
|
|
#include <unordered_map>
|
||
|
|
#include <queue>
|
||
|
|
#include <thread>
|
||
|
|
|
||
|
|
namespace osgEarth { namespace Util
|
||
|
|
{
|
||
|
|
/**
|
||
|
|
* A std::map-like map that uses a vector.
|
||
|
|
* This benchmarks much faster than std::map or std::unordered_map for small sets.
|
||
|
|
*/
|
||
|
|
template<typename KEY,typename DATA,typename LESS=std::less<KEY>>
|
||
|
|
struct vector_map
|
||
|
|
{
|
||
|
|
struct ENTRY {
|
||
|
|
KEY first;
|
||
|
|
DATA second;
|
||
|
|
};
|
||
|
|
|
||
|
|
using value_type = DATA;
|
||
|
|
using container_t = std::vector<ENTRY>;
|
||
|
|
using iterator = typename container_t::iterator;
|
||
|
|
using const_iterator = typename container_t::const_iterator;
|
||
|
|
|
||
|
|
container_t _container;
|
||
|
|
|
||
|
|
inline bool keys_equal(const KEY& a, const KEY& b) const {
|
||
|
|
return LESS()(a, b) == false && LESS()(b, a) == false;
|
||
|
|
}
|
||
|
|
|
||
|
|
inline DATA& operator[](const KEY& key) {
|
||
|
|
for(unsigned i=0; i<_container.size(); ++i) {
|
||
|
|
if (keys_equal(_container[i].first, key)) {
|
||
|
|
return _container[i].second;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
_container.resize(_container.size()+1);
|
||
|
|
_container.back().first = key;
|
||
|
|
return _container.back().second;
|
||
|
|
}
|
||
|
|
|
||
|
|
inline const_iterator begin() const { return _container.begin(); }
|
||
|
|
inline const_iterator end() const { return _container.end(); }
|
||
|
|
inline iterator begin() { return _container.begin(); }
|
||
|
|
inline iterator end() { return _container.end(); }
|
||
|
|
|
||
|
|
inline iterator find(const KEY& key) {
|
||
|
|
for (unsigned i = 0; i < _container.size(); ++i) {
|
||
|
|
if (keys_equal(_container[i].first, key)) {
|
||
|
|
return _container.begin() + i;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return _container.end();
|
||
|
|
}
|
||
|
|
|
||
|
|
inline const_iterator find(const KEY& key) const {
|
||
|
|
for(unsigned i=0; i<_container.size(); ++i) {
|
||
|
|
if (keys_equal(_container[i].first, key)) {
|
||
|
|
return _container.begin()+i;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return _container.end();
|
||
|
|
}
|
||
|
|
|
||
|
|
inline bool empty() const { return _container.empty(); }
|
||
|
|
|
||
|
|
inline void clear() { _container.clear(); }
|
||
|
|
|
||
|
|
inline void erase(const KEY& key) {
|
||
|
|
for(unsigned i=0; i<_container.size(); ++i) {
|
||
|
|
if (keys_equal(_container[i].first, key)) {
|
||
|
|
if (i+1 < _container.size()) {
|
||
|
|
_container[i] = _container[_container.size()-1];
|
||
|
|
}
|
||
|
|
_container.resize(_container.size()-1);
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
inline int indexOf(const KEY& key) const {
|
||
|
|
for(unsigned i=0; i<_container.size(); ++i) {
|
||
|
|
if (keys_equal(_container[i].first, key)) {
|
||
|
|
return i;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
|
||
|
|
inline int size() const { return _container.size(); }
|
||
|
|
|
||
|
|
template<typename InputIterator>
|
||
|
|
void insert(InputIterator a, InputIterator b) {
|
||
|
|
for(InputIterator i = a; i != b; ++i) (*this)[i->first] = i->second;
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
template<typename DATA>
|
||
|
|
struct vector_set
|
||
|
|
{
|
||
|
|
typedef std::vector<DATA> container_t;
|
||
|
|
|
||
|
|
typedef typename container_t::iterator iterator;
|
||
|
|
typedef typename container_t::const_iterator const_iterator;
|
||
|
|
typedef typename container_t::size_type size_type;
|
||
|
|
|
||
|
|
container_t _container;
|
||
|
|
|
||
|
|
inline const_iterator begin() const { return _container.begin(); }
|
||
|
|
inline const_iterator end() const { return _container.end(); }
|
||
|
|
inline iterator begin() { return _container.begin(); }
|
||
|
|
inline iterator end() { return _container.end(); }
|
||
|
|
|
||
|
|
inline std::pair<typename vector_set<DATA>::const_iterator, bool> insert(const DATA& data) {
|
||
|
|
const_iterator i = find(data);
|
||
|
|
if (i != end()) {
|
||
|
|
return std::make_pair(i, false);
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
_container.push_back(data);
|
||
|
|
return std::make_pair(_container.end()-1, true);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
inline const_iterator find(const DATA& data) const {
|
||
|
|
for (unsigned i = 0; i < _container.size(); ++i) {
|
||
|
|
if (_container[i] == data) {
|
||
|
|
return _container.begin() + i;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return _container.end();
|
||
|
|
}
|
||
|
|
|
||
|
|
inline bool contains(const DATA& data) const {
|
||
|
|
return find(data) != _container.end();
|
||
|
|
}
|
||
|
|
|
||
|
|
inline bool empty() const { return _container.empty(); }
|
||
|
|
|
||
|
|
inline void clear() { _container.clear(); }
|
||
|
|
|
||
|
|
inline size_type erase(const DATA& data) {
|
||
|
|
for (unsigned i = 0; i < _container.size(); ++i) {
|
||
|
|
if (_container[i] == data) {
|
||
|
|
if (i + 1 < _container.size()) {
|
||
|
|
_container[i] = _container[_container.size() - 1];
|
||
|
|
}
|
||
|
|
_container.resize(_container.size() - 1);
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
inline int size() const { return _container.size(); }
|
||
|
|
|
||
|
|
template<typename InputIterator>
|
||
|
|
void insert(InputIterator a, InputIterator b) {
|
||
|
|
for (InputIterator i = a; i != b; ++i)
|
||
|
|
insert(*i);
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
//------------------------------------------------------------------------
|
||
|
|
|
||
|
|
struct CacheStats
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
CacheStats( unsigned entries, unsigned maxEntries, unsigned queries, float hitRatio )
|
||
|
|
: _entries(entries), _maxEntries(maxEntries), _queries(queries), _hitRatio(hitRatio) { }
|
||
|
|
|
||
|
|
/** dtor */
|
||
|
|
virtual ~CacheStats() { }
|
||
|
|
|
||
|
|
unsigned _entries;
|
||
|
|
unsigned _maxEntries;
|
||
|
|
unsigned _queries;
|
||
|
|
float _hitRatio;
|
||
|
|
};
|
||
|
|
|
||
|
|
//------------------------------------------------------------------------
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Least-recently-used cache class.
|
||
|
|
* K = key type, T = value type
|
||
|
|
*
|
||
|
|
* usage:
|
||
|
|
* LRUCache<K,T> cache;
|
||
|
|
* cache.insert( key, value );
|
||
|
|
* LRUCache<K,T>::Record rec;
|
||
|
|
* if ( cache.get( key, rec ) )
|
||
|
|
* const T& value = rec.value();
|
||
|
|
*/
|
||
|
|
template<typename K, typename T, typename COMPARE=std::less<K> >
|
||
|
|
class LRUCache
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
struct Record {
|
||
|
|
Record() : _valid(false) { }
|
||
|
|
Record(const T& value) : _value(value), _valid(true) { }
|
||
|
|
bool valid() const { return _valid; }
|
||
|
|
const T& value() const { return _value; }
|
||
|
|
private:
|
||
|
|
bool _valid;
|
||
|
|
T _value;
|
||
|
|
friend class LRUCache;
|
||
|
|
};
|
||
|
|
|
||
|
|
using Functor = std::function<void(const K&, const T&)>;
|
||
|
|
|
||
|
|
protected:
|
||
|
|
typedef typename std::list<K>::iterator lru_iter;
|
||
|
|
typedef typename std::list<K> lru_type;
|
||
|
|
typedef typename std::pair<T, lru_iter> map_value_type;
|
||
|
|
typedef typename std::unordered_map<K, map_value_type> map_type;
|
||
|
|
typedef typename map_type::iterator map_iter;
|
||
|
|
typedef typename map_type::const_iterator map_const_iter;
|
||
|
|
|
||
|
|
map_type _map;
|
||
|
|
lru_type _lru;
|
||
|
|
unsigned _max;
|
||
|
|
unsigned _buf;
|
||
|
|
unsigned _queries;
|
||
|
|
unsigned _hits;
|
||
|
|
bool _threadsafe;
|
||
|
|
mutable std::mutex _mutex;
|
||
|
|
|
||
|
|
public:
|
||
|
|
LRUCache( unsigned max =100 ) : _max(max), _threadsafe(false) {
|
||
|
|
_queries = 0;
|
||
|
|
_hits = 0;
|
||
|
|
setMaxSize_impl(max);
|
||
|
|
}
|
||
|
|
LRUCache( bool threadsafe, unsigned max =100 ) : _max(max), _threadsafe(threadsafe) {
|
||
|
|
_queries = 0;
|
||
|
|
_hits = 0;
|
||
|
|
setMaxSize_impl(max);
|
||
|
|
}
|
||
|
|
|
||
|
|
/** dtor */
|
||
|
|
virtual ~LRUCache() { }
|
||
|
|
|
||
|
|
void insert( const K& key, const T& value ) {
|
||
|
|
if ( _threadsafe ) {
|
||
|
|
std::lock_guard<std::mutex> lock(_mutex);
|
||
|
|
insert_impl( key, value );
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
insert_impl( key, value );
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
bool get( const K& key, Record& out ) {
|
||
|
|
if ( _threadsafe ) {
|
||
|
|
std::lock_guard<std::mutex> lock(_mutex);
|
||
|
|
get_impl( key, out );
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
get_impl( key, out );
|
||
|
|
}
|
||
|
|
return out.valid();
|
||
|
|
}
|
||
|
|
|
||
|
|
bool has( const K& key ) {
|
||
|
|
if ( _threadsafe ) {
|
||
|
|
std::lock_guard<std::mutex> lock(_mutex);
|
||
|
|
return has_impl( key );
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
return has_impl( key );
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void erase( const K& key ) {
|
||
|
|
if ( _threadsafe ) {
|
||
|
|
std::lock_guard<std::mutex> lock(_mutex);
|
||
|
|
erase_impl( key );
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
erase_impl( key );
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void clear() {
|
||
|
|
if ( _threadsafe ) {
|
||
|
|
std::lock_guard<std::mutex> lock(_mutex);
|
||
|
|
clear_impl();
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
clear_impl();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void setMaxSize( unsigned max ) {
|
||
|
|
if ( _threadsafe ) {
|
||
|
|
std::lock_guard<std::mutex> lock(_mutex);
|
||
|
|
setMaxSize_impl( max );
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
setMaxSize_impl( max );
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
unsigned getMaxSize() const {
|
||
|
|
return _max;
|
||
|
|
}
|
||
|
|
|
||
|
|
CacheStats getStats() const {
|
||
|
|
return CacheStats(
|
||
|
|
_map.size(), _max, _queries, _queries > 0 ? (float)_hits/(float)_queries : 0.0f );
|
||
|
|
}
|
||
|
|
|
||
|
|
void forEach(const Functor& functor) const {
|
||
|
|
if (_threadsafe) {
|
||
|
|
std::lock_guard<std::mutex> lock(_mutex);
|
||
|
|
iterate_impl(functor);
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
iterate_impl(functor);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
private:
|
||
|
|
|
||
|
|
void insert_impl( const K& key, const T& value ) {
|
||
|
|
map_iter mi = _map.find( key );
|
||
|
|
if ( mi != _map.end() ) {
|
||
|
|
_lru.erase( mi->second.second );
|
||
|
|
mi->second.first = value;
|
||
|
|
_lru.push_back( key );
|
||
|
|
mi->second.second = _lru.end();
|
||
|
|
mi->second.second--;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
_lru.push_back( key );
|
||
|
|
lru_iter last = _lru.end(); last--;
|
||
|
|
_map[key] = std::make_pair(value, last);
|
||
|
|
}
|
||
|
|
|
||
|
|
if ( _map.size() > _max ) {
|
||
|
|
for( unsigned i=0; i < _buf; ++i ) {
|
||
|
|
const K& key = _lru.front();
|
||
|
|
_map.erase( key );
|
||
|
|
_lru.pop_front();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void get_impl( const K& key, Record& result ) {
|
||
|
|
_queries++;
|
||
|
|
map_iter mi = _map.find( key );
|
||
|
|
if ( mi != _map.end() ) {
|
||
|
|
_lru.erase( mi->second.second );
|
||
|
|
_lru.push_back( key );
|
||
|
|
lru_iter new_iter = _lru.end(); new_iter--;
|
||
|
|
mi->second.second = new_iter;
|
||
|
|
_hits++;
|
||
|
|
result._value = mi->second.first;
|
||
|
|
result._valid = true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
bool has_impl( const K& key ) {
|
||
|
|
return _map.find( key ) != _map.end();
|
||
|
|
}
|
||
|
|
|
||
|
|
void erase_impl( const K& key ) {
|
||
|
|
map_iter mi = _map.find( key );
|
||
|
|
if ( mi != _map.end() ) {
|
||
|
|
_lru.erase( mi->second.second );
|
||
|
|
_map.erase( mi );
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void clear_impl() {
|
||
|
|
_lru.clear();
|
||
|
|
_map.clear();
|
||
|
|
_queries = 0;
|
||
|
|
_hits = 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
void setMaxSize_impl( unsigned max ) {
|
||
|
|
_max = osg::maximum(max,10u);
|
||
|
|
_buf = _max/10u;
|
||
|
|
while( _map.size() > _max ) {
|
||
|
|
const K& key = _lru.front();
|
||
|
|
_map.erase( key );
|
||
|
|
_lru.pop_front();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void iterate_impl(const Functor& func) const {
|
||
|
|
for (auto i : _map)
|
||
|
|
func(i.first, i.second.first);
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
//--------------------------------------------------------------------
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Same of osg::InlineVector, but with a superclass template parameter.
|
||
|
|
*/
|
||
|
|
template<class ValueT, class SuperClass>
|
||
|
|
class InlineVector : public SuperClass
|
||
|
|
{
|
||
|
|
typedef typename std::vector<ValueT> vector_type;
|
||
|
|
public:
|
||
|
|
typedef typename vector_type::allocator_type allocator_type;
|
||
|
|
typedef typename vector_type::value_type value_type;
|
||
|
|
typedef typename vector_type::const_pointer const_pointer;
|
||
|
|
typedef typename vector_type::pointer pointer;
|
||
|
|
typedef typename vector_type::const_reference const_reference;
|
||
|
|
typedef typename vector_type::reference reference;
|
||
|
|
typedef typename vector_type::const_iterator const_iterator;
|
||
|
|
typedef typename vector_type::iterator iterator;
|
||
|
|
typedef typename vector_type::const_reverse_iterator const_reverse_iterator;
|
||
|
|
typedef typename vector_type::reverse_iterator reverse_iterator;
|
||
|
|
typedef typename vector_type::size_type size_type;
|
||
|
|
typedef typename vector_type::difference_type difference_type;
|
||
|
|
|
||
|
|
explicit InlineVector() : _impl()
|
||
|
|
{
|
||
|
|
}
|
||
|
|
|
||
|
|
explicit InlineVector(size_type initial_size, const value_type& fill_value = value_type())
|
||
|
|
: _impl(initial_size, fill_value)
|
||
|
|
{
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class InputIterator>
|
||
|
|
InlineVector(InputIterator first, InputIterator last)
|
||
|
|
: _impl(first, last)
|
||
|
|
{
|
||
|
|
}
|
||
|
|
|
||
|
|
InlineVector(const vector_type& other)
|
||
|
|
: _impl(other)
|
||
|
|
{
|
||
|
|
}
|
||
|
|
|
||
|
|
InlineVector(const InlineVector& other)
|
||
|
|
: _impl(other._impl)
|
||
|
|
{
|
||
|
|
}
|
||
|
|
|
||
|
|
InlineVector& operator=(const vector_type& other)
|
||
|
|
{
|
||
|
|
_impl = other;
|
||
|
|
return *this;
|
||
|
|
}
|
||
|
|
|
||
|
|
InlineVector& operator=(const InlineVector& other)
|
||
|
|
{
|
||
|
|
_impl = other._impl;
|
||
|
|
return *this;
|
||
|
|
}
|
||
|
|
|
||
|
|
virtual ~InlineVector() {}
|
||
|
|
|
||
|
|
void clear() { _impl.clear(); }
|
||
|
|
void resize(size_type new_size, const value_type& fill_value = value_type()) { _impl.resize(new_size, fill_value); }
|
||
|
|
void reserve(size_type new_capacity) { _impl.reserve(new_capacity); }
|
||
|
|
|
||
|
|
void swap(vector_type& other) { _impl.swap(other); }
|
||
|
|
void swap(InlineVector& other) { _impl.swap(other._impl); }
|
||
|
|
|
||
|
|
bool empty() const { return _impl.empty(); }
|
||
|
|
size_type size() const { return _impl.size(); }
|
||
|
|
size_type capacity() const { return _impl.capacity(); }
|
||
|
|
size_type max_size() const { return _impl.max_size(); }
|
||
|
|
allocator_type get_allocator() const { return _impl.get_allocator(); }
|
||
|
|
|
||
|
|
const_iterator begin() const { return _impl.begin(); }
|
||
|
|
iterator begin() { return _impl.begin(); }
|
||
|
|
const_iterator end() const { return _impl.end(); }
|
||
|
|
iterator end() { return _impl.end(); }
|
||
|
|
|
||
|
|
const_reverse_iterator rbegin() const { return _impl.rbegin(); }
|
||
|
|
reverse_iterator rbegin() { return _impl.rbegin(); }
|
||
|
|
const_reverse_iterator rend() const { return _impl.rend(); }
|
||
|
|
reverse_iterator rend() { return _impl.rend(); }
|
||
|
|
|
||
|
|
const_reference operator[](size_type index) const { return _impl[index]; }
|
||
|
|
reference operator[](size_type index) { return _impl[index]; }
|
||
|
|
|
||
|
|
const_reference at(size_type index) const { return _impl.at(index); }
|
||
|
|
reference at(size_type index) { return _impl.at(index); }
|
||
|
|
|
||
|
|
void assign(size_type count, const value_type& value) { _impl.assign(count, value); }
|
||
|
|
template<class Iter>
|
||
|
|
void assign(Iter first, Iter last) { _impl.assign(first, last); }
|
||
|
|
|
||
|
|
void push_back(const value_type& value) { _impl.push_back(value); }
|
||
|
|
void pop_back() { _impl.pop_back(); }
|
||
|
|
|
||
|
|
iterator erase(iterator where) { return _impl.erase(where); }
|
||
|
|
iterator erase(iterator first, iterator last) { return _impl.erase(first, last); }
|
||
|
|
|
||
|
|
iterator insert(iterator where, const value_type& value) { return _impl.insert(where, value); }
|
||
|
|
|
||
|
|
template<class InputIterator>
|
||
|
|
void insert(iterator where, InputIterator first, InputIterator last)
|
||
|
|
{
|
||
|
|
_impl.insert(where, first, last);
|
||
|
|
}
|
||
|
|
|
||
|
|
void insert(iterator where, size_type count, const value_type& value)
|
||
|
|
{
|
||
|
|
_impl.insert(where, count, value);
|
||
|
|
}
|
||
|
|
|
||
|
|
const_reference back() const { return _impl.back(); }
|
||
|
|
reference back() { return _impl.back(); }
|
||
|
|
const_reference front() const { return _impl.front(); }
|
||
|
|
reference front() { return _impl.front(); }
|
||
|
|
|
||
|
|
vector_type& asVector() { return _impl; }
|
||
|
|
const vector_type& asVector() const { return _impl; }
|
||
|
|
|
||
|
|
friend inline bool operator==(const InlineVector<ValueT,SuperClass>& left, const InlineVector<ValueT,SuperClass>& right) { return left._impl == right._impl; }
|
||
|
|
friend inline bool operator==(const InlineVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl == right; }
|
||
|
|
friend inline bool operator==(const std::vector<ValueT>& left, const InlineVector<ValueT,SuperClass>& right) { return left == right._impl; }
|
||
|
|
|
||
|
|
friend inline bool operator!=(const InlineVector<ValueT,SuperClass>& left, const InlineVector<ValueT,SuperClass>& right) { return left._impl != right._impl; }
|
||
|
|
friend inline bool operator!=(const InlineVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl != right; }
|
||
|
|
friend inline bool operator!=(const std::vector<ValueT>& left, const InlineVector<ValueT,SuperClass>& right) { return left != right._impl; }
|
||
|
|
|
||
|
|
friend inline bool operator<(const InlineVector<ValueT,SuperClass>& left, const InlineVector<ValueT,SuperClass>& right) { return left._impl < right._impl; }
|
||
|
|
friend inline bool operator<(const InlineVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl < right; }
|
||
|
|
friend inline bool operator<(const std::vector<ValueT>& left, const InlineVector<ValueT,SuperClass>& right) { return left < right._impl; }
|
||
|
|
|
||
|
|
friend inline bool operator>(const InlineVector<ValueT,SuperClass>& left, const InlineVector<ValueT,SuperClass>& right) { return left._impl > right._impl; }
|
||
|
|
friend inline bool operator>(const InlineVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl > right; }
|
||
|
|
friend inline bool operator>(const std::vector<ValueT>& left, const InlineVector<ValueT,SuperClass>& right) { return left > right._impl; }
|
||
|
|
|
||
|
|
friend inline bool operator<=(const InlineVector<ValueT,SuperClass>& left, const InlineVector<ValueT,SuperClass>& right) { return left._impl <= right._impl; }
|
||
|
|
friend inline bool operator<=(const InlineVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl <= right; }
|
||
|
|
friend inline bool operator<=(const std::vector<ValueT>& left, const InlineVector<ValueT,SuperClass>& right) { return left <= right._impl; }
|
||
|
|
|
||
|
|
friend inline bool operator>=(const InlineVector<ValueT,SuperClass>& left, const InlineVector<ValueT,SuperClass>& right) { return left._impl >= right._impl; }
|
||
|
|
friend inline bool operator>=(const InlineVector<ValueT,SuperClass>& left, const std::vector<ValueT>& right) { return left._impl >= right; }
|
||
|
|
friend inline bool operator>=(const std::vector<ValueT>& left, const InlineVector<ValueT,SuperClass>& right) { return left >= right._impl; }
|
||
|
|
|
||
|
|
private:
|
||
|
|
vector_type _impl;
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
/** Template for per-thread data storage */
|
||
|
|
template<typename T>
|
||
|
|
struct PerThread : public std::mutex
|
||
|
|
{
|
||
|
|
PerThread() { }
|
||
|
|
|
||
|
|
T& get() {
|
||
|
|
std::lock_guard<std::mutex> lock(*this);
|
||
|
|
return _data[std::this_thread::get_id()];
|
||
|
|
}
|
||
|
|
|
||
|
|
void clear() {
|
||
|
|
std::lock_guard<std::mutex> lock(*this);
|
||
|
|
_data.clear();
|
||
|
|
}
|
||
|
|
|
||
|
|
typedef typename std::unordered_map<std::thread::id,T> container_t;
|
||
|
|
typedef typename container_t::iterator iterator;
|
||
|
|
|
||
|
|
// NB. lock before using these!
|
||
|
|
iterator begin() { return _data.begin(); }
|
||
|
|
iterator end() { return _data.end(); }
|
||
|
|
|
||
|
|
private:
|
||
|
|
container_t _data;
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
/** Template for thread safe per-object data storage */
|
||
|
|
template<typename KEY, typename DATA>
|
||
|
|
struct PerObjectMap
|
||
|
|
{
|
||
|
|
PerObjectMap() { }
|
||
|
|
bool threadsafe = true;
|
||
|
|
|
||
|
|
DATA& get(KEY k)
|
||
|
|
{
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedReadLock readLock(_mutex);
|
||
|
|
typename std::unordered_map<KEY,DATA>::iterator i = _data.find(k);
|
||
|
|
if ( i != _data.end() )
|
||
|
|
return i->second;
|
||
|
|
}
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedWriteLock lock(_mutex);
|
||
|
|
typename std::unordered_map<KEY,DATA>::iterator i = _data.find(k);
|
||
|
|
if ( i != _data.end() )
|
||
|
|
return i->second;
|
||
|
|
else
|
||
|
|
return _data[k];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void remove(KEY k)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedWriteLock exclusive(_mutex);
|
||
|
|
_data.erase( k );
|
||
|
|
}
|
||
|
|
|
||
|
|
private:
|
||
|
|
std::unordered_map<KEY,DATA> _data;
|
||
|
|
osgEarth::Threading::ReadWriteMutex _mutex;
|
||
|
|
};
|
||
|
|
|
||
|
|
/** Template for thread safe per-object data storage */
|
||
|
|
template<typename KEY, typename DATA>
|
||
|
|
struct PerObjectFastMap
|
||
|
|
{
|
||
|
|
PerObjectFastMap() { }
|
||
|
|
bool threadsafe = true;
|
||
|
|
|
||
|
|
struct Functor {
|
||
|
|
virtual void operator()(DATA& data) =0;
|
||
|
|
};
|
||
|
|
|
||
|
|
struct ConstFunctor {
|
||
|
|
virtual void operator()(const DATA& data) const =0;
|
||
|
|
};
|
||
|
|
|
||
|
|
DATA& get(KEY k)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
typename std::unordered_map<KEY,DATA>::iterator i = _data.find(k);
|
||
|
|
if ( i != _data.end() )
|
||
|
|
return i->second;
|
||
|
|
else
|
||
|
|
return _data[k];
|
||
|
|
}
|
||
|
|
|
||
|
|
void remove(KEY k)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
_data.erase( k );
|
||
|
|
}
|
||
|
|
|
||
|
|
void forEach(Functor& functor)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
for (typename std::unordered_map<KEY, DATA>::iterator i = _data.begin(); i != _data.end(); ++i)
|
||
|
|
functor.operator()(i->second);
|
||
|
|
}
|
||
|
|
|
||
|
|
void forEach(std::function<void(DATA&)> functor)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
for (auto& entry : _data)
|
||
|
|
functor(entry.second);
|
||
|
|
}
|
||
|
|
|
||
|
|
void forEach(ConstFunctor& functor) const
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
for (typename std::unordered_map<KEY, DATA>::const_iterator i = _data.begin(); i != _data.end(); ++i)
|
||
|
|
functor.operator()(i->second);
|
||
|
|
}
|
||
|
|
|
||
|
|
void forEach(std::function<void(const DATA&)> functor) const
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
for (auto& entry : _data)
|
||
|
|
functor(entry.second);
|
||
|
|
}
|
||
|
|
|
||
|
|
unsigned size() const
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
return _data.size();
|
||
|
|
}
|
||
|
|
|
||
|
|
void clear()
|
||
|
|
{
|
||
|
|
osgEarth::Threading::scoped_lock_if lock(_mutex, threadsafe);
|
||
|
|
_data.clear();
|
||
|
|
}
|
||
|
|
|
||
|
|
private:
|
||
|
|
std::unordered_map<KEY,DATA> _data;
|
||
|
|
mutable std::mutex _mutex;
|
||
|
|
};
|
||
|
|
|
||
|
|
/** Template for thread safe per-object data storage */
|
||
|
|
template<typename KEY, typename DATA>
|
||
|
|
struct PerObjectRefMap
|
||
|
|
{
|
||
|
|
PerObjectRefMap() { }
|
||
|
|
|
||
|
|
DATA* get(KEY k)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedReadLock lock(_mutex);
|
||
|
|
typename std::unordered_map<KEY,osg::ref_ptr<DATA>>::const_iterator i = _data.find(k);
|
||
|
|
if ( i != _data.end() )
|
||
|
|
return i->second.get();
|
||
|
|
|
||
|
|
return 0L;
|
||
|
|
}
|
||
|
|
|
||
|
|
DATA* getOrCreate(KEY k, DATA* newDataIfNeeded)
|
||
|
|
{
|
||
|
|
osg::ref_ptr<DATA> _refReleaser = newDataIfNeeded;
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedReadLock lock(_mutex);
|
||
|
|
typename std::unordered_map<KEY,osg::ref_ptr<DATA>>::const_iterator i = _data.find(k);
|
||
|
|
if ( i != _data.end() )
|
||
|
|
return i->second.get();
|
||
|
|
}
|
||
|
|
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedWriteLock lock(_mutex);
|
||
|
|
typename std::unordered_map<KEY,osg::ref_ptr<DATA>>::iterator i = _data.find(k);
|
||
|
|
if ( i != _data.end() )
|
||
|
|
return i->second.get();
|
||
|
|
|
||
|
|
_data[k] = newDataIfNeeded;
|
||
|
|
return newDataIfNeeded;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void remove(KEY k)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedWriteLock exclusive(_mutex);
|
||
|
|
_data.erase( k );
|
||
|
|
}
|
||
|
|
|
||
|
|
void remove(DATA* data)
|
||
|
|
{
|
||
|
|
osgEarth::Threading::ScopedWriteLock exclusive(_mutex);
|
||
|
|
for( typename std::unordered_map<KEY,osg::ref_ptr<DATA>>::iterator i = _data.begin(); i != _data.end(); ++i )
|
||
|
|
{
|
||
|
|
if ( i->second.get() == data )
|
||
|
|
{
|
||
|
|
_data.erase( i );
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
private:
|
||
|
|
std::unordered_map<KEY,osg::ref_ptr<DATA>> _data;
|
||
|
|
osgEarth::Threading::ReadWriteMutex _mutex;
|
||
|
|
};
|
||
|
|
|
||
|
|
// borrowed from osg::buffered_object. Auto-resizing array.
|
||
|
|
template<class T>
|
||
|
|
class AutoArray
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
using iterator = typename std::vector<T>::iterator;
|
||
|
|
using const_iterator = typename std::vector<T>::const_iterator;
|
||
|
|
|
||
|
|
inline AutoArray() { }
|
||
|
|
|
||
|
|
inline AutoArray(unsigned int size) : _array(size) { }
|
||
|
|
|
||
|
|
AutoArray& operator = (const AutoArray& rhs)
|
||
|
|
{
|
||
|
|
_array = rhs._array;
|
||
|
|
return *this;
|
||
|
|
}
|
||
|
|
|
||
|
|
inline void setAllElementsTo(const T& t) { std::fill(_array.begin(), _array.end(), t); }
|
||
|
|
inline void clear() { _array.clear(); }
|
||
|
|
inline bool empty() const { return _array.empty(); }
|
||
|
|
inline unsigned int size() const { return _array.size(); }
|
||
|
|
inline void resize(unsigned int newSize) { _array.resize(newSize); }
|
||
|
|
|
||
|
|
inline iterator begin() { return _array.begin(); }
|
||
|
|
inline const_iterator begin() const { return _array.begin(); }
|
||
|
|
inline iterator end() { return _array.end(); }
|
||
|
|
inline const_iterator end() const { return _array.end(); }
|
||
|
|
|
||
|
|
inline T& operator[] (unsigned int pos)
|
||
|
|
{
|
||
|
|
if (_array.size() <= pos)
|
||
|
|
_array.resize(pos + 1);
|
||
|
|
|
||
|
|
return _array[pos];
|
||
|
|
}
|
||
|
|
|
||
|
|
inline const T& operator[] (unsigned int pos) const
|
||
|
|
{
|
||
|
|
// automatically resize array.
|
||
|
|
if (_array.size() <= pos)
|
||
|
|
_array.resize(pos + 1);
|
||
|
|
|
||
|
|
return _array[pos];
|
||
|
|
}
|
||
|
|
|
||
|
|
inline T& back() { return _array[size()-1]; }
|
||
|
|
inline const T& back() const { return _array[size()-1]; }
|
||
|
|
|
||
|
|
protected:
|
||
|
|
|
||
|
|
mutable std::vector<T> _array;
|
||
|
|
};
|
||
|
|
|
||
|
|
// A generic osg::Referenced vector
|
||
|
|
template<typename T>
|
||
|
|
class RefVector : public InlineVector<T, osg::Referenced>
|
||
|
|
{
|
||
|
|
};
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Thread-safe queue.
|
||
|
|
*/
|
||
|
|
template<typename T>
|
||
|
|
class MutexedQueue
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
//! Push a new item safely
|
||
|
|
void push(const T& t) {
|
||
|
|
std::lock_guard<std::mutex> lock(_m);
|
||
|
|
_queue.push(t);
|
||
|
|
}
|
||
|
|
//! Remove the front item safely
|
||
|
|
void pop() {
|
||
|
|
std::lock_guard<std::mutex> lock(_m);
|
||
|
|
_queue.pop();
|
||
|
|
}
|
||
|
|
//! Safely return a copy of the item at the head of
|
||
|
|
//! the queue
|
||
|
|
T front() {
|
||
|
|
std::lock_guard<std::mutex> lock(_m);
|
||
|
|
return _queue.empty() ? _default : _queue.front();
|
||
|
|
}
|
||
|
|
//! Safely remove the item at the head of the queue
|
||
|
|
//! and return it
|
||
|
|
T take_front() {
|
||
|
|
std::lock_guard<std::mutex> lock(_m);
|
||
|
|
T t = _queue.empty() ? _default : _queue.front();
|
||
|
|
if (_queue.empty() == false)
|
||
|
|
_queue.pop();
|
||
|
|
return t;
|
||
|
|
}
|
||
|
|
//! Safely clear the queue
|
||
|
|
void clear() {
|
||
|
|
std::lock_guard<std::mutex> lock(_m);
|
||
|
|
_queue.swap(std::queue<T>());
|
||
|
|
}
|
||
|
|
//! True if the queue is empty (but only at the
|
||
|
|
//! instant of the call.)
|
||
|
|
bool empty() const {
|
||
|
|
return _queue.empty();
|
||
|
|
}
|
||
|
|
|
||
|
|
private:
|
||
|
|
std::queue<T> _queue;
|
||
|
|
mutable std::mutex _m;
|
||
|
|
T _default;
|
||
|
|
};
|
||
|
|
|
||
|
|
/**
|
||
|
|
* A circular list that you can pull pointers from
|
||
|
|
* NOT thread safe.
|
||
|
|
*/
|
||
|
|
template<typename T>
|
||
|
|
class OSGEARTH_EXPORT RoundRobin {
|
||
|
|
public:
|
||
|
|
using iterator = typename std::list<T>::iterator;
|
||
|
|
using const_iterator = typename std::list<T>::const_iterator;
|
||
|
|
|
||
|
|
void add(const T& t) {
|
||
|
|
_list.push_back(t);
|
||
|
|
if (_list.size() == 1)
|
||
|
|
_iter = begin();
|
||
|
|
}
|
||
|
|
T next() {
|
||
|
|
OE_HARD_ASSERT(_list.size() > 0);
|
||
|
|
T t = *_iter++;
|
||
|
|
if (_iter == end()) _iter = begin();
|
||
|
|
return t;
|
||
|
|
}
|
||
|
|
iterator begin() {
|
||
|
|
return _list.begin();
|
||
|
|
}
|
||
|
|
const_iterator begin() const {
|
||
|
|
return _list.begin();
|
||
|
|
}
|
||
|
|
iterator end() {
|
||
|
|
return _list.end();
|
||
|
|
}
|
||
|
|
const_iterator end() const {
|
||
|
|
return _list.end();
|
||
|
|
}
|
||
|
|
bool empty() const {
|
||
|
|
return _list.empty();
|
||
|
|
}
|
||
|
|
private:
|
||
|
|
std::list<T> _list;
|
||
|
|
iterator _iter;
|
||
|
|
};
|
||
|
|
} }
|