src/third_party/mozjs/js/src/jit/InlineList.h - cobalt - Git at Google

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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 jit_InlineList_h
 #define jit_InlineList_h

 #include "mozilla/DebugOnly.h"

 #include "jsutil.h"

 namespace js {

 template <typename T> class InlineForwardList;
 template <typename T> class InlineForwardListIterator;

 template <typename T>
 class InlineForwardListNode
 {
   public:
     InlineForwardListNode() : next(NULL)
     { }
     InlineForwardListNode(InlineForwardListNode<T> *n) : next(n)
     { }

   protected:
     friend class InlineForwardList<T>;
     friend class InlineForwardListIterator<T>;

     InlineForwardListNode<T> *next;
 };

 template <typename T>
 class InlineForwardList : protected InlineForwardListNode<T>
 {
     friend class InlineForwardListIterator<T>;

     typedef InlineForwardListNode<T> Node;

     Node *tail_;
     mozilla::DebugOnly<int> modifyCount_;

     InlineForwardList<T> *thisFromConstructor() {
         return this;
     }

   public:
     InlineForwardList()
       : tail_(thisFromConstructor())
     {
         modifyCount_ = 0;
     }

   public:
     typedef InlineForwardListIterator<T> iterator;

   public:
     iterator begin() const {
         return iterator(this);
     }
     iterator end() const {
         return iterator(NULL);
     }
     iterator removeAt(iterator &where) {
         iterator iter(where);
         iter++;
         iter.prev = where.prev;
         iter.modifyCount_++;

         // Once the element 'where' points at has been removed, it is no longer
         // safe to do any operations that would touch 'iter', as the element
         // may be added to another list, etc. This NULL ensures that any
         // improper uses of this function will fail quickly and loudly.
         removeAfter(where.prev, where.iter);
         where.prev = where.iter = NULL;

         return iter;
     }
     void pushFront(Node *t) {
         insertAfter(this, t);
     }
     void pushBack(Node *t) {
         modifyCount_++;
         tail_->next = t;
         t->next = NULL;
         tail_ = t;
     }
     T *popFront() {
         JS_ASSERT(!empty());
         T* result = static_cast<T *>(this->next);
         removeAfter(this, result);
         return result;
     }
     void insertAfter(Node *at, Node *item) {
         modifyCount_++;
         if (at == tail_)
             tail_ = item;
         item->next = at->next;
         at->next = item;
     }
     void removeAfter(Node *at, Node *item) {
         modifyCount_++;
         if (item == tail_)
             tail_ = at;
         JS_ASSERT(at->next == item);
         at->next = item->next;
     }
     void splitAfter(Node *at, InlineForwardList<T> *to) {
         JS_ASSERT(to->empty());
         if (!at)
             at = this;
         if (at == tail_)
             return;
         modifyCount_++;
         to->next = at->next;
         to->tail_ = tail_;
         tail_ = at;
         at->next = NULL;
     }
     bool empty() const {
         return tail_ == this;
     }
     void clear() {
         this->next = NULL;
         tail_ = this;
         modifyCount_ = 0;
     }
 };

 template <typename T>
 class InlineForwardListIterator
 {
 private:
     friend class InlineForwardList<T>;

     typedef InlineForwardListNode<T> Node;

     InlineForwardListIterator<T>(const InlineForwardList<T> *owner)
       : prev(const_cast<Node *>(static_cast<const Node *>(owner))),
         iter(owner ? owner->next : NULL)
 #ifdef DEBUG
       , owner_(owner),
         modifyCount_(owner ? owner->modifyCount_.value : 0)
 #endif
     { }

 public:
     InlineForwardListIterator<T> & operator ++() {
         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
         prev = iter;
         iter = iter->next;
         return *this;
     }
     InlineForwardListIterator<T> operator ++(int) {
         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
         InlineForwardListIterator<T> old(*this);
         prev = iter;
         iter = iter->next;
         return old;
     }
     T * operator *() const {
         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
         return static_cast<T *>(iter);
     }
     T * operator ->() const {
         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
         return static_cast<T *>(iter);
     }
     bool operator !=(const InlineForwardListIterator<T> &where) const {
         return iter != where.iter;
     }
     bool operator ==(const InlineForwardListIterator<T> &where) const {
         return iter == where.iter;
     }

 private:
     Node *prev;
     Node *iter;

 #ifdef DEBUG
     const InlineForwardList<T> *owner_;
 #endif
     mozilla::DebugOnly<int> modifyCount_;
 };

 template <typename T> class InlineList;
 template <typename T> class InlineListIterator;
 template <typename T> class InlineListReverseIterator;

 template <typename T>
 class InlineListNode : public InlineForwardListNode<T>
 {
   public:
     InlineListNode() : InlineForwardListNode<T>(NULL), prev(NULL)
     { }
     InlineListNode(InlineListNode<T> *n, InlineListNode<T> *p)
       : InlineForwardListNode<T>(n),
         prev(p)
     { }

   protected:
     friend class InlineList<T>;
     friend class InlineListIterator<T>;
     friend class InlineListReverseIterator<T>;

     InlineListNode<T> *prev;
 };

 template <typename T>
 class InlineList : protected InlineListNode<T>
 {
     typedef InlineListNode<T> Node;

     // Silence MSVC warning C4355
     InlineList<T> *thisFromConstructor() {
         return this;
     }

   public:
     InlineList() : InlineListNode<T>(thisFromConstructor(), thisFromConstructor())
     { }

   public:
     typedef InlineListIterator<T> iterator;
     typedef InlineListReverseIterator<T> reverse_iterator;

   public:
     iterator begin() const {
         return iterator(static_cast<Node *>(this->next));
     }
     iterator begin(Node *t) const {
         return iterator(t);
     }
     iterator end() const {
         return iterator(this);
     }
     reverse_iterator rbegin() const {
         return reverse_iterator(this->prev);
     }
     reverse_iterator rbegin(Node *t) const {
         return reverse_iterator(t);
     }
     reverse_iterator rend() const {
         return reverse_iterator(this);
     }
     template <typename itertype>
     itertype removeAt(itertype &where) {
         itertype iter(where);
         iter++;

         // Once the element 'where' points at has been removed, it is no longer
         // safe to do any operations that would touch 'iter', as the element
         // may be added to another list, etc. This NULL ensures that any
         // improper uses of this function will fail quickly and loudly.
         remove(where.iter);
         where.iter = NULL;

         return iter;
     }
     void pushFront(Node *t) {
         insertAfter(this, t);
     }
     void pushBack(Node *t) {
         insertBefore(this, t);
     }
     T *popFront() {
         JS_ASSERT(!empty());
         T *t = static_cast<T *>(this->next);
         remove(t);
         return t;
     }
     T *popBack() {
         JS_ASSERT(!empty());
         T *t = static_cast<T *>(this->prev);
         remove(t);
         return t;
     }
     T *peekBack() const {
         iterator iter = end();
         iter--;
         return *iter;
     }
     void insertBefore(Node *at, Node *item) {
         item->next = at;
         item->prev = at->prev;
         at->prev->next = item;
         at->prev = item;
     }
     void insertAfter(Node *at, Node *item) {
         item->next = at->next;
         item->prev = at;
         static_cast<Node *>(at->next)->prev = item;
         at->next = item;
     }
     void remove(Node *t) {
         t->prev->next = t->next;
         static_cast<Node *>(t->next)->prev = t->prev;
         t->next = t->prev = NULL;
     }
     void clear() {
         this->next = this->prev = this;
     }
     bool empty() const {
         return begin() == end();
     }
 };

 template <typename T>
 class InlineListIterator
 {
   private:
     friend class InlineList<T>;

     typedef InlineListNode<T> Node;

     InlineListIterator(const Node *iter)
       : iter(const_cast<Node *>(iter))
     { }

   public:
     InlineListIterator<T> & operator ++() {
         iter = iter->next;
         return *iter;
     }
     InlineListIterator<T> operator ++(int) {
         InlineListIterator<T> old(*this);
         iter = static_cast<Node *>(iter->next);
         return old;
     }
     InlineListIterator<T> operator --(int) {
         InlineListIterator<T> old(*this);
         iter = iter->prev;
         return old;
     }
     T * operator *() const {
         return static_cast<T *>(iter);
     }
     T * operator ->() const {
         return static_cast<T *>(iter);
     }
     bool operator !=(const InlineListIterator<T> &where) const {
         return iter != where.iter;
     }
     bool operator ==(const InlineListIterator<T> &where) const {
         return iter == where.iter;
     }

   private:
     Node *iter;
 };

 template <typename T>
 class InlineListReverseIterator
 {
   private:
     friend class InlineList<T>;

     typedef InlineListNode<T> Node;

     InlineListReverseIterator(const Node *iter)
       : iter(const_cast<Node *>(iter))
     { }

   public:
     InlineListReverseIterator<T> & operator ++() {
         iter = iter->prev;
         return *iter;
     }
     InlineListReverseIterator<T> operator ++(int) {
         InlineListReverseIterator<T> old(*this);
         iter = iter->prev;
         return old;
     }
     T * operator *() {
         return static_cast<T *>(iter);
     }
     T * operator ->() {
         return static_cast<T *>(iter);
     }
     bool operator !=(const InlineListReverseIterator<T> &where) const {
         return iter != where.iter;
     }
     bool operator ==(const InlineListReverseIterator<T> &where) const {
         return iter == where.iter;
     }

   private:
     Node *iter;
 };

 } // namespace js

 #endif /* jit_InlineList_h */
	/* -- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 --
	* vim: set ts=8 sts=4 et sw=4 tw=99:
	* 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 jit_InlineList_h
	#define jit_InlineList_h

	#include "mozilla/DebugOnly.h"

	#include "jsutil.h"

	namespace js {

	template <typename T> class InlineForwardList;
	template <typename T> class InlineForwardListIterator;

	template <typename T>
	class InlineForwardListNode
	{
	public:
	InlineForwardListNode() : next(NULL)
	{ }
	InlineForwardListNode(InlineForwardListNode<T> *n) : next(n)
	{ }

	protected:
	friend class InlineForwardList<T>;
	friend class InlineForwardListIterator<T>;

	InlineForwardListNode<T> *next;
	};

	template <typename T>
	class InlineForwardList : protected InlineForwardListNode<T>
	{
	friend class InlineForwardListIterator<T>;

	typedef InlineForwardListNode<T> Node;

	Node *tail_;
	mozilla::DebugOnly<int> modifyCount_;

	InlineForwardList<T> *thisFromConstructor() {
	return this;
	}

	public:
	InlineForwardList()
	: tail_(thisFromConstructor())
	{
	modifyCount_ = 0;
	}

	public:
	typedef InlineForwardListIterator<T> iterator;

	public:
	iterator begin() const {
	return iterator(this);
	}
	iterator end() const {
	return iterator(NULL);
	}
	iterator removeAt(iterator &where) {
	iterator iter(where);
	iter++;
	iter.prev = where.prev;
	iter.modifyCount_++;

	// Once the element 'where' points at has been removed, it is no longer
	// safe to do any operations that would touch 'iter', as the element
	// may be added to another list, etc. This NULL ensures that any
	// improper uses of this function will fail quickly and loudly.
	removeAfter(where.prev, where.iter);
	where.prev = where.iter = NULL;

	return iter;
	}
	void pushFront(Node *t) {
	insertAfter(this, t);
	}
	void pushBack(Node *t) {
	modifyCount_++;
	tail_->next = t;
	t->next = NULL;
	tail_ = t;
	}
	T *popFront() {
	JS_ASSERT(!empty());
	T* result = static_cast<T *>(this->next);
	removeAfter(this, result);
	return result;
	}
	void insertAfter(Node at, Node item) {
	modifyCount_++;
	if (at == tail_)
	tail_ = item;
	item->next = at->next;
	at->next = item;
	}
	void removeAfter(Node at, Node item) {
	modifyCount_++;
	if (item == tail_)
	tail_ = at;
	JS_ASSERT(at->next == item);
	at->next = item->next;
	}
	void splitAfter(Node at, InlineForwardList<T> to) {
	JS_ASSERT(to->empty());
	if (!at)
	at = this;
	if (at == tail_)
	return;
	modifyCount_++;
	to->next = at->next;
	to->tail_ = tail_;
	tail_ = at;
	at->next = NULL;
	}
	bool empty() const {
	return tail_ == this;
	}
	void clear() {
	this->next = NULL;
	tail_ = this;
	modifyCount_ = 0;
	}
	};

	template <typename T>
	class InlineForwardListIterator
	{
	private:
	friend class InlineForwardList<T>;

	typedef InlineForwardListNode<T> Node;

	InlineForwardListIterator<T>(const InlineForwardList<T> *owner)
	: prev(const_cast<Node >(static_cast<const Node >(owner))),
	iter(owner ? owner->next : NULL)
	#ifdef DEBUG
	, owner_(owner),
	modifyCount_(owner ? owner->modifyCount_.value : 0)
	#endif
	{ }

	public:
	InlineForwardListIterator<T> & operator ++() {
	JS_ASSERT(modifyCount_ == owner_->modifyCount_);
	prev = iter;
	iter = iter->next;
	return *this;
	}
	InlineForwardListIterator<T> operator ++(int) {
	JS_ASSERT(modifyCount_ == owner_->modifyCount_);
	InlineForwardListIterator<T> old(*this);
	prev = iter;
	iter = iter->next;
	return old;
	}
	T * operator *() const {
	JS_ASSERT(modifyCount_ == owner_->modifyCount_);
	return static_cast<T *>(iter);
	}
	T * operator ->() const {
	JS_ASSERT(modifyCount_ == owner_->modifyCount_);
	return static_cast<T *>(iter);
	}
	bool operator !=(const InlineForwardListIterator<T> &where) const {
	return iter != where.iter;
	}
	bool operator ==(const InlineForwardListIterator<T> &where) const {
	return iter == where.iter;
	}

	private:
	Node *prev;
	Node *iter;

	#ifdef DEBUG
	const InlineForwardList<T> *owner_;
	#endif
	mozilla::DebugOnly<int> modifyCount_;
	};

	template <typename T> class InlineList;
	template <typename T> class InlineListIterator;
	template <typename T> class InlineListReverseIterator;

	template <typename T>
	class InlineListNode : public InlineForwardListNode<T>
	{
	public:
	InlineListNode() : InlineForwardListNode<T>(NULL), prev(NULL)
	{ }
	InlineListNode(InlineListNode<T> n, InlineListNode<T> p)
	: InlineForwardListNode<T>(n),
	prev(p)
	{ }

	protected:
	friend class InlineList<T>;
	friend class InlineListIterator<T>;
	friend class InlineListReverseIterator<T>;

	InlineListNode<T> *prev;
	};

	template <typename T>
	class InlineList : protected InlineListNode<T>
	{
	typedef InlineListNode<T> Node;

	// Silence MSVC warning C4355
	InlineList<T> *thisFromConstructor() {
	return this;
	}

	public:
	InlineList() : InlineListNode<T>(thisFromConstructor(), thisFromConstructor())
	{ }

	public:
	typedef InlineListIterator<T> iterator;
	typedef InlineListReverseIterator<T> reverse_iterator;

	public:
	iterator begin() const {
	return iterator(static_cast<Node *>(this->next));
	}
	iterator begin(Node *t) const {
	return iterator(t);
	}
	iterator end() const {
	return iterator(this);
	}
	reverse_iterator rbegin() const {
	return reverse_iterator(this->prev);
	}
	reverse_iterator rbegin(Node *t) const {
	return reverse_iterator(t);
	}
	reverse_iterator rend() const {
	return reverse_iterator(this);
	}
	template <typename itertype>
	itertype removeAt(itertype &where) {
	itertype iter(where);
	iter++;

	// Once the element 'where' points at has been removed, it is no longer
	// safe to do any operations that would touch 'iter', as the element
	// may be added to another list, etc. This NULL ensures that any
	// improper uses of this function will fail quickly and loudly.
	remove(where.iter);
	where.iter = NULL;

	return iter;
	}
	void pushFront(Node *t) {
	insertAfter(this, t);
	}
	void pushBack(Node *t) {
	insertBefore(this, t);
	}
	T *popFront() {
	JS_ASSERT(!empty());
	T t = static_cast<T >(this->next);
	remove(t);
	return t;
	}
	T *popBack() {
	JS_ASSERT(!empty());
	T t = static_cast<T >(this->prev);
	remove(t);
	return t;
	}
	T *peekBack() const {
	iterator iter = end();
	iter--;
	return *iter;
	}
	void insertBefore(Node at, Node item) {
	item->next = at;
	item->prev = at->prev;
	at->prev->next = item;
	at->prev = item;
	}
	void insertAfter(Node at, Node item) {
	item->next = at->next;
	item->prev = at;
	static_cast<Node *>(at->next)->prev = item;
	at->next = item;
	}
	void remove(Node *t) {
	t->prev->next = t->next;
	static_cast<Node *>(t->next)->prev = t->prev;
	t->next = t->prev = NULL;
	}
	void clear() {
	this->next = this->prev = this;
	}
	bool empty() const {
	return begin() == end();
	}
	};

	template <typename T>
	class InlineListIterator
	{
	private:
	friend class InlineList<T>;

	typedef InlineListNode<T> Node;

	InlineListIterator(const Node *iter)
	: iter(const_cast<Node *>(iter))
	{ }

	public:
	InlineListIterator<T> & operator ++() {
	iter = iter->next;
	return *iter;
	}
	InlineListIterator<T> operator ++(int) {
	InlineListIterator<T> old(*this);
	iter = static_cast<Node *>(iter->next);
	return old;
	}
	InlineListIterator<T> operator --(int) {
	InlineListIterator<T> old(*this);
	iter = iter->prev;
	return old;
	}
	T * operator *() const {
	return static_cast<T *>(iter);
	}
	T * operator ->() const {
	return static_cast<T *>(iter);
	}
	bool operator !=(const InlineListIterator<T> &where) const {
	return iter != where.iter;
	}
	bool operator ==(const InlineListIterator<T> &where) const {
	return iter == where.iter;
	}

	private:
	Node *iter;
	};

	template <typename T>
	class InlineListReverseIterator
	{
	private:
	friend class InlineList<T>;

	typedef InlineListNode<T> Node;

	InlineListReverseIterator(const Node *iter)
	: iter(const_cast<Node *>(iter))
	{ }

	public:
	InlineListReverseIterator<T> & operator ++() {
	iter = iter->prev;
	return *iter;
	}
	InlineListReverseIterator<T> operator ++(int) {
	InlineListReverseIterator<T> old(*this);
	iter = iter->prev;
	return old;
	}
	T * operator *() {
	return static_cast<T *>(iter);
	}
	T * operator ->() {
	return static_cast<T *>(iter);
	}
	bool operator !=(const InlineListReverseIterator<T> &where) const {
	return iter != where.iter;
	}
	bool operator ==(const InlineListReverseIterator<T> &where) const {
	return iter == where.iter;
	}

	private:
	Node *iter;
	};

	} // namespace js

	#endif /* jit_InlineList_h */