1 /*++
2 Copyright (c) 2011 Microsoft Corporation
3 
4 Module Name:
5 
6     dlist.h
7 
8 Abstract:
9 
10     Templates for manipulating circular doubly linked lists.
11 
12 Author:
13 
14     Leonardo de Moura (leonardo) 2011-01-25.
15 
16 Revision History:
17 
18 --*/
19 #pragma once
20 
21 
22 template<typename T>
23 class dll_base {
24     T* m_next { nullptr };
25     T* m_prev { nullptr };
26 public:
27 
prev()28     T* prev() { return m_prev; }
next()29     T* next() { return m_next; }
30 
init(T * t)31     void init(T* t) {
32         m_next = t;
33         m_prev = t;
34     }
35 
pop(T * & list)36     static T* pop(T*& list) {
37         if (!list)
38             return list;
39         T* head = list;
40         remove_from(list, head);
41         return head;
42     }
43 
remove_from(T * & list,T * elem)44     static void remove_from(T*& list, T* elem) {
45         if (list->m_next == list) {
46             SASSERT(elem == list);
47             list = nullptr;
48             return;
49         }
50         if (list == elem)
51             list = elem->m_next;
52         auto* next = elem->m_next;
53         auto* prev = elem->m_prev;
54         prev->m_next = next;
55         next->m_prev = prev;
56     }
57 
push_to_front(T * & list,T * elem)58     static void push_to_front(T*& list, T* elem) {
59         if (!list) {
60             list = elem;
61             elem->m_next = elem;
62             elem->m_prev = elem;
63         }
64         else if (list != elem) {
65             auto* next = elem->m_next;
66             auto* prev = elem->m_prev;
67             prev->m_next = next;
68             next->m_prev = prev;
69             list->m_prev->m_next = elem;
70             elem->m_prev = list->m_prev;
71             elem->m_next = list;
72             list->m_prev = elem;
73             list = elem;
74         }
75     }
76 
invariant()77     bool invariant() const {
78         auto* e = this;
79         do {
80             if (e->m_next->m_prev != e)
81                 return false;
82             e = e->m_next;
83         }
84         while (e != this);
85         return true;
86     }
87 };
88 
89 
90 
91