xpcom/ds/nsDeque.cpp
author Petru Lingurar <petru.lingurar@softvision.ro>
Fri, 13 Jul 2018 17:16:37 +0300
changeset 426733 c2b1f1b52866d2c58f5e23fe2df97c9127ebcacf
parent 367722 6a629adbb62a299d7208373d1c6f375149d2afdb
child 448588 b226d4c40893fdd080f65c9d8d8a52990a5386be
permissions -rw-r--r--
Bug 1385464 - Start using support library v. 26; r=nalexander This patch also: Resolves missing resources and api changes - LeanplumActionBarActivity was removed because Support Library 26 deprecated ActionBarActivity. Class was already not in use. - CustomTabsService added two new methods which we need to override. Tested to make sure that previous functionality was maintained but with the addition of the two new methods maybe that feature could be improved. - For checking layout direction we'll use our own new method from ViewUtil which mimics what the now restricted method from the support library would do. - Upgraded to use AppCompatResources#getDrawable(..) in place of the now restricted AppCompatDrawableManager.get().getDrawable(..). Resolves obscure leaks and crashes after the upgrade - LoaderManager.destroyLoader(..) was added before the existing call to LoaderManager.restartLoader(..) to prevent potential Cursor leaks - Disable website suggestions depending on the address bar inputs when running in automation to avoid Robocop tests failing (they were entering serially maybe 100 characters in <5 ms which created around that many new Threads, operation that could cause the Executor to throw a RejectedExecutionException) At the moment this functionality is not covered by tests anyway and it was the only fix I could find that would not involve changing the whole implemenation for address bar suggestions, implementation which in the real world works ok. MozReview-Commit-ID: 2fX1SBHiSh0

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "nsDeque.h"
#include "nsISupportsImpl.h"
#include <string.h>
#ifdef DEBUG_rickg
#include <stdio.h>
#endif

#include "mozilla/CheckedInt.h"

#define modulus(x,y) ((x)%(y))

/**
 * Standard constructor
 * @param deallocator, called by Erase and ~nsDeque
 */
nsDeque::nsDeque(nsDequeFunctor* aDeallocator)
{
  MOZ_COUNT_CTOR(nsDeque);
  mDeallocator = aDeallocator;
  mOrigin = mSize = 0;
  mData = mBuffer; // don't allocate space until you must
  mCapacity = sizeof(mBuffer) / sizeof(mBuffer[0]);
  memset(mData, 0, mCapacity * sizeof(mBuffer[0]));
}

/**
 * Destructor
 */
nsDeque::~nsDeque()
{
  MOZ_COUNT_DTOR(nsDeque);

#ifdef DEBUG_rickg
  char buffer[30];
  printf("Capacity: %i\n", mCapacity);

  static int mCaps[15] = {0};
  switch (mCapacity) {
    case 4:     mCaps[0]++; break;
    case 8:     mCaps[1]++; break;
    case 16:    mCaps[2]++; break;
    case 32:    mCaps[3]++; break;
    case 64:    mCaps[4]++; break;
    case 128:   mCaps[5]++; break;
    case 256:   mCaps[6]++; break;
    case 512:   mCaps[7]++; break;
    case 1024:  mCaps[8]++; break;
    case 2048:  mCaps[9]++; break;
    case 4096:  mCaps[10]++; break;
    default:
      break;
  }
#endif

  Erase();
  if (mData && mData != mBuffer) {
    free(mData);
  }
  mData = 0;
  SetDeallocator(0);
}

size_t
nsDeque::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
{
  size_t size = 0;
  if (mData != mBuffer) {
    size += aMallocSizeOf(mData);
  }

  if (mDeallocator) {
    size += aMallocSizeOf(mDeallocator);
  }

  return size;
}

size_t
nsDeque::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
{
  return aMallocSizeOf(this) + SizeOfExcludingThis(aMallocSizeOf);
}

/**
 * Set the functor to be called by Erase()
 * The deque owns the functor.
 *
 * @param   aDeallocator functor object for use by Erase()
 */
void
nsDeque::SetDeallocator(nsDequeFunctor* aDeallocator)
{
  delete mDeallocator;
  mDeallocator = aDeallocator;
}

/**
 * Remove all items from container without destroying them.
 */
void
nsDeque::Empty()
{
  if (mSize && mData) {
    memset(mData, 0, mCapacity * sizeof(*mData));
  }
  mSize = 0;
  mOrigin = 0;
}

/**
 * Remove and delete all items from container
 */
void
nsDeque::Erase()
{
  if (mDeallocator && mSize) {
    ForEach(*mDeallocator);
  }
  Empty();
}

/**
 * This method quadruples the size of the deque
 * Elements in the deque are resequenced so that elements
 * in the deque are stored sequentially
 *
 * @return  whether growing succeeded
 */
