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