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
17 #include "llvm/ADT/alist_node.h"
18 #include "llvm/ADT/STLExtras.h"
22 /// alist_iterator - An iterator class for alist.
24 template<class T, class LargestT = T, class ValueT = T,
25 class NodeIterT = ilist_iterator<alist_node<T, LargestT> > >
26 class alist_iterator : public bidirectional_iterator<ValueT, ptrdiff_t> {
27 typedef bidirectional_iterator<ValueT, ptrdiff_t> super;
28 typedef alist_node<T, LargestT> NodeTy;
30 /// NodeIter - The underlying iplist iterator that is being wrapped.
34 typedef size_t size_type;
35 typedef typename super::pointer pointer;
36 typedef typename super::reference reference;
38 alist_iterator(NodeIterT NI) : NodeIter(NI) {}
39 alist_iterator(pointer EP) : NodeIter(NodeTy::getNode(EP)) {}
40 alist_iterator() : NodeIter() {}
42 // This is templated so that we can allow constructing a const iterator from
43 // a nonconst iterator...
44 template<class V, class W, class X, class Y>
45 alist_iterator(const alist_iterator<V, W, X, Y> &RHS)
46 : NodeIter(RHS.getNodeIterUnchecked()) {}
48 // This is templated so that we can allow assigning to a const iterator from
49 // a nonconst iterator...
50 template<class V, class W, class X, class Y>
51 const alist_iterator &operator=(const alist_iterator<V, W, X, Y> &RHS) {
52 NodeIter = RHS.getNodeIterUnchecked();
56 operator pointer() const { return NodeIter->getElement((T*)0); }
58 reference operator*() const { return *NodeIter->getElement((T*)0); }
59 pointer operator->() const { return &operator*(); }
61 bool operator==(const alist_iterator &RHS) const {
62 return NodeIter == RHS.NodeIter;
64 bool operator!=(const alist_iterator &RHS) const {
65 return NodeIter != RHS.NodeIter;
68 alist_iterator &operator--() {
72 alist_iterator &operator++() {
76 alist_iterator operator--(int) {
77 alist_iterator tmp = *this;
81 alist_iterator operator++(int) {
82 alist_iterator tmp = *this;
87 NodeIterT getNodeIterUnchecked() const { return NodeIter; }
90 // do not implement. this is to catch errors when people try to use
91 // them as random access iterators
92 template<class T, class LargestT, class ValueT, class NodeIterT>
93 void operator-(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
94 template<class T, class LargestT, class ValueT, class NodeIterT>
95 void operator-(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
97 template<class T, class LargestT, class ValueT, class NodeIterT>
98 void operator+(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
99 template<class T, class LargestT, class ValueT, class NodeIterT>
100 void operator+(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
102 // operator!=/operator== - Allow mixed comparisons without dereferencing
103 // the iterator, which could very likely be pointing to end().
104 template<class T, class V, class W, class X, class Y>
105 bool operator!=(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
106 return LHS != RHS.getNodeIterUnchecked().getNodePtrUnchecked()
109 template<class T, class V, class W, class X, class Y>
110 bool operator==(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
111 return LHS == RHS.getNodeIterUnchecked().getNodePtrUnchecked()
115 // Allow alist_iterators to convert into pointers to a node automatically when
116 // used by the dyn_cast, cast, isa mechanisms...
118 template<class From> struct simplify_type;
120 template<class V, class W, class X, class Y>
121 struct simplify_type<alist_iterator<V, W, X, Y> > {
122 typedef alist_node<V, W> NodeTy;
123 typedef NodeTy* SimpleType;
126 getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
130 template<class V, class W, class X, class Y>
131 struct simplify_type<const alist_iterator<V, W, X, Y> > {
132 typedef alist_node<V, W> NodeTy;
133 typedef NodeTy* SimpleType;
136 getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
141 /// Template traits for alist. By specializing this template class, you
142 /// can register custom actions to be run when a node is added to or removed
143 /// from an alist. A common use of this is to update parent pointers.
145 template<class T, class LargestT = T>
147 typedef alist_iterator<T, LargestT> iterator;
150 void addNodeToList(T *) {}
151 void removeNodeFromList(T *) {}
152 void transferNodesFromList(alist_traits &, iterator, iterator) {}
153 void deleteNode(T *E) { delete alist_node<T, LargestT>::getNode(E); }
156 /// alist - This class is an ilist-style container that automatically
157 /// adds the next/prev pointers. It is designed to work in cooperation
158 /// with <llvm/Support/Recycler.h>.
160 template<class T, class LargestT = T>
162 typedef alist_node<T, LargestT> NodeTy;
165 typedef typename ilist<NodeTy>::size_type size_type;
168 /// NodeListTraits - ilist traits for NodeList.
170 struct NodeListTraits : ilist_traits<alist_node<T, LargestT> > {
171 alist_traits<T, LargestT> UserTraits;
173 void addNodeToList(NodeTy *N) {
174 UserTraits.addNodeToList(N->getElement((T*)0));
176 void removeNodeFromList(NodeTy *N) {
177 UserTraits.removeNodeFromList(N->getElement((T*)0));
179 void transferNodesFromList(iplist<NodeTy, NodeListTraits> &L2,
180 ilist_iterator<NodeTy> first,
181 ilist_iterator<NodeTy> last) {
182 UserTraits.transferNodesFromList(L2.UserTraits,
188 /// NodeList - Doubly-linked list of nodes that have constructed
189 /// contents and may be in active use.
191 iplist<NodeTy, NodeListTraits> NodeList;
194 ~alist() { clear(); }
196 typedef alist_iterator<T, LargestT, T, ilist_iterator<NodeTy> >
198 typedef alist_iterator<T, LargestT, const T, ilist_iterator<const NodeTy> >
200 typedef std::reverse_iterator<iterator> reverse_iterator;
201 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
203 iterator begin() { return iterator(NodeList.begin()); }
204 iterator end() { return iterator(NodeList.end()); }
205 const_iterator begin() const { return const_iterator(NodeList.begin()); }
206 const_iterator end() const { return const_iterator(NodeList.end()); }
207 reverse_iterator rbegin() { return reverse_iterator(NodeList.rbegin()); }
208 reverse_iterator rend() { return reverse_iterator(NodeList.rend()); }
209 const_reverse_iterator rbegin() const {
210 return const_reverse_iterator(NodeList.rbegin());
212 const_reverse_iterator rend() const {
213 return const_reverse_iterator(NodeList.rend());
216 typedef T& reference;
217 typedef const T& const_reference;
218 reference front() { return *NodeList.front().getElement((T*)0); }
219 reference back() { return *NodeList.back().getElement((T*)0); }
220 const_reference front() const { return *NodeList.front().getElement((T*)0); }
221 const_reference back() const { return *NodeList.back().getElement((T*)0); }
223 bool empty() const { return NodeList.empty(); }
224 size_type size() const { return NodeList.size(); }
226 void push_front(T *E) {
227 NodeTy *N = alist_node<T, LargestT>::getNode(E);
228 assert(N->getPrev() == 0);
229 assert(N->getNext() == 0);
230 NodeList.push_front(N);
232 void push_back(T *E) {
233 NodeTy *N = alist_node<T, LargestT>::getNode(E);
234 assert(N->getPrev() == 0);
235 assert(N->getNext() == 0);
236 NodeList.push_back(N);
238 iterator insert(iterator I, T *E) {
239 NodeTy *N = alist_node<T, LargestT>::getNode(E);
240 assert(N->getPrev() == 0);
241 assert(N->getNext() == 0);
242 return iterator(NodeList.insert(I.getNodeIterUnchecked(), N));
244 void splice(iterator where, alist &Other) {
245 NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList);
247 void splice(iterator where, alist &Other, iterator From) {
248 NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
249 From.getNodeIterUnchecked());
251 void splice(iterator where, alist &Other, iterator From,
253 NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
254 From.getNodeIterUnchecked(), To.getNodeIterUnchecked());
258 erase(NodeList.begin());
261 erase(prior(NodeList.end()));
263 iterator erase(iterator I) {
264 iterator Next = next(I);
265 NodeTy *N = NodeList.remove(I.getNodeIterUnchecked());
266 NodeList.UserTraits.deleteNode(N->getElement((T*)0));
269 iterator erase(iterator first, iterator last) {
270 while (first != last)
271 first = erase(first);
276 NodeTy *N = alist_node<T, LargestT>::getNode(E);
277 return NodeList.remove(N)->getElement((T*)0);
281 while (!empty()) pop_front();
284 alist_traits<T, LargestT> &getTraits() {
285 return NodeList.UserTraits;