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 <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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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         for ( size_t i = 0; i < m_aCacheObjects.size(); ++i )
 305         {
 306             SwCacheObj *pTmpObj = m_aCacheObjects[i].get();
 307             if ( !pTmpObj )
 308             {
 309                 m_aCacheObjects.erase( m_aCacheObjects.begin() + i );
 310                 --i;
 311             }
 312             else
 313             {
 314                 pTmpObj->SetCachePos( i );
 315             }
 316         }
 317         m_aFreePositions.clear();
 318     }
 319     CHECK;
 320 }
 321
 322 void SwCache::Delete(void const*const pOwner, sal_uInt16 const nIndex)
 323 {
 324     INCREMENT( m_nDelete );
 325     if (SwCacheObj *const pObj = Get(pOwner, nIndex, false))
 326         DeleteObj(pObj);
 327 }
 328
 329 void SwCache::Delete( const void *pOwner )
 330 {
 331     INCREMENT( m_nDelete );
 332     SwCacheObj *pObj = Get( pOwner, false );
 333     if ( pObj )
 334         DeleteObj( pObj );
 335 }
 336
 337 bool SwCache::Insert(SwCacheObj *const pNew, bool const isDuplicateOwnerAllowed)
 338 {
 339     CHECK;
 340     OSL_ENSURE( !pNew->GetPrev() && !pNew->GetNext(), "New but not new." );
 341     if (!isDuplicateOwnerAllowed)
 342     {
 343         for (auto const & rpObj : m_aCacheObjects)
 344         {   // check owner doesn't have a cache object yet; required for SwTextLine
 345             assert(!rpObj || rpObj->GetOwner() != pNew->GetOwner());
 346             (void) rpObj;
 347         }
 348     }
 349
 350     sal_uInt16 nPos;
 351     if ( m_aCacheObjects.size() < m_nCurMax )
 352     {
 353         // there is still space; insert directly
 354         INCREMENT( m_nAppend );
 355         nPos = m_aCacheObjects.size();
 356         m_aCacheObjects.emplace_back(pNew);
 357     }
 358     else if ( !m_aFreePositions.empty() )
 359     {
 360         // there are placeholders; use the last of those
 361         INCREMENT( m_nInsertFree );
 362         const sal_uInt16 nFreePos = m_aFreePositions.size() - 1;
 363         nPos = m_aFreePositions[ nFreePos ];
 364         m_aCacheObjects[nPos].reset(pNew);
 365         m_aFreePositions.erase( m_aFreePositions.begin() + nFreePos );
 366     }
 367     else
 368     {
 369         INCREMENT( m_nReplace );
 370         // the last of the LRU has to go
 371         SwCacheObj *pObj = m_pLast;
 372
 373         while ( pObj && pObj->IsLocked() )
 374             pObj = pObj->GetPrev();
 375         if ( !pObj )
 376         {
 377             SAL_WARN("sw.core", "SwCache overflow.");
 378             IncreaseMax(100); // embiggen & try again
 379             return Insert(pNew, isDuplicateOwnerAllowed);
 380         }
 381
 382         nPos = pObj->GetCachePos();
 383         if ( pObj == m_pLast )
 384         {
 385             m_pLast = pObj->GetPrev();
 386             assert(m_pLast); // must have capacity > 1
 387         }
 388         if (pObj == m_pFirst)
 389         {
 390             if (pObj->GetNext())
 391             {
 392                 m_pFirst = pObj->GetNext();
 393             }
 394             else
 395             {
 396                 m_pFirst = pObj->GetPrev();
 397             }
 398             assert(m_pFirst); // must have capacity > 1
 399         }
 400         if (pObj == m_pRealFirst)
 401         {
 402             m_pRealFirst = pObj->GetNext();
 403             assert(m_pRealFirst); // must have capacity > 1
 404         }
 405         if (pObj->GetPrev())
 406         {
 407             pObj->GetPrev()->SetNext( pObj->GetNext() );
 408         }
 409         if (pObj->GetNext())
 410         {
 411             pObj->GetNext()->SetPrev( pObj->GetPrev() );
 412         }
 413         m_aCacheObjects[nPos].reset(pNew);
 414     }
 415     pNew->SetCachePos( nPos );
 416
 417     if ( m_pFirst )
 418     {
 419         if ( m_pFirst->GetPrev() )
 420         {   m_pFirst->GetPrev()->SetNext( pNew );
 421             pNew->SetPrev( m_pFirst->GetPrev() );
 422         }
 423         m_pFirst->SetPrev( pNew );
 424         pNew->SetNext( m_pFirst );
 425     }
 426     else
 427     {
 428         assert(!m_pLast);
 429         m_pLast = pNew;
 430     }
 431     if ( m_pFirst == m_pRealFirst )
 432         m_pRealFirst = pNew;
 433     m_pFirst = pNew;
 434
 435     CHECK;
 436     return true;
 437 }
 438
 439 void SwCache::SetLRUOfst( const sal_uInt16 nOfst )
 440 {
 441     assert(nOfst < m_nCurMax);
 442     if ( !m_pRealFirst || ((m_aCacheObjects.size() - m_aFreePositions.size()) < nOfst) )
 443         return;
 444
 445     CHECK;
 446     m_pFirst = m_pRealFirst;
 447     for ( sal_uInt16 i = 0; i < m_aCacheObjects.size() && i < nOfst; ++i )
 448     {
 449         if ( m_pFirst->GetNext() && m_pFirst->GetNext()->GetNext() )
 450             m_pFirst = m_pFirst->GetNext();
 451         else
 452             break;
 453     }
 454     CHECK;
 455 }
 456
 457 SwCacheObj::SwCacheObj( const void *pOwn ) :
 458     m_pNext( nullptr ),
 459     m_pPrev( nullptr ),
 460     m_nCachePos( USHRT_MAX ),
 461     m_nLock( 0 ),
 462     m_pOwner( pOwn )
 463 {
 464 }
 465
 466 SwCacheObj::~SwCacheObj()
 467 {
 468 }
 469
 470 #ifdef DBG_UTIL
 471 void SwCacheObj::Lock()
 472 {
 473     assert( m_nLock < UCHAR_MAX && "Too many Locks for CacheObject." );
 474     ++m_nLock;
 475 }
 476
 477 void SwCacheObj::Unlock()
 478 {
 479     assert( m_nLock && "No more Locks available." );
 480     --m_nLock;
 481 }
 482 #endif
 483
 484 SwCacheAccess::~SwCacheAccess()
 485 {
 486     if ( m_pObj )
 487         m_pObj->Unlock();
 488 }
 489
 490 void SwCacheAccess::Get_(bool const isDuplicateOwnerAllowed)
 491 {
 492     OSL_ENSURE( !m_pObj, "SwCacheAcces Obj already available." );
 493
 494     m_pObj = NewObj();
 495     if (!m_rCache.Insert(m_pObj, isDuplicateOwnerAllowed))
 496     {
 497         delete m_pObj;
 498         m_pObj = nullptr;
 499     }
 500     else
 501     {
 502         m_pObj->Lock();
 503     }
 504 }
 505
 506 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */