SmallPointerArray.h

/* -*- 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/. */

/* A vector of pointers space-optimized for a small number of elements. */

#ifndef mozilla_SmallPointerArray_h
#define mozilla_SmallPointerArray_h

#include "mozilla/Assertions.h"

#include <algorithm>
#include <iterator>
#include <new>
#include <vector>

namespace mozilla {

// Array class for situations where a small number of NON-NULL elements (<= 2)
// is expected, a large number of elements must be accomodated if necessary,
// and the size of the class must be minimal. Typical vector implementations
// will fulfill the first two requirements by simply adding inline storage
// alongside the rest of their member variables. While this strategy works,
// it brings unnecessary storage overhead for vectors with an expected small
// number of elements. This class is intended to deal with that problem.
//
// This class is similar in performance to a vector class. Accessing its
// elements when it has not grown over a size of 2 does not require an extra
// level of indirection and will therefore be faster.
//
// The minimum (inline) size is 2 * sizeof(void*).
//
// Any modification of the array invalidates any outstanding iterators.
template <typename T>
class SmallPointerArray {
 public:
  SmallPointerArray() {
    // List-initialization would be nicer, but it only lets you initialize the
    // first union member.
    mArray[0].mValue = nullptr;
    mArray[1].mVector = nullptr;
  }

  ~SmallPointerArray() {
    if (!first()) {
      delete maybeVector();
    }
  }

  void Clear() {
    if (first()) {
      first() = nullptr;
      new (&mArray[1].mValue) std::vector<T*>*(nullptr);
      return;
    }

    delete maybeVector();
    mArray[1].mVector = nullptr;
  }

  void AppendElement(T* aElement) {
    // Storing nullptr as an element is not permitted, but we do check for it
    // to avoid corruption issues in non-debug builds.

    // In addition to this we assert in debug builds to point out mistakes to
    // users of the class.
    MOZ_ASSERT(aElement != nullptr);
    if (aElement == nullptr) {
      return;
    }

    if (!first()) {
      auto* vec = maybeVector();
      if (!vec) {
        first() = aElement;
        new (&mArray[1].mValue) T*(nullptr);
        return;
      }

      vec->push_back(aElement);
      return;
    }

    if (!second()) {
      second() = aElement;
      return;
    }

    auto* vec = new std::vector<T*>({first(), second(), aElement});
    first() = nullptr;
    new (&mArray[1].mVector) std::vector<T*>*(vec);
  }

  bool RemoveElement(T* aElement) {
    MOZ_ASSERT(aElement != nullptr);
    if (aElement == nullptr) {
      return false;
    }

    if (first() == aElement) {
      // Expected case.
      T* maybeSecond = second();
      first() = maybeSecond;
      if (maybeSecond) {
        second() = nullptr;
      } else {
        new (&mArray[1].mVector) std::vector<T*>*(nullptr);
      }

      return true;
    }

    if (first()) {
      if (second() == aElement) {
        second() = nullptr;
        return true;
      }
      return false;
    }

    if (auto* vec = maybeVector()) {
      for (auto iter = vec->begin(); iter != vec->end(); iter++) {
        if (*iter == aElement) {
          vec->erase(iter);
          return true;
        }
      }
    }
    return false;
  }

  bool Contains(T* aElement) const {
    MOZ_ASSERT(aElement != nullptr);
    if (aElement == nullptr) {
      return false;
    }

    if (T* v = first()) {
      return v == aElement || second() == aElement;
    }

    if (auto* vec = maybeVector()) {
      return std::find(vec->begin(), vec->end(), aElement) != vec->end();
    }

    return false;
  }

  size_t Length() const {
    if (first()) {
      return second() ? 2 : 1;
    }

    if (auto* vec = maybeVector()) {
      return vec->size();
    }

    return 0;
  }

  T* ElementAt(size_t aIndex) const {
    MOZ_ASSERT(aIndex < Length());
    if (first()) {
      return mArray[aIndex].mValue;
    }

    auto* vec = maybeVector();
    MOZ_ASSERT(vec, "must have backing vector if accessing an element");
    return (*vec)[aIndex];
  }

  T* operator[](size_t aIndex) const { return ElementAt(aIndex); }

  using iterator = T**;
  using const_iterator = const T**;

  // Methods for range-based for loops. Manipulation invalidates these.
  iterator begin() { return beginInternal(); }
  const_iterator begin() const { return beginInternal(); }
  const_iterator cbegin() const { return begin(); }
  iterator end() { return beginInternal() + Length(); }
  const_iterator end() const { return beginInternal() + Length(); }
  const_iterator cend() const { return end(); }

 private:
  T** beginInternal() const {
    if (first()) {
      static_assert(sizeof(T*) == sizeof(Element),
                    "pointer ops on &first() must produce adjacent "
                    "Element::mValue arms");
      return &first();
    }

    auto* vec = maybeVector();
    if (!vec) {
      return &first();
    }

    if (vec->empty()) {
      return nullptr;
    }

    return &(*vec)[0];
  }

  // Accessors for |mArray| element union arms.

  T*& first() const { return const_cast<T*&>(mArray[0].mValue); }

  T*& second() const {
    MOZ_ASSERT(first(), "first() must be non-null to have a T* second pointer");
    return const_cast<T*&>(mArray[1].mValue);
  }

  std::vector<T*>* maybeVector() const {
    MOZ_ASSERT(!first(),
               "function must only be called when this is either empty or has "
               "std::vector-backed elements");
    return mArray[1].mVector;
  }

  // In C++ active-union-arm terms:
  //
  //   - mArray[0].mValue is always active: a possibly null T*;
  //   - if mArray[0].mValue is null, mArray[1].mVector is active: a possibly
  //     null std::vector<T*>*; if mArray[0].mValue isn't null, mArray[1].mValue
  //     is active: a possibly null T*.
  //
  // SmallPointerArray begins empty, with mArray[1].mVector active and null.
  // Code that makes mArray[0].mValue non-null, i.e. assignments to first(),
  // must placement-new mArray[1].mValue with the proper value; code that goes
  // the opposite direction, making mArray[0].mValue null, must placement-new
  // mArray[1].mVector with the proper value.
  //
  // When !mArray[0].mValue && !mArray[1].mVector, the array is empty.
  //
  // When mArray[0].mValue && !mArray[1].mValue, the array has size 1 and
  // contains mArray[0].mValue.
  //
  // When mArray[0] && mArray[1], the array has size 2 and contains
  // mArray[0].mValue and mArray[1].mValue.
  //
  // When !mArray[0].mValue && mArray[1].mVector, mArray[1].mVector contains
  // the contents of an array of arbitrary size (even less than two if it ever
  // contained three elements and elements were removed).
  union Element {
    T* mValue;
    std::vector<T*>* mVector;
  } mArray[2];
};

}  // namespace mozilla

#endif  // mozilla_SmallPointerArray_h