summaryrefslogtreecommitdiffstats
path: root/xpcom/glue/nsDeque.h
diff options
context:
space:
mode:
Diffstat (limited to 'xpcom/glue/nsDeque.h')
-rw-r--r--xpcom/glue/nsDeque.h195
1 files changed, 195 insertions, 0 deletions
diff --git a/xpcom/glue/nsDeque.h b/xpcom/glue/nsDeque.h
new file mode 100644
index 000000000..ace7607d3
--- /dev/null
+++ b/xpcom/glue/nsDeque.h
@@ -0,0 +1,195 @@
+/* -*- 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/. */
+
+/**
+ * MODULE NOTES:
+ *
+ * The Deque is a very small, very efficient container object
+ * than can hold elements of type void*, offering the following features:
+ * Its interface supports pushing and popping of elements.
+ * It can iterate (via an interator class) its elements.
+ * When full, it can efficiently resize dynamically.
+ *
+ *
+ * NOTE: The only bit of trickery here is that this deque is
+ * built upon a ring-buffer. Like all ring buffers, the first
+ * element may not be at index[0]. The mOrigin member determines
+ * where the first child is. This point is quietly hidden from
+ * customers of this class.
+ *
+ */
+
+#ifndef _NSDEQUE
+#define _NSDEQUE
+
+#include "nscore.h"
+#include "nsDebug.h"
+#include "mozilla/Attributes.h"
+#include "mozilla/fallible.h"
+#include "mozilla/MemoryReporting.h"
+
+/**
+ * The nsDequeFunctor class is used when you want to create
+ * callbacks between the deque and your generic code.
+ * Use these objects in a call to ForEach();
+ *
+ */
+
+class nsDequeFunctor
+{
+public:
+ virtual void* operator()(void* aObject) = 0;
+ virtual ~nsDequeFunctor() {}
+};
+
+/******************************************************
+ * Here comes the nsDeque class itself...
+ ******************************************************/
+
+/**
+ * The deque (double-ended queue) class is a common container type,
+ * whose behavior mimics a line in your favorite checkout stand.
+ * Classic CS describes the common behavior of a queue as FIFO.
+ * A deque allows insertion and removal at both ends of
+ * the container.
+ *
+ * The deque stores pointers to items.
+ */
+
+class nsDequeIterator;
+
+class nsDeque
+{
+ typedef mozilla::fallible_t fallible_t;
+public:
+ explicit nsDeque(nsDequeFunctor* aDeallocator = nullptr);
+ ~nsDeque();
+
+ /**
+ * Returns the number of elements currently stored in
+ * this deque.
+ *
+ * @return number of elements currently in the deque
+ */
+ inline size_t GetSize() const { return mSize; }
+
+ /**
+ * Appends new member at the end of the deque.
+ *
+ * @param item to store in deque
+ */
+ void Push(void* aItem)
+ {
+ if (!Push(aItem, mozilla::fallible)) {
+ NS_ABORT_OOM(mSize * sizeof(void*));
+ }
+ }
+
+ MOZ_MUST_USE bool Push(void* aItem, const fallible_t&);
+
+ /**
+ * Inserts new member at the front of the deque.
+ *
+ * @param item to store in deque
+ */
+ void PushFront(void* aItem)
+ {
+ if (!PushFront(aItem, mozilla::fallible)) {
+ NS_ABORT_OOM(mSize * sizeof(void*));
+ }
+ }
+
+ MOZ_MUST_USE bool PushFront(void* aItem, const fallible_t&);
+
+ /**
+ * Remove and return the last item in the container.
+ *
+ * @return the item that was the last item in container
+ */
+ void* Pop();
+
+ /**
+ * Remove and return the first item in the container.
+ *
+ * @return the item that was first item in container
+ */
+ void* PopFront();
+
+ /**
+ * Retrieve the bottom item without removing it.
+ *
+ * @return the first item in container
+ */
+
+ void* Peek() const;
+ /**
+ * Return topmost item without removing it.
+ *
+ * @return the first item in container
+ */
+ void* PeekFront() const;
+
+ /**
+ * Retrieve a member from the deque without removing it.
+ *
+ * @param index of desired item
+ * @return element in list
+ */
+ void* ObjectAt(size_t aIndex) const;
+
+ /**
+ * Remove and delete all items from container.
+ * Deletes are handled by the deallocator nsDequeFunctor
+ * which is specified at deque construction.
+ */
+ void Erase();
+
+ /**
+ * 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
+ */
+ void ForEach(nsDequeFunctor& aFunctor) const;
+
+ size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
+ size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
+
+protected:
+ size_t mSize;
+ size_t mCapacity;
+ size_t mOrigin;
+ nsDequeFunctor* mDeallocator;
+ void* mBuffer[8];
+ void** mData;
+
+private:
+
+ /**
+ * Copy constructor (PRIVATE)
+ *
+ * @param aOther another deque
+ */
+ nsDeque(const nsDeque& aOther);
+
+ /**
+ * Deque assignment operator (PRIVATE)
+ *
+ * @param aOther another deque
+ * @return *this
+ */
+ nsDeque& operator=(const nsDeque& aOther);
+
+ bool GrowCapacity();
+ void SetDeallocator(nsDequeFunctor* aDeallocator);
+
+ /**
+ * Remove all items from container without destroying them.
+ */
+ void Empty();
+};
+#endif