LibreOffice Module sw (master)  1
swcache.cxx
Go to the documentation of this file.
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3  * This file is part of the LibreOffice project.
4  *
5  * This Source Code Form is subject to the terms of the Mozilla Public
6  * License, v. 2.0. If a copy of the MPL was not distributed with this
7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8  *
9  * This file incorporates work covered by the following license notice:
10  *
11  * Licensed to the Apache Software Foundation (ASF) under one or more
12  * contributor license agreements. See the NOTICE file distributed
13  * with this work for additional information regarding copyright
14  * ownership. The ASF licenses this file to you under the Apache
15  * License, Version 2.0 (the "License"); you may not use this file
16  * except in compliance with the License. You may obtain a copy of
17  * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18  */
19 
20 #include <swcache.hxx>
21 
22 #include <o3tl/safeint.hxx>
23 #include <rtl/strbuf.hxx>
24 #include <osl/diagnose.h>
25 #include <sal/log.hxx>
26 
27 #include <limits.h>
28 
29 #ifdef DBG_UTIL
31 {
32  if ( !m_pRealFirst )
33  {
34  assert(m_pFirst == nullptr && m_pLast == nullptr);
35  return;
36  }
37 
38  // consistency check
39  assert(m_pLast->GetNext() == nullptr);
40  assert(m_pRealFirst->GetPrev() == nullptr);
41  sal_uInt16 nCnt = 0;
42  bool bFirstFound = false;
43  SwCacheObj *pObj = m_pRealFirst;
44  SwCacheObj *const pOldRealFirst = m_pRealFirst;
45  while ( pObj )
46  {
47  // the object must be found also when moving backwards
48  SwCacheObj *pTmp = m_pLast;
49  while ( pTmp && pTmp != pObj )
50  pTmp = pTmp->GetPrev();
51  assert(pTmp && "Object not found.");
52 
53  ++nCnt;
54  if ( pObj == m_pFirst )
55  bFirstFound = true;
56  if ( !pObj->GetNext() )
57  {
58  assert(pObj == m_pLast);
59  }
60  pObj = pObj->GetNext();
61  assert(pObj != pOldRealFirst); (void) pOldRealFirst;
62  }
63  assert(bFirstFound);
64  SAL_WARN_IF( nCnt + m_aFreePositions.size() != size(), "sw.core", "Lost Chain." );
66  size() == m_nCurMax && m_nCurMax != m_aFreePositions.size() + nCnt, "sw.core",
67  "Lost FreePositions." );
68 }
69 
70 #define INCREMENT( nVar ) ++nVar
71 #define CHECK Check();
72 
73 #else
74 #define INCREMENT( nVar )
75 #define CHECK
76 #endif
77 
78 SwCache::SwCache( const sal_uInt16 nInitSize
79 #ifdef DBG_UTIL
80  , const OString &rNm
81 #endif
82  ) :
83  m_aCacheObjects(),
84  m_pRealFirst( nullptr ),
85  m_pFirst( nullptr ),
86  m_pLast( nullptr ),
87  m_nCurMax( nInitSize )
88 #ifdef DBG_UTIL
89  , m_aName( rNm )
90  , m_nAppend( 0 )
91  , m_nInsertFree( 0 )
92  , m_nReplace( 0 )
93  , m_nGetSuccess( 0 )
94  , m_nGetFail( 0 )
95  , m_nToTop( 0 )
96  , m_nDelete( 0 )
97  , m_nGetSeek( 0 )
98  , m_nAverageSeekCnt( 0 )
99  , m_nFlushCnt( 0 )
100  , m_nFlushedObjects( 0 )
101  , m_nIncreaseMax( 0 )
102  , m_nDecreaseMax( 0 )
103 #endif
104 {
105  m_aCacheObjects.reserve( nInitSize );
106 }
107 
109 {
110 #ifdef DBG_UTIL
111  SAL_INFO(
112  "sw.core",
113  m_aName << "; number of new entries: " << m_nAppend
114  << "; number of insert on free places: " << m_nInsertFree
115  << "; number of replacements: " << m_nReplace
116  << "; number of successful Gets: " << m_nGetSuccess
117  << "; number of failed Gets: " << m_nGetFail
118  << "; number or reordering (LRU): " << m_nToTop
119  << "; number of suppressions: " << m_nDelete
120  << "; number of Gets without Index: " << m_nGetSeek
121  << "; number of Seek for Get without Index: " << m_nAverageSeekCnt
122  << "; number of Flush calls: " << m_nFlushCnt
123  << "; number of flushed objects: " << m_nFlushedObjects
124  << "; number of Cache expansions: " << m_nIncreaseMax
125  << "; number of Cache reductions: " << m_nDecreaseMax);
126  Check();
127 #endif
128 }
129 
130 void SwCache::IncreaseMax( const sal_uInt16 nAdd )
131 {
133  {
134  std::abort();
135  }
136 #ifdef DBG_UTIL
137  ++m_nIncreaseMax;
138 #endif
139 }
140 
141 void SwCache::DecreaseMax( const sal_uInt16 nSub )
142 {
143  if ( m_nCurMax > nSub )
144  m_nCurMax = m_nCurMax - sal::static_int_cast< sal_uInt16 >(nSub);
145 #ifdef DBG_UTIL
146  ++m_nDecreaseMax;
147 #endif
148 }
149 
151 {
153  SwCacheObj *pObj = m_pRealFirst;
154  m_pRealFirst = m_pFirst = m_pLast = nullptr;
155  SwCacheObj *pTmp;
156  while ( pObj )
157  {
158  assert(!pObj->IsLocked());
159  {
160  pTmp = pObj;
161  pObj = pTmp->GetNext();
162  m_aFreePositions.push_back( pTmp->GetCachePos() );
163  m_aCacheObjects[pTmp->GetCachePos()].reset(); // deletes pTmp
165  }
166  }
167 }
168 
170 {
171  INCREMENT( m_nToTop );
172 
173  // cut object out of chain and insert at beginning
174  if ( m_pRealFirst == pObj ) // pFirst was checked by caller
175  {
176  CHECK;
177  return;
178  }
179 
180  if ( !m_pRealFirst )
181  {
182  // the first will be inserted
183  assert(!m_pFirst && !m_pLast);
184  m_pRealFirst = m_pFirst = m_pLast = pObj;
185  CHECK;
186  return;
187  }
188 
189  assert(m_pFirst && m_pLast);
190 
191  // cut
192  if ( pObj == m_pLast )
193  {
194  assert(pObj->GetPrev());
195  m_pLast = pObj->GetPrev();
196  m_pLast->SetNext( nullptr );
197  }
198  else
199  {
200  if ( pObj->GetNext() )
201  pObj->GetNext()->SetPrev( pObj->GetPrev() );
202  if ( pObj->GetPrev() )
203  pObj->GetPrev()->SetNext( pObj->GetNext() );
204  }
205 
206  // paste at the (virtual) beginning
207  if ( m_pRealFirst == m_pFirst )
208  {
209  m_pRealFirst->SetPrev( pObj );
210  pObj->SetNext( m_pRealFirst );
211  pObj->SetPrev( nullptr );
212  m_pRealFirst = m_pFirst = pObj;
213  CHECK;
214  }
215  else
216  {
217  if ( m_pFirst->GetPrev() )
218  {
219  m_pFirst->GetPrev()->SetNext( pObj );
220  pObj->SetPrev( m_pFirst->GetPrev() );
221  }
222  else
223  pObj->SetPrev( nullptr );
224  m_pFirst->SetPrev( pObj );
225  pObj->SetNext( m_pFirst );
226  m_pFirst = pObj;
227  CHECK;
228  }
229 }
230 
231 SwCacheObj *SwCache::Get( const void *pOwner, const sal_uInt16 nIndex,
232  const bool bToTop )
233 {
234  SwCacheObj *pRet;
235  if ( nullptr != (pRet = (nIndex < m_aCacheObjects.size()) ? m_aCacheObjects[ nIndex ].get() : nullptr) )
236  {
237  if ( !pRet->IsOwner( pOwner ) )
238  pRet = nullptr;
239  else if ( bToTop && pRet != m_pFirst )
240  ToTop( pRet );
241  }
242 
243 #ifdef DBG_UTIL
244  if ( pRet )
245  ++m_nGetSuccess;
246  else
247  ++m_nGetFail;
248 #endif
249 
250  return pRet;
251 }
252 
253 SwCacheObj *SwCache::Get( const void *pOwner, const bool bToTop )
254 {
255  SwCacheObj *pRet = m_pRealFirst;
256  while ( pRet && !pRet->IsOwner( pOwner ) )
257  {
259  pRet = pRet->GetNext();
260  }
261 
262  if ( bToTop && pRet && pRet != m_pFirst )
263  ToTop( pRet );
264 
265 #ifdef DBG_UTIL
266  if ( pRet )
267  ++m_nGetSuccess;
268  else
269  ++m_nGetFail;
270  ++m_nGetSeek;
271 #endif
272  return pRet;
273 }
274 
276 {
277  CHECK;
278  OSL_ENSURE( !pObj->IsLocked(), "SwCache::Delete: object is locked." );
279  if ( pObj->IsLocked() )
280  return;
281 
282  if ( m_pFirst == pObj )
283  {
284  if ( m_pFirst->GetNext() )
286  else
288  }
289  if ( m_pRealFirst == pObj )
291  if ( m_pLast == pObj )
292  m_pLast = m_pLast->GetPrev();
293  if ( pObj->GetPrev() )
294  pObj->GetPrev()->SetNext( pObj->GetNext() );
295  if ( pObj->GetNext() )
296  pObj->GetNext()->SetPrev( pObj->GetPrev() );
297 
298  m_aFreePositions.push_back( pObj->GetCachePos() );
299  assert(m_aCacheObjects[pObj->GetCachePos()].get() == pObj);
300  m_aCacheObjects[pObj->GetCachePos()] = nullptr; // deletes pObj
301 
302  CHECK;
303  if ( m_aCacheObjects.size() > m_nCurMax &&
304  (m_nCurMax <= (m_aCacheObjects.size() - m_aFreePositions.size())) )
305  {
306  // Shrink if possible.To do so we need enough free positions.
307  // Unpleasant side effect: positions will be moved and the owner of
308  // these might not find them afterwards
309  for ( size_t i = 0; i < m_aCacheObjects.size(); ++i )
310  {
311  SwCacheObj *pTmpObj = m_aCacheObjects[i].get();
312  if ( !pTmpObj )
313  {
314  m_aCacheObjects.erase( m_aCacheObjects.begin() + i );
315  --i;
316  }
317  else
318  {
319  pTmpObj->SetCachePos( i );
320  }
321  }
322  m_aFreePositions.clear();
323  }
324  CHECK;
325 }
326 
327 void SwCache::Delete(void const*const pOwner, sal_uInt16 const nIndex)
328 {
329  INCREMENT( m_nDelete );
330  if (SwCacheObj *const pObj = Get(pOwner, nIndex, false))
331  {
332  DeleteObj(pObj);
333  }
334 }
335 
336 void SwCache::Delete( const void *pOwner )
337 {
338  INCREMENT( m_nDelete );
339  SwCacheObj *pObj;
340  if ( nullptr != (pObj = Get( pOwner, false )) )
341  DeleteObj( pObj );
342 }
343 
344 bool SwCache::Insert(SwCacheObj *const pNew, bool const isDuplicateOwnerAllowed)
345 {
346  CHECK;
347  OSL_ENSURE( !pNew->GetPrev() && !pNew->GetNext(), "New but not new." );
348  if (!isDuplicateOwnerAllowed)
349  {
350  for (auto const & rpObj : m_aCacheObjects)
351  { // check owner doesn't have a cache object yet; required for SwTextLine
352  assert(!rpObj || rpObj->GetOwner() != pNew->GetOwner());
353  (void) rpObj;
354  }
355  }
356 
357  sal_uInt16 nPos;
358  if ( m_aCacheObjects.size() < m_nCurMax )
359  {
360  // there is still space; insert directly
361  INCREMENT( m_nAppend );
362  nPos = m_aCacheObjects.size();
363  m_aCacheObjects.emplace_back(pNew);
364  }
365  else if ( !m_aFreePositions.empty() )
366  {
367  // there are placeholders; use the last of those
369  const sal_uInt16 nFreePos = m_aFreePositions.size() - 1;
370  nPos = m_aFreePositions[ nFreePos ];
371  m_aCacheObjects[nPos].reset(pNew);
372  m_aFreePositions.erase( m_aFreePositions.begin() + nFreePos );
373  }
374  else
375  {
377  // the last of the LRU has to go
378  SwCacheObj *pObj = m_pLast;
379 
380  while ( pObj && pObj->IsLocked() )
381  pObj = pObj->GetPrev();
382  if ( !pObj )
383  {
384  SAL_WARN("sw.core", "SwCache overflow.");
385  IncreaseMax(100); // embiggen & try again
386  return Insert(pNew, isDuplicateOwnerAllowed);
387  }
388 
389  nPos = pObj->GetCachePos();
390  if ( pObj == m_pLast )
391  {
392  m_pLast = pObj->GetPrev();
393  assert(m_pLast); // must have capacity > 1
394  }
395  if (pObj == m_pFirst)
396  {
397  if (pObj->GetNext())
398  {
399  m_pFirst = pObj->GetNext();
400  }
401  else
402  {
403  m_pFirst = pObj->GetPrev();
404  }
405  assert(m_pFirst); // must have capacity > 1
406  }
407  if (pObj == m_pRealFirst)
408  {
409  m_pRealFirst = pObj->GetNext();
410  assert(m_pRealFirst); // must have capacity > 1
411  }
412  if (pObj->GetPrev())
413  {
414  pObj->GetPrev()->SetNext( pObj->GetNext() );
415  }
416  if (pObj->GetNext())
417  {
418  pObj->GetNext()->SetPrev( pObj->GetPrev() );
419  }
420  m_aCacheObjects[nPos].reset(pNew);
421  }
422  pNew->SetCachePos( nPos );
423 
424  if ( m_pFirst )
425  {
426  if ( m_pFirst->GetPrev() )
427  { m_pFirst->GetPrev()->SetNext( pNew );
428  pNew->SetPrev( m_pFirst->GetPrev() );
429  }
430  m_pFirst->SetPrev( pNew );
431  pNew->SetNext( m_pFirst );
432  }
433  else
434  {
435  assert(!m_pLast);
436  m_pLast = pNew;
437  }
438  if ( m_pFirst == m_pRealFirst )
439  m_pRealFirst = pNew;
440  m_pFirst = pNew;
441 
442  CHECK;
443  return true;
444 }
445 
446 void SwCache::SetLRUOfst( const sal_uInt16 nOfst )
447 {
448  assert(nOfst < m_nCurMax);
449  if ( !m_pRealFirst || ((m_aCacheObjects.size() - m_aFreePositions.size()) < nOfst) )
450  return;
451 
452  CHECK;
454  for ( sal_uInt16 i = 0; i < m_aCacheObjects.size() && i < nOfst; ++i )
455  {
456  if ( m_pFirst->GetNext() && m_pFirst->GetNext()->GetNext() )
458  else
459  break;
460  }
461  CHECK;
462 }
463 
464 SwCacheObj::SwCacheObj( const void *pOwn ) :
465  m_pNext( nullptr ),
466  m_pPrev( nullptr ),
467  m_nCachePos( USHRT_MAX ),
468  m_nLock( 0 ),
469  m_pOwner( pOwn )
470 {
471 }
472 
474 {
475 }
476 
477 #ifdef DBG_UTIL
479 {
480  OSL_ENSURE( m_nLock < UCHAR_MAX, "Too many Locks for CacheObject." );
481  ++m_nLock;
482 }
483 
485 {
486  OSL_ENSURE( m_nLock, "No more Locks available." );
487  --m_nLock;
488 }
489 #endif
490 
492 {
493  if ( m_pObj )
494  m_pObj->Unlock();
495 }
496 
497 void SwCacheAccess::Get_(bool const isDuplicateOwnerAllowed)
498 {
499  OSL_ENSURE( !m_pObj, "SwCacheAcces Obj already available." );
500 
501  m_pObj = NewObj();
502  if (!m_rCache.Insert(m_pObj, isDuplicateOwnerAllowed))
503  {
504  delete m_pObj;
505  m_pObj = nullptr;
506  }
507  else
508  {
509  m_pObj->Lock();
510  }
511 }
512 
513 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
long m_nIncreaseMax
Definition: swcache.hxx:79
long m_nAppend
Definition: swcache.hxx:68
sal_uInt16 GetCachePos() const
Definition: swcache.hxx:170
bool Insert(SwCacheObj *pNew, bool isDuplicateOwnerAllowed)
Definition: swcache.cxx:344
SwCacheObj * m_pLast
The virtual first.
Definition: swcache.hxx:60
void SetLRUOfst(const sal_uInt16 nOfst)
Definition: swcache.cxx:446
void Lock()
Definition: swcache.cxx:478
bool IsLocked() const
Definition: swcache.hxx:172
SwCacheObj * m_pObj
Definition: swcache.hxx:201
void Get_(bool isDuplicateOwnerAllowed)
Definition: swcache.cxx:497
SwCacheObj * GetPrev()
Definition: swcache.hxx:145
long m_nDecreaseMax
number of cache size increases
Definition: swcache.hxx:80
long m_nGetSuccess
number of LRU replacements
Definition: swcache.hxx:71
long m_nReplace
number of entries inserted on freed position
Definition: swcache.hxx:70
virtual SwCacheObj * NewObj()=0
Can be use in NewObj.
SwCacheObj * m_pFirst
ALWAYS the real first LRU
Definition: swcache.hxx:59
void SetNext(SwCacheObj *pNew)
Definition: swcache.hxx:146
virtual ~SwCacheObj()
Definition: swcache.cxx:473
std::vector< sal_uInt16 > m_aFreePositions
Definition: swcache.hxx:56
SwCacheObj * Get(const void *pOwner, const bool bToTop=true)
Definition: swcache.cxx:253
std::vector< std::unique_ptr< SwCacheObj > > m_aCacheObjects
Definition: swcache.hxx:55
SwCacheObj * m_pRealFirst
Free positions for the Insert if the maximum has not been reached.
Definition: swcache.hxx:58
void DecreaseMax(const sal_uInt16 nSub)
Definition: swcache.cxx:141
void DeleteObj(SwCacheObj *pObj)
Definition: swcache.cxx:275
OString m_aName
Definition: swcache.hxx:67
sal_uInt8 m_nLock
Position in the Cache array.
Definition: swcache.hxx:142
void Check()
number of cache size decreases
Definition: swcache.cxx:30
sal_uInt16 size()
Definition: swcache.hxx:117
bool IsOwner(const void *pNew) const
Definition: swcache.hxx:220
void IncreaseMax(const sal_uInt16 nAdd)
Definition: swcache.cxx:130
SwCacheObj(const void *pOwner)
Definition: swcache.cxx:464
long m_nGetSeek
number of explicit deletes
Definition: swcache.hxx:75
void ToTop(SwCacheObj *pObj)
Definition: swcache.cxx:169
void SetPrev(SwCacheObj *pNew)
Definition: swcache.hxx:147
int i
std::enable_if< std::is_signed< T >::value, bool >::type checked_add(T a, T b, T &result)
#define CHECK
Definition: swcache.cxx:71
#define INCREMENT(nVar)
Definition: swcache.cxx:70
sal_uInt16 m_nCurMax
Definition: swcache.hxx:62
void Flush()
Definition: swcache.cxx:150
void Delete(const void *pOwner, sal_uInt16 nIndex)
void SetCachePos(const sal_uInt16 nNew)
Definition: swcache.hxx:149
#define SAL_WARN_IF(condition, area, stream)
long m_nDelete
number of reordering (LRU)
Definition: swcache.hxx:74
The Cache object base class Users of the Cache must derrive a class from the SwCacheObj and store the...
Definition: swcache.hxx:133
const o3tl::enumarray< SvxAdjust, unsigned short > aSvxToUnoAdjust USHRT_MAX
Definition: unosett.cxx:261
long m_nGetFail
Definition: swcache.hxx:72
#define SAL_INFO(area, stream)
long m_nFlushedObjects
number of flush calls
Definition: swcache.hxx:78
~SwCache()
The dtor will free all objects still in the vector.
Definition: swcache.cxx:108
long m_nFlushCnt
number of seeks for all gets without index
Definition: swcache.hxx:77
virtual ~SwCacheAccess()
Definition: swcache.cxx:491
void Unlock()
Definition: swcache.cxx:484
#define SAL_WARN(area, stream)
long m_nInsertFree
number of entries appended
Definition: swcache.hxx:69
SwCache & m_rCache
Definition: swcache.hxx:196
SwCacheObj * GetNext()
Definition: swcache.hxx:144
sal_Int32 nPos
long m_nAverageSeekCnt
number of gets without index
Definition: swcache.hxx:76
long m_nToTop
Definition: swcache.hxx:73
SwCache(const sal_uInt16 nInitSize, const OString &rNm)
Definition: swcache.cxx:78
const void * GetOwner() const
Definition: swcache.hxx:167
typedef void(CALLTYPE *GetFuncDataPtr)(sal_uInt16 &nNo