xref: /trafficserver/include/tscore/List.h (revision 7651e269)
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() const164   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) const181   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() const343   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 *
operator newConsCell600   operator new(size_t size)
601   {
602     return A::alloc(size);
603   }
604   static void
operator 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