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)60 unsigned 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)74 list<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