Line data Source code
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 <rtl/strbuf.hxx>
23 : #include <osl/diagnose.h>
24 :
25 : #include <limits.h>
26 :
27 : #ifdef DBG_UTIL
28 : void SwCache::Check()
29 : {
30 : if ( !pRealFirst )
31 : return;
32 :
33 : // consistency check
34 : SAL_WARN_IF( pLast->GetNext(), "sw.core", "Last but not last." );
35 : SAL_WARN_IF( pRealFirst->GetPrev(), "sw.core", "First but not first." );
36 : sal_uInt16 nCnt = 0;
37 : bool bFirstFound = false;
38 : SwCacheObj *pObj = pRealFirst;
39 : SwCacheObj *const pOldRealFirst = pRealFirst;
40 : while ( pObj )
41 : {
42 : // the object must be found also when moving backwards
43 : SwCacheObj *pTmp = pLast;
44 : while ( pTmp && pTmp != pObj )
45 : pTmp = pTmp->GetPrev();
46 : SAL_WARN_IF( !pTmp, "sw.core", "Object not found." );
47 :
48 : ++nCnt;
49 : if ( pObj == pFirst )
50 : bFirstFound = true;
51 : if ( !pObj->GetNext() )
52 : SAL_WARN_IF( pObj != pLast, "sw.core", "Last not Found." );
53 : pObj = pObj->GetNext();
54 : SAL_WARN_IF(pObj == pOldRealFirst, "sw.core", "Recursion in SwCache.");
55 : }
56 : SAL_WARN_IF( !bFirstFound, "sw.core", "First not Found." );
57 : SAL_WARN_IF( nCnt + aFreePositions.size() != size(), "sw.core", "Lost Chain." );
58 : SAL_WARN_IF(
59 : size() == nCurMax && nCurMax != aFreePositions.size() + nCnt, "sw.core",
60 : "Lost FreePositions." );
61 : }
62 :
63 : #define INCREMENT( nVar ) ++nVar
64 : #define CHECK Check();
65 :
66 : #else
67 : #define INCREMENT( nVar )
68 : #define CHECK
69 : #endif
70 :
71 236 : SwCache::SwCache( const sal_uInt16 nInitSize
72 : #ifdef DBG_UTIL
73 : , const OString &rNm
74 : #endif
75 : ) :
76 : m_aCacheObjects(),
77 : pRealFirst( 0 ),
78 : pFirst( 0 ),
79 : pLast( 0 ),
80 236 : nCurMax( nInitSize )
81 : #ifdef DBG_UTIL
82 : , m_aName( rNm )
83 : , m_nAppend( 0 )
84 : , m_nInsertFree( 0 )
85 : , m_nReplace( 0 )
86 : , m_nGetSuccess( 0 )
87 : , m_nGetFail( 0 )
88 : , m_nToTop( 0 )
89 : , m_nDelete( 0 )
90 : , m_nGetSeek( 0 )
91 : , m_nAverageSeekCnt( 0 )
92 : , m_nFlushCnt( 0 )
93 : , m_nFlushedObjects( 0 )
94 : , m_nIncreaseMax( 0 )
95 : , m_nDecreaseMax( 0 )
96 : #endif
97 : {
98 236 : m_aCacheObjects.reserve( nInitSize );
99 236 : }
100 :
101 472 : SwCache::~SwCache()
102 : {
103 : #ifdef DBG_UTIL
104 : SAL_INFO(
105 : "sw.core",
106 : m_aName << "; number of new entries: " << m_nAppend
107 : << "; number of insert on free places: " << m_nInsertFree
108 : << "; number of replacements: " << m_nReplace
109 : << "; number of successful Get's: " << m_nGetSuccess
110 : << "; number of failed Get's: " << m_nGetFail
111 : << "; number or reordering (LRU): " << m_nToTop
112 : << "; number of suppressions: " << m_nDelete
113 : << "; number of Get's without Index: " << m_nGetSeek
114 : << "; number of Seek for Get without Index: " << m_nAverageSeekCnt
115 : << "; number of Flush calls: " << m_nFlushCnt
116 : << "; number of flushed objects: " << m_nFlushedObjects
117 : << "; number of Cache expansions: " << m_nIncreaseMax
118 : << "; number of Cache reductions: " << m_nDecreaseMax);
119 : Check();
120 : #endif
121 :
122 14770 : for(SwCacheObjArr::const_iterator it = m_aCacheObjects.begin(); it != m_aCacheObjects.end(); ++it)
123 14534 : delete *it;
124 236 : }
125 :
126 3124 : void SwCache::Flush( const sal_uInt8 )
127 : {
128 : INCREMENT( m_nFlushCnt );
129 3124 : SwCacheObj *pObj = pRealFirst;
130 3124 : pRealFirst = pFirst = pLast = 0;
131 : SwCacheObj *pTmp;
132 13810 : while ( pObj )
133 : {
134 : #ifdef DBG_UTIL
135 : if ( pObj->IsLocked() )
136 : {
137 : OSL_FAIL( "Flushing locked objects." );
138 : if ( !pRealFirst )
139 : {
140 : pRealFirst = pFirst = pLast = pObj;
141 : pTmp = pObj->GetNext();
142 : pObj->SetNext( 0 ); pObj->SetPrev( 0 );
143 : pObj = pTmp;
144 : }
145 : else
146 : { pLast->SetNext( pObj );
147 : pObj->SetPrev( pLast );
148 : pLast = pObj;
149 : pTmp = pObj->GetNext();
150 : pObj->SetNext( 0 );
151 : pObj = pTmp;
152 : }
153 : }
154 : else
155 : #endif
156 : {
157 7562 : pTmp = pObj;
158 7562 : pObj = pTmp->GetNext();
159 7562 : aFreePositions.push_back( pTmp->GetCachePos() );
160 7562 : m_aCacheObjects[pTmp->GetCachePos()] = NULL;
161 7562 : delete pTmp;
162 : INCREMENT( m_nFlushedObjects );
163 : }
164 : }
165 3124 : }
166 :
167 336915 : void SwCache::ToTop( SwCacheObj *pObj )
168 : {
169 : INCREMENT( m_nToTop );
170 :
171 : // cut object out of chain and insert at beginning
172 336915 : if ( pRealFirst == pObj ) // pFirst was checked by caller
173 : {
174 : CHECK;
175 32 : return;
176 : }
177 :
178 336883 : if ( !pRealFirst )
179 : {
180 : // the first will be inserted
181 : OSL_ENSURE( !pFirst && !pLast, "First not first." );
182 0 : pRealFirst = pFirst = pLast = pObj;
183 : CHECK;
184 0 : return;
185 : }
186 :
187 : // cut
188 336883 : if ( pObj == pLast )
189 : {
190 : OSL_ENSURE( pObj->GetPrev(), "Last but no Prev." );
191 36899 : pLast = pObj->GetPrev();
192 36899 : pLast->SetNext( 0 );
193 : }
194 : else
195 : {
196 299984 : if ( pObj->GetNext() )
197 299984 : pObj->GetNext()->SetPrev( pObj->GetPrev() );
198 299984 : if ( pObj->GetPrev() )
199 299984 : pObj->GetPrev()->SetNext( pObj->GetNext() );
200 : }
201 :
202 : // paste at the (virtual) beginning
203 336883 : if ( pRealFirst == pFirst )
204 : {
205 331685 : pRealFirst->SetPrev( pObj );
206 331685 : pObj->SetNext( pRealFirst );
207 331685 : pObj->SetPrev( 0 );
208 331685 : pRealFirst = pFirst = pObj;
209 : CHECK;
210 : }
211 : else
212 : {
213 : OSL_ENSURE( pFirst, "ToTop, First ist not RealFirst an Empty." );
214 :
215 5198 : if ( pFirst->GetPrev() )
216 : {
217 5198 : pFirst->GetPrev()->SetNext( pObj );
218 5198 : pObj->SetPrev( pFirst->GetPrev() );
219 : }
220 : else
221 0 : pObj->SetPrev( 0 );
222 5198 : pFirst->SetPrev( pObj );
223 5198 : pObj->SetNext( pFirst );
224 5198 : pFirst = pObj;
225 : CHECK;
226 : }
227 : }
228 :
229 2259803 : SwCacheObj *SwCache::Get( const void *pOwner, const sal_uInt16 nIndex,
230 : const bool bToTop )
231 : {
232 : SwCacheObj *pRet;
233 2259803 : if ( 0 != (pRet = (nIndex < m_aCacheObjects.size()) ? m_aCacheObjects[ nIndex ] : 0) )
234 : {
235 2233159 : if ( !pRet->IsOwner( pOwner ) )
236 7761 : pRet = 0;
237 2225398 : else if ( bToTop && pRet != pFirst )
238 92971 : ToTop( pRet );
239 : }
240 :
241 : #ifdef DBG_UTIL
242 : if ( pRet )
243 : ++m_nGetSuccess;
244 : else
245 : ++m_nGetFail;
246 : #endif
247 :
248 2259803 : return pRet;
249 : }
250 :
251 568335 : SwCacheObj *SwCache::Get( const void *pOwner, const bool bToTop )
252 : {
253 568335 : SwCacheObj *pRet = pRealFirst;
254 3324666 : while ( pRet && !pRet->IsOwner( pOwner ) )
255 : {
256 : INCREMENT( m_nAverageSeekCnt );
257 2187996 : pRet = pRet->GetNext();
258 : }
259 :
260 568335 : if ( bToTop && pRet && pRet != pFirst )
261 243944 : ToTop( pRet );
262 :
263 : #ifdef DBG_UTIL
264 : if ( pRet )
265 : ++m_nGetSuccess;
266 : else
267 : ++m_nGetFail;
268 : ++m_nGetSeek;
269 : #endif
270 568335 : return pRet;
271 : }
272 :
273 36986 : void SwCache::DeleteObj( SwCacheObj *pObj )
274 : {
275 : CHECK;
276 : OSL_ENSURE( !pObj->IsLocked(), "SwCache::Delete: object is locked." );
277 36986 : if ( pObj->IsLocked() )
278 36986 : return;
279 :
280 36986 : if ( pFirst == pObj )
281 : {
282 10945 : if ( pFirst->GetNext() )
283 8277 : pFirst = pFirst->GetNext();
284 : else
285 2668 : pFirst = pFirst->GetPrev();
286 : }
287 36986 : if ( pRealFirst == pObj )
288 10945 : pRealFirst = pRealFirst->GetNext();
289 36986 : if ( pLast == pObj )
290 5811 : pLast = pLast->GetPrev();
291 36986 : if ( pObj->GetPrev() )
292 26041 : pObj->GetPrev()->SetNext( pObj->GetNext() );
293 36986 : if ( pObj->GetNext() )
294 31175 : pObj->GetNext()->SetPrev( pObj->GetPrev() );
295 :
296 36986 : aFreePositions.push_back( pObj->GetCachePos() );
297 36986 : m_aCacheObjects[pObj->GetCachePos()] = NULL;
298 36986 : delete pObj;
299 :
300 : CHECK;
301 36986 : if ( m_aCacheObjects.size() > nCurMax &&
302 0 : (nCurMax <= (m_aCacheObjects.size() - aFreePositions.size())) )
303 : {
304 : // Shrink if possible.To do so we need enough free positions.
305 : // Unpleasent side effect: positions will be moved and the owner of
306 : // these might not find them afterwards
307 0 : for ( size_t i = 0; i < m_aCacheObjects.size(); ++i )
308 : {
309 0 : SwCacheObj *pTmpObj = m_aCacheObjects[i];
310 0 : if ( !pTmpObj )
311 0 : { m_aCacheObjects.erase( m_aCacheObjects.begin() + i );
312 0 : --i;
313 : }
314 : else
315 : {
316 0 : pTmpObj->SetCachePos( i );
317 : }
318 : }
319 0 : aFreePositions.clear();
320 : }
321 : CHECK;
322 : }
323 :
324 36986 : void SwCache::Delete( const void *pOwner )
325 : {
326 : INCREMENT( m_nDelete );
327 : SwCacheObj *pObj;
328 36986 : if ( 0 != (pObj = Get( pOwner, false )) )
329 36986 : DeleteObj( pObj );
330 36986 : }
331 :
332 113881 : bool SwCache::Insert( SwCacheObj *pNew )
333 : {
334 : CHECK;
335 : OSL_ENSURE( !pNew->GetPrev() && !pNew->GetNext(), "New but not new." );
336 :
337 : sal_uInt16 nPos;
338 113881 : if ( m_aCacheObjects.size() < nCurMax )
339 : {
340 : // there is still space; insert directly
341 : INCREMENT( m_nAppend );
342 14534 : nPos = m_aCacheObjects.size();
343 14534 : m_aCacheObjects.push_back(pNew);
344 : }
345 99347 : else if ( !aFreePositions.empty() )
346 : {
347 : // there are placeholders; use the last of those
348 : INCREMENT( m_nInsertFree );
349 39326 : const sal_uInt16 nFreePos = aFreePositions.size() - 1;
350 39326 : nPos = aFreePositions[ nFreePos ];
351 39326 : m_aCacheObjects[nPos] = pNew;
352 39326 : aFreePositions.erase( aFreePositions.begin() + nFreePos );
353 : }
354 : else
355 : {
356 : INCREMENT( m_nReplace );
357 : // the last of the LRU has to go
358 60021 : SwCacheObj *pObj = pLast;
359 :
360 137179 : while ( pObj && pObj->IsLocked() )
361 17137 : pObj = pObj->GetPrev();
362 60021 : if ( !pObj )
363 : {
364 : OSL_FAIL( "Cache overflow." );
365 0 : return false;
366 : }
367 :
368 60021 : nPos = pObj->GetCachePos();
369 60021 : if ( pObj == pLast )
370 : { OSL_ENSURE( pObj->GetPrev(), "Last but no Prev" );
371 47368 : pLast = pObj->GetPrev();
372 47368 : pLast->SetNext( 0 );
373 : }
374 : else
375 : {
376 12653 : if ( pObj->GetPrev() )
377 12653 : pObj->GetPrev()->SetNext( pObj->GetNext() );
378 12653 : if ( pObj->GetNext() )
379 12653 : pObj->GetNext()->SetPrev( pObj->GetPrev() );
380 : }
381 60021 : delete pObj;
382 60021 : m_aCacheObjects[nPos] = pNew;
383 : }
384 113881 : pNew->SetCachePos( nPos );
385 :
386 113881 : if ( pFirst )
387 : {
388 107992 : if ( pFirst->GetPrev() )
389 7342 : { pFirst->GetPrev()->SetNext( pNew );
390 7342 : pNew->SetPrev( pFirst->GetPrev() );
391 : }
392 107992 : pFirst->SetPrev( pNew );
393 107992 : pNew->SetNext( pFirst );
394 : }
395 : else
396 : { OSL_ENSURE( !pLast, "Last but no First." );
397 5889 : pLast = pNew;
398 : }
399 113881 : if ( pFirst == pRealFirst )
400 106539 : pRealFirst = pNew;
401 113881 : pFirst = pNew;
402 :
403 : CHECK;
404 113881 : return true;
405 : }
406 :
407 26777873 : void SwCache::SetLRUOfst( const sal_uInt16 nOfst )
408 : {
409 26777873 : if ( !pRealFirst || ((m_aCacheObjects.size() - aFreePositions.size()) < nOfst) )
410 53554354 : return;
411 :
412 : CHECK;
413 1392 : pFirst = pRealFirst;
414 418984 : for ( sal_uInt16 i = 0; i < m_aCacheObjects.size() && i < nOfst; ++i )
415 : {
416 417597 : if ( pFirst->GetNext() && pFirst->GetNext()->GetNext() )
417 417592 : pFirst = pFirst->GetNext();
418 : else
419 5 : break;
420 : }
421 : CHECK;
422 : }
423 :
424 113881 : SwCacheObj::SwCacheObj( const void *pOwn ) :
425 : pNext( 0 ),
426 : pPrev( 0 ),
427 : nCachePos( USHRT_MAX ),
428 : nLock( 0 ),
429 113881 : pOwner( pOwn )
430 : {
431 113881 : }
432 :
433 113881 : SwCacheObj::~SwCacheObj()
434 : {
435 113881 : }
436 :
437 : #ifdef DBG_UTIL
438 : void SwCacheObj::Lock()
439 : {
440 : OSL_ENSURE( nLock < UCHAR_MAX, "Too many Locks for CacheObject." );
441 : ++nLock;
442 : }
443 :
444 : void SwCacheObj::Unlock()
445 : {
446 : OSL_ENSURE( nLock, "No more Locks available." );
447 : --nLock;
448 : }
449 : #endif
450 :
451 1863723 : SwCacheAccess::~SwCacheAccess()
452 : {
453 1863723 : if ( pObj )
454 1863723 : pObj->Unlock();
455 1863723 : }
456 :
457 111175 : void SwCacheAccess::_Get()
458 : {
459 : OSL_ENSURE( !pObj, "SwCacheAcces Obj already available." );
460 :
461 111175 : pObj = NewObj();
462 111175 : if ( !rCache.Insert( pObj ) )
463 : {
464 0 : delete pObj;
465 0 : pObj = 0;
466 : }
467 : else
468 : {
469 111175 : pObj->Lock();
470 : }
471 111175 : }
472 :
473 0 : bool SwCacheAccess::IsAvailable() const
474 : {
475 0 : return pObj != 0;
476 : }
477 :
478 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|