sw/source/core/bastyp/swcache.cxx

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