1 /** @file
2
3 A brief file description
4
5 @section license License
6
7 Licensed to the Apache Software Foundation (ASF) under one
8 or more contributor license agreements. See the NOTICE file
9 distributed with this work for additional information
10 regarding copyright ownership. The ASF licenses this file
11 to you under the Apache License, Version 2.0 (the
12 "License"); you may not use this file except in compliance
13 with the License. You may obtain a copy of the License at
14
15 http://www.apache.org/licenses/LICENSE-2.0
16
17 Unless required by applicable law or agreed to in writing, software
18 distributed under the License is distributed on an "AS IS" BASIS,
19 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20 See the License for the specific language governing permissions and
21 limitations under the License.
22 */
23
24 /****************************************************************************
25
26 List.h
27
28 This file implements singly and doubly linked list templates for
29 homomorphic lists.
30
31 There are two main data structures defined for each list, a link cell
32 and a list descriptor. Both are parameterized by template object class.
33 The link cell and list descriptor are named as follows:
34
35 list type 1-linked list 2-linked list queue
36 --------- ------------- ------------- -----
37 link cell SLink<C> Link<C> Link<C>
38 list descriptor SLL<C> DLL<C> Queue<C>
39
40 The list descriptor contains state about the lists (for example: head and
41 tail pointers) and supports list manipulation methods.
42
43 The link cell strings objects together in the list, and is normally part
44 of the object itself. An SLink only points to the next object. A Link
45 points both to the previous and the next object in a list.
46
47 The link() method can help find the location of the location of the link
48 cell within an object, given the location of the link cell in another
49 object. This is useful when iterating along lists.
50
51
52 ****************************************************************************/
53
54 #pragma once
55
56 #include <cstdint>
57
58 #include "tscore/ink_assert.h"
59 #include "tscore/ink_queue.h"
60 #include "tscore/defalloc.h"
61
62 //
63 // Link cell for singly-linked list of objects of type C.
64 //
65 template <class C> class SLink
66 {
67 public:
68 C *next;
SLink()69 SLink() : next(nullptr){};
70 };
71 #define SLINK(_c, _f) \
72 class Link##_##_f : public SLink<_c> \
73 { \
74 public: \
75 static _c *& \
76 next_link(_c *c) \
77 { \
78 return c->_f.next; \
79 } \
80 static const _c * \
81 next_link(const _c *c) \
82 { \
83 return c->_f.next; \
84 } \
85 }; \
86 SLink<_c> _f
87 #define SLINKM(_c, _m, _f) \
88 class Link##_##_m##_##_f : public SLink<_c> \
89 { \
90 public: \
91 static _c *& \
92 next_link(_c *c) \
93 { \
94 return c->_m._f.next; \
95 } \
96 };
97
98 //
99 // Link cell for doubly-linked list of objects of type C.
100 //
101 template <class C> struct Link : public SLink<C> {
102 C *prev;
LinkLink103 Link() : prev(nullptr) {}
104 };
105 #define LINK(_c, _f) \
106 class Link##_##_f : public Link<_c> \
107 { \
108 public: \
109 static _c *& \
110 next_link(_c *c) \
111 { \
112 return c->_f.next; \
113 } \
114 static _c *& \
115 prev_link(_c *c) \
116 { \
117 return c->_f.prev; \
118 } \
119 static const _c * \
120 next_link(const _c *c) \
121 { \
122 return c->_f.next; \
123 } \
124 static const _c * \
125 prev_link(const _c *c) \
126 { \
127 return c->_f.prev; \
128 } \
129 }; \
130 Link<_c> _f
131 #define LINKM(_c, _m, _f) \
132 class Link##_##_m##_##_f : public Link<_c> \
133 { \
134 public: \
135 static _c *& \
136 next_link(_c *c) \
137 { \
138 return c->_m._f.next; \
139 } \
140 static _c *& \
141 prev_link(_c *c) \
142 { \
143 return c->_m._f.prev; \
144 } \
145 };
146 #define LINK_FORWARD_DECLARATION(_c, _f) \
147 class Link##_##_c##_##_f : public Link<_c> \
148 { \
149 public: \
150 static _c *&next_link(_c *c); \
151 static _c *&prev_link(_c *c); \
152 };
153 #define LINK_DEFINITION(_c, _f) \
154 inline _c *&Link##_##_c##_##_f::next_link(_c *c) { return c->_f.next; } \
155 inline _c *&Link##_##_c##_##_f::prev_link(_c *c) { return c->_f.prev; }
156 //
157 // List descriptor for singly-linked list of objects of type C.
158 //
159 template <class C, class L = typename C::Link_link> class SLL
160 {
161 public:
162 C *head;
163 bool
empty()164 empty() const
165 {
166 return head == nullptr;
167 }
168 void push(C *e);
169 C *pop();
170 void
clear()171 clear()
172 {
173 head = nullptr;
174 }
175 C *&
next(C * e)176 next(C *e)
177 {
178 return L::next_link(e);
179 }
180 const C *
next(const C * e)181 next(const C *e) const
182 {
183 return L::next_link(e);
184 }
185
SLL()186 SLL() : head(nullptr) {}
SLL(C * c)187 SLL(C *c) : head(c) {}
188 };
189 #define SList(_c, _f) SLL<_c, _c::Link##_##_f>
190 #define SListM(_c, _m, _ml, _l) SLL<_c, _c::Link##_##_ml##_##_l>
191 #define forl_LL(_c, _p, _l) for (_c *_p = (_l).head; _p; _p = (_l).next(_p))
192
193 template <class C, class L>
194 inline void
push(C * e)195 SLL<C, L>::push(C *e)
196 {
197 next(e) = head;
198 head = e;
199 }
200
201 template <class C, class L>
202 inline C *
pop()203 SLL<C, L>::pop()
204 {
205 C *ret = head;
206 if (ret) {
207 head = next(ret);
208 next(ret) = nullptr;
209 }
210 return ret;
211 }
212
213 //
214 // List descriptor for doubly-linked list of objects of type C.
215 //
216 template <class C, class L = typename C::Link_link> struct DLL {
217 C *head;
218 bool
emptyDLL219 empty() const
220 {
221 return head == nullptr;
222 }
223 void push(C *e);
224 C *pop();
225 void remove(C *e);
226 void insert(C *e, C *after);
227 bool
inDLL228 in(C *e)
229 {
230 return head == e || next(e) || prev(e);
231 }
232 void
clearDLL233 clear()
234 {
235 head = nullptr;
236 }
237 static C *&
nextDLL238 next(C *e)
239 {
240 return reinterpret_cast<C *&>(L::next_link(e));
241 }
242 static C *&
prevDLL243 prev(C *e)
244 {
245 return reinterpret_cast<C *&>(L::prev_link(e));
246 }
247 static C const *
nextDLL248 next(const C *e)
249 {
250 return L::next_link(e);
251 }
252 static C const *
prevDLL253 prev(const C *e)
254 {
255 return L::prev_link(e);
256 }
257
DLLDLL258 DLL() : head(nullptr) {}
259 };
260 #define DList(_c, _f) DLL<_c, _c::Link##_##_f>
261 #define DListM(_c, _m, _ml, _l) DLL<_c, _c::Link##_##_ml##_##_l>
262
263 template <class C, class L>
264 inline void
push(C * e)265 DLL<C, L>::push(C *e)
266 {
267 if (head)
268 prev(head) = e;
269 next(e) = head;
270 head = e;
271 }
272
273 template <class C, class L>
274 inline void
remove(C * e)275 DLL<C, L>::remove(C *e)
276 {
277 if (!head)
278 return;
279 if (e == head)
280 head = next(e);
281 if (prev(e))
282 next(prev(e)) = next(e);
283 if (next(e))
284 prev(next(e)) = prev(e);
285 prev(e) = nullptr;
286 next(e) = nullptr;
287 }
288
289 template <class C, class L>
290 inline C *
pop()291 DLL<C, L>::pop()
292 {
293 C *ret = head;
294 if (ret) {
295 head = next(ret);
296 if (head)
297 prev(head) = nullptr;
298 next(ret) = nullptr;
299 return ret;
300 } else
301 return nullptr;
302 }
303
304 template <class C, class L>
305 inline void
insert(C * e,C * after)306 DLL<C, L>::insert(C *e, C *after)
307 {
308 if (!after) {
309 push(e);
310 return;
311 }
312 prev(e) = after;
313 next(e) = next(after);
314 next(after) = e;
315 if (next(e))
316 prev(next(e)) = e;
317 }
318
319 //
320 // List descriptor for queue of objects of type C.
321 //
322 template <class C, class L = typename C::Link_link> class Queue : public DLL<C, L>
323 {
324 public:
325 using DLL<C, L>::head;
326 C *tail;
327 void push(C *e);
328 C *pop();
329 void enqueue(C *e);
330 void in_or_enqueue(C *e);
331 C *dequeue();
332 void remove(C *e);
333 void insert(C *e, C *after);
334 void append(Queue<C, L> q);
335 void append(DLL<C, L> q);
336 void
clear()337 clear()
338 {
339 head = nullptr;
340 tail = nullptr;
341 }
342 bool
empty()343 empty() const
344 {
345 return head == nullptr;
346 }
347
Queue()348 Queue() : tail(nullptr) {}
349 };
350 #define Que(_c, _f) Queue<_c, _c::Link##_##_f>
351 #define QueM(_c, _m, _mf, _f) Queue<_c, _c::Link##_##_mf##_##_f>
352
353 template <class C, class L>
354 inline void
push(C * e)355 Queue<C, L>::push(C *e)
356 {
357 DLL<C, L>::push(e);
358 if (!tail)
359 tail = head;
360 }
361
362 template <class C, class L>
363 inline C *
pop()364 Queue<C, L>::pop()
365 {
366 C *ret = DLL<C, L>::pop();
367 if (!head)
368 tail = nullptr;
369 return ret;
370 }
371
372 template <class C, class L>
373 inline void
insert(C * e,C * after)374 Queue<C, L>::insert(C *e, C *after)
375 {
376 DLL<C, L>::insert(e, after);
377 if (!tail)
378 tail = head;
379 else if (tail == after)
380 tail = e;
381 }
382
383 template <class C, class L>
384 inline void
remove(C * e)385 Queue<C, L>::remove(C *e)
386 {
387 if (tail == e)
388 tail = (C *)this->prev(e);
389 DLL<C, L>::remove(e);
390 }
391
392 template <class C, class L>
393 inline void
append(DLL<C,L> q)394 Queue<C, L>::append(DLL<C, L> q)
395 {
396 C *qtail = q.head;
397 if (qtail)
398 while (this->next(qtail))
399 qtail = this->next(qtail);
400 if (!head) {
401 head = q.head;
402 tail = qtail;
403 } else {
404 if (q.head) {
405 this->next(tail) = q.head;
406 this->prev(q.head) = tail;
407 tail = qtail;
408 }
409 }
410 }
411
412 template <class C, class L>
413 inline void
append(Queue<C,L> q)414 Queue<C, L>::append(Queue<C, L> q)
415 {
416 if (!head) {
417 head = q.head;
418 tail = q.tail;
419 } else {
420 if (q.head) {
421 this->next(tail) = q.head;
422 this->prev(q.head) = tail;
423 tail = q.tail;
424 }
425 }
426 }
427
428 template <class C, class L>
429 inline void
enqueue(C * e)430 Queue<C, L>::enqueue(C *e)
431 {
432 if (tail)
433 insert(e, tail);
434 else
435 push(e);
436 }
437
438 template <class C, class L>
439 inline void
in_or_enqueue(C * e)440 Queue<C, L>::in_or_enqueue(C *e)
441 {
442 if (!this->in(e))
443 enqueue(e);
444 }
445
446 template <class C, class L>
447 inline C *
dequeue()448 Queue<C, L>::dequeue()
449 {
450 return pop();
451 }
452
453 //
454 // Adds sorting, but requires that elements implement <
455 //
456
457 template <class C, class L = typename C::Link_link> struct SortableQueue : public Queue<C, L> {
458 using DLL<C, L>::head;
459 using Queue<C, L>::tail;
460 void
sortSortableQueue461 sort()
462 {
463 if (!head)
464 return;
465 bool clean = false;
466 while (!clean) {
467 clean = true;
468 C *v = head;
469 C *n = this->next(head);
470 while (n) {
471 C *f = this->next(n);
472 if (*n < *v) {
473 clean = false;
474 // swap 'em
475 if (head == v)
476 head = n;
477 if (tail == n)
478 tail = v;
479 // fix prev (p)
480 C *p = this->prev(v);
481 if (p) {
482 this->next(p) = n;
483 this->prev(n) = p;
484 } else
485 this->prev(n) = nullptr;
486 // fix follow (f)
487 if (f) {
488 this->prev(f) = v;
489 this->next(v) = f;
490 } else
491 this->next(v) = nullptr;
492 // fix interior
493 this->prev(v) = n;
494 this->next(n) = v;
495 } else
496 v = n;
497 n = f;
498 }
499 }
500 }
501 };
502 #define SortableQue(_c, _l) SortableQueue<_c, _c::Link##_##_f>
503
504 //
505 // Adds counting to the Queue
506 //
507
508 template <class C, class L = typename C::Link_link> struct CountQueue : public Queue<C, L> {
509 int size = 0;
CountQueueCountQueue510 inline CountQueue() {}
511 inline void push(C *e);
512 inline C *pop();
513 inline void enqueue(C *e);
514 inline C *dequeue();
515 inline void remove(C *e);
516 inline void insert(C *e, C *after);
517 inline void append(CountQueue<C, L> &q);
518 inline void append_clear(CountQueue<C, L> &q);
519 };
520 #define CountQue(_c, _f) CountQueue<_c, _c::Link##_##_f>
521 #define CountQueM(_c, _m, _mf, _f) CountQueue<_c, _c::Link##_##_mf##_##_f>
522
523 template <class C, class L>
524 inline void
push(C * e)525 CountQueue<C, L>::push(C *e)
526 {
527 Queue<C, L>::push(e);
528 size++;
529 }
530
531 template <class C, class L>
532 inline C *
pop()533 CountQueue<C, L>::pop()
534 {
535 C *ret = Queue<C, L>::pop();
536 if (ret)
537 size--;
538 return ret;
539 }
540
541 template <class C, class L>
542 inline void
remove(C * e)543 CountQueue<C, L>::remove(C *e)
544 {
545 Queue<C, L>::remove(e);
546 size--;
547 }
548
549 template <class C, class L>
550 inline void
enqueue(C * e)551 CountQueue<C, L>::enqueue(C *e)
552 {
553 Queue<C, L>::enqueue(e);
554 size++;
555 }
556
557 template <class C, class L>
558 inline C *
dequeue()559 CountQueue<C, L>::dequeue()
560 {
561 return pop();
562 }
563
564 template <class C, class L>
565 inline void
insert(C * e,C * after)566 CountQueue<C, L>::insert(C *e, C *after)
567 {
568 Queue<C, L>::insert(e, after);
569 size++;
570 }
571
572 template <class C, class L>
573 inline void
append(CountQueue<C,L> & q)574 CountQueue<C, L>::append(CountQueue<C, L> &q)
575 {
576 Queue<C, L>::append(q);
577 size += q.size;
578 }
579
580 template <class C, class L>
581 inline void
append_clear(CountQueue<C,L> & q)582 CountQueue<C, L>::append_clear(CountQueue<C, L> &q)
583 {
584 append(q);
585 q.head = q.tail = 0;
586 q.size = 0;
587 }
588
589 //
590 // List using cons cells
591 //
592
593 template <class C, class A = DefaultAlloc> struct ConsCell {
594 C car;
595 ConsCell *cdr;
ConsCellConsCell596 ConsCell(C acar, ConsCell *acdr) : car(acar), cdr(acdr) {}
ConsCellConsCell597 ConsCell(C acar) : car(acar), cdr(nullptr) {}
ConsCellConsCell598 ConsCell(ConsCell *acdr) : cdr(acdr) {}
599 static void *
newConsCell600 operator new(size_t size)
601 {
602 return A::alloc(size);
603 }
604 static void
deleteConsCell605 operator delete(void *p, size_t /* size ATS_UNUSED */)
606 {
607 A::free(p);
608 }
609 };
610
611 template <class C, class A = DefaultAlloc> struct List {
612 ConsCell<C, A> *head;
613 C
firstList614 first()
615 {
616 if (head)
617 return head->car;
618 else
619 return 0;
620 }
621 C
carList622 car()
623 {
624 return first();
625 }
626 ConsCell<C, A> *
restList627 rest()
628 {
629 if (head)
630 return head->cdr;
631 else
632 return 0;
633 }
634 ConsCell<C, A> *
cdrList635 cdr()
636 {
637 return rest();
638 }
639 void
pushList640 push(C a)
641 {
642 head = new ConsCell<C, A>(a, head);
643 }
644 void
pushList645 push()
646 {
647 head = new ConsCell<C, A>(head);
648 }
649 C
popList650 pop()
651 {
652 C a = car();
653 head = cdr();
654 return a;
655 }
656 void
clearList657 clear()
658 {
659 head = nullptr;
660 }
661 void reverse();
ListList662 List(C acar) : head(new ConsCell<C, A>(acar)) {}
ListList663 List(C a, C b) : head(new ConsCell<C, A>(a, new ConsCell<C, A>(b))) {}
ListList664 List(C a, C b, C c) : head(new ConsCell<C, A>(a, new ConsCell<C, A>(b, new ConsCell<C, A>(c)))) {}
ListList665 List() : head(0) {}
666 };
667 #define forc_List(_c, _p, _l) \
668 if ((_l).head) \
669 for (_c *_p = (_l).head; _p; _p = _p->cdr)
670
671 template <class C, class A>
672 void
reverse()673 List<C, A>::reverse()
674 {
675 ConsCell<C, A> *n, *t;
676 for (ConsCell<C, A> *p = head; p; p = n) {
677 n = p->cdr;
678 p->cdr = t;
679 t = p;
680 }
681 head = t;
682 }
683
684 //
685 // Atomic lists
686 //
687
688 template <class C, class L = typename C::Link_link> struct AtomicSLL {
689 void
pushAtomicSLL690 push(C *c)
691 {
692 ink_atomiclist_push(&al, c);
693 }
694 C *
popAtomicSLL695 pop()
696 {
697 return (C *)ink_atomiclist_pop(&al);
698 }
699 C *
popallAtomicSLL700 popall()
701 {
702 return (C *)ink_atomiclist_popall(&al);
703 }
704 bool
emptyAtomicSLL705 empty()
706 {
707 return INK_ATOMICLIST_EMPTY(al);
708 }
709
710 /*
711 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING
712 * only if only one thread is doing pops it is possible to have a "remove"
713 * which only that thread can use as well.
714 * WARNING WARNING WARNING WARNING WARNING WARNING WARNING
715 */
716 C *
removeAtomicSLL717 remove(C *c)
718 {
719 return (C *)ink_atomiclist_remove(&al, c);
720 }
721 C *
headAtomicSLL722 head()
723 {
724 return (C *)TO_PTR(FREELIST_POINTER(al.head));
725 }
726 C *
nextAtomicSLL727 next(C *c)
728 {
729 return (C *)TO_PTR(c);
730 }
731
732 InkAtomicList al;
733
734 AtomicSLL();
735 };
736
737 #define ASLL(_c, _l) AtomicSLL<_c, _c::Link##_##_l>
738 #define ASLLM(_c, _m, _ml, _l) AtomicSLL<_c, _c::Link##_##_ml##_##_l>
739
AtomicSLL()740 template <class C, class L> inline AtomicSLL<C, L>::AtomicSLL()
741 {
742 // need @c offsetof but that's not reliable until C++17, and we can't use the nullptr trick directly because
743 // clang-analyzer gets upset, so we use 0x10 as the base and subtract it back afterwards.
744 ink_atomiclist_init(&al, "AtomicSLL", reinterpret_cast<uintptr_t>(&L::next_link(reinterpret_cast<C *>(0x10))) - 0x10);
745 }
746