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> // USHRT_MAX
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", "Objekt 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 :
69 132 : SwCache::SwCache( const sal_uInt16 nInitSize
70 : #ifdef DBG_UTIL
71 : , const OString &rNm
72 : #endif
73 : ) :
74 : m_aCacheObjects(),
75 : pRealFirst( 0 ),
76 : pFirst( 0 ),
77 : pLast( 0 ),
78 132 : nCurMax( nInitSize )
79 : #ifdef DBG_UTIL
80 : , m_aName( rNm )
81 : , m_nAppend( 0 )
82 : , m_nInsertFree( 0 )
83 : , m_nReplace( 0 )
84 : , m_nGetSuccess( 0 )
85 : , m_nGetFail( 0 )
86 : , m_nToTop( 0 )
87 : , m_nDelete( 0 )
88 : , m_nGetSeek( 0 )
89 : , m_nAverageSeekCnt( 0 )
90 : , m_nFlushCnt( 0 )
91 : , m_nFlushedObjects( 0 )
92 : , m_nIncreaseMax( 0 )
93 : , m_nDecreaseMax( 0 )
94 : #endif
95 : {
96 132 : m_aCacheObjects.reserve( (sal_uInt8)nInitSize );
97 132 : }
98 :
99 264 : SwCache::~SwCache()
100 : {
101 : #ifdef DBG_UTIL
102 : SAL_INFO(
103 : "sw.core",
104 : m_aName << "; number of new entries: " << m_nAppend
105 : << "; number of insert on free places: " << m_nInsertFree
106 : << "; number of replacements: " << m_nReplace
107 : << "; number of successful Get's: " << m_nGetSuccess
108 : << "; number of failed Get's: " << m_nGetFail
109 : << "; number or reordering (LRU): " << m_nToTop
110 : << "; number of suppressions: " << m_nDelete
111 : << "; number of Get's without Index: " << m_nGetSeek
112 : << "; number of Seek for Get without Index: " << m_nAverageSeekCnt
113 : << "; number of Flush calls: " << m_nFlushCnt
114 : << "; number of flushed objects: " << m_nFlushedObjects
115 : << "; number of Cache expansions: " << m_nIncreaseMax
116 : << "; number of Cache reductions: " << m_nDecreaseMax);
117 : Check();
118 : #endif
119 :
120 5248 : for(SwCacheObjArr::const_iterator it = m_aCacheObjects.begin(); it != m_aCacheObjects.end(); ++it)
121 5116 : delete *it;
122 132 : }
123 :
124 821 : void SwCache::Flush( const sal_uInt8 )
125 : {
126 : INCREMENT( m_nFlushCnt );
127 821 : SwCacheObj *pObj = pRealFirst;
128 821 : pRealFirst = pFirst = pLast = 0;
129 : SwCacheObj *pTmp;
130 3080 : while ( pObj )
131 : {
132 : #ifdef DBG_UTIL
133 : if ( pObj->IsLocked() )
134 : {
135 : OSL_FAIL( "Flushing locked objects." );
136 : if ( !pRealFirst )
137 : {
138 : pRealFirst = pFirst = pLast = pObj;
139 : pTmp = pObj->GetNext();
140 : pObj->SetNext( 0 ); pObj->SetPrev( 0 );
141 : pObj = pTmp;
142 : }
143 : else
144 : { pLast->SetNext( pObj );
145 : pObj->SetPrev( pLast );
146 : pLast = pObj;
147 : pTmp = pObj->GetNext();
148 : pObj->SetNext( 0 );
149 : pObj = pTmp;
150 : }
151 : }
152 : else
153 : #endif
154 : {
155 1438 : pTmp = (SwCacheObj*)pObj;
156 1438 : pObj = pTmp->GetNext();
157 1438 : aFreePositions.push_back( pTmp->GetCachePos() );
158 1438 : m_aCacheObjects[pTmp->GetCachePos()] = NULL;
159 1438 : delete pTmp;
160 : INCREMENT( m_nFlushedObjects );
161 : }
162 : }
163 821 : }
164 :
165 59424 : void SwCache::ToTop( SwCacheObj *pObj )
166 : {
167 : INCREMENT( m_nToTop );
168 :
169 : // cut object out of chain and insert at beginning
170 59424 : if ( pRealFirst == pObj ) // pFirst was checked by caller
171 : {
172 : CHECK;
173 0 : return;
174 : }
175 :
176 59424 : if ( !pRealFirst )
177 : {
178 : // the first will be inserted
179 : OSL_ENSURE( !pFirst && !pLast, "First not first." );
180 0 : pRealFirst = pFirst = pLast = pObj;
181 : CHECK;
182 0 : return;
183 : }
184 :
185 : // cut
186 59424 : if ( pObj == pLast )
187 : {
188 : OSL_ENSURE( pObj->GetPrev(), "Last but no Prev." );
189 14541 : pLast = pObj->GetPrev();
190 14541 : pLast->SetNext( 0 );
191 : }
192 : else
193 : {
194 44883 : if ( pObj->GetNext() )
195 44883 : pObj->GetNext()->SetPrev( pObj->GetPrev() );
196 44883 : if ( pObj->GetPrev() )
197 44883 : pObj->GetPrev()->SetNext( pObj->GetNext() );
198 : }
199 :
200 : // paste at the (virtual) beginning
201 59424 : if ( pRealFirst == pFirst )
202 : {
203 59424 : pRealFirst->SetPrev( pObj );
204 59424 : pObj->SetNext( pRealFirst );
205 59424 : pObj->SetPrev( 0 );
206 59424 : pRealFirst = pFirst = pObj;
207 : CHECK;
208 : }
209 : else
210 : {
211 : OSL_ENSURE( pFirst, "ToTop, First ist not RealFirst an Empty." );
212 :
213 0 : if ( pFirst->GetPrev() )
214 : {
215 0 : pFirst->GetPrev()->SetNext( pObj );
216 0 : pObj->SetPrev( pFirst->GetPrev() );
217 : }
218 : else
219 0 : pObj->SetPrev( 0 );
220 0 : pFirst->SetPrev( pObj );
221 0 : pObj->SetNext( pFirst );
222 0 : pFirst = pObj;
223 : CHECK;
224 : }
225 : }
226 :
227 569950 : SwCacheObj *SwCache::Get( const void *pOwner, const sal_uInt16 nIndex,
228 : const sal_Bool bToTop )
229 : {
230 : SwCacheObj *pRet;
231 569950 : if ( 0 != (pRet = (nIndex < m_aCacheObjects.size()) ? m_aCacheObjects[ nIndex ] : 0) )
232 : {
233 567113 : if ( !pRet->IsOwner( pOwner ) )
234 135 : pRet = 0;
235 566978 : else if ( bToTop && pRet != pFirst )
236 10124 : ToTop( pRet );
237 : }
238 :
239 : #ifdef DBG_UTIL
240 : if ( pRet )
241 : ++m_nGetSuccess;
242 : else
243 : ++m_nGetFail;
244 : #endif
245 :
246 569950 : return pRet;
247 : }
248 :
249 135731 : SwCacheObj *SwCache::Get( const void *pOwner, const sal_Bool bToTop )
250 : {
251 135731 : SwCacheObj *pRet = pRealFirst;
252 620524 : while ( pRet && !pRet->IsOwner( pOwner ) )
253 : {
254 : INCREMENT( m_nAverageSeekCnt );
255 349062 : pRet = pRet->GetNext();
256 : }
257 :
258 135731 : if ( bToTop && pRet && pRet != pFirst )
259 49300 : ToTop( pRet );
260 :
261 : #ifdef DBG_UTIL
262 : if ( pRet )
263 : ++m_nGetSuccess;
264 : else
265 : ++m_nGetFail;
266 : ++m_nGetSeek;
267 : #endif
268 135731 : return pRet;
269 : }
270 :
271 8354 : void SwCache::DeleteObj( SwCacheObj *pObj )
272 : {
273 : CHECK;
274 : OSL_ENSURE( !pObj->IsLocked(), "SwCache::Delete: object is locked." );
275 8354 : if ( pObj->IsLocked() )
276 8354 : return;
277 :
278 8354 : if ( pFirst == pObj )
279 : {
280 2694 : if ( pFirst->GetNext() )
281 1966 : pFirst = pFirst->GetNext();
282 : else
283 728 : pFirst = pFirst->GetPrev();
284 : }
285 8354 : if ( pRealFirst == pObj )
286 2694 : pRealFirst = pRealFirst->GetNext();
287 8354 : if ( pLast == pObj )
288 1347 : pLast = pLast->GetPrev();
289 8354 : if ( pObj->GetPrev() )
290 5660 : pObj->GetPrev()->SetNext( pObj->GetNext() );
291 8354 : if ( pObj->GetNext() )
292 7007 : pObj->GetNext()->SetPrev( pObj->GetPrev() );
293 :
294 8354 : aFreePositions.push_back( pObj->GetCachePos() );
295 8354 : m_aCacheObjects[pObj->GetCachePos()] = NULL;
296 8354 : delete pObj;
297 :
298 : CHECK;
299 8354 : if ( m_aCacheObjects.size() > nCurMax &&
300 0 : (nCurMax <= (m_aCacheObjects.size() - aFreePositions.size())) )
301 : {
302 : // Shrink if possible.To do so we need enough free positions.
303 : // Unpleasent side effect: positions will be moved and the owner of
304 : // these might not find them afterwards
305 0 : for ( sal_uInt16 i = 0; i < m_aCacheObjects.size(); ++i )
306 : {
307 0 : SwCacheObj *pTmpObj = m_aCacheObjects[i];
308 0 : if ( !pTmpObj )
309 0 : { m_aCacheObjects.erase( m_aCacheObjects.begin() + i );
310 0 : --i;
311 : }
312 : else
313 : {
314 0 : pTmpObj->SetCachePos( i );
315 : }
316 : }
317 0 : aFreePositions.clear();
318 : }
319 : CHECK;
320 : }
321 :
322 8354 : void SwCache::Delete( const void *pOwner )
323 : {
324 : INCREMENT( m_nDelete );
325 : SwCacheObj *pObj;
326 8354 : if ( 0 != (pObj = Get( pOwner, sal_Bool(sal_False) )) )
327 8354 : DeleteObj( pObj );
328 8354 : }
329 :
330 14794 : sal_Bool SwCache::Insert( SwCacheObj *pNew )
331 : {
332 : CHECK;
333 : OSL_ENSURE( !pNew->GetPrev() && !pNew->GetNext(), "New but not new." );
334 :
335 : sal_uInt16 nPos;
336 14794 : if ( m_aCacheObjects.size() < nCurMax )
337 : {
338 : // there is still space; insert directly
339 : INCREMENT( m_nAppend );
340 5116 : nPos = m_aCacheObjects.size();
341 5116 : m_aCacheObjects.push_back(pNew);
342 : }
343 9678 : else if ( !aFreePositions.empty() )
344 : {
345 : // there are placeholders; use the last of those
346 : INCREMENT( m_nInsertFree );
347 7606 : const sal_uInt16 nFreePos = aFreePositions.size() - 1;
348 7606 : nPos = aFreePositions[ nFreePos ];
349 7606 : m_aCacheObjects[nPos] = pNew;
350 7606 : aFreePositions.erase( aFreePositions.begin() + nFreePos );
351 : }
352 : else
353 : {
354 : INCREMENT( m_nReplace );
355 : // the last of the LRU has to go
356 2072 : SwCacheObj *pObj = pLast;
357 :
358 4144 : while ( pObj && pObj->IsLocked() )
359 0 : pObj = pObj->GetPrev();
360 2072 : if ( !pObj )
361 : {
362 : OSL_FAIL( "Cache overflow." );
363 0 : return sal_False;
364 : }
365 :
366 2072 : nPos = pObj->GetCachePos();
367 2072 : if ( pObj == pLast )
368 : { OSL_ENSURE( pObj->GetPrev(), "Last but no Prev" );
369 2072 : pLast = pObj->GetPrev();
370 2072 : pLast->SetNext( 0 );
371 : }
372 : else
373 : {
374 0 : if ( pObj->GetPrev() )
375 0 : pObj->GetPrev()->SetNext( pObj->GetNext() );
376 0 : if ( pObj->GetNext() )
377 0 : pObj->GetNext()->SetPrev( pObj->GetPrev() );
378 : }
379 2072 : delete pObj;
380 2072 : m_aCacheObjects[nPos] = pNew;
381 : }
382 14794 : pNew->SetCachePos( nPos );
383 :
384 14794 : if ( pFirst )
385 : {
386 13187 : if ( pFirst->GetPrev() )
387 0 : { pFirst->GetPrev()->SetNext( pNew );
388 0 : pNew->SetPrev( pFirst->GetPrev() );
389 : }
390 13187 : pFirst->SetPrev( pNew );
391 13187 : pNew->SetNext( pFirst );
392 : }
393 : else
394 : { OSL_ENSURE( !pLast, "Last but no First." );
395 1607 : pLast = pNew;
396 : }
397 14794 : if ( pFirst == pRealFirst )
398 14794 : pRealFirst = pNew;
399 14794 : pFirst = pNew;
400 :
401 : CHECK;
402 14794 : return sal_True;
403 : }
404 :
405 1527 : void SwCache::SetLRUOfst( const sal_uInt16 nOfst )
406 : {
407 1527 : if ( !pRealFirst || ((m_aCacheObjects.size() - aFreePositions.size()) < nOfst) )
408 3014 : return;
409 :
410 : CHECK;
411 40 : pFirst = pRealFirst;
412 12039 : for ( sal_uInt16 i = 0; i < m_aCacheObjects.size() && i < nOfst; ++i )
413 : {
414 12000 : if ( pFirst->GetNext() && pFirst->GetNext()->GetNext() )
415 11999 : pFirst = pFirst->GetNext();
416 : else
417 1 : break;
418 : }
419 : CHECK;
420 : }
421 :
422 14794 : SwCacheObj::SwCacheObj( const void *pOwn ) :
423 : pNext( 0 ),
424 : pPrev( 0 ),
425 : nCachePos( USHRT_MAX ),
426 : nLock( 0 ),
427 14794 : pOwner( pOwn )
428 : {
429 14794 : }
430 :
431 14794 : SwCacheObj::~SwCacheObj()
432 : {
433 14794 : }
434 :
435 : #ifdef DBG_UTIL
436 : void SwCacheObj::Lock()
437 : {
438 : OSL_ENSURE( nLock < UCHAR_MAX, "Too many Locks for CacheObject." );
439 : ++nLock;
440 : }
441 :
442 : void SwCacheObj::Unlock()
443 : {
444 : OSL_ENSURE( nLock, "No more Locks available." );
445 : --nLock;
446 : }
447 : #endif
448 :
449 425496 : SwCacheAccess::~SwCacheAccess()
450 : {
451 425496 : if ( pObj )
452 425496 : pObj->Unlock();
453 425496 : }
454 :
455 14725 : void SwCacheAccess::_Get()
456 : {
457 : OSL_ENSURE( !pObj, "SwCacheAcces Obj already available." );
458 :
459 14725 : pObj = NewObj();
460 14725 : if ( !rCache.Insert( pObj ) )
461 : {
462 0 : delete pObj;
463 0 : pObj = 0;
464 : }
465 : else
466 : {
467 14725 : pObj->Lock();
468 : }
469 14725 : }
470 :
471 0 : sal_Bool SwCacheAccess::IsAvailable() const
472 : {
473 0 : return pObj != 0;
474 : }
475 :
476 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
