include/llvm/ADT/alist_node.h

   1 //==- llvm/ADT/alist_node.h - Next/Prev helper class for alist ---*- 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_node class template, which is used by the alist
  11 // class template to provide next/prev pointers for arbitrary objects.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ADT_ALIST_NODE_H
  16 #define LLVM_ADT_ALIST_NODE_H
  17
  18 #include "llvm/ADT/ilist.h"
  19 #include "llvm/Support/AlignOf.h"
  20 #include "llvm/Support/DataTypes.h"
  21 #include <cassert>
  22
  23 namespace llvm {
  24
  25 /// alist_node - This is a utility class used by alist. It holds prev and next
  26 /// pointers for use with ilists, as well as storage for objects as large as
  27 /// LargestT, that are in T's inheritance tree.
  28 ///
  29 template<class T, class LargestT = T>
  30 class alist_node {
  31   alist_node *Prev, *Next;
  32
  33 public:
  34   alist_node() : Prev(0), Next(0) {}
  35
  36   alist_node *getPrev() const { return Prev; }
  37   alist_node *getNext() const { return Next; }
  38   void setPrev(alist_node *N) { Prev = N; }
  39   void setNext(alist_node *N) { Next = N; }
  40
  41   union {
  42     char Bytes[sizeof(LargestT)];
  43     long long L;
  44     void *P;
  45   } Storage;
  46
  47   template<class SubClass>
  48   SubClass *getElement(SubClass *) {
  49     assert(sizeof(SubClass) <= sizeof(LargestT));
  50     assert(unsigned(AlignOf<SubClass>::Alignment) <=
  51            unsigned(AlignOf<LargestT>::Alignment));
  52     return reinterpret_cast<SubClass*>(&Storage.Bytes);
  53   }
  54
  55   template<class SubClass>
  56   const SubClass *getElement(SubClass *) const {
  57     assert(sizeof(SubClass) <= sizeof(LargestT));
  58     assert(unsigned(AlignOf<SubClass>::Alignment) <=
  59            unsigned(AlignOf<LargestT>::Alignment));
  60     return reinterpret_cast<const SubClass*>(&Storage.Bytes);
  61   }
  62
  63   // This code essentially does offsetof, but actual offsetof hits an ICE in
  64   // GCC 4.0 relating to offsetof being used inside a template.
  65   static alist_node* getNode(T *D) {
  66     return reinterpret_cast<alist_node*>(reinterpret_cast<char*>(D) -
  67                                                 (uintptr_t)&getNull()->Storage);
  68   }
  69   static const alist_node* getNode(const T *D) {
  70     return reinterpret_cast<alist_node*>(reinterpret_cast<char*>(D) -
  71                                                 (uintptr_t)&getNull()->Storage);
  72   }
  73 private:
  74   static alist_node* getNull() { return 0; }
  75 };
  76
  77 // A specialization of ilist_traits for alist_nodes.
  78 template<class T, class LargestT>
  79 class ilist_traits<alist_node<T, LargestT> > {
  80 public:
  81   typedef alist_node<T, LargestT> NodeTy;
  82
  83 protected:
  84   // Allocate a sentinel inside the traits class. This works
  85   // because iplist carries an instance of the traits class.
  86   NodeTy Sentinel;
  87
  88 public:
  89   static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); }
  90   static NodeTy *getNext(NodeTy *N) { return N->getNext(); }
  91   static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); }
  92   static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); }
  93
  94   static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); }
  95   static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); }
  96
  97   NodeTy *createSentinel() const {
  98     assert(Sentinel.getPrev() == 0);
  99     assert(Sentinel.getNext() == 0);
 100     return const_cast<NodeTy*>(&Sentinel);
 101   }
 102
 103   void destroySentinel(NodeTy *N) {
 104     assert(N == &Sentinel); N = N;
 105     Sentinel.setPrev(0);
 106     Sentinel.setNext(0);
 107   }
 108
 109   void addNodeToList(NodeTy *) {}
 110   void removeNodeFromList(NodeTy *) {}
 111   void transferNodesFromList(iplist<NodeTy, ilist_traits> &,
 112                              ilist_iterator<NodeTy> /*first*/,
 113                              ilist_iterator<NodeTy> /*last*/) {}
 114
 115   // Ideally we wouldn't implement this, but ilist's clear calls it,
 116   // which is called from ilist's destructor. We won't ever call
 117   // either of those with a non-empty list, but statically this
 118   // method needs to exist.
 119   void deleteNode(NodeTy *) { assert(0); }
 120
 121 private:
 122   static NodeTy *createNode(const NodeTy &V); // do not implement
 123 };
 124
 125 }
 126
 127 #endif