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> {
28 typedef bidirectional_iterator<ValueT, ptrdiff_t> super;
29 typedef alist_node<T, LargestT> NodeTy;
32 /// NodeIter - The underlying iplist iterator that is being wrapped.
36 typedef size_t size_type;
37 typedef typename super::pointer pointer;
38 typedef typename super::reference reference;
40 alist_iterator(NodeIterT NI) : NodeIter(NI) {}
41 alist_iterator(pointer EP) : NodeIter(NodeTy::getNode(EP)) {}
42 alist_iterator() : NodeIter() {}
44 // This is templated so that we can allow constructing a const iterator from
45 // a nonconst iterator...
46 template<class V, class W, class X, class Y>
47 alist_iterator(const alist_iterator<V, W, X, Y> &RHS)
48 : NodeIter(RHS.getNodeIterUnchecked()) {}
50 // This is templated so that we can allow assigning to a const iterator from
51 // a nonconst iterator...
52 template<class V, class W, class X, class Y>
53 const alist_iterator &operator=(const alist_iterator<V, W, X, Y> &RHS) {
54 NodeIter = RHS.getNodeIterUnchecked();
58 operator pointer() const { return NodeIter->getElement((T*)0); }
60 reference operator*() const { return *NodeIter->getElement((T*)0); }
61 pointer operator->() const { return &operator*(); }
63 bool operator==(const alist_iterator &RHS) const {
64 return NodeIter == RHS.NodeIter;
66 bool operator!=(const alist_iterator &RHS) const {
67 return NodeIter != RHS.NodeIter;
70 alist_iterator &operator--() {
74 alist_iterator &operator++() {
78 alist_iterator operator--(int) {
79 alist_iterator tmp = *this;
83 alist_iterator operator++(int) {
84 alist_iterator tmp = *this;
89 NodeIterT getNodeIterUnchecked() const { return NodeIter; }
92 // do not implement. this is to catch errors when people try to use
93 // them as random access iterators
94 template<class T, class LargestT, class ValueT, class NodeIterT>
95 void operator-(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
96 template<class T, class LargestT, class ValueT, class NodeIterT>
97 void operator-(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
99 template<class T, class LargestT, class ValueT, class NodeIterT>
100 void operator+(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
101 template<class T, class LargestT, class ValueT, class NodeIterT>
102 void operator+(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
104 // operator!=/operator== - Allow mixed comparisons without dereferencing
105 // the iterator, which could very likely be pointing to end().
106 template<class T, class V, class W, class X, class Y>
107 bool operator!=(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
108 return LHS != RHS.getNodeIterUnchecked().getNodePtrUnchecked()
111 template<class T, class V, class W, class X, class Y>
112 bool operator==(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
113 return LHS == RHS.getNodeIterUnchecked().getNodePtrUnchecked()
117 // Allow alist_iterators to convert into pointers to a node automatically when
118 // used by the dyn_cast, cast, isa mechanisms...
120 template<class From> struct simplify_type;
122 template<class V, class W, class X, class Y>
123 struct simplify_type<alist_iterator<V, W, X, Y> > {
124 typedef alist_node<V, W> NodeTy;
125 typedef NodeTy* SimpleType;
128 getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
132 template<class V, class W, class X, class Y>
133 struct simplify_type<const alist_iterator<V, W, X, Y> > {
134 typedef alist_node<V, W> NodeTy;
135 typedef NodeTy* SimpleType;
138 getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
143 /// Template traits for alist. By specializing this template class, you
144 /// can register custom actions to be run when a node is added to or removed
145 /// from an alist. A common use of this is to update parent pointers.
147 template<class T, class LargestT = T>
150 typedef alist_iterator<T, LargestT> iterator;
152 void addNodeToList(T *) {}
153 void removeNodeFromList(T *) {}
154 void transferNodesFromList(alist_traits &, iterator, iterator) {}
155 void deleteNode(T *E) { delete alist_node<T, LargestT>::getNode(E); }
158 /// alist - This class is an ilist-style container that automatically
159 /// adds the next/prev pointers. It is designed to work in cooperation
160 /// with <llvm/Support/Recycler.h>.
162 template<class T, class LargestT = T>
165 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;