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