svl/source/notify/broadcast.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 <svl/broadcast.hxx>
  21 #include <svl/listener.hxx>
  22 #include <svl/hint.hxx>
  23 #include <o3tl/safeint.hxx>
  24 #include <cassert>
  25 #include <algorithm>
  26
  27 /**
  28  Design Notes
  29  -------------------------------
  30
  31  This class is extremely heavily used - we can have millions of broadcasters and listeners and we can also
  32  have a broadcaster that has a million listeners.
  33
  34  So we do a number of things
  35  (*) use a cache-dense listener list (std::vector) because caching effects dominate a lot of operations
  36  (*) use a sorted list to speed up find operations
  37  (*) only sort the list when we absolutely have to, to speed up sequential add/remove operations
  38  (*) defer removing items from the list by (ab)using the last bit of the pointer
  39
  40  Also we have some complications around destruction because
  41  (*) we broadcast a message to indicate that we are destructing
  42  (*) which can trigger arbitrality complicated behaviour, including
  43  (*) adding a removing things from the in-destruction object!
  44
  45 */
  46
  47 static bool isDeletedPtr(SvtListener* p)
  48 {
  49     /** mark deleted entries by toggling the last bit,which is effectively unused, since the struct we point
  50      * to is at least 16-bit aligned. This allows the binary search to continue working even when we have
  51      * deleted entries */
  52     return (reinterpret_cast<uintptr_t>(p) & 0x01) == 0x01;
  53 }
  54
  55 static void markDeletedPtr(SvtListener*& rp)
  56 {
  57     reinterpret_cast<uintptr_t&>(rp) |= 0x01;
  58 }
  59
  60 static void sortListeners(std::vector<SvtListener*>& listeners, size_t firstUnsorted)
  61 {
  62     // Add() only appends new values, so often the container will be sorted expect for one
  63     // or few last items. For larger containers it is much more efficient to just handle
  64     // the unsorted part.
  65     auto sortedEnd = firstUnsorted == 0
  66         ? std::is_sorted_until(listeners.begin(),listeners.end())
  67         : listeners.begin() + firstUnsorted;
  68     if( listeners.end() - sortedEnd == 1 )
  69     {   // Just one item, insert it in the right place.
  70         SvtListener* item = listeners.back();
  71         listeners.pop_back();
  72         listeners.insert( std::upper_bound( listeners.begin(), listeners.end(), item ), item );
  73     }
  74     else if( o3tl::make_unsigned( sortedEnd - listeners.begin()) > listeners.size() * 3 / 4 )
  75     {   // Sort the unsorted part and then merge.
  76         std::sort( sortedEnd, listeners.end());
  77         std::inplace_merge( listeners.begin(), sortedEnd, listeners.end());
  78     }
  79     else
  80     {
  81         std::sort(listeners.begin(), listeners.end());
  82     }
  83 }
  84
  85 void SvtBroadcaster::Normalize() const
  86 {
  87     // clear empty slots first, because then we often have to do very little sorting
  88     if (mnEmptySlots)
  89     {
  90         std::erase_if(maListeners, [] (SvtListener* p) { return isDeletedPtr(p); });
  91         mnEmptySlots = 0;
  92     }
  93
  94     if (mnListenersFirstUnsorted != static_cast<sal_Int32>(maListeners.size()))
  95     {
  96         sortListeners(maListeners, mnListenersFirstUnsorted);
  97         mnListenersFirstUnsorted = maListeners.size();
  98     }
  99
 100     if (!mbDestNormalized)
 101     {
 102         sortListeners(maDestructedListeners, 0);
 103         mbDestNormalized = true;
 104     }
 105 }
 106
 107 void SvtBroadcaster::Add( SvtListener* p )
 108 {
 109     assert(!mbDisposing && "called inside my own destructor?");
 110     assert(!mbAboutToDie && "called after PrepareForDestruction()?");
 111     if (mbDisposing || mbAboutToDie)
 112         return;
 113     // Avoid normalizing if the item appended keeps the container sorted.
 114     auto nRealSize = static_cast<sal_Int32>(maListeners.size() - mnEmptySlots);
 115     auto bSorted = mnListenersFirstUnsorted == nRealSize;
 116     if (maListeners.empty() || (bSorted && maListeners.back() <= p))
 117     {
 118         ++mnListenersFirstUnsorted;
 119         maListeners.push_back(p);
 120         return;
 121     }
 122     // see if we can stuff it into an empty slot, which succeeds surprisingly often in
 123     // some calc workloads where it removes and then re-adds the same listener
 124     if (mnEmptySlots && bSorted)
 125     {
 126         auto it = std::lower_bound(maListeners.begin(), maListeners.end(), p);
 127         if (it != maListeners.end() && isDeletedPtr(*it))
 128         {
 129             *it = p;
 130             ++mnListenersFirstUnsorted;
 131             --mnEmptySlots;
 132             return;
 133         }
 134     }
 135     maListeners.push_back(p);
 136 }
 137
 138 void SvtBroadcaster::Remove( SvtListener* p )
 139 {
 140     if (mbDisposing)
 141         return;
 142
 143     if (mbAboutToDie)
 144     {
 145         // only reset mbDestNormalized if we are going to become unsorted
 146         if (!maDestructedListeners.empty() && maDestructedListeners.back() > p)
 147             mbDestNormalized = false;
 148         maDestructedListeners.push_back(p);
 149         return;
 150     }
 151
 152     // We only need to fully normalize if one or more Add()s have been performed that make the array unsorted.
 153     auto nRealSize = static_cast<sal_Int32>(maListeners.size() - mnEmptySlots);
 154     if (mnListenersFirstUnsorted != nRealSize || (maListeners.size() > 1024 && maListeners.size() / nRealSize > 16))
 155         Normalize();
 156
 157     auto it = std::lower_bound(maListeners.begin(), maListeners.end(), p);
 158     assert (it != maListeners.end() && *it == p);
 159     if (it != maListeners.end() && *it == p)
 160     {
 161         markDeletedPtr(*it);
 162         ++mnEmptySlots;
 163         --mnListenersFirstUnsorted;
 164     }
 165
 166     if (!HasListeners())
 167         ListenersGone();
 168 }
 169
 170 SvtBroadcaster::SvtBroadcaster( const SvtBroadcaster &rBC ) :
 171     mnEmptySlots(0), mnListenersFirstUnsorted(0),
 172     mbAboutToDie(false), mbDisposing(false),
 173     mbDestNormalized(true)
 174 {
 175     assert(!rBC.mbAboutToDie && "copying an object marked with PrepareForDestruction()?");
 176     assert(!rBC.mbDisposing && "copying an object that is in its destructor?");
 177
 178     rBC.Normalize(); // so that insert into ourself is in-order, and therefore we do not need to Normalize()
 179     maListeners.reserve(rBC.maListeners.size());
 180     for (SvtListener* p : rBC.maListeners)
 181          p->StartListening(*this); // this will call back into this->Add()
 182 }
 183
 184 SvtBroadcaster::~SvtBroadcaster()
 185 {
 186     mbDisposing = true;
 187     Broadcast( SfxHint(SfxHintId::Dying) );
 188
 189     Normalize();
 190
 191     // now when both lists are sorted, we can linearly unregister all
 192     // listeners, with the exception of those that already asked to be removed
 193     // during their own destruction
 194     ListenersType::const_iterator dest(maDestructedListeners.begin());
 195     for (auto& rpListener : maListeners)
 196     {
 197         // skip the destructed ones
 198         while (dest != maDestructedListeners.end() && (*dest < rpListener))
 199             ++dest;
 200
 201         if (dest == maDestructedListeners.end() || *dest != rpListener)
 202             rpListener->BroadcasterDying(*this);
 203     }
 204 }
 205
 206 void SvtBroadcaster::Broadcast( const SfxHint &rHint )
 207 {
 208     Normalize();
 209
 210     ListenersType::const_iterator dest(maDestructedListeners.begin());
 211     ListenersType aListeners(maListeners); // this copy is important to avoid erasing entries while iterating
 212     for (auto& rpListener : aListeners)
 213     {
 214         // skip the destructed ones
 215         while (dest != maDestructedListeners.end() && (*dest < rpListener))
 216             ++dest;
 217
 218         if (dest == maDestructedListeners.end() || *dest != rpListener)
 219             rpListener->Notify(rHint);
 220     }
 221 }
 222
 223 void SvtBroadcaster::ListenersGone() {}
 224
 225 SvtBroadcaster::ListenersType& SvtBroadcaster::GetAllListeners()
 226 {
 227     Normalize();
 228     return maListeners;
 229 }
 230
 231 const SvtBroadcaster::ListenersType& SvtBroadcaster::GetAllListeners() const
 232 {
 233     Normalize();
 234     return maListeners;
 235 }
 236
 237 void SvtBroadcaster::PrepareForDestruction()
 238 {
 239     mbAboutToDie = true;
 240     // the reserve() serves two purpose (1) performance (2) makes sure our iterators do not become invalid
 241     maDestructedListeners.reserve(maListeners.size());
 242 }
 243
 244 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */