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