+#if wxUSE_STRING_POS_CACHE
+ // this is an extremely simple cache used by PosToImpl(): each cache element
+ // contains the string it applies to and the index corresponding to the last
+ // used position in this wxString in its m_impl string
+ //
+ // NB: notice that this struct (and nested Element one) must be a POD or we
+ // wouldn't be able to use a thread-local variable of this type, in
+ // particular it should have no ctor -- we rely on statics being
+ // initialized to 0 instead
+ struct Cache
+ {
+ enum { SIZE = 8 };
+
+ struct Element
+ {
+ const wxString *str; // the string to which this element applies
+ size_t pos, // the cached index in this string
+ impl, // the corresponding position in its m_impl
+ len; // cached length or npos if unknown
+
+ // reset cached index to 0
+ void ResetPos() { pos = impl = 0; }
+
+ // reset position and length
+ void Reset() { ResetPos(); len = npos; }
+ };
+
+ // cache the indices mapping for the last few string used
+ Element cached[SIZE];
+
+ // the last used index
+ unsigned lastUsed;
+ };
+
+#ifndef wxHAS_COMPILER_TLS
+ // we must use an accessor function and not a static variable when the TLS
+ // variables support is implemented in the library (and not by the compiler)
+ // because the global s_cache variable could be not yet initialized when a
+ // ctor of another global object is executed and if that ctor uses any
+ // wxString methods, bad things happen
+ //
+ // however notice that this approach does not work when compiler TLS is used,
+ // at least not with g++ 4.1.2 under amd64 as it apparently compiles code
+ // using this accessor incorrectly when optimizations are enabled (-O2 is
+ // enough) -- luckily we don't need it then neither as static __thread
+ // variables are initialized by 0 anyhow then and so we can use the variable
+ // directly
+ WXEXPORT static Cache& GetCache()
+ {
+ static wxTLS_TYPE(Cache) s_cache;
+
+ return wxTLS_VALUE(s_cache);
+ }
+
+ // this helper struct is used to ensure that GetCache() is called during
+ // static initialization time, i.e. before any threads creation, as otherwise
+ // the static s_cache construction inside GetCache() wouldn't be MT-safe
+ friend struct wxStrCacheInitializer;
+#else // wxHAS_COMPILER_TLS
+ static wxTLS_TYPE(Cache) ms_cache;
+ static Cache& GetCache() { return wxTLS_VALUE(ms_cache); }
+#endif // !wxHAS_COMPILER_TLS/wxHAS_COMPILER_TLS
+
+ static Cache::Element *GetCacheBegin() { return GetCache().cached; }
+ static Cache::Element *GetCacheEnd() { return GetCacheBegin() + Cache::SIZE; }
+ static unsigned& LastUsedCacheElement() { return GetCache().lastUsed; }
+
+ // this is used in debug builds only to provide a convenient function,
+ // callable from a debugger, to show the cache contents
+ friend struct wxStrCacheDumper;
+
+ // uncomment this to have access to some profiling statistics on program
+ // termination
+ //#define wxPROFILE_STRING_CACHE
+
+#ifdef wxPROFILE_STRING_CACHE
+ static struct PosToImplCacheStats
+ {
+ unsigned postot, // total non-trivial calls to PosToImpl
+ poshits, // cache hits from PosToImpl()
+ mishits, // cached position beyond the needed one
+ sumpos, // sum of all positions, used to compute the
+ // average position after dividing by postot
+ sumofs, // sum of all offsets after using the cache, used to
+ // compute the average after dividing by hits
+ lentot, // number of total calls to length()
+ lenhits; // number of cache hits in length()
+ } ms_cacheStats;
+
+ friend struct wxStrCacheStatsDumper;
+
+ #define wxCACHE_PROFILE_FIELD_INC(field) ms_cacheStats.field++
+ #define wxCACHE_PROFILE_FIELD_ADD(field, val) ms_cacheStats.field += (val)
+#else // !wxPROFILE_STRING_CACHE
+ #define wxCACHE_PROFILE_FIELD_INC(field)
+ #define wxCACHE_PROFILE_FIELD_ADD(field, val)
+#endif // wxPROFILE_STRING_CACHE/!wxPROFILE_STRING_CACHE
+
+ // note: it could seem that the functions below shouldn't be inline because
+ // they are big, contain loops and so the compiler shouldn't be able to
+ // inline them anyhow, however moving them into string.cpp does decrease the
+ // code performance by ~5%, at least when using g++ 4.1 so do keep them here
+ // unless tests show that it's not advantageous any more
+
+ // return the pointer to the cache element for this string or NULL if not
+ // cached
+ Cache::Element *FindCacheElement() const
+ {
+ // profiling seems to show a small but consistent gain if we use this
+ // simple loop instead of starting from the last used element (there are
+ // a lot of misses in this function...)
+ Cache::Element * const cacheBegin = GetCacheBegin();
+#ifndef wxHAS_COMPILER_TLS
+ // during destruction tls calls may return NULL, in this case return NULL
+ // immediately without accessing anything else
+ if ( cacheBegin == NULL )
+ return NULL;
+#endif
+ Cache::Element * const cacheEnd = GetCacheEnd();
+ for ( Cache::Element *c = cacheBegin; c != cacheEnd; c++ )
+ {
+ if ( c->str == this )
+ return c;
+ }
+
+ return NULL;
+ }
+
+ // unlike FindCacheElement(), this one always returns a valid pointer to the
+ // cache element for this string, it may have valid last cached position and
+ // its corresponding index in the byte string or not
+ Cache::Element *GetCacheElement() const
+ {
+ Cache::Element * const cacheBegin = GetCacheBegin();
+ Cache::Element * const cacheEnd = GetCacheEnd();
+ Cache::Element * const cacheStart = cacheBegin + LastUsedCacheElement();
+
+ // check the last used first, this does no (measurable) harm for a miss
+ // but does help for simple loops addressing the same string all the time
+ if ( cacheStart->str == this )
+ return cacheStart;
+
+ // notice that we're going to check cacheStart again inside this call but
+ // profiling shows that it's still faster to use a simple loop like
+ // inside FindCacheElement() than manually looping with wrapping starting
+ // from the cache entry after the start one
+ Cache::Element *c = FindCacheElement();
+ if ( !c )
+ {
+ // claim the next cache entry for this string
+ c = cacheStart;
+ if ( ++c == cacheEnd )
+ c = cacheBegin;
+
+ c->str = this;
+ c->Reset();
+
+ // and remember the last used element
+ LastUsedCacheElement() = c - cacheBegin;
+ }
+
+ return c;
+ }
+
+ size_t DoPosToImpl(size_t pos) const
+ {
+ wxCACHE_PROFILE_FIELD_INC(postot);
+
+ // NB: although the case of pos == 1 (and offset from cached position
+ // equal to 1) are common, nothing is gained by writing special code
+ // for handling them, the compiler (at least g++ 4.1 used) seems to
+ // optimize the code well enough on its own
+
+ wxCACHE_PROFILE_FIELD_ADD(sumpos, pos);
+
+ Cache::Element * const cache = GetCacheElement();
+
+ // cached position can't be 0 so if it is, it means that this entry was
+ // used for length caching only so far, i.e. it doesn't count as a hit
+ // from our point of view
+ if ( cache->pos )
+ {
+ wxCACHE_PROFILE_FIELD_INC(poshits);
+ }
+
+ if ( pos == cache->pos )
+ return cache->impl;
+
+ // this seems to happen only rarely so just reset the cache in this case
+ // instead of complicating code even further by seeking backwards in this
+ // case
+ if ( cache->pos > pos )
+ {
+ wxCACHE_PROFILE_FIELD_INC(mishits);
+
+ cache->ResetPos();
+ }
+
+ wxCACHE_PROFILE_FIELD_ADD(sumofs, pos - cache->pos);
+
+
+ wxStringImpl::const_iterator i(m_impl.begin() + cache->impl);
+ for ( size_t n = cache->pos; n < pos; n++ )
+ wxStringOperations::IncIter(i);
+
+ cache->pos = pos;
+ cache->impl = i - m_impl.begin();
+
+ wxSTRING_CACHE_ASSERT(
+ (int)cache->impl == (begin() + pos).impl() - m_impl.begin() );
+
+ return cache->impl;
+ }
+
+ void InvalidateCache()
+ {
+ Cache::Element * const cache = FindCacheElement();
+ if ( cache )
+ cache->Reset();
+ }
+
+ void InvalidateCachedLength()
+ {
+ Cache::Element * const cache = FindCacheElement();
+ if ( cache )
+ cache->len = npos;
+ }
+
+ void SetCachedLength(size_t len)
+ {
+ // we optimistically cache the length here even if the string wasn't
+ // present in the cache before, this seems to do no harm and the
+ // potential for avoiding length recomputation for long strings looks
+ // interesting
+ GetCacheElement()->len = len;
+ }
+
+ void UpdateCachedLength(ptrdiff_t delta)
+ {
+ Cache::Element * const cache = FindCacheElement();
+ if ( cache && cache->len != npos )
+ {
+ wxSTRING_CACHE_ASSERT( (ptrdiff_t)cache->len + delta >= 0 );
+
+ cache->len += delta;
+ }
+ }
+
+ #define wxSTRING_INVALIDATE_CACHE() InvalidateCache()
+ #define wxSTRING_INVALIDATE_CACHED_LENGTH() InvalidateCachedLength()
+ #define wxSTRING_UPDATE_CACHED_LENGTH(n) UpdateCachedLength(n)
+ #define wxSTRING_SET_CACHED_LENGTH(n) SetCachedLength(n)
+#else // !wxUSE_STRING_POS_CACHE
+ size_t DoPosToImpl(size_t pos) const
+ {
+ return (begin() + pos).impl() - m_impl.begin();
+ }
+
+ #define wxSTRING_INVALIDATE_CACHE()
+ #define wxSTRING_INVALIDATE_CACHED_LENGTH()
+ #define wxSTRING_UPDATE_CACHED_LENGTH(n)
+ #define wxSTRING_SET_CACHED_LENGTH(n)
+#endif // wxUSE_STRING_POS_CACHE/!wxUSE_STRING_POS_CACHE
+
projects / wxWidgets.git / blobdiff