You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@openoffice.apache.org by hd...@apache.org on 2013/12/12 09:50:56 UTC
svn commit: r1550375 - in /openoffice/trunk/main/binaryurp/source: cache.hxx
lessoperators.cxx lessoperators.hxx
Author: hdu
Date: Thu Dec 12 08:50:55 2013
New Revision: 1550375
URL: http://svn.apache.org/r1550375
Log:
#i122208# replace the binaryurp cache for improved C++ compatibility
The C++ standards allows that the instantiation of incomplete types fails. The
Map::iterator in binaryurp Cache's Entry members had this problem. This rewrite
makes the code work with all compliant C++ compilers/STLs such as clang/libc++.
A Cache variant using an unordered_map is also provided and may be faster.
An interesting alternative would be to use boost's multi_index_container.
Modified:
openoffice/trunk/main/binaryurp/source/cache.hxx
openoffice/trunk/main/binaryurp/source/lessoperators.cxx
openoffice/trunk/main/binaryurp/source/lessoperators.hxx
Modified: openoffice/trunk/main/binaryurp/source/cache.hxx
URL: http://svn.apache.org/viewvc/openoffice/trunk/main/binaryurp/source/cache.hxx?rev=1550375&r1=1550374&r2=1550375&view=diff
==============================================================================
--- openoffice/trunk/main/binaryurp/source/cache.hxx (original)
+++ openoffice/trunk/main/binaryurp/source/cache.hxx Thu Dec 12 08:50:55 2013
@@ -27,7 +27,12 @@
#include "sal/config.h"
#include <cstddef>
-#include <map>
+#include <list>
+#ifdef USE_UNORDERED_MAP
+ #include <unordered_map>
+#else
+ #include <map>
+#endif
#include "boost/noncopyable.hpp"
#include "osl/diagnose.h"
@@ -41,90 +46,66 @@ enum { size = 256, ignore = 0xFFFF };
}
-template< typename T > class Cache: private boost::noncopyable {
+template< typename T > class Cache : private boost::noncopyable {
public:
+ typedef sal_uInt16 IdxType;
+
explicit Cache(std::size_t size):
- size_(size), first_(map_.end()), last_(map_.end())
+ size_(size)
{
OSL_ASSERT(size < cache::ignore);
}
- sal_uInt16 add(T const & content, bool * found) {
- OSL_ASSERT(found != 0);
- typename Map::iterator i(map_.find(content));
- *found = i != map_.end();
- if (i == map_.end()) {
- typename Map::size_type n = map_.size();
- if (n < size_) {
- i =
- (map_.insert(
- typename Map::value_type(
- content,
- Entry(
- static_cast< sal_uInt16 >(n), map_.end(),
- first_)))).
- first;
- if (first_ == map_.end()) {
- last_ = i;
- } else {
- first_->second.prev = i;
- }
- first_ = i;
- } else if (last_ != map_.end()) {
- i =
- (map_.insert(
- typename Map::value_type(
- content,
- Entry(last_->second.index, map_.end(), first_)))).
- first;
- first_->second.prev = i;
- first_ = i;
- typename Map::iterator j(last_);
- last_ = last_->second.prev;
- last_->second.next = map_.end();
- map_.erase(j);
- } else {
- // Reached iff size_ == 0:
- return cache::ignore;
- }
- } else if (i != first_) {
- // Move to front (reached only if size_ > 1):
- i->second.prev->second.next = i->second.next;
- if (i->second.next == map_.end()) {
- last_ = i->second.prev;
- } else {
- i->second.next->second.prev = i->second.prev;
- }
- i->second.prev = map_.end();
- i->second.next = first_;
- first_->second.prev = i;
- first_ = i;
- }
- return i->second.index;
+ IdxType add( const T& rContent, bool* pbFound) {
+ OSL_ASSERT( pbFound != NULL);
+ if( !size_) {
+ *pbFound = false;
+ return cache::ignore;
+ }
+ // try to insert into the map
+ list_.push_front( rContent); // create a temp entry
+ typedef std::pair<typename LruList::iterator, IdxType> MappedType;
+ typedef std::pair<typename LruItMap::iterator,bool> MapPair;
+ MapPair aMP = map_.insert( MappedType( list_.begin(), 0));
+ *pbFound = !aMP.second;
+
+ if( !aMP.second) { // insertion not needed => found the entry
+ list_.pop_front(); // remove the temp entry
+ list_.splice( list_.begin(), list_, aMP.first->first); // the found entry is moved to front
+ return aMP.first->second;
+ }
+
+ // test insertion successful => it was new so we keep it
+ IdxType n = static_cast<IdxType>( map_.size() - 1);
+ if( n >= size_) { // cache full => replace the LRU entry
+ // find the least recently used element in the map
+ typename LruItMap::iterator it = map_.find( --list_.end());
+ n = it->second;
+ map_.erase( it); // remove it from the map
+ list_.pop_back(); // remove from the list
+ }
+ aMP.first->second = n;
+ return n;
}
private:
- struct Entry;
-
- typedef std::map< T, Entry > Map;
-
- struct Entry {
- sal_uInt16 index;
- typename Map::iterator prev;
- typename Map::iterator next;
-
- Entry(
- sal_uInt16 theIndex, typename Map::iterator thePrev,
- typename Map::iterator theNext):
- index(theIndex), prev(thePrev), next(theNext) {}
- };
+ typedef std::list<T> LruList; // last recently used list
+ typedef typename LruList::iterator LruListIt;
+#ifdef URPCACHE_USES_UNORDERED_MAP
+ struct HashT{ size_t operator()( const LruListIt& rA) const { return hash(*rA;);};
+ struct EqualT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return *rA==*rB;}};
+ typedef ::std::unordered_map< LruListIt, IdxType, HashT, EqualT > LruItMap; // a map into a LruList
+#else
+ struct CmpT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return (*rA<*rB);}};
+ typedef ::std::map< LruListIt, IdxType, CmpT > LruItMap; // a map into a LruList
+#endif
std::size_t size_;
- Map map_;
- typename Map::iterator first_;
- typename Map::iterator last_;
+ LruItMap map_;
+ LruList list_;
};
}
#endif
+
Modified: openoffice/trunk/main/binaryurp/source/lessoperators.cxx
URL: http://svn.apache.org/viewvc/openoffice/trunk/main/binaryurp/source/lessoperators.cxx?rev=1550375&r1=1550374&r2=1550375&view=diff
==============================================================================
--- openoffice/trunk/main/binaryurp/source/lessoperators.cxx (original)
+++ openoffice/trunk/main/binaryurp/source/lessoperators.cxx Thu Dec 12 08:50:55 2013
@@ -36,14 +36,38 @@
namespace com { namespace sun { namespace star { namespace uno {
-bool operator <(TypeDescription const & left, TypeDescription const & right) {
- OSL_ASSERT(left.is() && right.is());
- typelib_TypeClass tc1 = left.get()->eTypeClass;
- typelib_TypeClass tc2 = right.get()->eTypeClass;
- return tc1 < tc2 ||
- (tc1 == tc2 &&
- (rtl::OUString(left.get()->pTypeName) <
- rtl::OUString(right.get()->pTypeName)));
+bool operator<( const TypeDescription& rLeft, const TypeDescription& rRight) {
+ OSL_ASSERT( rLeft.is() && rRight.is());
+ const typelib_TypeDescription& rA = *rLeft.get();
+ const typelib_TypeDescription& rB = *rRight.get();
+ if( rA.eTypeClass != rA.eTypeClass)
+ return (rA.eTypeClass < rB.eTypeClass);
+ const sal_Int32 nCmp = rtl_ustr_compare_WithLength(
+ rA.pTypeName->buffer, rA.pTypeName->length,
+ rB.pTypeName->buffer, rB.pTypeName->length);
+ return (nCmp < 0);
+}
+
+bool TypeDescEqual::operator()( const TypeDescription& rLeft, const TypeDescription& rRight) const
+{
+ OSL_ASSERT( rLeft.is() && rRight.is());
+ const typelib_TypeDescription& rA = *rLeft.get();
+ const typelib_TypeDescription& rB = *rRight.get();
+ if( rA.eTypeClass != rB.eTypeClass)
+ return false;
+ const sal_Int32 nCmp = rtl_ustr_compare_WithLength(
+ rA.pTypeName->buffer, rA.pTypeName->length,
+ rB.pTypeName->buffer, rB.pTypeName->length);
+ return (nCmp == 0);
+}
+
+sal_Int32 TypeDescHash::operator()( const TypeDescription& rTD) const
+{
+ OSL_ASSERT( rTD.is());
+ const typelib_TypeDescription& rA = *rTD.get();
+ sal_Int32 h = rtl_ustr_hashCode_WithLength( rA.pTypeName->buffer, rA.pTypeName->length);
+ h ^= static_cast<sal_Int32>(rA.eTypeClass);
+ return h;
}
} } } }
@@ -51,8 +75,8 @@ bool operator <(TypeDescription const &
namespace rtl {
bool operator <(ByteSequence const & left, ByteSequence const & right) {
- for (sal_Int32 i = 0; i != std::min(left.getLength(), right.getLength());
- ++i)
+ const sal_Int32 nLen = std::min( left.getLength(), right.getLength());
+ for( sal_Int32 i = 0; i < nLen; ++i )
{
if (left[i] < right[i]) {
return true;
@@ -65,3 +89,4 @@ bool operator <(ByteSequence const & lef
}
}
+
Modified: openoffice/trunk/main/binaryurp/source/lessoperators.hxx
URL: http://svn.apache.org/viewvc/openoffice/trunk/main/binaryurp/source/lessoperators.hxx?rev=1550375&r1=1550374&r2=1550375&view=diff
==============================================================================
--- openoffice/trunk/main/binaryurp/source/lessoperators.hxx (original)
+++ openoffice/trunk/main/binaryurp/source/lessoperators.hxx Thu Dec 12 08:50:55 2013
@@ -35,6 +35,10 @@ namespace com { namespace sun { namespac
bool operator <(TypeDescription const & left, TypeDescription const & right);
+struct TypeDescHash { sal_Int32 operator()( const TypeDescription&) const; };
+
+struct TypeDescEqual { bool operator()( const TypeDescription&, const TypeDescription&) const; };
+
} } } }
namespace rtl {