1 /*++ 2 Copyright (c) 2006 Microsoft Corporation 3 4 Module Name: 5 6 list.h 7 8 Abstract: 9 10 Simple list data structure. It is meant to be used with region allocators. 11 12 Author: 13 14 Leonardo de Moura (leonardo) 2007-07-10. 15 16 Revision History: 17 18 --*/ 19 #pragma once 20 21 #include "util/buffer.h" 22 #include "util/region.h" 23 24 template<typename T> 25 class list { 26 T m_head; 27 list * m_tail; 28 29 public: 30 list(T const & h, list * t = nullptr): m_head(h)31 m_head(h), 32 m_tail(t) { 33 } 34 head()35 T const & head() const { return m_head; } tail()36 list * tail() const { return m_tail; } head()37 T & head() { return m_head; } tail()38 list * & tail() { return m_tail; } 39 40 class iterator { 41 list const * m_curr; 42 public: m_curr(c)43 iterator(list const * c = 0):m_curr(c) {} 44 T const & operator*() const { return m_curr->head(); } 45 iterator & operator++() { m_curr = m_curr->tail(); return *this; } 46 iterator operator++(int) { iterator tmp = *this; ++*this; return tmp; } 47 bool operator==(iterator const & it) { return m_curr == it.m_curr; } 48 bool operator!=(iterator const & it) { return m_curr != it.m_curr; } 49 }; 50 51 typedef iterator const_iterator; begin()52 iterator begin() const { return iterator(this); } end()53 iterator end() const { return iterator(0); } 54 }; 55 56 /** 57 \brief Return the list length. 58 */ 59 template<typename T> length(list<T> * l)60unsigned length(list<T> * l) { 61 unsigned r = 0; 62 while(l) { 63 l = l->tail(); 64 r++; 65 } 66 return r; 67 } 68 69 /** 70 \brief Non destructive append operation. The new nodes are allocated 71 using the given region allocator. 72 */ 73 template<typename T> append(region & r,list<T> * l1,list<T> * l2)74list<T> * append(region & r, list<T> * l1, list<T> * l2) { 75 if (l2 == nullptr) { 76 return l1; 77 } 78 ptr_buffer<list<T> > buffer; 79 while (l1) { 80 buffer.push_back(l1); 81 l1 = l1->tail(); 82 } 83 list<T> * result = l2; 84 typename ptr_buffer<list<T> >::const_iterator it = buffer.end(); 85 typename ptr_buffer<list<T> >::const_iterator begin = buffer.begin(); 86 while (it != begin) { 87 --it; 88 list<T> * curr = *it; 89 result = new (r) list<T>(curr->head(), result); 90 } 91 return result; 92 } 93 94 95