The Tor Browser / file comparison

comparison: js/src/jit/InlineList.h

js/src/jit/InlineList.h

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:d74c0801277c
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifndef jit_InlineList_h
8 #define jit_InlineList_h
9
10 #include "jsutil.h"
11
12 namespace js {
13
14 template <typename T> class InlineForwardList;
15 template <typename T> class InlineForwardListIterator;
16
17 template <typename T>
18 class InlineForwardListNode
19 {
20 public:
21 InlineForwardListNode() : next(nullptr)
22 { }
23 InlineForwardListNode(InlineForwardListNode<T> *n) : next(n)
24 { }
25
26 protected:
27 friend class InlineForwardList<T>;
28 friend class InlineForwardListIterator<T>;
29
30 InlineForwardListNode<T> *next;
31 };
32
33 template <typename T>
34 class InlineForwardList : protected InlineForwardListNode<T>
35 {
36 friend class InlineForwardListIterator<T>;
37
38 typedef InlineForwardListNode<T> Node;
39
40 Node *tail_;
41 #ifdef DEBUG
42 int modifyCount_;
43 #endif
44
45 InlineForwardList<T> *thisFromConstructor() {
46 return this;
47 }
48
49 public:
50 InlineForwardList()
51 : tail_(thisFromConstructor())
52 {
53 #ifdef DEBUG
54 modifyCount_ = 0;
55 #endif
56 }
57
58 public:
59 typedef InlineForwardListIterator<T> iterator;
60
61 public:
62 iterator begin() const {
63 return iterator(this);
64 }
65 iterator end() const {
66 return iterator(nullptr);
67 }
68 iterator removeAt(iterator &where) {
69 iterator iter(where);
70 iter++;
71 iter.prev = where.prev;
72 #ifdef DEBUG
73 iter.modifyCount_++;
74 #endif
75
76 // Once the element 'where' points at has been removed, it is no longer
77 // safe to do any operations that would touch 'iter', as the element
78 // may be added to another list, etc. This nullptr ensures that any
79 // improper uses of this function will fail quickly and loudly.
80 removeAfter(where.prev, where.iter);
81 where.prev = where.iter = nullptr;
82
83 return iter;
84 }
85 void pushFront(Node *t) {
86 insertAfter(this, t);
87 }
88 void pushBack(Node *t) {
89 #ifdef DEBUG
90 modifyCount_++;
91 #endif
92 tail_->next = t;
93 t->next = nullptr;
94 tail_ = t;
95 }
96 T *popFront() {
97 JS_ASSERT(!empty());
98 T* result = static_cast<T *>(this->next);
99 removeAfter(this, result);
100 return result;
101 }
102 T *back() {
103 JS_ASSERT(!empty());
104 return static_cast<T *>(tail_);
105 }
106 void insertAfter(Node *at, Node *item) {
107 #ifdef DEBUG
108 modifyCount_++;
109 #endif
110 if (at == tail_)
111 tail_ = item;
112 item->next = at->next;
113 at->next = item;
114 }
115 void removeAfter(Node *at, Node *item) {
116 #ifdef DEBUG
117 modifyCount_++;
118 #endif
119 if (item == tail_)
120 tail_ = at;
121 JS_ASSERT(at->next == item);
122 at->next = item->next;
123 }
124 void splitAfter(Node *at, InlineForwardList<T> *to) {
125 JS_ASSERT(to->empty());
126 if (!at)
127 at = this;
128 if (at == tail_)
129 return;
130 #ifdef DEBUG
131 modifyCount_++;
132 #endif
133 to->next = at->next;
134 to->tail_ = tail_;
135 tail_ = at;
136 at->next = nullptr;
137 }
138 bool empty() const {
139 return tail_ == this;
140 }
141 void clear() {
142 this->next = nullptr;
143 tail_ = this;
144 #ifdef DEBUG
145 modifyCount_ = 0;
146 #endif
147 }
148 };
149
150 template <typename T>
151 class InlineForwardListIterator
152 {
153 private:
154 friend class InlineForwardList<T>;
155
156 typedef InlineForwardListNode<T> Node;
157
158 InlineForwardListIterator<T>(const InlineForwardList<T> *owner)
159 : prev(const_cast<Node *>(static_cast<const Node *>(owner))),
160 iter(owner ? owner->next : nullptr)
161 #ifdef DEBUG
162 , owner_(owner),
163 modifyCount_(owner ? owner->modifyCount_ : 0)
164 #endif
165 { }
166
167 public:
168 InlineForwardListIterator<T> & operator ++() {
169 JS_ASSERT(modifyCount_ == owner_->modifyCount_);
170 prev = iter;
171 iter = iter->next;
172 return *this;
173 }
174 InlineForwardListIterator<T> operator ++(int) {
175 JS_ASSERT(modifyCount_ == owner_->modifyCount_);
176 InlineForwardListIterator<T> old(*this);
177 prev = iter;
178 iter = iter->next;
179 return old;
180 }
181 T * operator *() const {
182 JS_ASSERT(modifyCount_ == owner_->modifyCount_);
183 return static_cast<T *>(iter);
184 }
185 T * operator ->() const {
186 JS_ASSERT(modifyCount_ == owner_->modifyCount_);
187 return static_cast<T *>(iter);
188 }
189 bool operator !=(const InlineForwardListIterator<T> &where) const {
190 return iter != where.iter;
191 }
192 bool operator ==(const InlineForwardListIterator<T> &where) const {
193 return iter == where.iter;
194 }
195
196 private:
197 Node *prev;
198 Node *iter;
199
200 #ifdef DEBUG
201 const InlineForwardList<T> *owner_;
202 int modifyCount_;
203 #endif
204 };
205
206 template <typename T> class InlineList;
207 template <typename T> class InlineListIterator;
208 template <typename T> class InlineListReverseIterator;
209
210 template <typename T>
211 class InlineListNode : public InlineForwardListNode<T>
212 {
213 public:
214 InlineListNode() : InlineForwardListNode<T>(nullptr), prev(nullptr)
215 { }
216 InlineListNode(InlineListNode<T> *n, InlineListNode<T> *p)
217 : InlineForwardListNode<T>(n),
218 prev(p)
219 { }
220
221 protected:
222 friend class InlineList<T>;
223 friend class InlineListIterator<T>;
224 friend class InlineListReverseIterator<T>;
225
226 InlineListNode<T> *prev;
227 };
228
229 template <typename T>
230 class InlineList : protected InlineListNode<T>
231 {
232 typedef InlineListNode<T> Node;
233
234 public:
235 InlineList() : InlineListNode<T>(MOZ_THIS_IN_INITIALIZER_LIST(), MOZ_THIS_IN_INITIALIZER_LIST())
236 { }
237
238 public:
239 typedef InlineListIterator<T> iterator;
240 typedef InlineListReverseIterator<T> reverse_iterator;
241
242 public:
243 iterator begin() const {
244 return iterator(static_cast<Node *>(this->next));
245 }
246 iterator begin(Node *t) const {
247 return iterator(t);
248 }
249 iterator end() const {
250 return iterator(this);
251 }
252 reverse_iterator rbegin() const {
253 return reverse_iterator(this->prev);
254 }
255 reverse_iterator rbegin(Node *t) const {
256 return reverse_iterator(t);
257 }
258 reverse_iterator rend() const {
259 return reverse_iterator(this);
260 }
261 template <typename itertype>
262 itertype removeAt(itertype &where) {
263 itertype iter(where);
264 iter++;
265
266 // Once the element 'where' points at has been removed, it is no longer
267 // safe to do any operations that would touch 'iter', as the element
268 // may be added to another list, etc. This nullptr ensures that any
269 // improper uses of this function will fail quickly and loudly.
270 remove(where.iter);
271 where.iter = nullptr;
272
273 return iter;
274 }
275 void pushFront(Node *t) {
276 insertAfter(this, t);
277 }
278 void pushBack(Node *t) {
279 insertBefore(this, t);
280 }
281 T *popFront() {
282 JS_ASSERT(!empty());
283 T *t = static_cast<T *>(this->next);
284 remove(t);
285 return t;
286 }
287 T *popBack() {
288 JS_ASSERT(!empty());
289 T *t = static_cast<T *>(this->prev);
290 remove(t);
291 return t;
292 }
293 T *peekBack() const {
294 iterator iter = end();
295 iter--;
296 return *iter;
297 }
298 void insertBefore(Node *at, Node *item) {
299 item->next = at;
300 item->prev = at->prev;
301 at->prev->next = item;
302 at->prev = item;
303 }
304 void insertAfter(Node *at, Node *item) {
305 item->next = at->next;
306 item->prev = at;
307 static_cast<Node *>(at->next)->prev = item;
308 at->next = item;
309 }
310 void remove(Node *t) {
311 t->prev->next = t->next;
312 static_cast<Node *>(t->next)->prev = t->prev;
313 t->next = t->prev = nullptr;
314 }
315 void clear() {
316 this->next = this->prev = this;
317 }
318 bool empty() const {
319 return begin() == end();
320 }
321 };
322
323 template <typename T>
324 class InlineListIterator
325 {
326 private:
327 friend class InlineList<T>;
328
329 typedef InlineListNode<T> Node;
330
331 InlineListIterator(const Node *iter)
332 : iter(const_cast<Node *>(iter))
333 { }
334
335 public:
336 InlineListIterator<T> & operator ++() {
337 iter = static_cast<Node *>(iter->next);
338 return *this;
339 }
340 InlineListIterator<T> operator ++(int) {
341 InlineListIterator<T> old(*this);
342 iter = static_cast<Node *>(iter->next);
343 return old;
344 }
345 InlineListIterator<T> operator --(int) {
346 InlineListIterator<T> old(*this);
347 iter = iter->prev;
348 return old;
349 }
350 T * operator *() const {
351 return static_cast<T *>(iter);
352 }
353 T * operator ->() const {
354 return static_cast<T *>(iter);
355 }
356 bool operator !=(const InlineListIterator<T> &where) const {
357 return iter != where.iter;
358 }
359 bool operator ==(const InlineListIterator<T> &where) const {
360 return iter == where.iter;
361 }
362
363 private:
364 Node *iter;
365 };
366
367 template <typename T>
368 class InlineListReverseIterator
369 {
370 private:
371 friend class InlineList<T>;
372
373 typedef InlineListNode<T> Node;
374
375 InlineListReverseIterator(const Node *iter)
376 : iter(const_cast<Node *>(iter))
377 { }
378
379 public:
380 InlineListReverseIterator<T> & operator ++() {
381 iter = iter->prev;
382 return *this;
383 }
384 InlineListReverseIterator<T> operator ++(int) {
385 InlineListReverseIterator<T> old(*this);
386 iter = iter->prev;
387 return old;
388 }
389 T * operator *() {
390 return static_cast<T *>(iter);
391 }
392 T * operator ->() {
393 return static_cast<T *>(iter);
394 }
395 bool operator !=(const InlineListReverseIterator<T> &where) const {
396 return iter != where.iter;
397 }
398 bool operator ==(const InlineListReverseIterator<T> &where) const {
399 return iter == where.iter;
400 }
401
402 private:
403 Node *iter;
404 };
405
406 /* This list type is more or less exactly an InlineForwardList without a sentinel
407 * node. It is useful in cases where you are doing algorithms that deal with many
408 * merging singleton lists, rather than often empty ones.
409 */
410 template <typename T> class InlineConcatListIterator;
411 template <typename T>
412 class InlineConcatList
413 {
414 private:
415 typedef InlineConcatList<T> Node;
416
417 InlineConcatList<T> *thisFromConstructor() {
418 return this;
419 }
420
421 public:
422 InlineConcatList() : next(nullptr), tail(thisFromConstructor())
423 { }
424
425 typedef InlineConcatListIterator<T> iterator;
426
427 iterator begin() const {
428 return iterator(this);
429 }
430
431 iterator end() const {
432 return iterator(nullptr);
433 }
434
435 void append(InlineConcatList<T> *adding)
436 {
437 JS_ASSERT(tail);
438 JS_ASSERT(!tail->next);
439 JS_ASSERT(adding->tail);
440 JS_ASSERT(!adding->tail->next);
441
442 tail->next = adding;
443 tail = adding->tail;
444 adding->tail = nullptr;
445 }
446
447 protected:
448 friend class InlineConcatListIterator<T>;
449 Node *next;
450 Node *tail;
451 };
452
453 template <typename T>
454 class InlineConcatListIterator
455 {
456 private:
457 friend class InlineConcatList<T>;
458
459 typedef InlineConcatList<T> Node;
460
461 InlineConcatListIterator(const Node *iter)
462 : iter(const_cast<Node *>(iter))
463 { }
464
465 public:
466 InlineConcatListIterator<T> & operator ++() {
467 iter = iter->next;
468 return *iter;
469 }
470 InlineConcatListIterator<T> operator ++(int) {
471 InlineConcatListIterator<T> old(*this);
472 iter = static_cast<Node *>(iter->next);
473 return old;
474 }
475 T * operator *() const {
476 return static_cast<T *>(iter);
477 }
478 T * operator ->() const {
479 return static_cast<T *>(iter);
480 }
481 bool operator !=(const InlineConcatListIterator<T> &where) const {
482 return iter != where.iter;
483 }
484 bool operator ==(const InlineConcatListIterator<T> &where) const {
485 return iter == where.iter;
486 }
487
488 private:
489 Node *iter;
490 };
491
492 } // namespace js
493
494 #endif /* jit_InlineList_h */

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial