Hex Artifact Content
Not logged in

Artifact 914a87586055c0fe19130ffd53ddb23f9e98dbd2:

Unrecognized artifact
0000: 2f 2f 3d 3d 2d 2d 2d 20 49 6d 6d 75 74 61 62 6c  //==--- Immutabl
0010: 65 4c 69 73 74 2e 68 20 2d 20 49 6d 6d 75 74 61  eList.h - Immuta
0020: 62 6c 65 20 28 66 75 6e 63 74 69 6f 6e 61 6c 29  ble (functional)
0030: 20 6c 69 73 74 20 69 6e 74 65 72 66 61 63 65 20   list interface 
0040: 2d 2d 2a 2d 20 43 2b 2b 20 2d 2a 2d 3d 3d 2f 2f  --*- C++ -*-==//
0050: 0a 2f 2f 0a 2f 2f 20 20 20 20 20 20 20 20 20 20  .//.//          
0060: 20 20 20 20 20 20 20 20 20 20 20 54 68 65 20 4c             The L
0070: 4c 56 4d 20 43 6f 6d 70 69 6c 65 72 20 49 6e 66  LVM Compiler Inf
0080: 72 61 73 74 72 75 63 74 75 72 65 0a 2f 2f 0a 2f  rastructure.//./
0090: 2f 20 54 68 69 73 20 66 69 6c 65 20 69 73 20 64  / This file is d
00a0: 69 73 74 72 69 62 75 74 65 64 20 75 6e 64 65 72  istributed under
00b0: 20 74 68 65 20 55 6e 69 76 65 72 73 69 74 79 20   the University 
00c0: 6f 66 20 49 6c 6c 69 6e 6f 69 73 20 4f 70 65 6e  of Illinois Open
00d0: 20 53 6f 75 72 63 65 0a 2f 2f 20 4c 69 63 65 6e   Source.// Licen
00e0: 73 65 2e 20 53 65 65 20 4c 49 43 45 4e 53 45 2e  se. See LICENSE.
00f0: 54 58 54 20 66 6f 72 20 64 65 74 61 69 6c 73 2e  TXT for details.
0100: 0a 2f 2f 0a 2f 2f 3d 3d 3d 2d 2d 2d 2d 2d 2d 2d  .//.//===-------
0110: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0120: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0140: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 3d  ---------------=
0150: 3d 3d 2f 2f 0a 2f 2f 0a 2f 2f 20 54 68 69 73 20  ==//.//.// This 
0160: 66 69 6c 65 20 64 65 66 69 6e 65 73 20 74 68 65  file defines the
0170: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 20 63   ImmutableList c
0180: 6c 61 73 73 2e 0a 2f 2f 0a 2f 2f 3d 3d 3d 2d 2d  lass..//.//===--
0190: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
01a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
01b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
01c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
01d0: 2d 2d 2d 2d 3d 3d 3d 2f 2f 0a 0a 23 69 66 6e 64  ----===//..#ifnd
01e0: 65 66 20 4c 4c 56 4d 5f 41 44 54 5f 49 4d 4d 55  ef LLVM_ADT_IMMU
01f0: 54 41 42 4c 45 4c 49 53 54 5f 48 0a 23 64 65 66  TABLELIST_H.#def
0200: 69 6e 65 20 4c 4c 56 4d 5f 41 44 54 5f 49 4d 4d  ine LLVM_ADT_IMM
0210: 55 54 41 42 4c 45 4c 49 53 54 5f 48 0a 0a 23 69  UTABLELIST_H..#i
0220: 6e 63 6c 75 64 65 20 22 6c 6c 76 6d 2f 41 44 54  nclude "llvm/ADT
0230: 2f 46 6f 6c 64 69 6e 67 53 65 74 2e 68 22 0a 23  /FoldingSet.h".#
0240: 69 6e 63 6c 75 64 65 20 22 6c 6c 76 6d 2f 53 75  include "llvm/Su
0250: 70 70 6f 72 74 2f 41 6c 6c 6f 63 61 74 6f 72 2e  pport/Allocator.
0260: 68 22 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73  h".#include <cas
0270: 73 65 72 74 3e 0a 23 69 6e 63 6c 75 64 65 20 3c  sert>.#include <
0280: 63 73 74 64 69 6e 74 3e 0a 23 69 6e 63 6c 75 64  cstdint>.#includ
0290: 65 20 3c 6e 65 77 3e 0a 0a 6e 61 6d 65 73 70 61  e <new>..namespa
02a0: 63 65 20 6c 6c 76 6d 20 7b 0a 0a 74 65 6d 70 6c  ce llvm {..templ
02b0: 61 74 65 20 3c 74 79 70 65 6e 61 6d 65 20 54 3e  ate <typename T>
02c0: 20 63 6c 61 73 73 20 49 6d 6d 75 74 61 62 6c 65   class Immutable
02d0: 4c 69 73 74 46 61 63 74 6f 72 79 3b 0a 0a 74 65  ListFactory;..te
02e0: 6d 70 6c 61 74 65 20 3c 74 79 70 65 6e 61 6d 65  mplate <typename
02f0: 20 54 3e 0a 63 6c 61 73 73 20 49 6d 6d 75 74 61   T>.class Immuta
0300: 62 6c 65 4c 69 73 74 49 6d 70 6c 20 3a 20 70 75  bleListImpl : pu
0310: 62 6c 69 63 20 46 6f 6c 64 69 6e 67 53 65 74 4e  blic FoldingSetN
0320: 6f 64 65 20 7b 0a 20 20 66 72 69 65 6e 64 20 63  ode {.  friend c
0330: 6c 61 73 73 20 49 6d 6d 75 74 61 62 6c 65 4c 69  lass ImmutableLi
0340: 73 74 46 61 63 74 6f 72 79 3c 54 3e 3b 0a 0a 20  stFactory<T>;.. 
0350: 20 54 20 48 65 61 64 3b 0a 20 20 63 6f 6e 73 74   T Head;.  const
0360: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 49 6d   ImmutableListIm
0370: 70 6c 2a 20 54 61 69 6c 3b 0a 0a 20 20 49 6d 6d  pl* Tail;..  Imm
0380: 75 74 61 62 6c 65 4c 69 73 74 49 6d 70 6c 28 63  utableListImpl(c
0390: 6f 6e 73 74 20 54 26 20 68 65 61 64 2c 20 63 6f  onst T& head, co
03a0: 6e 73 74 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73  nst ImmutableLis
03b0: 74 49 6d 70 6c 2a 20 74 61 69 6c 20 3d 20 6e 75  tImpl* tail = nu
03c0: 6c 6c 70 74 72 29 0a 20 20 20 20 3a 20 48 65 61  llptr).    : Hea
03d0: 64 28 68 65 61 64 29 2c 20 54 61 69 6c 28 74 61  d(head), Tail(ta
03e0: 69 6c 29 20 7b 7d 0a 0a 70 75 62 6c 69 63 3a 0a  il) {}..public:.
03f0: 20 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 49    ImmutableListI
0400: 6d 70 6c 28 63 6f 6e 73 74 20 49 6d 6d 75 74 61  mpl(const Immuta
0410: 62 6c 65 4c 69 73 74 49 6d 70 6c 20 26 29 20 3d  bleListImpl &) =
0420: 20 64 65 6c 65 74 65 3b 0a 20 20 49 6d 6d 75 74   delete;.  Immut
0430: 61 62 6c 65 4c 69 73 74 49 6d 70 6c 20 26 6f 70  ableListImpl &op
0440: 65 72 61 74 6f 72 3d 28 63 6f 6e 73 74 20 49 6d  erator=(const Im
0450: 6d 75 74 61 62 6c 65 4c 69 73 74 49 6d 70 6c 20  mutableListImpl 
0460: 26 29 20 3d 20 64 65 6c 65 74 65 3b 0a 0a 20 20  &) = delete;..  
0470: 63 6f 6e 73 74 20 54 26 20 67 65 74 48 65 61 64  const T& getHead
0480: 28 29 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72  () const { retur
0490: 6e 20 48 65 61 64 3b 20 7d 0a 20 20 63 6f 6e 73  n Head; }.  cons
04a0: 74 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 49  t ImmutableListI
04b0: 6d 70 6c 2a 20 67 65 74 54 61 69 6c 28 29 20 63  mpl* getTail() c
04c0: 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 54 61  onst { return Ta
04d0: 69 6c 3b 20 7d 0a 0a 20 20 73 74 61 74 69 63 20  il; }..  static 
04e0: 69 6e 6c 69 6e 65 20 76 6f 69 64 20 50 72 6f 66  inline void Prof
04f0: 69 6c 65 28 46 6f 6c 64 69 6e 67 53 65 74 4e 6f  ile(FoldingSetNo
0500: 64 65 49 44 26 20 49 44 2c 20 63 6f 6e 73 74 20  deID& ID, const 
0510: 54 26 20 48 2c 0a 20 20 20 20 20 20 20 20 20 20  T& H,.          
0520: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0530: 20 20 20 63 6f 6e 73 74 20 49 6d 6d 75 74 61 62     const Immutab
0540: 6c 65 4c 69 73 74 49 6d 70 6c 2a 20 4c 29 7b 0a  leListImpl* L){.
0550: 20 20 20 20 49 44 2e 41 64 64 50 6f 69 6e 74 65      ID.AddPointe
0560: 72 28 4c 29 3b 0a 20 20 20 20 49 44 2e 41 64 64  r(L);.    ID.Add
0570: 28 48 29 3b 0a 20 20 7d 0a 0a 20 20 76 6f 69 64  (H);.  }..  void
0580: 20 50 72 6f 66 69 6c 65 28 46 6f 6c 64 69 6e 67   Profile(Folding
0590: 53 65 74 4e 6f 64 65 49 44 26 20 49 44 29 20 7b  SetNodeID& ID) {
05a0: 0a 20 20 20 20 50 72 6f 66 69 6c 65 28 49 44 2c  .    Profile(ID,
05b0: 20 48 65 61 64 2c 20 54 61 69 6c 29 3b 0a 20 20   Head, Tail);.  
05c0: 7d 0a 7d 3b 0a 0a 2f 2f 2f 20 49 6d 6d 75 74 61  }.};../// Immuta
05d0: 62 6c 65 4c 69 73 74 20 2d 20 54 68 69 73 20 63  bleList - This c
05e0: 6c 61 73 73 20 72 65 70 72 65 73 65 6e 74 73 20  lass represents 
05f0: 61 6e 20 69 6d 6d 75 74 61 62 6c 65 20 28 66 75  an immutable (fu
0600: 6e 63 74 69 6f 6e 61 6c 29 20 6c 69 73 74 2e 0a  nctional) list..
0610: 2f 2f 2f 20 20 49 74 20 69 73 20 69 6d 70 6c 65  ///  It is imple
0620: 6d 65 6e 74 65 64 20 61 73 20 61 20 73 6d 61 72  mented as a smar
0630: 74 20 70 6f 69 6e 74 65 72 20 28 77 72 61 70 73  t pointer (wraps
0640: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 49 6d   ImmutableListIm
0650: 70 6c 29 2c 20 73 6f 20 69 74 0a 2f 2f 2f 20 20  pl), so it.///  
0660: 69 74 20 69 73 20 69 6e 74 65 6e 64 65 64 20 74  it is intended t
0670: 6f 20 61 6c 77 61 79 73 20 62 65 20 63 6f 70 69  o always be copi
0680: 65 64 20 62 79 20 76 61 6c 75 65 20 61 73 20 69  ed by value as i
0690: 66 20 69 74 20 77 65 72 65 20 61 20 70 6f 69 6e  f it were a poin
06a0: 74 65 72 2e 0a 2f 2f 2f 20 20 54 68 69 73 20 69  ter..///  This i
06b0: 6e 74 65 72 66 61 63 65 20 6d 61 74 63 68 65 73  nterface matches
06c0: 20 49 6d 6d 75 74 61 62 6c 65 53 65 74 20 61 6e   ImmutableSet an
06d0: 64 20 49 6d 6d 75 74 61 62 6c 65 4d 61 70 2e 20  d ImmutableMap. 
06e0: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 0a 2f   ImmutableList./
06f0: 2f 2f 20 20 6f 62 6a 65 63 74 73 20 73 68 6f 75  //  objects shou
0700: 6c 64 20 61 6c 6d 6f 73 74 20 6e 65 76 65 72 20  ld almost never 
0710: 62 65 20 63 72 65 61 74 65 64 20 64 69 72 65 63  be created direc
0720: 74 6c 79 2c 20 61 6e 64 20 69 6e 73 74 65 61 64  tly, and instead
0730: 20 73 68 6f 75 6c 64 0a 2f 2f 2f 20 20 62 65 20   should.///  be 
0740: 63 72 65 61 74 65 64 20 62 79 20 49 6d 6d 75 74  created by Immut
0750: 61 62 6c 65 4c 69 73 74 46 61 63 74 6f 72 79 20  ableListFactory 
0760: 6f 62 6a 65 63 74 73 20 74 68 61 74 20 6d 61 6e  objects that man
0770: 61 67 65 20 74 68 65 20 6c 69 66 65 74 69 6d 65  age the lifetime
0780: 0a 2f 2f 2f 20 20 6f 66 20 61 20 67 72 6f 75 70  .///  of a group
0790: 20 6f 66 20 6c 69 73 74 73 2e 20 20 57 68 65 6e   of lists.  When
07a0: 20 74 68 65 20 66 61 63 74 6f 72 79 20 6f 62 6a   the factory obj
07b0: 65 63 74 20 69 73 20 72 65 63 6c 61 69 6d 65 64  ect is reclaimed
07c0: 2c 20 61 6c 6c 20 6c 69 73 74 73 0a 2f 2f 2f 20  , all lists./// 
07d0: 20 63 72 65 61 74 65 64 20 62 79 20 74 68 61 74   created by that
07e0: 20 66 61 63 74 6f 72 79 20 61 72 65 20 72 65 6c   factory are rel
07f0: 65 61 73 65 64 20 61 73 20 77 65 6c 6c 2e 0a 74  eased as well..t
0800: 65 6d 70 6c 61 74 65 20 3c 74 79 70 65 6e 61 6d  emplate <typenam
0810: 65 20 54 3e 0a 63 6c 61 73 73 20 49 6d 6d 75 74  e T>.class Immut
0820: 61 62 6c 65 4c 69 73 74 20 7b 0a 70 75 62 6c 69  ableList {.publi
0830: 63 3a 0a 20 20 75 73 69 6e 67 20 76 61 6c 75 65  c:.  using value
0840: 5f 74 79 70 65 20 3d 20 54 3b 0a 20 20 75 73 69  _type = T;.  usi
0850: 6e 67 20 46 61 63 74 6f 72 79 20 3d 20 49 6d 6d  ng Factory = Imm
0860: 75 74 61 62 6c 65 4c 69 73 74 46 61 63 74 6f 72  utableListFactor
0870: 79 3c 54 3e 3b 0a 0a 70 72 69 76 61 74 65 3a 0a  y<T>;..private:.
0880: 20 20 63 6f 6e 73 74 20 49 6d 6d 75 74 61 62 6c    const Immutabl
0890: 65 4c 69 73 74 49 6d 70 6c 3c 54 3e 2a 20 58 3b  eListImpl<T>* X;
08a0: 0a 0a 70 75 62 6c 69 63 3a 0a 20 20 2f 2f 20 54  ..public:.  // T
08b0: 68 69 73 20 63 6f 6e 73 74 72 75 63 74 6f 72 20  his constructor 
08c0: 73 68 6f 75 6c 64 20 6e 6f 72 6d 61 6c 6c 79 20  should normally 
08d0: 6f 6e 6c 79 20 62 65 20 63 61 6c 6c 65 64 20 62  only be called b
08e0: 79 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 46  y ImmutableListF
08f0: 61 63 74 6f 72 79 3c 54 3e 2e 0a 20 20 2f 2f 20  actory<T>..  // 
0900: 54 68 65 72 65 20 6d 61 79 20 62 65 20 63 61 73  There may be cas
0910: 65 73 2c 20 68 6f 77 65 76 65 72 2c 20 77 68 65  es, however, whe
0920: 6e 20 6f 6e 65 20 6e 65 65 64 73 20 74 6f 20 65  n one needs to e
0930: 78 74 72 61 63 74 20 74 68 65 20 69 6e 74 65 72  xtract the inter
0940: 6e 61 6c 20 70 6f 69 6e 74 65 72 0a 20 20 2f 2f  nal pointer.  //
0950: 20 61 6e 64 20 72 65 63 6f 6e 73 74 72 75 63 74   and reconstruct
0960: 20 61 20 6c 69 73 74 20 6f 62 6a 65 63 74 20 66   a list object f
0970: 72 6f 6d 20 74 68 61 74 20 70 6f 69 6e 74 65 72  rom that pointer
0980: 2e 0a 20 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73  ..  ImmutableLis
0990: 74 28 63 6f 6e 73 74 20 49 6d 6d 75 74 61 62 6c  t(const Immutabl
09a0: 65 4c 69 73 74 49 6d 70 6c 3c 54 3e 2a 20 78 20  eListImpl<T>* x 
09b0: 3d 20 6e 75 6c 6c 70 74 72 29 20 3a 20 58 28 78  = nullptr) : X(x
09c0: 29 20 7b 7d 0a 0a 20 20 63 6f 6e 73 74 20 49 6d  ) {}..  const Im
09d0: 6d 75 74 61 62 6c 65 4c 69 73 74 49 6d 70 6c 3c  mutableListImpl<
09e0: 54 3e 2a 20 67 65 74 49 6e 74 65 72 6e 61 6c 50  T>* getInternalP
09f0: 6f 69 6e 74 65 72 28 29 20 63 6f 6e 73 74 20 7b  ointer() const {
0a00: 0a 20 20 20 20 72 65 74 75 72 6e 20 58 3b 0a 20  .    return X;. 
0a10: 20 7d 0a 0a 20 20 63 6c 61 73 73 20 69 74 65 72   }..  class iter
0a20: 61 74 6f 72 20 7b 0a 20 20 20 20 63 6f 6e 73 74  ator {.    const
0a30: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 49 6d   ImmutableListIm
0a40: 70 6c 3c 54 3e 2a 20 4c 20 3d 20 6e 75 6c 6c 70  pl<T>* L = nullp
0a50: 74 72 3b 0a 0a 20 20 70 75 62 6c 69 63 3a 0a 20  tr;..  public:. 
0a60: 20 20 20 69 74 65 72 61 74 6f 72 28 29 20 3d 20     iterator() = 
0a70: 64 65 66 61 75 6c 74 3b 0a 20 20 20 20 69 74 65  default;.    ite
0a80: 72 61 74 6f 72 28 49 6d 6d 75 74 61 62 6c 65 4c  rator(ImmutableL
0a90: 69 73 74 20 6c 29 20 3a 20 4c 28 6c 2e 67 65 74  ist l) : L(l.get
0aa0: 49 6e 74 65 72 6e 61 6c 50 6f 69 6e 74 65 72 28  InternalPointer(
0ab0: 29 29 20 7b 7d 0a 0a 20 20 20 20 69 74 65 72 61  )) {}..    itera
0ac0: 74 6f 72 26 20 6f 70 65 72 61 74 6f 72 2b 2b 28  tor& operator++(
0ad0: 29 20 7b 20 4c 20 3d 20 4c 2d 3e 67 65 74 54 61  ) { L = L->getTa
0ae0: 69 6c 28 29 3b 20 72 65 74 75 72 6e 20 2a 74 68  il(); return *th
0af0: 69 73 3b 20 7d 0a 20 20 20 20 62 6f 6f 6c 20 6f  is; }.    bool o
0b00: 70 65 72 61 74 6f 72 3d 3d 28 63 6f 6e 73 74 20  perator==(const 
0b10: 69 74 65 72 61 74 6f 72 26 20 49 29 20 63 6f 6e  iterator& I) con
0b20: 73 74 20 7b 20 72 65 74 75 72 6e 20 4c 20 3d 3d  st { return L ==
0b30: 20 49 2e 4c 3b 20 7d 0a 20 20 20 20 62 6f 6f 6c   I.L; }.    bool
0b40: 20 6f 70 65 72 61 74 6f 72 21 3d 28 63 6f 6e 73   operator!=(cons
0b50: 74 20 69 74 65 72 61 74 6f 72 26 20 49 29 20 63  t iterator& I) c
0b60: 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 4c 20  onst { return L 
0b70: 21 3d 20 49 2e 4c 3b 20 7d 0a 20 20 20 20 63 6f  != I.L; }.    co
0b80: 6e 73 74 20 76 61 6c 75 65 5f 74 79 70 65 26 20  nst value_type& 
0b90: 6f 70 65 72 61 74 6f 72 2a 28 29 20 63 6f 6e 73  operator*() cons
0ba0: 74 20 7b 20 72 65 74 75 72 6e 20 4c 2d 3e 67 65  t { return L->ge
0bb0: 74 48 65 61 64 28 29 3b 20 7d 0a 0a 20 20 20 20  tHead(); }..    
0bc0: 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 20 67 65  ImmutableList ge
0bd0: 74 4c 69 73 74 28 29 20 63 6f 6e 73 74 20 7b 20  tList() const { 
0be0: 72 65 74 75 72 6e 20 4c 3b 20 7d 0a 20 20 7d 3b  return L; }.  };
0bf0: 0a 0a 20 20 2f 2f 2f 20 62 65 67 69 6e 20 2d 20  ..  /// begin - 
0c00: 52 65 74 75 72 6e 73 20 61 6e 20 69 74 65 72 61  Returns an itera
0c10: 74 6f 72 20 72 65 66 65 72 72 69 6e 67 20 74 6f  tor referring to
0c20: 20 74 68 65 20 68 65 61 64 20 6f 66 20 74 68 65   the head of the
0c30: 20 6c 69 73 74 2c 20 6f 72 0a 20 20 2f 2f 2f 20   list, or.  /// 
0c40: 20 61 6e 20 69 74 65 72 61 74 6f 72 20 64 65 6e   an iterator den
0c50: 6f 74 69 6e 67 20 74 68 65 20 65 6e 64 20 6f 66  oting the end of
0c60: 20 74 68 65 20 6c 69 73 74 20 69 66 20 74 68 65   the list if the
0c70: 20 6c 69 73 74 20 69 73 20 65 6d 70 74 79 2e 0a   list is empty..
0c80: 20 20 69 74 65 72 61 74 6f 72 20 62 65 67 69 6e    iterator begin
0c90: 28 29 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72  () const { retur
0ca0: 6e 20 69 74 65 72 61 74 6f 72 28 58 29 3b 20 7d  n iterator(X); }
0cb0: 0a 0a 20 20 2f 2f 2f 20 65 6e 64 20 2d 20 52 65  ..  /// end - Re
0cc0: 74 75 72 6e 73 20 61 6e 20 69 74 65 72 61 74 6f  turns an iterato
0cd0: 72 20 64 65 6e 6f 74 69 6e 67 20 74 68 65 20 65  r denoting the e
0ce0: 6e 64 20 6f 66 20 74 68 65 20 6c 69 73 74 2e 20  nd of the list. 
0cf0: 20 54 68 69 73 20 69 74 65 72 61 74 6f 72 0a 20   This iterator. 
0d00: 20 2f 2f 2f 20 20 64 6f 65 73 20 6e 6f 74 20 72   ///  does not r
0d10: 65 66 65 72 20 74 6f 20 61 20 76 61 6c 69 64 20  efer to a valid 
0d20: 6c 69 73 74 20 65 6c 65 6d 65 6e 74 2e 0a 20 20  list element..  
0d30: 69 74 65 72 61 74 6f 72 20 65 6e 64 28 29 20 63  iterator end() c
0d40: 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 69 74  onst { return it
0d50: 65 72 61 74 6f 72 28 29 3b 20 7d 0a 0a 20 20 2f  erator(); }..  /
0d60: 2f 2f 20 69 73 45 6d 70 74 79 20 2d 20 52 65 74  // isEmpty - Ret
0d70: 75 72 6e 73 20 74 72 75 65 20 69 66 20 74 68 65  urns true if the
0d80: 20 6c 69 73 74 20 69 73 20 65 6d 70 74 79 2e 0a   list is empty..
0d90: 20 20 62 6f 6f 6c 20 69 73 45 6d 70 74 79 28 29    bool isEmpty()
0da0: 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20   const { return 
0db0: 21 58 3b 20 7d 0a 0a 20 20 62 6f 6f 6c 20 63 6f  !X; }..  bool co
0dc0: 6e 74 61 69 6e 73 28 63 6f 6e 73 74 20 54 26 20  ntains(const T& 
0dd0: 56 29 20 63 6f 6e 73 74 20 7b 0a 20 20 20 20 66  V) const {.    f
0de0: 6f 72 20 28 69 74 65 72 61 74 6f 72 20 49 20 3d  or (iterator I =
0df0: 20 62 65 67 69 6e 28 29 2c 20 45 20 3d 20 65 6e   begin(), E = en
0e00: 64 28 29 3b 20 49 20 21 3d 20 45 3b 20 2b 2b 49  d(); I != E; ++I
0e10: 29 20 7b 0a 20 20 20 20 20 20 69 66 20 28 2a 49  ) {.      if (*I
0e20: 20 3d 3d 20 56 29 0a 20 20 20 20 20 20 20 20 72   == V).        r
0e30: 65 74 75 72 6e 20 74 72 75 65 3b 0a 20 20 20 20  eturn true;.    
0e40: 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 66 61 6c  }.    return fal
0e50: 73 65 3b 0a 20 20 7d 0a 0a 20 20 2f 2f 2f 20 69  se;.  }..  /// i
0e60: 73 45 71 75 61 6c 20 2d 20 52 65 74 75 72 6e 73  sEqual - Returns
0e70: 20 74 72 75 65 20 69 66 20 74 77 6f 20 6c 69 73   true if two lis
0e80: 74 73 20 61 72 65 20 65 71 75 61 6c 2e 20 20 42  ts are equal.  B
0e90: 65 63 61 75 73 65 20 61 6c 6c 20 6c 69 73 74 73  ecause all lists
0ea0: 20 63 72 65 61 74 65 64 0a 20 20 2f 2f 2f 20 20   created.  ///  
0eb0: 66 72 6f 6d 20 74 68 65 20 73 61 6d 65 20 49 6d  from the same Im
0ec0: 6d 75 74 61 62 6c 65 4c 69 73 74 46 61 63 74 6f  mutableListFacto
0ed0: 72 79 20 61 72 65 20 75 6e 69 71 75 65 64 2c 20  ry are uniqued, 
0ee0: 74 68 69 73 20 68 61 73 20 4f 28 31 29 20 63 6f  this has O(1) co
0ef0: 6d 70 6c 65 78 69 74 79 0a 20 20 2f 2f 2f 20 20  mplexity.  ///  
0f00: 62 65 63 61 75 73 65 20 69 74 20 74 68 65 20 63  because it the c
0f10: 6f 6e 74 65 6e 74 73 20 6f 66 20 74 68 65 20 6c  ontents of the l
0f20: 69 73 74 20 64 6f 20 6e 6f 74 20 6e 65 65 64 20  ist do not need 
0f30: 74 6f 20 62 65 20 63 6f 6d 70 61 72 65 64 2e 20  to be compared. 
0f40: 20 4e 6f 74 65 0a 20 20 2f 2f 2f 20 20 74 68 61   Note.  ///  tha
0f50: 74 20 79 6f 75 20 73 68 6f 75 6c 64 20 6f 6e 6c  t you should onl
0f60: 79 20 63 6f 6d 70 61 72 65 20 74 77 6f 20 6c 69  y compare two li
0f70: 73 74 73 20 63 72 65 61 74 65 64 20 66 72 6f 6d  sts created from
0f80: 20 74 68 65 20 73 61 6d 65 0a 20 20 2f 2f 2f 20   the same.  /// 
0f90: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 46 61   ImmutableListFa
0fa0: 63 74 6f 72 79 2e 0a 20 20 62 6f 6f 6c 20 69 73  ctory..  bool is
0fb0: 45 71 75 61 6c 28 63 6f 6e 73 74 20 49 6d 6d 75  Equal(const Immu
0fc0: 74 61 62 6c 65 4c 69 73 74 26 20 4c 29 20 63 6f  tableList& L) co
0fd0: 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 58 20 3d  nst { return X =
0fe0: 3d 20 4c 2e 58 3b 20 7d 0a 0a 20 20 62 6f 6f 6c  = L.X; }..  bool
0ff0: 20 6f 70 65 72 61 74 6f 72 3d 3d 28 63 6f 6e 73   operator==(cons
1000: 74 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 26  t ImmutableList&
1010: 20 4c 29 20 63 6f 6e 73 74 20 7b 20 72 65 74 75   L) const { retu
1020: 72 6e 20 69 73 45 71 75 61 6c 28 4c 29 3b 20 7d  rn isEqual(L); }
1030: 0a 0a 20 20 2f 2f 2f 20 67 65 74 48 65 61 64 20  ..  /// getHead 
1040: 2d 20 52 65 74 75 72 6e 73 20 74 68 65 20 68 65  - Returns the he
1050: 61 64 20 6f 66 20 74 68 65 20 6c 69 73 74 2e 0a  ad of the list..
1060: 20 20 63 6f 6e 73 74 20 54 26 20 67 65 74 48 65    const T& getHe
1070: 61 64 28 29 20 7b 0a 20 20 20 20 61 73 73 65 72  ad() {.    asser
1080: 74 28 21 69 73 45 6d 70 74 79 28 29 20 26 26 20  t(!isEmpty() && 
1090: 22 43 61 6e 6e 6f 74 20 67 65 74 20 74 68 65 20  "Cannot get the 
10a0: 68 65 61 64 20 6f 66 20 61 6e 20 65 6d 70 74 79  head of an empty
10b0: 20 6c 69 73 74 2e 22 29 3b 0a 20 20 20 20 72 65   list.");.    re
10c0: 74 75 72 6e 20 58 2d 3e 67 65 74 48 65 61 64 28  turn X->getHead(
10d0: 29 3b 0a 20 20 7d 0a 0a 20 20 2f 2f 2f 20 67 65  );.  }..  /// ge
10e0: 74 54 61 69 6c 20 2d 20 52 65 74 75 72 6e 73 20  tTail - Returns 
10f0: 74 68 65 20 74 61 69 6c 20 6f 66 20 74 68 65 20  the tail of the 
1100: 6c 69 73 74 2c 20 77 68 69 63 68 20 69 73 20 61  list, which is a
1110: 6e 6f 74 68 65 72 20 28 70 6f 73 73 69 62 6c 79  nother (possibly
1120: 20 65 6d 70 74 79 29 0a 20 20 2f 2f 2f 20 20 49   empty).  ///  I
1130: 6d 6d 75 74 61 62 6c 65 4c 69 73 74 2e 0a 20 20  mmutableList..  
1140: 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 20 67 65  ImmutableList ge
1150: 74 54 61 69 6c 28 29 20 7b 0a 20 20 20 20 72 65  tTail() {.    re
1160: 74 75 72 6e 20 58 20 3f 20 58 2d 3e 67 65 74 54  turn X ? X->getT
1170: 61 69 6c 28 29 20 3a 20 6e 75 6c 6c 70 74 72 3b  ail() : nullptr;
1180: 0a 20 20 7d 0a 0a 20 20 76 6f 69 64 20 50 72 6f  .  }..  void Pro
1190: 66 69 6c 65 28 46 6f 6c 64 69 6e 67 53 65 74 4e  file(FoldingSetN
11a0: 6f 64 65 49 44 26 20 49 44 29 20 63 6f 6e 73 74  odeID& ID) const
11b0: 20 7b 0a 20 20 20 20 49 44 2e 41 64 64 50 6f 69   {.    ID.AddPoi
11c0: 6e 74 65 72 28 58 29 3b 0a 20 20 7d 0a 7d 3b 0a  nter(X);.  }.};.
11d0: 0a 74 65 6d 70 6c 61 74 65 20 3c 74 79 70 65 6e  .template <typen
11e0: 61 6d 65 20 54 3e 0a 63 6c 61 73 73 20 49 6d 6d  ame T>.class Imm
11f0: 75 74 61 62 6c 65 4c 69 73 74 46 61 63 74 6f 72  utableListFactor
1200: 79 20 7b 0a 20 20 75 73 69 6e 67 20 4c 69 73 74  y {.  using List
1210: 54 79 20 3d 20 49 6d 6d 75 74 61 62 6c 65 4c 69  Ty = ImmutableLi
1220: 73 74 49 6d 70 6c 3c 54 3e 3b 0a 20 20 75 73 69  stImpl<T>;.  usi
1230: 6e 67 20 43 61 63 68 65 54 79 20 3d 20 46 6f 6c  ng CacheTy = Fol
1240: 64 69 6e 67 53 65 74 3c 4c 69 73 74 54 79 3e 3b  dingSet<ListTy>;
1250: 0a 0a 20 20 43 61 63 68 65 54 79 20 43 61 63 68  ..  CacheTy Cach
1260: 65 3b 0a 20 20 75 69 6e 74 70 74 72 5f 74 20 41  e;.  uintptr_t A
1270: 6c 6c 6f 63 61 74 6f 72 3b 0a 0a 20 20 62 6f 6f  llocator;..  boo
1280: 6c 20 6f 77 6e 73 41 6c 6c 6f 63 61 74 6f 72 28  l ownsAllocator(
1290: 29 20 63 6f 6e 73 74 20 7b 0a 20 20 20 20 72 65  ) const {.    re
12a0: 74 75 72 6e 20 28 41 6c 6c 6f 63 61 74 6f 72 20  turn (Allocator 
12b0: 26 20 30 78 31 29 20 3d 3d 20 30 3b 0a 20 20 7d  & 0x1) == 0;.  }
12c0: 0a 0a 20 20 42 75 6d 70 50 74 72 41 6c 6c 6f 63  ..  BumpPtrAlloc
12d0: 61 74 6f 72 26 20 67 65 74 41 6c 6c 6f 63 61 74  ator& getAllocat
12e0: 6f 72 28 29 20 63 6f 6e 73 74 20 7b 0a 20 20 20  or() const {.   
12f0: 20 72 65 74 75 72 6e 20 2a 72 65 69 6e 74 65 72   return *reinter
1300: 70 72 65 74 5f 63 61 73 74 3c 42 75 6d 70 50 74  pret_cast<BumpPt
1310: 72 41 6c 6c 6f 63 61 74 6f 72 2a 3e 28 41 6c 6c  rAllocator*>(All
1320: 6f 63 61 74 6f 72 20 26 20 7e 30 78 31 29 3b 0a  ocator & ~0x1);.
1330: 20 20 7d 0a 0a 70 75 62 6c 69 63 3a 0a 20 20 49    }..public:.  I
1340: 6d 6d 75 74 61 62 6c 65 4c 69 73 74 46 61 63 74  mmutableListFact
1350: 6f 72 79 28 29 0a 20 20 20 20 3a 20 41 6c 6c 6f  ory().    : Allo
1360: 63 61 74 6f 72 28 72 65 69 6e 74 65 72 70 72 65  cator(reinterpre
1370: 74 5f 63 61 73 74 3c 75 69 6e 74 70 74 72 5f 74  t_cast<uintptr_t
1380: 3e 28 6e 65 77 20 42 75 6d 70 50 74 72 41 6c 6c  >(new BumpPtrAll
1390: 6f 63 61 74 6f 72 28 29 29 29 20 7b 7d 0a 0a 20  ocator())) {}.. 
13a0: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 46 61   ImmutableListFa
13b0: 63 74 6f 72 79 28 42 75 6d 70 50 74 72 41 6c 6c  ctory(BumpPtrAll
13c0: 6f 63 61 74 6f 72 26 20 41 6c 6c 6f 63 29 0a 20  ocator& Alloc). 
13d0: 20 3a 20 41 6c 6c 6f 63 61 74 6f 72 28 72 65 69   : Allocator(rei
13e0: 6e 74 65 72 70 72 65 74 5f 63 61 73 74 3c 75 69  nterpret_cast<ui
13f0: 6e 74 70 74 72 5f 74 3e 28 26 41 6c 6c 6f 63 29  ntptr_t>(&Alloc)
1400: 20 7c 20 30 78 31 29 20 7b 7d 0a 0a 20 20 7e 49   | 0x1) {}..  ~I
1410: 6d 6d 75 74 61 62 6c 65 4c 69 73 74 46 61 63 74  mmutableListFact
1420: 6f 72 79 28 29 20 7b 0a 20 20 20 20 69 66 20 28  ory() {.    if (
1430: 6f 77 6e 73 41 6c 6c 6f 63 61 74 6f 72 28 29 29  ownsAllocator())
1440: 20 64 65 6c 65 74 65 20 26 67 65 74 41 6c 6c 6f   delete &getAllo
1450: 63 61 74 6f 72 28 29 3b 0a 20 20 7d 0a 0a 20 20  cator();.  }..  
1460: 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 3c 54 3e  ImmutableList<T>
1470: 20 63 6f 6e 63 61 74 28 63 6f 6e 73 74 20 54 26   concat(const T&
1480: 20 48 65 61 64 2c 20 49 6d 6d 75 74 61 62 6c 65   Head, Immutable
1490: 4c 69 73 74 3c 54 3e 20 54 61 69 6c 29 20 7b 0a  List<T> Tail) {.
14a0: 20 20 20 20 2f 2f 20 50 72 6f 66 69 6c 65 20 74      // Profile t
14b0: 68 65 20 6e 65 77 20 6c 69 73 74 20 74 6f 20 73  he new list to s
14c0: 65 65 20 69 66 20 69 74 20 61 6c 72 65 61 64 79  ee if it already
14d0: 20 65 78 69 73 74 73 20 69 6e 20 6f 75 72 20 63   exists in our c
14e0: 61 63 68 65 2e 0a 20 20 20 20 46 6f 6c 64 69 6e  ache..    Foldin
14f0: 67 53 65 74 4e 6f 64 65 49 44 20 49 44 3b 0a 20  gSetNodeID ID;. 
1500: 20 20 20 76 6f 69 64 2a 20 49 6e 73 65 72 74 50     void* InsertP
1510: 6f 73 3b 0a 0a 20 20 20 20 63 6f 6e 73 74 20 4c  os;..    const L
1520: 69 73 74 54 79 2a 20 54 61 69 6c 49 6d 70 6c 20  istTy* TailImpl 
1530: 3d 20 54 61 69 6c 2e 67 65 74 49 6e 74 65 72 6e  = Tail.getIntern
1540: 61 6c 50 6f 69 6e 74 65 72 28 29 3b 0a 20 20 20  alPointer();.   
1550: 20 4c 69 73 74 54 79 3a 3a 50 72 6f 66 69 6c 65   ListTy::Profile
1560: 28 49 44 2c 20 48 65 61 64 2c 20 54 61 69 6c 49  (ID, Head, TailI
1570: 6d 70 6c 29 3b 0a 20 20 20 20 4c 69 73 74 54 79  mpl);.    ListTy
1580: 2a 20 4c 20 3d 20 43 61 63 68 65 2e 46 69 6e 64  * L = Cache.Find
1590: 4e 6f 64 65 4f 72 49 6e 73 65 72 74 50 6f 73 28  NodeOrInsertPos(
15a0: 49 44 2c 20 49 6e 73 65 72 74 50 6f 73 29 3b 0a  ID, InsertPos);.
15b0: 0a 20 20 20 20 69 66 20 28 21 4c 29 20 7b 0a 20  .    if (!L) {. 
15c0: 20 20 20 20 20 2f 2f 20 54 68 65 20 6c 69 73 74       // The list
15d0: 20 64 6f 65 73 20 6e 6f 74 20 65 78 69 73 74 20   does not exist 
15e0: 69 6e 20 6f 75 72 20 63 61 63 68 65 2e 20 20 43  in our cache.  C
15f0: 72 65 61 74 65 20 69 74 2e 0a 20 20 20 20 20 20  reate it..      
1600: 42 75 6d 70 50 74 72 41 6c 6c 6f 63 61 74 6f 72  BumpPtrAllocator
1610: 26 20 41 20 3d 20 67 65 74 41 6c 6c 6f 63 61 74  & A = getAllocat
1620: 6f 72 28 29 3b 0a 20 20 20 20 20 20 4c 20 3d 20  or();.      L = 
1630: 28 4c 69 73 74 54 79 2a 29 20 41 2e 41 6c 6c 6f  (ListTy*) A.Allo
1640: 63 61 74 65 3c 4c 69 73 74 54 79 3e 28 29 3b 0a  cate<ListTy>();.
1650: 20 20 20 20 20 20 6e 65 77 20 28 4c 29 20 4c 69        new (L) Li
1660: 73 74 54 79 28 48 65 61 64 2c 20 54 61 69 6c 49  stTy(Head, TailI
1670: 6d 70 6c 29 3b 0a 0a 20 20 20 20 20 20 2f 2f 20  mpl);..      // 
1680: 49 6e 73 65 72 74 20 74 68 65 20 6e 65 77 20 6c  Insert the new l
1690: 69 73 74 20 69 6e 74 6f 20 74 68 65 20 63 61 63  ist into the cac
16a0: 68 65 2e 0a 20 20 20 20 20 20 43 61 63 68 65 2e  he..      Cache.
16b0: 49 6e 73 65 72 74 4e 6f 64 65 28 4c 2c 20 49 6e  InsertNode(L, In
16c0: 73 65 72 74 50 6f 73 29 3b 0a 20 20 20 20 7d 0a  sertPos);.    }.
16d0: 0a 20 20 20 20 72 65 74 75 72 6e 20 4c 3b 0a 20  .    return L;. 
16e0: 20 7d 0a 0a 20 20 49 6d 6d 75 74 61 62 6c 65 4c   }..  ImmutableL
16f0: 69 73 74 3c 54 3e 20 61 64 64 28 63 6f 6e 73 74  ist<T> add(const
1700: 20 54 26 20 44 2c 20 49 6d 6d 75 74 61 62 6c 65   T& D, Immutable
1710: 4c 69 73 74 3c 54 3e 20 4c 29 20 7b 0a 20 20 20  List<T> L) {.   
1720: 20 72 65 74 75 72 6e 20 63 6f 6e 63 61 74 28 44   return concat(D
1730: 2c 20 4c 29 3b 0a 20 20 7d 0a 0a 20 20 49 6d 6d  , L);.  }..  Imm
1740: 75 74 61 62 6c 65 4c 69 73 74 3c 54 3e 20 67 65  utableList<T> ge
1750: 74 45 6d 70 74 79 4c 69 73 74 28 29 20 63 6f 6e  tEmptyList() con
1760: 73 74 20 7b 0a 20 20 20 20 72 65 74 75 72 6e 20  st {.    return 
1770: 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 3c 54 3e  ImmutableList<T>
1780: 28 6e 75 6c 6c 70 74 72 29 3b 0a 20 20 7d 0a 0a  (nullptr);.  }..
1790: 20 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 3c    ImmutableList<
17a0: 54 3e 20 63 72 65 61 74 65 28 63 6f 6e 73 74 20  T> create(const 
17b0: 54 26 20 58 29 20 7b 0a 20 20 20 20 72 65 74 75  T& X) {.    retu
17c0: 72 6e 20 43 6f 6e 63 61 74 28 58 2c 20 67 65 74  rn Concat(X, get
17d0: 45 6d 70 74 79 4c 69 73 74 28 29 29 3b 0a 20 20  EmptyList());.  
17e0: 7d 0a 7d 3b 0a 0a 2f 2f 3d 3d 3d 2d 2d 2d 2d 2d  }.};..//===-----
17f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1800: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1810: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1820: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1830: 2d 3d 3d 3d 2f 2f 0a 2f 2f 20 50 61 72 74 69 61  -===//.// Partia
1840: 6c 6c 79 2d 73 70 65 63 69 61 6c 69 7a 65 64 20  lly-specialized 
1850: 54 72 61 69 74 73 2e 0a 2f 2f 3d 3d 3d 2d 2d 2d  Traits..//===---
1860: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1870: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1880: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
1890: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
18a0: 2d 2d 2d 3d 3d 3d 2f 2f 0a 0a 74 65 6d 70 6c 61  ---===//..templa
18b0: 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 73  te<typename T> s
18c0: 74 72 75 63 74 20 44 65 6e 73 65 4d 61 70 49 6e  truct DenseMapIn
18d0: 66 6f 3b 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70  fo;.template<typ
18e0: 65 6e 61 6d 65 20 54 3e 20 73 74 72 75 63 74 20  ename T> struct 
18f0: 44 65 6e 73 65 4d 61 70 49 6e 66 6f 3c 49 6d 6d  DenseMapInfo<Imm
1900: 75 74 61 62 6c 65 4c 69 73 74 3c 54 3e 3e 20 7b  utableList<T>> {
1910: 0a 20 20 73 74 61 74 69 63 20 69 6e 6c 69 6e 65  .  static inline
1920: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 3c 54   ImmutableList<T
1930: 3e 20 67 65 74 45 6d 70 74 79 4b 65 79 28 29 20  > getEmptyKey() 
1940: 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 72 65 69  {.    return rei
1950: 6e 74 65 72 70 72 65 74 5f 63 61 73 74 3c 49 6d  nterpret_cast<Im
1960: 6d 75 74 61 62 6c 65 4c 69 73 74 49 6d 70 6c 3c  mutableListImpl<
1970: 54 3e 2a 3e 28 2d 31 29 3b 0a 20 20 7d 0a 0a 20  T>*>(-1);.  }.. 
1980: 20 73 74 61 74 69 63 20 69 6e 6c 69 6e 65 20 49   static inline I
1990: 6d 6d 75 74 61 62 6c 65 4c 69 73 74 3c 54 3e 20  mmutableList<T> 
19a0: 67 65 74 54 6f 6d 62 73 74 6f 6e 65 4b 65 79 28  getTombstoneKey(
19b0: 29 20 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 72  ) {.    return r
19c0: 65 69 6e 74 65 72 70 72 65 74 5f 63 61 73 74 3c  einterpret_cast<
19d0: 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 49 6d 70  ImmutableListImp
19e0: 6c 3c 54 3e 2a 3e 28 2d 32 29 3b 0a 20 20 7d 0a  l<T>*>(-2);.  }.
19f0: 0a 20 20 73 74 61 74 69 63 20 75 6e 73 69 67 6e  .  static unsign
1a00: 65 64 20 67 65 74 48 61 73 68 56 61 6c 75 65 28  ed getHashValue(
1a10: 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 3c 54 3e  ImmutableList<T>
1a20: 20 58 29 20 7b 0a 20 20 20 20 75 69 6e 74 70 74   X) {.    uintpt
1a30: 72 5f 74 20 50 74 72 56 61 6c 20 3d 20 72 65 69  r_t PtrVal = rei
1a40: 6e 74 65 72 70 72 65 74 5f 63 61 73 74 3c 75 69  nterpret_cast<ui
1a50: 6e 74 70 74 72 5f 74 3e 28 58 2e 67 65 74 49 6e  ntptr_t>(X.getIn
1a60: 74 65 72 6e 61 6c 50 6f 69 6e 74 65 72 28 29 29  ternalPointer())
1a70: 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 28 75 6e  ;.    return (un
1a80: 73 69 67 6e 65 64 28 28 75 69 6e 74 70 74 72 5f  signed((uintptr_
1a90: 74 29 50 74 72 56 61 6c 29 20 3e 3e 20 34 29 20  t)PtrVal) >> 4) 
1aa0: 5e 0a 20 20 20 20 20 20 20 20 20 20 20 28 75 6e  ^.           (un
1ab0: 73 69 67 6e 65 64 28 28 75 69 6e 74 70 74 72 5f  signed((uintptr_
1ac0: 74 29 50 74 72 56 61 6c 29 20 3e 3e 20 39 29 3b  t)PtrVal) >> 9);
1ad0: 0a 20 20 7d 0a 0a 20 20 73 74 61 74 69 63 20 62  .  }..  static b
1ae0: 6f 6f 6c 20 69 73 45 71 75 61 6c 28 49 6d 6d 75  ool isEqual(Immu
1af0: 74 61 62 6c 65 4c 69 73 74 3c 54 3e 20 58 31 2c  tableList<T> X1,
1b00: 20 49 6d 6d 75 74 61 62 6c 65 4c 69 73 74 3c 54   ImmutableList<T
1b10: 3e 20 58 32 29 20 7b 0a 20 20 20 20 72 65 74 75  > X2) {.    retu
1b20: 72 6e 20 58 31 20 3d 3d 20 58 32 3b 0a 20 20 7d  rn X1 == X2;.  }
1b30: 0a 7d 3b 0a 0a 74 65 6d 70 6c 61 74 65 20 3c 74  .};..template <t
1b40: 79 70 65 6e 61 6d 65 20 54 3e 20 73 74 72 75 63  ypename T> struc
1b50: 74 20 69 73 50 6f 64 4c 69 6b 65 3b 0a 74 65 6d  t isPodLike;.tem
1b60: 70 6c 61 74 65 20 3c 74 79 70 65 6e 61 6d 65 20  plate <typename 
1b70: 54 3e 0a 73 74 72 75 63 74 20 69 73 50 6f 64 4c  T>.struct isPodL
1b80: 69 6b 65 3c 49 6d 6d 75 74 61 62 6c 65 4c 69 73  ike<ImmutableLis
1b90: 74 3c 54 3e 3e 20 7b 20 73 74 61 74 69 63 20 63  t<T>> { static c
1ba0: 6f 6e 73 74 20 62 6f 6f 6c 20 76 61 6c 75 65 20  onst bool value 
1bb0: 3d 20 74 72 75 65 3b 20 7d 3b 0a 0a 7d 20 2f 2f  = true; };..} //
1bc0: 20 65 6e 64 20 6e 61 6d 65 73 70 61 63 65 20 6c   end namespace l
1bd0: 6c 76 6d 0a 0a 23 65 6e 64 69 66 20 2f 2f 20 4c  lvm..#endif // L
1be0: 4c 56 4d 5f 41 44 54 5f 49 4d 4d 55 54 41 42 4c  LVM_ADT_IMMUTABL
1bf0: 45 4c 49 53 54 5f 48 0a                          ELIST_H.