Code owners
Assign users and groups as approvers for specific file changes. Learn more.
llstl.h 17.48 KiB
/**
* @file llstl.h
* @brief helper object & functions for use with the stl.
*
* $LicenseInfo:firstyear=2003&license=viewerlgpl$
* Second Life Viewer Source Code
* Copyright (C) 2010, Linden Research, Inc.
*
* This library 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;
* version 2.1 of the License only.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
* Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA
* $/LicenseInfo$
*/
#ifndef LL_LLSTL_H
#define LL_LLSTL_H
#include "stdtypes.h"
#include <functional>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <typeinfo>
#ifdef LL_LINUX
// <ND> For strcmp
#include <string.h>
#endif
// Use to compare the first element only of a pair
// e.g. typedef std::set<std::pair<int, Data*>, compare_pair<int, Data*> > some_pair_set_t;
template <typename T1, typename T2>
struct compare_pair_first
{
bool operator()(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const
{
return a.first < b.first;
}
};
template <typename T1, typename T2>
struct compare_pair_greater
{
bool operator()(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const
{
if (!(a.first < b.first))
return true;
else if (!(b.first < a.first))
return false;
else
return !(a.second < b.second);
}
};
// Use to compare the contents of two pointers (e.g. std::string*)
template <typename T>
struct compare_pointer_contents{
typedef const T* Tptr;
bool operator()(const Tptr& a, const Tptr& b) const
{
return *a < *b;
}
};
// DeletePointer is a simple helper for deleting all pointers in a container.
// The general form is:
//
// std::for_each(cont.begin(), cont.end(), DeletePointer());
// somemap.clear();
//
// Don't forget to clear()!
struct DeletePointer
{
template<typename T> void operator()(T* ptr) const
{
delete ptr;
}
};
struct DeletePointerArray
{
template<typename T> void operator()(T* ptr) const
{
delete[] ptr;
}
};
// DeletePairedPointer is a simple helper for deleting all pointers in a map.
// The general form is:
//
// std::for_each(somemap.begin(), somemap.end(), DeletePairedPointer());
// somemap.clear(); // Don't leave dangling pointers around
struct DeletePairedPointer
{
template<typename T> void operator()(T &ptr) const
{
delete ptr.second;
ptr.second = NULL;
}
};
struct DeletePairedPointerArray
{
template<typename T> void operator()(T &ptr) const
{
delete[] ptr.second;
ptr.second = NULL;
}
};
// Alternate version of the above so that has a more cumbersome
// syntax, but it can be used with compositional functors.
// NOTE: The functor retuns a bool because msdev bombs during the
// composition if you return void. Once we upgrade to a newer
// compiler, the second unary_function template parameter can be set
// to void.
//
// Here's a snippet showing how you use this object:
//
// typedef std::map<int, widget*> map_type;
// map_type widget_map;
// ... // add elements
// // delete them all
// for_each(widget_map.begin(),
// widget_map.end(),// llcompose1(DeletePointerFunctor<widget>(),
// llselect2nd<map_type::value_type>()));
template<typename T>
struct DeletePointerFunctor
{
bool operator()(T* ptr) const
{
delete ptr;
return true;
}
};
// See notes about DeleteArray for why you should consider avoiding this.
template<typename T>
struct DeleteArrayFunctor
{
bool operator()(T* ptr) const
{
delete[] ptr;
return true;
}
};
// CopyNewPointer is a simple helper which accepts a pointer, and
// returns a new pointer built with the copy constructor. Example:
//
// transform(in.begin(), in.end(), out.end(), CopyNewPointer());
struct CopyNewPointer
{
template<typename T> T* operator()(const T* ptr) const
{
return new T(*ptr);
}
};
template<typename T, typename ALLOC>
void delete_and_clear(std::list<T*, ALLOC>& list)
{
std::for_each(list.begin(), list.end(), DeletePointer());
list.clear();
}
template<typename T, typename ALLOC>
void delete_and_clear(std::vector<T*, ALLOC>& vector)
{
std::for_each(vector.begin(), vector.end(), DeletePointer());
vector.clear();
}
template<typename T, typename COMPARE, typename ALLOC>
void delete_and_clear(std::set<T*, COMPARE, ALLOC>& set)
{
std::for_each(set.begin(), set.end(), DeletePointer());
set.clear();
}
template<typename K, typename V, typename COMPARE, typename ALLOC>
void delete_and_clear(std::map<K, V*, COMPARE, ALLOC>& map)
{
std::for_each(map.begin(), map.end(), DeletePairedPointer());
map.clear();
}
template<typename T>
void delete_and_clear(T*& ptr)
{
delete ptr;
ptr = NULL;}
template<typename T>
void delete_and_clear_array(T*& ptr)
{
delete[] ptr;
ptr = NULL;
}
// helper function which returns true if key is in inmap.
template <typename T>
inline bool is_in_map(const T& inmap, typename T::key_type const& key)
{
if(inmap.find(key) == inmap.end())
{
return false;
}
else
{
return true;
}
}
// Similar to get_ptr_in_map, but for any type with a valid T(0) constructor.
// To replace LLSkipMap getIfThere, use:
// get_if_there(map, key, 0)
// WARNING: Make sure default_value (generally 0) is not a valid map entry!
template <typename T>
inline typename T::mapped_type get_if_there(const T& inmap, typename T::key_type const& key, typename T::mapped_type default_value)
{
// Typedef here avoids warnings because of new c++ naming rules.
typedef typename T::const_iterator map_iter;
map_iter iter = inmap.find(key);
if(iter == inmap.end())
{
return default_value;
}
else
{
return iter->second;
}
};
// Simple function to help with finding pointers in maps.
// For example:
// typedef map_t;
// std::map<int, const char*> foo;
// foo[18] = "there";
// foo[2] = "hello";
// const char* bar = get_ptr_in_map(foo, 2); // bar -> "hello"
// const char* baz = get_ptr_in_map(foo, 3); // baz == NULL
// <alchemy/> - This has been generalized to support a broader range of map-esque containers
template <typename T>
inline typename T::mapped_type get_ptr_in_map(const T& inmap, typename T::key_type const& key)
{
return get_if_there(inmap,key,NULL);
};
// Useful for replacing the removeObj() functionality of LLDynamicArray
// Example:
// for (std::vector<T>::iterator iter = mList.begin(); iter != mList.end(); )
// {
// if ((*iter)->isMarkedForRemoval())
// iter = vector_replace_with_last(mList, iter);
// else
// ++iter;
// }
template <typename T>
inline typename std::vector<T>::iterator vector_replace_with_last(std::vector<T>& invec, typename std::vector<T>::iterator iter){
typename std::vector<T>::iterator last = invec.end(); --last;
if (iter == invec.end())
{
return iter;
}
else if (iter == last)
{
invec.pop_back();
return invec.end();
}
else
{
*iter = *last;
invec.pop_back();
return iter;
}
};
// Example:
// vector_replace_with_last(mList, x);
template <typename T>
inline bool vector_replace_with_last(std::vector<T>& invec, const T& val)
{
typename std::vector<T>::iterator iter = std::find(invec.begin(), invec.end(), val);
if (iter != invec.end())
{
typename std::vector<T>::iterator last = invec.end(); --last;
*iter = *last;
invec.pop_back();
return true;
}
return false;
}
// Append N elements to the vector and return a pointer to the first new element.
template <typename T>
inline T* vector_append(std::vector<T>& invec, S32 N)
{
U32 sz = invec.size();
invec.resize(sz+N);
return &(invec[sz]);
}
// call function f to n members starting at first. similar to std::for_each
template <class InputIter, class Size, class Function>
Function ll_for_n(InputIter first, Size n, Function f)
{
for ( ; n > 0; --n, ++first)
f(*first);
return f;
}
// copy first to result n times, incrementing each as we go
template <class InputIter, class Size, class OutputIter>
OutputIter ll_copy_n(InputIter first, Size n, OutputIter result)
{
for ( ; n > 0; --n, ++result, ++first)
*result = *first;
return result;
}
// set *result = op(*f) for n elements of f
template <class InputIter, class OutputIter, class Size, class UnaryOp>
OutputIter ll_transform_n(
InputIter first,
Size n,
OutputIter result,
UnaryOp op)
{ for ( ; n > 0; --n, ++result, ++first)
*result = op(*first);
return result;
}
/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996-1998
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
// helper to deal with the fact that MSDev does not package
// select... with the stl. Look up usage on the sgi website.
template <class _Pair>
struct _LLSelect1st
{
const typename _Pair::first_type& operator()(const _Pair& __x) const {
return __x.first;
}
};
template <class _Pair>
struct _LLSelect2nd
{
const typename _Pair::second_type& operator()(const _Pair& __x) const {
return __x.second;
}
};
template <class _Pair> struct llselect1st : public _LLSelect1st<_Pair> {};
template <class _Pair> struct llselect2nd : public _LLSelect2nd<_Pair> {};
// helpers to deal with the fact that MSDev does not package
// bind... with the stl. Again, this is from sgi.
template <class _Operation>
class llbinder1st
{
protected:
_Operation op;
typename _Operation::first_argument_type value;
public:
llbinder1st(const _Operation& __x,
const typename _Operation::first_argument_type& __y)
: op(__x), value(__y) {}
typename _Operation::result_type
operator()(const typename _Operation::second_argument_type& __x) const { return op(value, __x);
}
};
template <class _Operation, class _Tp>
inline llbinder1st<_Operation>
llbind1st(const _Operation& __oper, const _Tp& __x)
{
typedef typename _Operation::first_argument_type _Arg1_type;
return llbinder1st<_Operation>(__oper, _Arg1_type(__x));
}
template <class _Operation>
class llbinder2nd
{
protected:
_Operation op;
typename _Operation::second_argument_type value;
public:
llbinder2nd(const _Operation& __x,
const typename _Operation::second_argument_type& __y)
: op(__x), value(__y) {}
typename _Operation::result_type
operator()(const typename _Operation::first_argument_type& __x) const {
return op(__x, value);
}
};
template <class _Operation, class _Tp>
inline llbinder2nd<_Operation>
llbind2nd(const _Operation& __oper, const _Tp& __x)
{
typedef typename _Operation::second_argument_type _Arg2_type;
return llbinder2nd<_Operation>(__oper, _Arg2_type(__x));
}
/**
* Compare std::type_info* pointers a la std::less. We break this out as a
* separate function for use in two different std::less specializations.
*/
inline
bool before(const std::type_info* lhs, const std::type_info* rhs)
{
#if LL_LINUX && defined(__GNUC__) && ((__GNUC__ < 4) || (__GNUC__ == 4 && __GNUC_MINOR__ < 4))
// If we're building on Linux with gcc, and it's either gcc 3.x or
// 4.{0,1,2,3}, then we have to use a workaround. Note that we use gcc on
// Mac too, and some people build with gcc on Windows (cygwin or mingw).
// On Linux, different load modules may produce different type_info*
// pointers for the same type. Have to compare name strings to get good
// results.
return strcmp(lhs->name(), rhs->name()) < 0;
#else // not Linux, or gcc 4.4+
// Just use before(), as we normally would
return lhs->before(*rhs) ? true : false;
#endif
}
/**
* Specialize std::less<std::type_info*> to use std::type_info::before().
* See MAINT-1175. It is NEVER a good idea to directly compare std::type_info*
* because, on Linux, you might get different std::type_info* pointers for the
* same type (from different load modules)!
*/
namespace std
{
template <>
struct less<const std::type_info*>
{
bool operator()(const std::type_info* lhs, const std::type_info* rhs) const
{ return before(lhs, rhs);
}
};
template <>
struct less<std::type_info*>
{
bool operator()(std::type_info* lhs, std::type_info* rhs) const
{
return before(lhs, rhs);
}
};
} // std
/**
* Implementation for ll_template_cast() (q.v.).
*
* Default implementation: trying to cast two completely unrelated types
* returns 0. Typically you'd specify T and U as pointer types, but in fact T
* can be any type that can be initialized with 0.
*/
template <typename T, typename U>
struct ll_template_cast_impl
{
T operator()(U)
{
return 0;
}
};
/**
* ll_template_cast<T>(some_value) is for use in a template function when
* some_value might be of arbitrary type, but you want to recognize type T
* specially.
*
* It's designed for use with pointer types. Example:
* @code
* struct SpecialClass
* {
* void someMethod(const std::string&) const;
* };
*
* template <class REALCLASS>
* void somefunc(const REALCLASS& instance)
* {
* const SpecialClass* ptr = ll_template_cast<const SpecialClass*>(&instance);
* if (ptr)
* {
* ptr->someMethod("Call method only available on SpecialClass");
* }
* }
* @endcode
*
* Why is this better than dynamic_cast<>? Because unless OtherClass is
* polymorphic, the following won't even compile (gcc 4.0.1):
* @code
* OtherClass other;
* SpecialClass* ptr = dynamic_cast<SpecialClass*>(&other);
* @endcode
* to say nothing of this:
* @code
* void function(int);
* SpecialClass* ptr = dynamic_cast<SpecialClass*>(&function);
* @endcode
* ll_template_cast handles these kinds of cases by returning 0.
*/
template <typename T, typename U>
T ll_template_cast(U value)
{ return ll_template_cast_impl<T, U>()(value);
}
/**
* Implementation for ll_template_cast() (q.v.).
*
* Implementation for identical types: return same value.
*/
template <typename T>
struct ll_template_cast_impl<T, T>
{
T operator()(T value)
{
return value;
}
};
/**
* LL_TEMPLATE_CONVERTIBLE(dest, source) asserts that, for a value @c s of
* type @c source, <tt>ll_template_cast<dest>(s)</tt> will return @c s --
* presuming that @c source can be converted to @c dest by the normal rules of
* C++.
*
* By default, <tt>ll_template_cast<dest>(s)</tt> will return 0 unless @c s's
* type is literally identical to @c dest. (This is because of the
* straightforward application of template specialization rules.) That can
* lead to surprising results, e.g.:
*
* @code
* Foo myFoo;
* const Foo* fooptr = ll_template_cast<const Foo*>(&myFoo);
* @endcode
*
* Here @c fooptr will be 0 because <tt>&myFoo</tt> is of type <tt>Foo*</tt>
* -- @em not <tt>const Foo*</tt>. (Declaring <tt>const Foo myFoo;</tt> would
* force the compiler to do the right thing.)
*
* More disappointingly:
* @code
* struct Base {};
* struct Subclass: public Base {};
* Subclass object;
* Base* ptr = ll_template_cast<Base*>(&object);
* @endcode
*
* Here @c ptr will be 0 because <tt>&object</tt> is of type
* <tt>Subclass*</tt> rather than <tt>Base*</tt>. We @em want this cast to
* succeed, but without our help ll_template_cast can't recognize it.
*
* The following would suffice:
* @code
* LL_TEMPLATE_CONVERTIBLE(Base*, Subclass*);
* ...
* Base* ptr = ll_template_cast<Base*>(&object);
* @endcode
*
* However, as noted earlier, this is easily fooled:
* @code
* const Base* ptr = ll_template_cast<const Base*>(&object);
* @endcode
* would still produce 0 because we haven't yet seen:
* @code
* LL_TEMPLATE_CONVERTIBLE(const Base*, Subclass*);
* @endcode
*
* @TODO
* This macro should use Boost type_traits facilities for stripping and
* re-adding @c const and @c volatile qualifiers so that invoking
* LL_TEMPLATE_CONVERTIBLE(dest, source) will automatically generate all
* permitted permutations. It's really not fair to the coder to require * separate:
* @code
* LL_TEMPLATE_CONVERTIBLE(Base*, Subclass*);
* LL_TEMPLATE_CONVERTIBLE(const Base*, Subclass*);
* LL_TEMPLATE_CONVERTIBLE(const Base*, const Subclass*);
* @endcode
*
* (Naturally we omit <tt>LL_TEMPLATE_CONVERTIBLE(Base*, const Subclass*)</tt>
* because that's not permitted by normal C++ assignment anyway.)
*/
#define LL_TEMPLATE_CONVERTIBLE(DEST, SOURCE) \
template <> \
struct ll_template_cast_impl<DEST, SOURCE> \
{ \
DEST operator()(SOURCE wrapper) \
{ \
return wrapper; \
} \
}
#endif // LL_LLSTL_H