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 #include <utility>
26
27 #include <limits.h>
28
29 #ifdef DBG_UTIL
Check()30 void SwCache::Check()
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 ++nCnt;
48 if ( pObj == m_pFirst )
49 bFirstFound = true;
50 SwCacheObj* pNext = pObj->GetNext();
51 if ( !pNext )
52 {
53 assert(pObj == m_pLast);
54 }
55 else
56 {
57 assert(pObj == pNext->GetPrev());
58 }
59 pObj = pNext;
60 assert(pObj != pOldRealFirst); (void) pOldRealFirst;
61 }
62 assert(bFirstFound);
63 SAL_WARN_IF( nCnt + m_aFreePositions.size() != size(), "sw.core", "Lost Chain." );
64 SAL_WARN_IF(
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
SwCache(const sal_uInt16 nInitSize,OString aNm)77 SwCache::SwCache( const sal_uInt16 nInitSize
78 #ifdef DBG_UTIL
79 , OString aNm
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(std::move( aNm ))
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
~SwCache()106 SwCache::~SwCache()
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
IncreaseMax(const sal_uInt16 nAdd)128 void SwCache::IncreaseMax( const sal_uInt16 nAdd )
129 {
130 if (o3tl::checked_add(m_nCurMax, nAdd, m_nCurMax))
131 {
132 std::abort();
133 }
134 #ifdef DBG_UTIL
135 ++m_nIncreaseMax;
136 #endif
137 }
138
DecreaseMax(const sal_uInt16 nSub)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
Flush()148 void SwCache::Flush()
149 {
150 INCREMENT( m_nFlushCnt );
151 SwCacheObj *pObj = m_pRealFirst;
152 m_pRealFirst = m_pFirst = m_pLast = nullptr;
153 while ( pObj )
154 {
155 assert(!pObj->IsLocked());
156 SwCacheObj *pTmp = pObj;
157 pObj = pTmp->GetNext();
158 m_aFreePositions.push_back( pTmp->GetCachePos() );
159 m_aCacheObjects[pTmp->GetCachePos()].reset(); // deletes pTmp
160 INCREMENT( m_nFlushedObjects );
161 }
162 }
163
ToTop(SwCacheObj * pObj)164 void SwCache::ToTop( SwCacheObj *pObj )
165 {
166 INCREMENT( m_nToTop );
167
168 // cut object out of chain and insert at beginning
169 if ( m_pRealFirst == pObj ) // pFirst was checked by caller
170 {
171 CHECK;
172 return;
173 }
174
175 if ( !m_pRealFirst )
176 {
177 // the first will be inserted
178 assert(!m_pFirst && !m_pLast);
179 m_pRealFirst = m_pFirst = m_pLast = pObj;
180 CHECK;
181 return;
182 }
183
184 assert(m_pFirst && m_pLast);
185
186 // cut
187 if ( pObj == m_pLast )
188 {
189 assert(pObj->GetPrev());
190 m_pLast = pObj->GetPrev();
191 m_pLast->SetNext( nullptr );
192 }
193 else
194 {
195 if ( pObj->GetNext() )
196 pObj->GetNext()->SetPrev( pObj->GetPrev() );
197 if ( pObj->GetPrev() )
198 pObj->GetPrev()->SetNext( pObj->GetNext() );
199 }
200
201 // paste at the (virtual) beginning
202 if ( m_pRealFirst == m_pFirst )
203 {
204 m_pRealFirst->SetPrev( pObj );
205 pObj->SetNext( m_pRealFirst );
206 pObj->SetPrev( nullptr );
207 m_pRealFirst = m_pFirst = pObj;
208 CHECK;
209 }
210 else
211 {
212 if ( m_pFirst->GetPrev() )
213 {
214 m_pFirst->GetPrev()->SetNext( pObj );
215 pObj->SetPrev( m_pFirst->GetPrev() );
216 }
217 else
218 pObj->SetPrev( nullptr );
219 m_pFirst->SetPrev( pObj );
220 pObj->SetNext( m_pFirst );
221 m_pFirst = pObj;
222 CHECK;
223 }
224 }
225
Get(const void * pOwner,const sal_uInt16 nIndex,const bool bToTop)226 SwCacheObj *SwCache::Get( const void *pOwner, const sal_uInt16 nIndex,
227 const bool bToTop )
228 {
229 SwCacheObj *pRet = (nIndex < m_aCacheObjects.size()) ? m_aCacheObjects[ nIndex ].get() : nullptr;
230 if ( pRet )
231 {
232 if ( !pRet->IsOwner( pOwner ) )
233 pRet = nullptr;
234 else if ( bToTop && pRet != m_pFirst )
235 ToTop( pRet );
236 }
237
238 #ifdef DBG_UTIL
239 if ( pRet )
240 ++m_nGetSuccess;
241 else
242 ++m_nGetFail;
243 #endif
244
245 return pRet;
246 }
247
Get(const void * pOwner,const bool bToTop)248 SwCacheObj *SwCache::Get( const void *pOwner, const bool bToTop )
249 {
250 SwCacheObj *pRet = m_pRealFirst;
251 while ( pRet && !pRet->IsOwner( pOwner ) )
252 {
253 INCREMENT( m_nAverageSeekCnt );
254 pRet = pRet->GetNext();
255 }
256
257 if ( bToTop && pRet && pRet != m_pFirst )
258 ToTop( pRet );
259
260 #ifdef DBG_UTIL
261 if ( pRet )
262 ++m_nGetSuccess;
263 else
264 ++m_nGetFail;
265 ++m_nGetSeek;
266 #endif
267 return pRet;
268 }
269
DeleteObj(SwCacheObj * pObj)270 void SwCache::DeleteObj( SwCacheObj *pObj )
271 {
272 CHECK;
273 OSL_ENSURE( !pObj->IsLocked(), "SwCache::Delete: object is locked." );
274 if ( pObj->IsLocked() )
275 return;
276
277 if ( m_pFirst == pObj )
278 {
279 if ( m_pFirst->GetNext() )
280 m_pFirst = m_pFirst->GetNext();
281 else
282 m_pFirst = m_pFirst->GetPrev();
283 }
284 if ( m_pRealFirst == pObj )
285 m_pRealFirst = m_pRealFirst->GetNext();
286 if ( m_pLast == pObj )
287 m_pLast = m_pLast->GetPrev();
288 if ( pObj->GetPrev() )
289 pObj->GetPrev()->SetNext( pObj->GetNext() );
290 if ( pObj->GetNext() )
291 pObj->GetNext()->SetPrev( pObj->GetPrev() );
292
293 m_aFreePositions.push_back( pObj->GetCachePos() );
294 assert(m_aCacheObjects[pObj->GetCachePos()].get() == pObj);
295 m_aCacheObjects[pObj->GetCachePos()] = nullptr; // deletes pObj
296
297 CHECK;
298 if ( m_aCacheObjects.size() > m_nCurMax &&
299 (m_nCurMax <= (m_aCacheObjects.size() - m_aFreePositions.size())) )
300 {
301 // Shrink if possible.To do so we need enough free positions.
302 // Unpleasant side effect: positions will be moved and the owner of
303 // these might not find them afterwards
304 size_t i = 0;
305 while (i < m_aCacheObjects.size())
306 {
307 SwCacheObj *pTmpObj = m_aCacheObjects[i].get();
308 if ( !pTmpObj )
309 {
310 m_aCacheObjects.erase( m_aCacheObjects.begin() + i );
311 }
312 else
313 {
314 pTmpObj->SetCachePos( i );
315 ++i;
316 }
317 }
318 m_aFreePositions.clear();
319 }
320 CHECK;
321 }
322
Delete(void const * const pOwner,sal_uInt16 const nIndex)323 void SwCache::Delete(void const*const pOwner, sal_uInt16 const nIndex)
324 {
325 INCREMENT( m_nDelete );
326 if (SwCacheObj *const pObj = Get(pOwner, nIndex, false))
327 DeleteObj(pObj);
328 }
329
Delete(const void * pOwner)330 void SwCache::Delete( const void *pOwner )
331 {
332 INCREMENT( m_nDelete );
333 SwCacheObj *pObj = Get( pOwner, false );
334 if ( pObj )
335 DeleteObj( pObj );
336 }
337
Insert(SwCacheObj * const pNew,bool const isDuplicateOwnerAllowed)338 bool SwCache::Insert(SwCacheObj *const pNew, bool const isDuplicateOwnerAllowed)
339 {
340 CHECK;
341 OSL_ENSURE( !pNew->GetPrev() && !pNew->GetNext(), "New but not new." );
342 if (!isDuplicateOwnerAllowed)
343 {
344 for (auto const & rpObj : m_aCacheObjects)
345 { // check owner doesn't have a cache object yet; required for SwTextLine
346 assert(!rpObj || rpObj->GetOwner() != pNew->GetOwner());
347 (void) rpObj;
348 }
349 }
350
351 sal_uInt16 nPos;
352 if ( m_aCacheObjects.size() < m_nCurMax )
353 {
354 // there is still space; insert directly
355 INCREMENT( m_nAppend );
356 nPos = m_aCacheObjects.size();
357 m_aCacheObjects.emplace_back(pNew);
358 }
359 else if ( !m_aFreePositions.empty() )
360 {
361 // there are placeholders; use the last of those
362 INCREMENT( m_nInsertFree );
363 const sal_uInt16 nFreePos = m_aFreePositions.size() - 1;
364 nPos = m_aFreePositions[ nFreePos ];
365 m_aCacheObjects[nPos].reset(pNew);
366 m_aFreePositions.erase( m_aFreePositions.begin() + nFreePos );
367 }
368 else
369 {
370 INCREMENT( m_nReplace );
371 // the last of the LRU has to go
372 SwCacheObj *pObj = m_pLast;
373
374 while ( pObj && pObj->IsLocked() )
375 pObj = pObj->GetPrev();
376 if ( !pObj )
377 {
378 SAL_WARN("sw.core", "SwCache overflow.");
379 IncreaseMax(100); // embiggen & try again
380 return Insert(pNew, isDuplicateOwnerAllowed);
381 }
382
383 nPos = pObj->GetCachePos();
384 if ( pObj == m_pLast )
385 {
386 m_pLast = pObj->GetPrev();
387 assert(m_pLast); // must have capacity > 1
388 }
389 if (pObj == m_pFirst)
390 {
391 if (pObj->GetNext())
392 {
393 m_pFirst = pObj->GetNext();
394 }
395 else
396 {
397 m_pFirst = pObj->GetPrev();
398 }
399 assert(m_pFirst); // must have capacity > 1
400 }
401 if (pObj == m_pRealFirst)
402 {
403 m_pRealFirst = pObj->GetNext();
404 assert(m_pRealFirst); // must have capacity > 1
405 }
406 if (pObj->GetPrev())
407 {
408 pObj->GetPrev()->SetNext( pObj->GetNext() );
409 }
410 if (pObj->GetNext())
411 {
412 pObj->GetNext()->SetPrev( pObj->GetPrev() );
413 }
414 m_aCacheObjects[nPos].reset(pNew);
415 }
416 pNew->SetCachePos( nPos );
417
418 if ( m_pFirst )
419 {
420 if ( m_pFirst->GetPrev() )
421 { m_pFirst->GetPrev()->SetNext( pNew );
422 pNew->SetPrev( m_pFirst->GetPrev() );
423 }
424 m_pFirst->SetPrev( pNew );
425 pNew->SetNext( m_pFirst );
426 }
427 else
428 {
429 assert(!m_pLast);
430 m_pLast = pNew;
431 }
432 if ( m_pFirst == m_pRealFirst )
433 m_pRealFirst = pNew;
434 m_pFirst = pNew;
435
436 CHECK;
437 return true;
438 }
439
SetLRUOfst(const sal_uInt16 nOfst)440 void SwCache::SetLRUOfst( const sal_uInt16 nOfst )
441 {
442 assert(nOfst < m_nCurMax);
443 if ( !m_pRealFirst || ((m_aCacheObjects.size() - m_aFreePositions.size()) < nOfst) )
444 return;
445
446 CHECK;
447 m_pFirst = m_pRealFirst;
448 for ( sal_uInt16 i = 0; i < m_aCacheObjects.size() && i < nOfst; ++i )
449 {
450 if ( m_pFirst->GetNext() && m_pFirst->GetNext()->GetNext() )
451 m_pFirst = m_pFirst->GetNext();
452 else
453 break;
454 }
455 CHECK;
456 }
457
SwCacheObj(const void * pOwn)458 SwCacheObj::SwCacheObj( const void *pOwn ) :
459 m_pNext( nullptr ),
460 m_pPrev( nullptr ),
461 m_nCachePos( USHRT_MAX ),
462 m_nLock( 0 ),
463 m_pOwner( pOwn )
464 {
465 }
466
~SwCacheObj()467 SwCacheObj::~SwCacheObj()
468 {
469 }
470
471 #ifdef DBG_UTIL
Lock()472 void SwCacheObj::Lock()
473 {
474 assert( m_nLock < UCHAR_MAX && "Too many Locks for CacheObject." );
475 ++m_nLock;
476 }
477
Unlock()478 void SwCacheObj::Unlock()
479 {
480 assert( m_nLock && "No more Locks available." );
481 --m_nLock;
482 }
483 #endif
484
~SwCacheAccess()485 SwCacheAccess::~SwCacheAccess()
486 {
487 if ( m_pObj )
488 m_pObj->Unlock();
489 }
490
Get_(bool const isDuplicateOwnerAllowed)491 void SwCacheAccess::Get_(bool const isDuplicateOwnerAllowed)
492 {
493 OSL_ENSURE( !m_pObj, "SwCacheAcces Obj already available." );
494
495 m_pObj = NewObj();
496 if (!m_rCache.Insert(m_pObj, isDuplicateOwnerAllowed))
497 {
498 delete m_pObj;
499 m_pObj = nullptr;
500 }
501 else
502 {
503 m_pObj->Lock();
504 }
505 }
506
507 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
508
