include/llvm/ADT/alist.h

   1 //==- llvm/ADT/alist.h - Linked lists with hooks -----------------*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the alist class template, and related infrastructure.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_ALIST_H
  15 #define LLVM_ADT_ALIST_H
  16
  17 #include "llvm/ADT/alist_node.h"
  18 #include "llvm/ADT/STLExtras.h"
  19
  20 namespace llvm {
  21
  22 /// alist_iterator - An iterator class for alist.
  23 ///
  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 public:
  28   typedef bidirectional_iterator<ValueT, ptrdiff_t> super;
  29   typedef alist_node<T, LargestT> NodeTy;
  30
  31 private:
  32   /// NodeIter - The underlying iplist iterator that is being wrapped.
  33   NodeIterT NodeIter;
  34
  35 public:
  36   typedef size_t size_type;
  37
  38   // FIX for MSVC++.  This should be reviewed more.
  39   // typedef typename super::pointer pointer;
  40   typedef ValueT* pointer;
  41
  42   typedef typename super::reference reference;
  43
  44   alist_iterator(NodeIterT NI) : NodeIter(NI) {}
  45   alist_iterator(pointer EP) : NodeIter(NodeTy::getNode(EP)) {}
  46   alist_iterator() : NodeIter() {}
  47
  48   // This is templated so that we can allow constructing a const iterator from
  49   // a nonconst iterator...
  50   template<class V, class W, class X, class Y>
  51   alist_iterator(const alist_iterator<V, W, X, Y> &RHS)
  52     : NodeIter(RHS.getNodeIterUnchecked()) {}
  53
  54   // This is templated so that we can allow assigning to a const iterator from
  55   // a nonconst iterator...
  56   template<class V, class W, class X, class Y>
  57   const alist_iterator &operator=(const alist_iterator<V, W, X, Y> &RHS) {
  58     NodeIter = RHS.getNodeIterUnchecked();
  59     return *this;
  60   }
  61
  62   operator pointer() const { return NodeIter->getElement((T*)0); }
  63
  64   reference operator*() const { return *NodeIter->getElement((T*)0); }
  65   pointer   operator->() const { return &operator*(); }
  66
  67   bool operator==(const alist_iterator &RHS) const {
  68     return NodeIter == RHS.NodeIter;
  69   }
  70   bool operator!=(const alist_iterator &RHS) const {
  71     return NodeIter != RHS.NodeIter;
  72   }
  73
  74   alist_iterator &operator--() {
  75     --NodeIter;
  76     return *this;
  77   }
  78   alist_iterator &operator++() {
  79     ++NodeIter;
  80     return *this;
  81   }
  82   alist_iterator operator--(int) {
  83     alist_iterator tmp = *this;
  84     --*this;
  85     return tmp;
  86   }
  87   alist_iterator operator++(int) {
  88     alist_iterator tmp = *this;
  89     ++*this;
  90     return tmp;
  91   }
  92
  93   NodeIterT getNodeIterUnchecked() const { return NodeIter; }
  94 };
  95
  96 // do not implement. this is to catch errors when people try to use
  97 // them as random access iterators
  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);
 102
 103 template<class T, class LargestT, class ValueT, class NodeIterT>
 104 void operator+(int, alist_iterator<T, LargestT, ValueT, NodeIterT>);
 105 template<class T, class LargestT, class ValueT, class NodeIterT>
 106 void operator+(alist_iterator<T, LargestT, ValueT, NodeIterT>,int);
 107
 108 // operator!=/operator== - Allow mixed comparisons without dereferencing
 109 // the iterator, which could very likely be pointing to end().
 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()
 113                                                             ->getElement((T*)0);
 114 }
 115 template<class T, class V, class W, class X, class Y>
 116 bool operator==(T* LHS, const alist_iterator<V, W, X, Y> &RHS) {
 117   return LHS == RHS.getNodeIterUnchecked().getNodePtrUnchecked()
 118                                                             ->getElement((T*)0);
 119 }
 120
 121 // Allow alist_iterators to convert into pointers to a node automatically when
 122 // used by the dyn_cast, cast, isa mechanisms...
 123
 124 template<class From> struct simplify_type;
 125
 126 template<class V, class W, class X, class Y>
 127 struct simplify_type<alist_iterator<V, W, X, Y> > {
 128   typedef alist_node<V, W> NodeTy;
 129   typedef NodeTy* SimpleType;
 130
 131   static SimpleType
 132   getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
 133     return &*Node;
 134   }
 135 };
 136 template<class V, class W, class X, class Y>
 137 struct simplify_type<const alist_iterator<V, W, X, Y> > {
 138   typedef alist_node<V, W> NodeTy;
 139   typedef NodeTy* SimpleType;
 140
 141   static SimpleType
 142   getSimplifiedValue(const alist_iterator<V, W, X, Y> &Node) {
 143     return &*Node;
 144   }
 145 };
 146
 147 /// Template traits for alist.  By specializing this template class, you
 148 /// can register custom actions to be run when a node is added to or removed
 149 /// from an alist. A common use of this is to update parent pointers.
 150 ///
 151 template<class T, class LargestT = T>
 152 class alist_traits {
 153 public:
 154   typedef alist_iterator<T, LargestT> iterator;
 155
 156   void addNodeToList(T *) {}
 157   void removeNodeFromList(T *) {}
 158   void transferNodesFromList(alist_traits &, iterator, iterator) {}
 159   void deleteNode(T *E) { delete alist_node<T, LargestT>::getNode(E); }
 160 };
 161
 162 /// alist - This class is an ilist-style container that automatically
 163 /// adds the next/prev pointers. It is designed to work in cooperation
 164 /// with <llvm/Support/Recycler.h>.
 165 ///
 166 template<class T, class LargestT = T>
 167 class alist {
 168 public:
 169   typedef alist_node<T, LargestT> NodeTy;
 170   typedef typename ilist<NodeTy>::size_type size_type;
 171
 172 private:
 173   /// NodeListTraits - ilist traits for NodeList.
 174   ///
 175   struct NodeListTraits : ilist_traits<alist_node<T, LargestT> > {
 176     alist_traits<T, LargestT> UserTraits;
 177
 178     void addNodeToList(NodeTy *N) {
 179       UserTraits.addNodeToList(N->getElement((T*)0));
 180     }
 181     void removeNodeFromList(NodeTy *N) {
 182       UserTraits.removeNodeFromList(N->getElement((T*)0));
 183     }
 184     void transferNodesFromList(iplist<NodeTy, NodeListTraits> &L2,
 185                                ilist_iterator<NodeTy> first,
 186                                ilist_iterator<NodeTy> last) {
 187       UserTraits.transferNodesFromList(L2.UserTraits,
 188                                        iterator(first),
 189                                        iterator(last));
 190     }
 191   };
 192
 193   /// NodeList - Doubly-linked list of nodes that have constructed
 194   /// contents and may be in active use.
 195   ///
 196   iplist<NodeTy, NodeListTraits> NodeList;
 197
 198 public:
 199   ~alist() { clear(); }
 200
 201   typedef alist_iterator<T, LargestT, T, ilist_iterator<NodeTy> >
 202     iterator;
 203   typedef alist_iterator<T, LargestT, const T, ilist_iterator<const NodeTy> >
 204     const_iterator;
 205   typedef std::reverse_iterator<iterator> reverse_iterator;
 206   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 207
 208   iterator begin() { return iterator(NodeList.begin()); }
 209   iterator end() { return iterator(NodeList.end()); }
 210   const_iterator begin() const { return const_iterator(NodeList.begin()); }
 211   const_iterator end() const { return const_iterator(NodeList.end()); }
 212   reverse_iterator rbegin() { return reverse_iterator(NodeList.rbegin()); }
 213   reverse_iterator rend() { return reverse_iterator(NodeList.rend()); }
 214   const_reverse_iterator rbegin() const {
 215     return const_reverse_iterator(NodeList.rbegin());
 216   }
 217   const_reverse_iterator rend() const {
 218     return const_reverse_iterator(NodeList.rend());
 219   }
 220
 221   typedef T& reference;
 222   typedef const T& const_reference;
 223   reference front() { return *NodeList.front().getElement((T*)0); }
 224   reference back()  { return *NodeList.back().getElement((T*)0); }
 225   const_reference front() const { return *NodeList.front().getElement((T*)0); }
 226   const_reference back()  const { return *NodeList.back().getElement((T*)0); }
 227
 228   bool empty() const { return NodeList.empty(); }
 229   size_type size() const { return NodeList.size(); }
 230
 231   void push_front(T *E) {
 232     NodeTy *N = alist_node<T, LargestT>::getNode(E);
 233     assert(N->getPrev() == 0);
 234     assert(N->getNext() == 0);
 235     NodeList.push_front(N);
 236   }
 237   void push_back(T *E) {
 238     NodeTy *N = alist_node<T, LargestT>::getNode(E);
 239     assert(N->getPrev() == 0);
 240     assert(N->getNext() == 0);
 241     NodeList.push_back(N);
 242   }
 243   iterator insert(iterator I, T *E) {
 244     NodeTy *N = alist_node<T, LargestT>::getNode(E);
 245     assert(N->getPrev() == 0);
 246     assert(N->getNext() == 0);
 247     return iterator(NodeList.insert(I.getNodeIterUnchecked(), N));
 248   }
 249   void splice(iterator where, alist &Other) {
 250     NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList);
 251   }
 252   void splice(iterator where, alist &Other, iterator From) {
 253     NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
 254                     From.getNodeIterUnchecked());
 255   }
 256   void splice(iterator where, alist &Other, iterator From,
 257               iterator To) {
 258     NodeList.splice(where.getNodeIterUnchecked(), Other.NodeList,
 259                     From.getNodeIterUnchecked(), To.getNodeIterUnchecked());
 260   }
 261
 262   void pop_front() {
 263     erase(NodeList.begin());
 264   }
 265   void pop_back() {
 266     erase(prior(NodeList.end()));
 267   }
 268   iterator erase(iterator I) {
 269     iterator Next = next(I);
 270     NodeTy *N = NodeList.remove(I.getNodeIterUnchecked());
 271     NodeList.UserTraits.deleteNode(N->getElement((T*)0));
 272     return Next;
 273   }
 274   iterator erase(iterator first, iterator last) {
 275     while (first != last)
 276       first = erase(first);
 277     return last;
 278   }
 279
 280   T *remove(T *E) {
 281     NodeTy *N = alist_node<T, LargestT>::getNode(E);
 282     return NodeList.remove(N)->getElement((T*)0);
 283   }
 284
 285   void clear() {
 286     while (!empty()) pop_front();
 287   }
 288
 289   alist_traits<T, LargestT> &getTraits() {
 290     return NodeList.UserTraits;
 291   }
 292 };
 293
 294 }
 295
 296 #endif