text: // Copyright 2014 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #include "config.h"
  #include "platform/heap/CallbackStack.h"
  
  #include "platform/heap/Heap.h"
  
  namespace blink {
  
  void CallbackStack::Block::clear()
  {
      m_current = &m_buffer[0];
      m_next = 0;
      clearUnused();
  }
  
  void CallbackStack::Block::invokeEphemeronCallbacks(Visitor* visitor)
  {
      // This loop can tolerate entries being added by the callbacks after
      // iteration starts.
      for (unsigned i = 0; m_buffer + i < m_current; i++) {
          Item& item = m_buffer[i];
  
          // We don't need to check for orphaned pages when popping an ephemeron
          // callback since the callback is only pushed after the object containing
          // it has been traced. There are basically three cases to consider:
          // 1. Member<EphemeronCollection>
          // 2. EphemeronCollection is part of a containing object
          // 3. EphemeronCollection is a value object in a collection
          //
          // Ad. 1. In this case we push the start of the ephemeron on the
          // marking stack and do the orphaned page check when popping it off
          // the marking stack.
          // Ad. 2. The containing object cannot be on an orphaned page since
          // in that case we wouldn't have traced its parts. This also means
          // the ephemeron collection is not on the orphaned page.
          // Ad. 3. Is the same as 2. The collection containing the ephemeron
          // collection as a value object cannot be on an orphaned page since
          // it would not have traced its values in that case.
          item.call(visitor);
      }
  }
  
  #if ENABLE(ASSERT)
  bool CallbackStack::Block::hasCallbackForObject(const void* object)
  {
      for (unsigned i = 0; m_buffer + i < m_current; i++) {
          Item* item = &m_buffer[i];
          if (item->object() == object)
              return true;
      }
      return false;
  }
  #endif
  
  void CallbackStack::Block::clearUnused()
  {
  #if ENABLE(ASSERT)
      for (size_t i = 0; i < blockSize; i++)
          m_buffer[i] = Item(0, 0);
  #endif
  }
  
  CallbackStack::CallbackStack() : m_first(new Block(0)), m_last(m_first)
  {
  }
  
  CallbackStack::~CallbackStack()
  {
      clear();
      delete m_first;
      m_first = 0;
      m_last = 0;
  }
  
  void CallbackStack::clear()
  {
      Block* next;
      for (Block* current = m_first->next(); current; current = next) {
          next = current->next();
          delete current;
      }
      m_first->clear();
      m_last = m_first;
  }
  
  bool CallbackStack::isEmpty() const
  {
      return hasJustOneBlock() && m_first->isEmptyBlock();
  }
  
  CallbackStack::Item* CallbackStack::allocateEntrySlow()
  {
      ASSERT(!m_first->allocateEntry());
      m_first = new Block(m_first);
      return m_first->allocateEntry();
  }
  
  CallbackStack::Item* CallbackStack::popSlow()
  {
      ASSERT(m_first->isEmptyBlock());
  
      for (;;) {
          if (hasJustOneBlock()) {
  #if ENABLE(ASSERT)
              m_first->clear();
  #endif
              return 0;
          }
          Block* next = m_first->next();
          delete m_first;
          m_first = next;
          if (Item* item = m_first->pop())
              return item;
      }
  }
  
  void CallbackStack::invokeEphemeronCallbacks(Visitor* visitor)
  {
      // The first block is the only one where new ephemerons are added, so we
      // call the callbacks on that last, to catch any new ephemerons discovered
      // in the callbacks.
      // However, if enough ephemerons were added, we may have a new block that
      // has been prepended to the chain. This will be very rare, but we can
      // handle the situation by starting again and calling all the callbacks
      // on the prepended blocks.
      Block* from = 0;
      Block* upto = 0;
      while (from != m_first) {
          upto = from;
          from = m_first;
          invokeOldestCallbacks(from, upto, visitor);
      }
  }
  
  void CallbackStack::invokeOldestCallbacks(Block* from, Block* upto, Visitor* visitor)
  {
      if (from == upto)
          return;
      ASSERT(from);
      // Recurse first (blockSize at a time) so we get to the newly added entries last.
      invokeOldestCallbacks(from->next(), upto, visitor);
      from->invokeEphemeronCallbacks(visitor);
  }
  
  bool CallbackStack::hasJustOneBlock() const
  {
      return !m_first->next();
  }
  
  void CallbackStack::swap(CallbackStack* other)
  {
      Block* tmp = m_first;
      m_first = other->m_first;
      other->m_first = tmp;
      tmp = m_last;
      m_last = other->m_last;
      other->m_last = tmp;
  }
  
  #if ENABLE(ASSERT)
  bool CallbackStack::hasCallbackForObject(const void* object)
  {
      for (Block* current = m_first; current; current = current->next()) {
          if (current->hasCallbackForObject(object))
              return true;
      }
      return false;
  }
  #endif
  
  }
  