bool
nsDeque::GrowCapacity()
{
  mozilla::CheckedInt<size_t> newCapacity = mCapacity;
  newCapacity *= 4;

  NS_ASSERTION(newCapacity.isValid(), "Overflow");
  if (!newCapacity.isValid()) {
    return false;
  }

  // Sanity check the new byte size.
  mozilla::CheckedInt<size_t> newByteSize = newCapacity;
  newByteSize *= sizeof(void*);

  NS_ASSERTION(newByteSize.isValid(), "Overflow");
  if (!newByteSize.isValid()) {
    return false;
  }

  void** temp = (void**)malloc(newByteSize.value());
  if (!temp) {
    return false;
  }

  //Here's the interesting part: You can't just move the elements
  //directly (in situ) from the old buffer to the new one.
  //Since capacity has changed, the old origin doesn't make
  //sense anymore. It's better to resequence the elements now.

  memcpy(temp, mData + mOrigin, sizeof(void*) * (mCapacity - mOrigin));
  memcpy(temp + (mCapacity - mOrigin), mData, sizeof(void*) * mOrigin);

  if (mData != mBuffer) {
    free(mData);
  }

  mCapacity = newCapacity.value();
  mOrigin = 0; //now realign the origin...
  mData = temp;

  return true;
}

/**
 * This method adds an item to the end of the deque.
 * This operation has the potential to cause the
 * underlying buffer to resize.
 *
 * @param   aItem: new item to be added to deque
 */
bool
nsDeque::Push(void* aItem, const fallible_t&)
{
  if (mSize == mCapacity && !GrowCapacity()) {
    return false;
  }
  mData[modulus(mOrigin + mSize, mCapacity)] = aItem;
  mSize++;
  return true;
}

/**
 * This method adds an item to the front of the deque.
 * This operation has the potential to cause the
 * underlying buffer to resize.
 *
 * --Commments for GrowCapacity() case
 * We've grown and shifted which means that the old
 * final element in the deque is now the first element
 * in the deque.  This is temporary.
 * We haven't inserted the new element at the front.
 *
 * To continue with the idea of having the front at zero
 * after a grow, we move the old final item (which through
 * the voodoo of mOrigin-- is now the first) to its final
 * position which is conveniently the old length.
 *
 * Note that this case only happens when the deque is full.
 * [And that pieces of this magic only work if the deque is full.]
 * picture:
 *   [ABCDEFGH] @[mOrigin:3]:D.
 * Task: PushFront("Z")
 * shift mOrigin so, @[mOrigin:2]:C
 * stretch and rearrange: (mOrigin:0)
 *   [CDEFGHAB ________ ________ ________]
 * copy: (The second C is currently out of bounds)
 *   [CDEFGHAB C_______ ________ ________]
 * later we will insert Z:
 *   [ZDEFGHAB C_______ ________ ________]
 * and increment size: 9. (C is no longer out of bounds)
 * --
 * @param   aItem: new item to be added to deque
 */
bool
nsDeque::PushFront(void* aItem, const fallible_t&)
{

  if (mOrigin == 0) {
    mOrigin = mCapacity - 1;
  } else {
    mOrigin--;
  }

  if (mSize == mCapacity) {
    if (!GrowCapacity()) {
      return false;
    }
    /* Comments explaining this are above*/
    mData[mSize] = mData[mOrigin];
  }
  mData[mOrigin] = aItem;
  mSize++;
  return true;
}

/**
 * Remove and return the last item in the container.
 *
 * @return  ptr to last item in container
 */
void*
nsDeque::Pop()
{
  void* result = 0;
  if (mSize > 0) {
    --mSize;
    size_t offset = modulus(mSize + mOrigin, mCapacity);
    result = mData[offset];
    mData[offset] = 0;
    if (!mSize) {
      mOrigin = 0;
    }
  }
  return result;
}

/**
 * This method gets called you want to remove and return
 * the first member in the container.
 *
 * @return  last item in container
 */
void*
nsDeque::PopFront()
{
  void* result = 0;
  if (mSize > 0) {
    NS_ASSERTION(mOrigin < mCapacity, "Error: Bad origin");
    result = mData[mOrigin];
    mData[mOrigin++] = 0;   //zero it out for debugging purposes.
    mSize--;
    // Cycle around if we pop off the end
    // and reset origin if when we pop the last element
    if (mCapacity == mOrigin || !mSize) {
      mOrigin = 0;
    }
  }
  return result;
}

/**
 * This method gets called you want to peek at the bottom
 * member without removing it.
 *
 * @return  last item in container
 */
void*
nsDeque::Peek() const
{
  void* result = 0;
  if (mSize > 0) {
    result = mData[modulus(mSize - 1 + mOrigin, mCapacity)];
  }
  return result;
}

/**
 * This method gets called you want to peek at the topmost
 * member without removing it.
 *
 * @return  last item in container
 */
void*
nsDeque::PeekFront() const
{
  void* result = 0;
  if (mSize > 0) {
    result = mData[mOrigin];
  }
  return result;
}

/**
 * Call this to retrieve the ith element from this container.
 * Keep in mind that accessing the underlying elements is
 * done in a relative fashion. Object 0 is not necessarily
 * the first element (the first element is at mOrigin).
 *
 * @param   aIndex : 0 relative offset of item you want
 * @return  void* or null
 */
void*
nsDeque::ObjectAt(size_t aIndex) const
{
  void* result = 0;
  if (aIndex < mSize) {
    result = mData[modulus(mOrigin + aIndex, mCapacity)];
  }
  return result;
}

/**
 * Call this method when you want to iterate all the
 * members of the container, passing a functor along
 * to call your code.
 *
 * @param   aFunctor object to call for each member
 * @return  *this
 */
void
nsDeque::ForEach(nsDequeFunctor& aFunctor) const
{
  for (size_t i = 0; i < mSize; ++i) {
    aFunctor(ObjectAt(i));
  }
}