1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsDeque.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,391 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +/**
1.10 + * MODULE NOTES:
1.11 + *
1.12 + * The Deque is a very small, very efficient container object
1.13 + * than can hold elements of type void*, offering the following features:
1.14 + * Its interface supports pushing and popping of elements.
1.15 + * It can iterate (via an interator class) its elements.
1.16 + * When full, it can efficiently resize dynamically.
1.17 + *
1.18 + *
1.19 + * NOTE: The only bit of trickery here is that this deque is
1.20 + * built upon a ring-buffer. Like all ring buffers, the first
1.21 + * element may not be at index[0]. The mOrigin member determines
1.22 + * where the first child is. This point is quietly hidden from
1.23 + * customers of this class.
1.24 + *
1.25 + */
1.26 +
1.27 +#ifndef _NSDEQUE
1.28 +#define _NSDEQUE
1.29 +
1.30 +#include "nscore.h"
1.31 +#include "nsDebug.h"
1.32 +#include "mozilla/Attributes.h"
1.33 +#include "mozilla/fallible.h"
1.34 +#include "mozilla/MemoryReporting.h"
1.35 +
1.36 +/**
1.37 + * The nsDequeFunctor class is used when you want to create
1.38 + * callbacks between the deque and your generic code.
1.39 + * Use these objects in a call to ForEach();
1.40 + *
1.41 + */
1.42 +
1.43 +class nsDequeFunctor{
1.44 +public:
1.45 + virtual void* operator()(void* anObject)=0;
1.46 + virtual ~nsDequeFunctor() {}
1.47 +};
1.48 +
1.49 +/******************************************************
1.50 + * Here comes the nsDeque class itself...
1.51 + ******************************************************/
1.52 +
1.53 +/**
1.54 + * The deque (double-ended queue) class is a common container type,
1.55 + * whose behavior mimics a line in your favorite checkout stand.
1.56 + * Classic CS describes the common behavior of a queue as FIFO.
1.57 + * A deque allows insertion and removal at both ends of
1.58 + * the container.
1.59 + *
1.60 + * The deque stores pointers to items.
1.61 + */
1.62 +
1.63 +class nsDequeIterator;
1.64 +
1.65 +class NS_COM_GLUE nsDeque {
1.66 + friend class nsDequeIterator;
1.67 + typedef mozilla::fallible_t fallible_t;
1.68 + public:
1.69 + nsDeque(nsDequeFunctor* aDeallocator = nullptr);
1.70 + ~nsDeque();
1.71 +
1.72 + /**
1.73 + * Returns the number of elements currently stored in
1.74 + * this deque.
1.75 + *
1.76 + * @return number of elements currently in the deque
1.77 + */
1.78 + inline int32_t GetSize() const {return mSize;}
1.79 +
1.80 + /**
1.81 + * Appends new member at the end of the deque.
1.82 + *
1.83 + * @param item to store in deque
1.84 + */
1.85 + void Push(void* aItem) {
1.86 + if (!Push(aItem, fallible_t())) {
1.87 + NS_ABORT_OOM(mSize);
1.88 + }
1.89 + }
1.90 +
1.91 + bool Push(void* aItem, const fallible_t&) NS_WARN_UNUSED_RESULT;
1.92 +
1.93 + /**
1.94 + * Inserts new member at the front of the deque.
1.95 + *
1.96 + * @param item to store in deque
1.97 + */
1.98 + void PushFront(void* aItem) {
1.99 + if (!PushFront(aItem, fallible_t())) {
1.100 + NS_ABORT_OOM(mSize);
1.101 + }
1.102 + }
1.103 +
1.104 + bool PushFront(void* aItem, const fallible_t&) NS_WARN_UNUSED_RESULT;
1.105 +
1.106 + /**
1.107 + * Remove and return the last item in the container.
1.108 + *
1.109 + * @return the item that was the last item in container
1.110 + */
1.111 + void* Pop();
1.112 +
1.113 + /**
1.114 + * Remove and return the first item in the container.
1.115 + *
1.116 + * @return the item that was first item in container
1.117 + */
1.118 + void* PopFront();
1.119 +
1.120 + /**
1.121 + * Retrieve the bottom item without removing it.
1.122 + *
1.123 + * @return the first item in container
1.124 + */
1.125 +
1.126 + void* Peek();
1.127 + /**
1.128 + * Return topmost item without removing it.
1.129 + *
1.130 + * @return the first item in container
1.131 + */
1.132 + void* PeekFront();
1.133 +
1.134 + /**
1.135 + * Retrieve the i'th member from the deque without removing it.
1.136 + *
1.137 + * @param index of desired item
1.138 + * @return i'th element in list
1.139 + */
1.140 + void* ObjectAt(int aIndex) const;
1.141 +
1.142 + /**
1.143 + * Removes and returns the i'th member from the deque.
1.144 + *
1.145 + * @param index of desired item
1.146 + * @return the element which was removed
1.147 + */
1.148 + void* RemoveObjectAt(int aIndex);
1.149 +
1.150 + /**
1.151 + * Remove all items from container without destroying them.
1.152 + */
1.153 + void Empty();
1.154 +
1.155 + /**
1.156 + * Remove and delete all items from container.
1.157 + * Deletes are handled by the deallocator nsDequeFunctor
1.158 + * which is specified at deque construction.
1.159 + */
1.160 + void Erase();
1.161 +
1.162 + /**
1.163 + * Creates a new iterator, pointing to the first
1.164 + * item in the deque.
1.165 + *
1.166 + * @return new dequeIterator
1.167 + */
1.168 + nsDequeIterator Begin() const;
1.169 +
1.170 + /**
1.171 + * Creates a new iterator, pointing to the last
1.172 + * item in the deque.
1.173 + *
1.174 + * @return new dequeIterator
1.175 + */
1.176 + nsDequeIterator End() const;
1.177 +
1.178 + void* Last() const;
1.179 +
1.180 + /**
1.181 + * Call this method when you want to iterate all the
1.182 + * members of the container, passing a functor along
1.183 + * to call your code.
1.184 + *
1.185 + * @param aFunctor object to call for each member
1.186 + */
1.187 + void ForEach(nsDequeFunctor& aFunctor) const;
1.188 +
1.189 + /**
1.190 + * Call this method when you want to iterate all the
1.191 + * members of the container, calling the functor you
1.192 + * passed with each member. This process will interrupt
1.193 + * if your function returns non 0 to this method.
1.194 + *
1.195 + * @param aFunctor object to call for each member
1.196 + * @return first nonzero result of aFunctor or 0.
1.197 + */
1.198 + const void* FirstThat(nsDequeFunctor& aFunctor) const;
1.199 +
1.200 + void SetDeallocator(nsDequeFunctor* aDeallocator);
1.201 +
1.202 + size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
1.203 + size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
1.204 +
1.205 +protected:
1.206 + int32_t mSize;
1.207 + int32_t mCapacity;
1.208 + int32_t mOrigin;
1.209 + nsDequeFunctor* mDeallocator;
1.210 + void* mBuffer[8];
1.211 + void** mData;
1.212 +
1.213 +private:
1.214 +
1.215 + /**
1.216 + * Copy constructor (PRIVATE)
1.217 + *
1.218 + * @param another deque
1.219 + */
1.220 + nsDeque(const nsDeque& other);
1.221 +
1.222 + /**
1.223 + * Deque assignment operator (PRIVATE)
1.224 + *
1.225 + * @param another deque
1.226 + * @return *this
1.227 + */
1.228 + nsDeque& operator=(const nsDeque& anOther);
1.229 +
1.230 + bool GrowCapacity();
1.231 +};
1.232 +
1.233 +/******************************************************
1.234 + * Here comes the nsDequeIterator class...
1.235 + ******************************************************/
1.236 +
1.237 +class NS_COM_GLUE nsDequeIterator {
1.238 +public:
1.239 + /**
1.240 + * DequeIterator is an object that knows how to iterate
1.241 + * (forward and backward) through a Deque. Normally,
1.242 + * you don't need to do this, but there are some special
1.243 + * cases where it is pretty handy.
1.244 + *
1.245 + * One warning: the iterator is not bound to an item,
1.246 + * it is bound to an index, so if you insert or remove
1.247 + * from the beginning while using an iterator
1.248 + * (which is not recommended) then the iterator will
1.249 + * point to a different item. @see GetCurrent()
1.250 + *
1.251 + * Here you go.
1.252 + *
1.253 + * @param aQueue is the deque object to be iterated
1.254 + * @param aIndex is the starting position for your iteration
1.255 + */
1.256 + nsDequeIterator(const nsDeque& aQueue, int aIndex=0);
1.257 +
1.258 + /**
1.259 + * Create a copy of a DequeIterator
1.260 + *
1.261 + * @param aCopy is another iterator to copy from
1.262 + */
1.263 + nsDequeIterator(const nsDequeIterator& aCopy);
1.264 +
1.265 + /**
1.266 + * Moves iterator to first element in the deque
1.267 + * @return *this
1.268 + */
1.269 + nsDequeIterator& First();
1.270 +
1.271 + /**
1.272 + * Standard assignment operator for dequeiterator
1.273 + * @param aCopy is another iterator to copy from
1.274 + * @return *this
1.275 + */
1.276 + nsDequeIterator& operator=(const nsDequeIterator& aCopy);
1.277 +
1.278 + /**
1.279 + * preform ! operation against two iterators to test for equivalence
1.280 + * (or lack thereof)!
1.281 + *
1.282 + * @param aIter is the object to be compared to
1.283 + * @return TRUE if NOT equal.
1.284 + */
1.285 + bool operator!=(nsDequeIterator& aIter);
1.286 +
1.287 + /**
1.288 + * Compare two iterators for increasing order.
1.289 + *
1.290 + * @param aIter is the other iterator to be compared to
1.291 + * @return TRUE if this object points to an element before
1.292 + * the element pointed to by aIter.
1.293 + * FALSE if this and aIter are not iterating over
1.294 + * the same deque.
1.295 + */
1.296 + bool operator<(nsDequeIterator& aIter);
1.297 +
1.298 + /**
1.299 + * Compare two iterators for equivalence.
1.300 + *
1.301 + * @param aIter is the other iterator to be compared to
1.302 + * @return TRUE if EQUAL
1.303 + */
1.304 + bool operator==(nsDequeIterator& aIter);
1.305 +
1.306 + /**
1.307 + * Compare two iterators for non strict decreasing order.
1.308 + *
1.309 + * @param aIter is the other iterator to be compared to
1.310 + * @return TRUE if this object points to the same element, or
1.311 + * an element after the element pointed to by aIter.
1.312 + * FALSE if this and aIter are not iterating over
1.313 + * the same deque.
1.314 + */
1.315 + bool operator>=(nsDequeIterator& aIter);
1.316 +
1.317 + /**
1.318 + * Pre-increment operator
1.319 + * Iterator will advance one index towards the end.
1.320 + *
1.321 + * @return object_at(++index)
1.322 + */
1.323 + void* operator++();
1.324 +
1.325 + /**
1.326 + * Post-increment operator
1.327 + * Iterator will advance one index towards the end.
1.328 + *
1.329 + * @param param is ignored
1.330 + * @return object_at(mIndex++)
1.331 + */
1.332 + void* operator++(int);
1.333 +
1.334 + /**
1.335 + * Pre-decrement operator
1.336 + * Iterator will advance one index towards the beginning.
1.337 + *
1.338 + * @return object_at(--index)
1.339 + */
1.340 + void* operator--();
1.341 +
1.342 + /**
1.343 + * Post-decrement operator
1.344 + * Iterator will advance one index towards the beginning.
1.345 + *
1.346 + * @param param is ignored
1.347 + * @return object_at(index--)
1.348 + */
1.349 + void* operator--(int);
1.350 +
1.351 + /**
1.352 + * Retrieve the the iterator's notion of current node.
1.353 + *
1.354 + * Note that the iterator floats, so you don't need to do:
1.355 + * <code>++iter; aDeque.PopFront();</code>
1.356 + * Unless you actually want your iterator to jump 2 positions
1.357 + * relative to its origin.
1.358 + *
1.359 + * Picture: [1 2i 3 4]
1.360 + * PopFront()
1.361 + * Picture: [2 3i 4]
1.362 + * Note that I still happily points to object at the second index.
1.363 + *
1.364 + * @return object at i'th index
1.365 + */
1.366 + void* GetCurrent();
1.367 +
1.368 + /**
1.369 + * Call this method when you want to iterate all the
1.370 + * members of the container, passing a functor along
1.371 + * to call your code.
1.372 + *
1.373 + * @param aFunctor object to call for each member
1.374 + * @return *this
1.375 + */
1.376 + void ForEach(nsDequeFunctor& aFunctor) const;
1.377 +
1.378 + /**
1.379 + * Call this method when you want to iterate all the
1.380 + * members of the container, calling the functor you
1.381 + * passed with each member. This process will interrupt
1.382 + * if your function returns non 0 to this method.
1.383 + *
1.384 + * @param aFunctor object to call for each member
1.385 + * @return first nonzero result of aFunctor or 0.
1.386 + */
1.387 + const void* FirstThat(nsDequeFunctor& aFunctor) const;
1.388 +
1.389 + protected:
1.390 +
1.391 + int32_t mIndex;
1.392 + const nsDeque& mDeque;
1.393 +};
1.394 +#endif
