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         maListeners.erase(
  91             std::remove_if(maListeners.begin(), maListeners.end(), [] (SvtListener* p) { return isDeletedPtr(p); }),
  92             maListeners.end());
  93         mnEmptySlots = 0;
  94     }
  95
  96     if (mnListenersFirstUnsorted != static_cast<sal_Int32>(maListeners.size()))
  97     {
  98         sortListeners(maListeners, mnListenersFirstUnsorted);
  99         mnListenersFirstUnsorted = maListeners.size();
 100     }
 101
 102     if (!mbDestNormalized)
 103     {
 104         sortListeners(maDestructedListeners, 0);
 105         mbDestNormalized = true;
 106     }
 107 }
 108
 109 void SvtBroadcaster::Add( SvtListener* p )
 110 {
 111     assert(!mbDisposing && "called inside my own destructor?");
 112     assert(!mbAboutToDie && "called after PrepareForDestruction()?");
 113     if (mbDisposing || mbAboutToDie)
 114         return;
 115     // Avoid normalizing if the item appended keeps the container sorted.
 116     auto nRealSize = static_cast<sal_Int32>(maListeners.size() - mnEmptySlots);
 117     auto bSorted = mnListenersFirstUnsorted == nRealSize;
 118     if (maListeners.empty() || (bSorted && maListeners.back() <= p))
 119     {
 120         ++mnListenersFirstUnsorted;
 121         maListeners.push_back(p);
 122         return;
 123     }
 124     // see if we can stuff it into an empty slot, which succeeds surprisingly often in
 125     // some calc workloads where it removes and then re-adds the same listener
 126     if (mnEmptySlots && bSorted)
 127     {
 128         auto it = std::lower_bound(maListeners.begin(), maListeners.end(), p);
 129         if (it != maListeners.end() && isDeletedPtr(*it))
 130         {
 131             *it = p;
 132             ++mnListenersFirstUnsorted;
 133             --mnEmptySlots;
 134             return;
 135         }
 136     }
 137     maListeners.push_back(p);
 138 }
 139
 140 void SvtBroadcaster::Remove( SvtListener* p )
 141 {
 142     if (mbDisposing)
 143         return;
 144
 145     if (mbAboutToDie)
 146     {
 147         // only reset mbDestNormalized if we are going to become unsorted
 148         if (!maDestructedListeners.empty() && maDestructedListeners.back() > p)
 149             mbDestNormalized = false;
 150         maDestructedListeners.push_back(p);
 151         return;
 152     }
 153
 154     // We only need to fully normalize if one or more Add()s have been performed that make the array unsorted.
 155     auto nRealSize = static_cast<sal_Int32>(maListeners.size() - mnEmptySlots);
 156     if (mnListenersFirstUnsorted != nRealSize || (maListeners.size() > 1024 && maListeners.size() / nRealSize > 16))
 157         Normalize();
 158
 159     auto it = std::lower_bound(maListeners.begin(), maListeners.end(), p);
 160     assert (it != maListeners.end() && *it == p);
 161     if (it != maListeners.end() && *it == p)
 162     {
 163         markDeletedPtr(*it);
 164         ++mnEmptySlots;
 165         --mnListenersFirstUnsorted;
 166     }
 167
 168     if (!HasListeners())
 169         ListenersGone();
 170 }
 171
 172 SvtBroadcaster::SvtBroadcaster( const SvtBroadcaster &rBC ) :
 173     mnEmptySlots(0), mnListenersFirstUnsorted(0),
 174     mbAboutToDie(false), mbDisposing(false),
 175     mbDestNormalized(true)
 176 {
 177     assert(!rBC.mbAboutToDie && "copying an object marked with PrepareForDestruction()?");
 178     assert(!rBC.mbDisposing && "copying an object that is in its destructor?");
 179
 180     rBC.Normalize(); // so that insert into ourself is in-order, and therefore we do not need to Normalize()
 181     maListeners.reserve(rBC.maListeners.size());
 182     for (SvtListener* p : rBC.maListeners)
 183          p->StartListening(*this); // this will call back into this->Add()
 184 }
 185
 186 SvtBroadcaster::~SvtBroadcaster()
 187 {
 188     mbDisposing = true;
 189     Broadcast( SfxHint(SfxHintId::Dying) );
 190
 191     Normalize();
 192
 193     // now when both lists are sorted, we can linearly unregister all
 194     // listeners, with the exception of those that already asked to be removed
 195     // during their own destruction
 196     ListenersType::const_iterator dest(maDestructedListeners.begin());
 197     for (auto& rpListener : maListeners)
 198     {
 199         // skip the destructed ones
 200         while (dest != maDestructedListeners.end() && (*dest < rpListener))
 201             ++dest;
 202
 203         if (dest == maDestructedListeners.end() || *dest != rpListener)
 204             rpListener->BroadcasterDying(*this);
 205     }
 206 }
 207
 208 void SvtBroadcaster::Broadcast( const SfxHint &rHint )
 209 {
 210     Normalize();
 211
 212     ListenersType::const_iterator dest(maDestructedListeners.begin());
 213     ListenersType aListeners(maListeners); // this copy is important to avoid erasing entries while iterating
 214     for (auto& rpListener : aListeners)
 215     {
 216         // skip the destructed ones
 217         while (dest != maDestructedListeners.end() && (*dest < rpListener))
 218             ++dest;
 219
 220         if (dest == maDestructedListeners.end() || *dest != rpListener)
 221             rpListener->Notify(rHint);
 222     }
 223 }
 224
 225 void SvtBroadcaster::ListenersGone() {}
 226
 227 SvtBroadcaster::ListenersType& SvtBroadcaster::GetAllListeners()
 228 {
 229     Normalize();
 230     return maListeners;
 231 }
 232
 233 const SvtBroadcaster::ListenersType& SvtBroadcaster::GetAllListeners() const
 234 {
 235     Normalize();
 236     return maListeners;
 237 }
 238
 239 void SvtBroadcaster::PrepareForDestruction()
 240 {
 241     mbAboutToDie = true;
 242     // the reserve() serves two purpose (1) performance (2) makes sure our iterators do not become invalid
 243     maDestructedListeners.reserve(maListeners.size());
 244 }
 245
 246 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */