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