1 //==- llvm/ADT/alist.h - Linked lists with hooks -----------------*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the alist class template, and related infrastructure.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_ALIST_H
15 #define LLVM_ADT_ALIST_H
18 #include "llvm/ADT/alist_node.h"
19 #include "llvm/ADT/STLExtras.h"
23 /// alist_iterator - An iterator class for alist.
25 template<class T, class LargestT = T, class ValueT = T,
26 class NodeIterT = ilist_iterator<alist_node<T, LargestT> > >
27 class alist_iterator : public bidirectional_iterator<ValueT, ptrdiff_t> {
28 typedef bidirectional_iterator<ValueT, ptrdiff_t> super;
29 typedef alist_node<T, LargestT> NodeTy;
31 /// NodeIter - The underlying iplist iterator that is being wrapped.
35 typedef size_t size_type;
36 typedef typename super::pointer pointer;
37 typedef typename super::reference reference;
39 alist_iterator(NodeIterT NI) : NodeIter(NI) {}
40 alist_iterator(pointer EP) : NodeIter(NodeTy::getNode(EP)) {}
41 alist_iterator() : NodeIter() {}
43 // This is templated so that we can allow constructing a const iterator from
44 // a nonconst iterator...
45 template<class V, class W, class X, class Y>
46 alist_iterator(const alist_iterator<V, W, X, Y> &RHS)
47 : NodeIter(RHS.getNodeIterUnchecked()) {}
49 // This is templated so that we can allow assigning to a const iterator from
50 // a nonconst iterator...
51 template<class V, class W, class X, class Y>
52 const alist_iterator &operator=(const alist_iterator<V, W, X, Y> &RHS) {
53 NodeIter = RHS.getNodeIterUnchecked();
57 operator pointer() const { return NodeIter->getElement((T*)0); }
59 reference operator*() const { return *NodeIter->getElement((T*)0); }
60 pointer operator->() const { return &operator*(); }
62 bool operator==(const alist_iterator &RHS) const {
63 return NodeIter == RHS.NodeIter;
65 bool operator!=(const alist_iterator &RHS) const {
66 return NodeIter != RHS.NodeIter;
69 alist_iterator &operator--() {
73 alist_iterator &operator++() {
77 alist_iterator operator--(int) {
78 alist_iterator tmp = *this;
82 alist_iterator operator++(int) {
83 alist_iterator tmp = *this;
88 NodeIterT getNodeIterUnchecked() const { return NodeIter; }
91 // do not implement. this is to catch errors when people try to use
92 // them as random access iterators
93 template<class T, class LargestT, class ValueT, class NodeIterT>
94 void operator-(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
95 template<class T, class LargestT, class ValueT, class NodeIterT>
96 void operator-(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
98 template<class T, class LargestT, class ValueT, class NodeIterT>
99 void operator+(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
100 template<class T, class LargestT, class ValueT, class NodeIterT>
101 void operator+(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
103 // operator!=/operator== - Allow mixed comparisons without dereferencing
104 // the iterator, which could very likely be pointing to end().
105 template<class T, class V, class W, class X, class Y>
106 bool operator!=(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
107 return LHS != RHS.getNodeIterUnchecked().getNodePtrUnchecked()
110 template<class T, class V, class W, class X, class Y>
111 bool operator==(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
112 return LHS == RHS.getNodeIterUnchecked().getNodePtrUnchecked()
116 // Allow alist_iterators to convert into pointers to a node automatically when
117 // used by the dyn_cast, cast, isa mechanisms...
119 template<class From> struct simplify_type;
121 template<class V, class W, class X, class Y>
122 struct simplify_type<alist_iterator<V, W, X, Y> > {
123 typedef alist_node<V, W> NodeTy;
124 typedef NodeTy* SimpleType;
127 getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
131 template<class V, class W, class X, class Y>
132 struct simplify_type<const alist_iterator<V, W, X, Y> > {
133 typedef alist_node<V, W> NodeTy;
134 typedef NodeTy* SimpleType;
137 getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
142 /// Template traits for alist. By specializing this template class, you
143 /// can register custom actions to be run when a node is added to or removed
144 /// from an alist. A common use of this is to update parent pointers.
146 template<class T, class LargestT = T>
148 typedef alist_iterator<T, LargestT> iterator;
151 void addNodeToList(T *) {}
152 void removeNodeFromList(T *) {}
153 void transferNodesFromList(alist_traits &, iterator, iterator) {}
154 void deleteNode(T *E) { delete alist_node<T, LargestT>::getNode(E); }
157 /// alist - This class is an ilist-style container that automatically
158 /// adds the next/prev pointers. It is designed to work in cooperation
159 /// with <llvm/Support/Recycler.h>.
161 template<class T, class LargestT = T>
163 typedef alist_node<T, LargestT> NodeTy;
166 typedef typename ilist<NodeTy>::size_type size_type;
169 /// NodeListTraits - ilist traits for NodeList.
171 struct NodeListTraits : ilist_traits<alist_node<T, LargestT> > {
172 alist_traits<T, LargestT> UserTraits;
174 void addNodeToList(NodeTy *N) {
175 UserTraits.addNodeToList(N->getElement((T*)0));
177 void removeNodeFromList(NodeTy *N) {
178 UserTraits.removeNodeFromList(N->getElement((T*)0));
180 void transferNodesFromList(iplist<NodeTy, NodeListTraits> &L2,
181 ilist_iterator<NodeTy> first,
182 ilist_iterator<NodeTy> last) {
183 UserTraits.transferNodesFromList(L2.UserTraits,
189 /// NodeList - Doubly-linked list of nodes that have constructed
190 /// contents and may be in active use.
192 iplist<NodeTy, NodeListTraits> NodeList;
195 ~alist() { clear(); }
197 typedef alist_iterator<T, LargestT, T, ilist_iterator<NodeTy> >
199 typedef alist_iterator<T, LargestT, const T, ilist_iterator<const NodeTy> >
201 typedef std::reverse_iterator<iterator> reverse_iterator;
202 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
204 iterator begin() { return iterator(NodeList.begin()); }
205 iterator end() { return iterator(NodeList.end()); }
206 const_iterator begin() const { return const_iterator(NodeList.begin()); }
207 const_iterator end() const { return const_iterator(NodeList.end()); }
208 reverse_iterator rbegin() { return reverse_iterator(NodeList.rbegin()); }
209 reverse_iterator rend() { return reverse_iterator(NodeList.rend()); }
210 const_reverse_iterator rbegin() const {
211 return const_reverse_iterator(NodeList.rbegin());
213 const_reverse_iterator rend() const {
214 return const_reverse_iterator(NodeList.rend());
217 typedef T& reference;
218 typedef const T& const_reference;
219 reference front() { return *NodeList.front().getElement((T*)0); }
220 reference back() { return *NodeList.back().getElement((T*)0); }
221 const_reference front() const { return *NodeList.front().getElement((T*)0); }
222 const_reference back() const { return *NodeList.back().getElement((T*)0); }
224 bool empty() const { return NodeList.empty(); }
225 size_type size() const { return NodeList.size(); }
227 void push_front(T *E) {
228 NodeTy *N = alist_node<T, LargestT>::getNode(E);
229 assert(N->getPrev() == 0);
230 assert(N->getNext() == 0);
231 NodeList.push_front(N);
233 void push_back(T *E) {
234 NodeTy *N = alist_node<T, LargestT>::getNode(E);
235 assert(N->getPrev() == 0);
236 assert(N->getNext() == 0);
237 NodeList.push_back(N);
239 iterator insert(iterator I, T *E) {
240 NodeTy *N = alist_node<T, LargestT>::getNode(E);
241 assert(N->getPrev() == 0);
242 assert(N->getNext() == 0);
243 return iterator(NodeList.insert(I.getNodeIterUnchecked(), N));
245 void splice(iterator where, alist &Other) {
246 NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList);
248 void splice(iterator where, alist &Other, iterator From) {
249 NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
250 From.getNodeIterUnchecked());
252 void splice(iterator where, alist &Other, iterator From,
254 NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
255 From.getNodeIterUnchecked(), To.getNodeIterUnchecked());
259 erase(NodeList.begin());
262 erase(prior(NodeList.end()));
264 iterator erase(iterator I) {
265 iterator Next = next(I);
266 NodeTy *N = NodeList.remove(I.getNodeIterUnchecked());
267 NodeList.UserTraits.deleteNode(N->getElement((T*)0));
270 iterator erase(iterator first, iterator last) {
271 while (first != last)
272 first = erase(first);
277 NodeTy *N = alist_node<T, LargestT>::getNode(E);
278 return NodeList.remove(N)->getElement((T*)0);
282 while (!empty()) pop_front();
285 alist_traits<T, LargestT> &getTraits() {
286 return NodeList.UserTraits;