1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/InlineList.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,494 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jit_InlineList_h
1.11 +#define jit_InlineList_h
1.12 +
1.13 +#include "jsutil.h"
1.14 +
1.15 +namespace js {
1.16 +
1.17 +template <typename T> class InlineForwardList;
1.18 +template <typename T> class InlineForwardListIterator;
1.19 +
1.20 +template <typename T>
1.21 +class InlineForwardListNode
1.22 +{
1.23 + public:
1.24 + InlineForwardListNode() : next(nullptr)
1.25 + { }
1.26 + InlineForwardListNode(InlineForwardListNode<T> *n) : next(n)
1.27 + { }
1.28 +
1.29 + protected:
1.30 + friend class InlineForwardList<T>;
1.31 + friend class InlineForwardListIterator<T>;
1.32 +
1.33 + InlineForwardListNode<T> *next;
1.34 +};
1.35 +
1.36 +template <typename T>
1.37 +class InlineForwardList : protected InlineForwardListNode<T>
1.38 +{
1.39 + friend class InlineForwardListIterator<T>;
1.40 +
1.41 + typedef InlineForwardListNode<T> Node;
1.42 +
1.43 + Node *tail_;
1.44 +#ifdef DEBUG
1.45 + int modifyCount_;
1.46 +#endif
1.47 +
1.48 + InlineForwardList<T> *thisFromConstructor() {
1.49 + return this;
1.50 + }
1.51 +
1.52 + public:
1.53 + InlineForwardList()
1.54 + : tail_(thisFromConstructor())
1.55 + {
1.56 +#ifdef DEBUG
1.57 + modifyCount_ = 0;
1.58 +#endif
1.59 + }
1.60 +
1.61 + public:
1.62 + typedef InlineForwardListIterator<T> iterator;
1.63 +
1.64 + public:
1.65 + iterator begin() const {
1.66 + return iterator(this);
1.67 + }
1.68 + iterator end() const {
1.69 + return iterator(nullptr);
1.70 + }
1.71 + iterator removeAt(iterator &where) {
1.72 + iterator iter(where);
1.73 + iter++;
1.74 + iter.prev = where.prev;
1.75 +#ifdef DEBUG
1.76 + iter.modifyCount_++;
1.77 +#endif
1.78 +
1.79 + // Once the element 'where' points at has been removed, it is no longer
1.80 + // safe to do any operations that would touch 'iter', as the element
1.81 + // may be added to another list, etc. This nullptr ensures that any
1.82 + // improper uses of this function will fail quickly and loudly.
1.83 + removeAfter(where.prev, where.iter);
1.84 + where.prev = where.iter = nullptr;
1.85 +
1.86 + return iter;
1.87 + }
1.88 + void pushFront(Node *t) {
1.89 + insertAfter(this, t);
1.90 + }
1.91 + void pushBack(Node *t) {
1.92 +#ifdef DEBUG
1.93 + modifyCount_++;
1.94 +#endif
1.95 + tail_->next = t;
1.96 + t->next = nullptr;
1.97 + tail_ = t;
1.98 + }
1.99 + T *popFront() {
1.100 + JS_ASSERT(!empty());
1.101 + T* result = static_cast<T *>(this->next);
1.102 + removeAfter(this, result);
1.103 + return result;
1.104 + }
1.105 + T *back() {
1.106 + JS_ASSERT(!empty());
1.107 + return static_cast<T *>(tail_);
1.108 + }
1.109 + void insertAfter(Node *at, Node *item) {
1.110 +#ifdef DEBUG
1.111 + modifyCount_++;
1.112 +#endif
1.113 + if (at == tail_)
1.114 + tail_ = item;
1.115 + item->next = at->next;
1.116 + at->next = item;
1.117 + }
1.118 + void removeAfter(Node *at, Node *item) {
1.119 +#ifdef DEBUG
1.120 + modifyCount_++;
1.121 +#endif
1.122 + if (item == tail_)
1.123 + tail_ = at;
1.124 + JS_ASSERT(at->next == item);
1.125 + at->next = item->next;
1.126 + }
1.127 + void splitAfter(Node *at, InlineForwardList<T> *to) {
1.128 + JS_ASSERT(to->empty());
1.129 + if (!at)
1.130 + at = this;
1.131 + if (at == tail_)
1.132 + return;
1.133 +#ifdef DEBUG
1.134 + modifyCount_++;
1.135 +#endif
1.136 + to->next = at->next;
1.137 + to->tail_ = tail_;
1.138 + tail_ = at;
1.139 + at->next = nullptr;
1.140 + }
1.141 + bool empty() const {
1.142 + return tail_ == this;
1.143 + }
1.144 + void clear() {
1.145 + this->next = nullptr;
1.146 + tail_ = this;
1.147 +#ifdef DEBUG
1.148 + modifyCount_ = 0;
1.149 +#endif
1.150 + }
1.151 +};
1.152 +
1.153 +template <typename T>
1.154 +class InlineForwardListIterator
1.155 +{
1.156 +private:
1.157 + friend class InlineForwardList<T>;
1.158 +
1.159 + typedef InlineForwardListNode<T> Node;
1.160 +
1.161 + InlineForwardListIterator<T>(const InlineForwardList<T> *owner)
1.162 + : prev(const_cast<Node *>(static_cast<const Node *>(owner))),
1.163 + iter(owner ? owner->next : nullptr)
1.164 +#ifdef DEBUG
1.165 + , owner_(owner),
1.166 + modifyCount_(owner ? owner->modifyCount_ : 0)
1.167 +#endif
1.168 + { }
1.169 +
1.170 +public:
1.171 + InlineForwardListIterator<T> & operator ++() {
1.172 + JS_ASSERT(modifyCount_ == owner_->modifyCount_);
1.173 + prev = iter;
1.174 + iter = iter->next;
1.175 + return *this;
1.176 + }
1.177 + InlineForwardListIterator<T> operator ++(int) {
1.178 + JS_ASSERT(modifyCount_ == owner_->modifyCount_);
1.179 + InlineForwardListIterator<T> old(*this);
1.180 + prev = iter;
1.181 + iter = iter->next;
1.182 + return old;
1.183 + }
1.184 + T * operator *() const {
1.185 + JS_ASSERT(modifyCount_ == owner_->modifyCount_);
1.186 + return static_cast<T *>(iter);
1.187 + }
1.188 + T * operator ->() const {
1.189 + JS_ASSERT(modifyCount_ == owner_->modifyCount_);
1.190 + return static_cast<T *>(iter);
1.191 + }
1.192 + bool operator !=(const InlineForwardListIterator<T> &where) const {
1.193 + return iter != where.iter;
1.194 + }
1.195 + bool operator ==(const InlineForwardListIterator<T> &where) const {
1.196 + return iter == where.iter;
1.197 + }
1.198 +
1.199 +private:
1.200 + Node *prev;
1.201 + Node *iter;
1.202 +
1.203 +#ifdef DEBUG
1.204 + const InlineForwardList<T> *owner_;
1.205 + int modifyCount_;
1.206 +#endif
1.207 +};
1.208 +
1.209 +template <typename T> class InlineList;
1.210 +template <typename T> class InlineListIterator;
1.211 +template <typename T> class InlineListReverseIterator;
1.212 +
1.213 +template <typename T>
1.214 +class InlineListNode : public InlineForwardListNode<T>
1.215 +{
1.216 + public:
1.217 + InlineListNode() : InlineForwardListNode<T>(nullptr), prev(nullptr)
1.218 + { }
1.219 + InlineListNode(InlineListNode<T> *n, InlineListNode<T> *p)
1.220 + : InlineForwardListNode<T>(n),
1.221 + prev(p)
1.222 + { }
1.223 +
1.224 + protected:
1.225 + friend class InlineList<T>;
1.226 + friend class InlineListIterator<T>;
1.227 + friend class InlineListReverseIterator<T>;
1.228 +
1.229 + InlineListNode<T> *prev;
1.230 +};
1.231 +
1.232 +template <typename T>
1.233 +class InlineList : protected InlineListNode<T>
1.234 +{
1.235 + typedef InlineListNode<T> Node;
1.236 +
1.237 + public:
1.238 + InlineList() : InlineListNode<T>(MOZ_THIS_IN_INITIALIZER_LIST(), MOZ_THIS_IN_INITIALIZER_LIST())
1.239 + { }
1.240 +
1.241 + public:
1.242 + typedef InlineListIterator<T> iterator;
1.243 + typedef InlineListReverseIterator<T> reverse_iterator;
1.244 +
1.245 + public:
1.246 + iterator begin() const {
1.247 + return iterator(static_cast<Node *>(this->next));
1.248 + }
1.249 + iterator begin(Node *t) const {
1.250 + return iterator(t);
1.251 + }
1.252 + iterator end() const {
1.253 + return iterator(this);
1.254 + }
1.255 + reverse_iterator rbegin() const {
1.256 + return reverse_iterator(this->prev);
1.257 + }
1.258 + reverse_iterator rbegin(Node *t) const {
1.259 + return reverse_iterator(t);
1.260 + }
1.261 + reverse_iterator rend() const {
1.262 + return reverse_iterator(this);
1.263 + }
1.264 + template <typename itertype>
1.265 + itertype removeAt(itertype &where) {
1.266 + itertype iter(where);
1.267 + iter++;
1.268 +
1.269 + // Once the element 'where' points at has been removed, it is no longer
1.270 + // safe to do any operations that would touch 'iter', as the element
1.271 + // may be added to another list, etc. This nullptr ensures that any
1.272 + // improper uses of this function will fail quickly and loudly.
1.273 + remove(where.iter);
1.274 + where.iter = nullptr;
1.275 +
1.276 + return iter;
1.277 + }
1.278 + void pushFront(Node *t) {
1.279 + insertAfter(this, t);
1.280 + }
1.281 + void pushBack(Node *t) {
1.282 + insertBefore(this, t);
1.283 + }
1.284 + T *popFront() {
1.285 + JS_ASSERT(!empty());
1.286 + T *t = static_cast<T *>(this->next);
1.287 + remove(t);
1.288 + return t;
1.289 + }
1.290 + T *popBack() {
1.291 + JS_ASSERT(!empty());
1.292 + T *t = static_cast<T *>(this->prev);
1.293 + remove(t);
1.294 + return t;
1.295 + }
1.296 + T *peekBack() const {
1.297 + iterator iter = end();
1.298 + iter--;
1.299 + return *iter;
1.300 + }
1.301 + void insertBefore(Node *at, Node *item) {
1.302 + item->next = at;
1.303 + item->prev = at->prev;
1.304 + at->prev->next = item;
1.305 + at->prev = item;
1.306 + }
1.307 + void insertAfter(Node *at, Node *item) {
1.308 + item->next = at->next;
1.309 + item->prev = at;
1.310 + static_cast<Node *>(at->next)->prev = item;
1.311 + at->next = item;
1.312 + }
1.313 + void remove(Node *t) {
1.314 + t->prev->next = t->next;
1.315 + static_cast<Node *>(t->next)->prev = t->prev;
1.316 + t->next = t->prev = nullptr;
1.317 + }
1.318 + void clear() {
1.319 + this->next = this->prev = this;
1.320 + }
1.321 + bool empty() const {
1.322 + return begin() == end();
1.323 + }
1.324 +};
1.325 +
1.326 +template <typename T>
1.327 +class InlineListIterator
1.328 +{
1.329 + private:
1.330 + friend class InlineList<T>;
1.331 +
1.332 + typedef InlineListNode<T> Node;
1.333 +
1.334 + InlineListIterator(const Node *iter)
1.335 + : iter(const_cast<Node *>(iter))
1.336 + { }
1.337 +
1.338 + public:
1.339 + InlineListIterator<T> & operator ++() {
1.340 + iter = static_cast<Node *>(iter->next);
1.341 + return *this;
1.342 + }
1.343 + InlineListIterator<T> operator ++(int) {
1.344 + InlineListIterator<T> old(*this);
1.345 + iter = static_cast<Node *>(iter->next);
1.346 + return old;
1.347 + }
1.348 + InlineListIterator<T> operator --(int) {
1.349 + InlineListIterator<T> old(*this);
1.350 + iter = iter->prev;
1.351 + return old;
1.352 + }
1.353 + T * operator *() const {
1.354 + return static_cast<T *>(iter);
1.355 + }
1.356 + T * operator ->() const {
1.357 + return static_cast<T *>(iter);
1.358 + }
1.359 + bool operator !=(const InlineListIterator<T> &where) const {
1.360 + return iter != where.iter;
1.361 + }
1.362 + bool operator ==(const InlineListIterator<T> &where) const {
1.363 + return iter == where.iter;
1.364 + }
1.365 +
1.366 + private:
1.367 + Node *iter;
1.368 +};
1.369 +
1.370 +template <typename T>
1.371 +class InlineListReverseIterator
1.372 +{
1.373 + private:
1.374 + friend class InlineList<T>;
1.375 +
1.376 + typedef InlineListNode<T> Node;
1.377 +
1.378 + InlineListReverseIterator(const Node *iter)
1.379 + : iter(const_cast<Node *>(iter))
1.380 + { }
1.381 +
1.382 + public:
1.383 + InlineListReverseIterator<T> & operator ++() {
1.384 + iter = iter->prev;
1.385 + return *this;
1.386 + }
1.387 + InlineListReverseIterator<T> operator ++(int) {
1.388 + InlineListReverseIterator<T> old(*this);
1.389 + iter = iter->prev;
1.390 + return old;
1.391 + }
1.392 + T * operator *() {
1.393 + return static_cast<T *>(iter);
1.394 + }
1.395 + T * operator ->() {
1.396 + return static_cast<T *>(iter);
1.397 + }
1.398 + bool operator !=(const InlineListReverseIterator<T> &where) const {
1.399 + return iter != where.iter;
1.400 + }
1.401 + bool operator ==(const InlineListReverseIterator<T> &where) const {
1.402 + return iter == where.iter;
1.403 + }
1.404 +
1.405 + private:
1.406 + Node *iter;
1.407 +};
1.408 +
1.409 +/* This list type is more or less exactly an InlineForwardList without a sentinel
1.410 + * node. It is useful in cases where you are doing algorithms that deal with many
1.411 + * merging singleton lists, rather than often empty ones.
1.412 + */
1.413 +template <typename T> class InlineConcatListIterator;
1.414 +template <typename T>
1.415 +class InlineConcatList
1.416 +{
1.417 + private:
1.418 + typedef InlineConcatList<T> Node;
1.419 +
1.420 + InlineConcatList<T> *thisFromConstructor() {
1.421 + return this;
1.422 + }
1.423 +
1.424 + public:
1.425 + InlineConcatList() : next(nullptr), tail(thisFromConstructor())
1.426 + { }
1.427 +
1.428 + typedef InlineConcatListIterator<T> iterator;
1.429 +
1.430 + iterator begin() const {
1.431 + return iterator(this);
1.432 + }
1.433 +
1.434 + iterator end() const {
1.435 + return iterator(nullptr);
1.436 + }
1.437 +
1.438 + void append(InlineConcatList<T> *adding)
1.439 + {
1.440 + JS_ASSERT(tail);
1.441 + JS_ASSERT(!tail->next);
1.442 + JS_ASSERT(adding->tail);
1.443 + JS_ASSERT(!adding->tail->next);
1.444 +
1.445 + tail->next = adding;
1.446 + tail = adding->tail;
1.447 + adding->tail = nullptr;
1.448 + }
1.449 +
1.450 + protected:
1.451 + friend class InlineConcatListIterator<T>;
1.452 + Node *next;
1.453 + Node *tail;
1.454 +};
1.455 +
1.456 +template <typename T>
1.457 +class InlineConcatListIterator
1.458 +{
1.459 + private:
1.460 + friend class InlineConcatList<T>;
1.461 +
1.462 + typedef InlineConcatList<T> Node;
1.463 +
1.464 + InlineConcatListIterator(const Node *iter)
1.465 + : iter(const_cast<Node *>(iter))
1.466 + { }
1.467 +
1.468 + public:
1.469 + InlineConcatListIterator<T> & operator ++() {
1.470 + iter = iter->next;
1.471 + return *iter;
1.472 + }
1.473 + InlineConcatListIterator<T> operator ++(int) {
1.474 + InlineConcatListIterator<T> old(*this);
1.475 + iter = static_cast<Node *>(iter->next);
1.476 + return old;
1.477 + }
1.478 + T * operator *() const {
1.479 + return static_cast<T *>(iter);
1.480 + }
1.481 + T * operator ->() const {
1.482 + return static_cast<T *>(iter);
1.483 + }
1.484 + bool operator !=(const InlineConcatListIterator<T> &where) const {
1.485 + return iter != where.iter;
1.486 + }
1.487 + bool operator ==(const InlineConcatListIterator<T> &where) const {
1.488 + return iter == where.iter;
1.489 + }
1.490 +
1.491 + private:
1.492 + Node *iter;
1.493 +};
1.494 +
1.495 +} // namespace js
1.496 +
1.497 +#endif /* jit_InlineList_h */
