Bug 1331718 - Part 1: Add small pointer array. r=froydnj draft
authorBas Schouten <bschouten@mozilla.com>
Thu, 04 May 2017 02:07:40 +0200
changeset 572340 c2fc0d2c992eb2221e9d7234dcb0d79522eb9216
parent 570751 5f4342d186d22b33cafdca5fb387a6bda661a311
child 572341 f98cefdd402ad24102ab11b82b5de3b80562742a
push id57037
push userbschouten@mozilla.com
push dateThu, 04 May 2017 00:18:36 +0000
reviewersfroydnj
bugs1331718
milestone55.0a1
Bug 1331718 - Part 1: Add small pointer array. r=froydnj MozReview-Commit-ID: 3NBFPGeW4fD
mfbt/SmallPointerArray.h
mfbt/moz.build
new file mode 100644
--- /dev/null
+++ b/mfbt/SmallPointerArray.h
@@ -0,0 +1,196 @@
+/* -*- 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/. */
+
+#ifndef mozilla_SmallPointerArray_h
+#define mozilla_SmallPointerArray_h
+
+#include "mozilla/Assertions.h"
+#include <iterator>
+#include <vector>
+
+namespace mozilla {
+
+// Array class specialized to hold a small number (1 or 2 elements) of pointers
+// in a minimal amount of inline space. Can be grown larger if required.
+//
+// This class is similar is 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 therefor be faster.
+//
+// The minimum (inline) size is 2 * sizeof(void*).
+//
+// Any manipulation of the array invalidates the iterators.
+template<typename T>
+class SmallPointerArray
+{
+public:
+  SmallPointerArray()
+  {
+    mInlineElements[0] = mInlineElements[1] = nullptr;
+  }
+  ~SmallPointerArray()
+  {
+    if (!mInlineElements[0] && mArray) {
+      delete mArray;
+    }
+  }
+
+  void Clear() {
+    if (!mInlineElements[0] && mArray) {
+      delete mArray;
+      mArray = nullptr;
+      return;
+    }
+    mInlineElements[0] = mInlineElements[1] = nullptr;
+  }
+
+  void AppendElement(T* aElement) {
+    MOZ_ASSERT(aElement != nullptr);
+    if (!mInlineElements[0]) {
+      if (!mArray) {
+        mInlineElements[0] = aElement;
+        // Harmless if aElement == nullptr;
+        return;
+      }
+
+      if (!aElement) {
+        return;
+      }
+
+      mArray->push_back(aElement);
+      return;
+    }
+
+    if (!aElement) {
+      return;
+    }
+
+    if (!mInlineElements[1]) {
+      mInlineElements[1] = aElement;
+      return;
+    }
+
+    mArray = new std::vector<T*>({ mInlineElements[0], mInlineElements[1], aElement });
+    mInlineElements[0] = nullptr;
+  }
+
+  void RemoveElement(T* aElement) {
+    MOZ_ASSERT(aElement != nullptr);
+    if (aElement == nullptr) {
+      return;
+    }
+
+    if (mInlineElements[0] == aElement) {
+      // Expectected case.
+      mInlineElements[0] = mInlineElements[1];
+      mInlineElements[1] = nullptr;
+      return;
+    }
+
+    if (mInlineElements[0]) {
+      if (mInlineElements[1] == aElement) {
+        mInlineElements[1] = nullptr;
+      }
+      return;
+    }
+
+    if (mArray) {
+      for (auto iter = mArray->begin(); iter != mArray->end(); iter++) {
+        if (*iter == aElement) {
+          mArray->erase(iter);
+          return;
+        }
+      }
+    }
+  }
+
+  size_t Length() const
+  {
+    if (mInlineElements[0]) {
+      if (!mInlineElements[1]) {
+        return 1;
+      }
+      return 2;
+    }
+
+    if (mArray) {
+      return mArray->size();
+    }
+
+    return 0;
+  }
+
+  T* ElementAt(size_t aIndex) const {
+    MOZ_ASSERT(aIndex < Length());
+    if (mInlineElements[0]) {
+      return mInlineElements[aIndex];
+    }
+
+    return (*mArray)[aIndex];
+  }
+
+  T* operator[](size_t aIndex) const
+  {
+    return ElementAt(aIndex);
+  }
+
+  typedef T**                        iterator;
+  typedef const T**                  const_iterator;
+
+  // 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 (mInlineElements[0] || !mArray) {
+      return &const_cast<T*>(mInlineElements[0]);
+    }
+
+    if (!mArray->size()) {
+      return nullptr;
+    }
+
+    return &(*mArray)[0];
+  }
+
+  // mArray and mInlineElements[1] share the same area in memory.
+  //
+  // When !mInlineElemnts[0] && !mInlineElements[1] the array is empty.
+  //
+  // When mInlineElements[0] && !mInlineElements[1], mInlineElements[0]
+  // contains the first element. The array is of size 1.
+  //
+  // When mInlineElements[0] && mInlineElements[1], mInlineElements[0]
+  // contains the first element and mInlineElements[1] the second. The
+  // array is of size 2.
+  //
+  // When !mInlineElements[0] && mArray, mArray contains the full contents
+  // of the array and is of arbitrary size.
+  union {
+    T* mInlineElements[2];
+    struct {
+      void* mPadding;
+      std::vector<T*>* mArray;
+    };
+  };
+};
+
+} // namespace mozilla
+
+#endif // mozilla_SmallPointerArray_h
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -78,16 +78,17 @@ EXPORTS.mozilla = [
     'ReverseIterator.h',
     'RollingMean.h',
     'Saturate.h',
     'Scoped.h',
     'ScopeExit.h',
     'SegmentedVector.h',
     'SHA1.h',
     'SizePrintfMacros.h',
+    'SmallPointerArray.h',
     'Span.h',
     'SplayTree.h',
     'Sprintf.h',
     'StaticAnalysisFunctions.h',
     'TaggedAnonymousMemory.h',
     'TemplateLib.h',
     'ThreadLocal.h',
     'ToString.h',