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