ImmutableList.h revision 2c228834fc226619c25a678394bab73dd1b1f85d
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com//==--- ImmutableList.h - Immutable (functional) list interface --*- C++ -*-==// 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// The LLVM Compiler Infrastructure 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// This file is distributed under the University of Illinois Open Source 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// License. See LICENSE.TXT for details. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 8b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo//===----------------------------------------------------------------------===// 9b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo// 1075356a713f0576d5e4f542898267acbcf4d18d88bsalomon@google.com// This file defines the ImmutableList class. 11b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo// 129df214e836f2b897224178676c03017e9190b7e0Scroggo//===----------------------------------------------------------------------===// 139df214e836f2b897224178676c03017e9190b7e0Scroggo 14b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo#ifndef LLVM_ADT_IMLIST_H 15b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo#define LLVM_ADT_IMLIST_H 16b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo 17b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo#include "llvm/Support/Allocator.h" 1808526c07f4f530e56b70d4b22f5a4af35d9ebccascroggo#include "llvm/ADT/FoldingSet.h" 19b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo#include "llvm/Support/DataTypes.h" 20b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo#include <cassert> 219df214e836f2b897224178676c03017e9190b7e0Scroggo 229df214e836f2b897224178676c03017e9190b7e0Scroggonamespace llvm { 239df214e836f2b897224178676c03017e9190b7e0Scroggo 249df214e836f2b897224178676c03017e9190b7e0Scroggotemplate <typename T> class ImmutableListFactory; 259df214e836f2b897224178676c03017e9190b7e0Scroggo 269df214e836f2b897224178676c03017e9190b7e0Scroggotemplate <typename T> 279df214e836f2b897224178676c03017e9190b7e0Scroggoclass ImmutableListImpl : public FoldingSetNode { 28aed68d999bfd307c2cdf1539e4ed4caa9130c7f3Scroggo T Head; 29aed68d999bfd307c2cdf1539e4ed4caa9130c7f3Scroggo const ImmutableListImpl* Tail; 309df214e836f2b897224178676c03017e9190b7e0Scroggo 319df214e836f2b897224178676c03017e9190b7e0Scroggo ImmutableListImpl(const T& head, const ImmutableListImpl* tail = 0) 329df214e836f2b897224178676c03017e9190b7e0Scroggo : Head(head), Tail(tail) {} 339df214e836f2b897224178676c03017e9190b7e0Scroggo 34b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo friend class ImmutableListFactory<T>; 3593c7ee34dc5c8f6bfad65809f4b39f8d00d7f0d4sugoi@google.com 364bdfb8c9d6482a56c7212034a6f73046227ed023robertphillips@google.com // Do not implement. 371195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com void operator=(const ImmutableListImpl&); 381195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com ImmutableListImpl(const ImmutableListImpl&); 398108c47b50d13cf55b0265b97d729f354e7a697ebsalomon@google.com 4064cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.compublic: 419df214e836f2b897224178676c03017e9190b7e0Scroggo const T& getHead() const { return Head; } 42b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo const ImmutableListImpl* getTail() const { return Tail; } 43b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo 448108c47b50d13cf55b0265b97d729f354e7a697ebsalomon@google.com static inline void Profile(FoldingSetNodeID& ID, const T& H, 451195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com const ImmutableListImpl* L){ 461195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com ID.AddPointer(L); 471195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com ID.Add(H); 481195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com } 498108c47b50d13cf55b0265b97d729f354e7a697ebsalomon@google.com 501195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com void Profile(FoldingSetNodeID& ID) { 511195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com Profile(ID, Head, Tail); 528108c47b50d13cf55b0265b97d729f354e7a697ebsalomon@google.com } 531195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com}; 549df214e836f2b897224178676c03017e9190b7e0Scroggo 551195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com/// ImmutableList - This class represents an immutable (functional) list. 569df214e836f2b897224178676c03017e9190b7e0Scroggo/// It is implemented as a smart pointer (wraps ImmutableListImpl), so it 571195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com/// it is intended to always be copied by value as if it were a pointer. 581195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com/// This interface matches ImmutableSet and ImmutableMap. ImmutableList 591195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com/// objects should almost never be created directly, and instead should 601195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com/// be created by ImmutableListFactory objects that manage the lifetime 611195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com/// of a group of lists. When the factory object is reclaimed, all lists 6264cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com/// created by that factory are released as well. 631195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.comtemplate <typename T> 641195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.comclass ImmutableList { 651195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.compublic: 661195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com typedef T value_type; 671195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com typedef ImmutableListFactory<T> Factory; 6864cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com 6964cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.comprivate: 7064cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com const ImmutableListImpl<T>* X; 7164cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com 7264cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.compublic: 7364cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com // This constructor should normally only be called by ImmutableListFactory<T>. 7464cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com // There may be cases, however, when one needs to extract the internal pointer 7564cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com // and reconstruct a list object from that pointer. 7664cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com ImmutableList(const ImmutableListImpl<T>* x = 0) : X(x) {} 771195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 781195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com const ImmutableListImpl<T>* getInternalPointer() const { 791195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com return X; 801195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com } 811195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 821195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com class iterator { 831195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com const ImmutableListImpl<T>* L; 841195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com public: 851195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com iterator() : L(0) {} 861195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com iterator(ImmutableList l) : L(l.getInternalPointer()) {} 871195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 881195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com iterator& operator++() { L = L->getTail(); return *this; } 891195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com bool operator==(const iterator& I) const { return L == I.L; } 901195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com bool operator!=(const iterator& I) const { return L != I.L; } 911195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com const value_type& operator*() const { return L->getHead(); } 921195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com ImmutableList getList() const { return L; } 931195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com }; 941195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 951195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// begin - Returns an iterator referring to the head of the list, or 961195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// an iterator denoting the end of the list if the list is empty. 971195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com iterator begin() const { return iterator(X); } 981195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 991195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// end - Returns an iterator denoting the end of the list. This iterator 1001195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// does not refer to a valid list element. 1011195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com iterator end() const { return iterator(); } 1021195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 1031195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// isEmpty - Returns true if the list is empty. 1041195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com bool isEmpty() const { return !X; } 1051195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 1061195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// isEqual - Returns true if two lists are equal. Because all lists created 1071195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// from the same ImmutableListFactory are uniqued, this has O(1) complexity 1081195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// because it the contents of the list do not need to be compared. Note 1091195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// that you should only compare two lists created from the same 1101195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// ImmutableListFactory. 1111195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com bool isEqual(const ImmutableList& L) const { return X == L.X; } 1121195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 11364cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com bool operator==(const ImmutableList& L) const { return isEqual(L); } 11464cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com 11564cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com /// getHead - Returns the head of the list. 11664cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com const T& getHead() { 1171195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com assert (!isEmpty() && "Cannot get the head of an empty list."); 1181195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com return X->getHead(); 1191195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com } 1201195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 1211195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// getTail - Returns the tail of the list, which is another (possibly empty) 1221195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com /// ImmutableList. 1231195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com ImmutableList getTail() { 1241195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com return X ? X->getTail() : 0; 1251195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com } 1261195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 1271195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com void Profile(FoldingSetNodeID& ID) const { 1281195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com ID.AddPointer(X); 1291195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com } 1301195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com}; 1311195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 1321195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.comtemplate <typename T> 1331195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.comclass ImmutableListFactory { 1341195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com typedef ImmutableListImpl<T> ListTy; 13564cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com typedef FoldingSet<ListTy> CacheTy; 13664cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com 13764cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com CacheTy Cache; 13864cc810ad165724f9c666a75bd52e41c67f13564bsalomon@google.com uintptr_t Allocator; 1391195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 1401195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com bool ownsAllocator() const { 1411195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com return Allocator & 0x1 ? false : true; 1421195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com } 1431195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com 1441195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com BumpPtrAllocator& getAllocator() const { 1451195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 1461195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com } 1479df214e836f2b897224178676c03017e9190b7e0Scroggo 1481195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.compublic: 1491195925b05ee9d666ea8a8f68fde5d8ca7e49b04bsalomon@google.com ImmutableListFactory() 150b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 151b7e9aee1acf27fc98cb37ed69c05da71b4c3c69bscroggo 15237924183583cf3fdc59b91de0acc26e1fcf2598dreed@google.com ImmutableListFactory(BumpPtrAllocator& Alloc) 153e378d833489476f68485a64dc437da325e75ee71reed@google.com : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 154e378d833489476f68485a64dc437da325e75ee71reed@google.com 155e378d833489476f68485a64dc437da325e75ee71reed@google.com ~ImmutableListFactory() { 156e378d833489476f68485a64dc437da325e75ee71reed@google.com if (ownsAllocator()) delete &getAllocator(); 157e378d833489476f68485a64dc437da325e75ee71reed@google.com } 158e378d833489476f68485a64dc437da325e75ee71reed@google.com 159e378d833489476f68485a64dc437da325e75ee71reed@google.com ImmutableList<T> Concat(const T& Head, ImmutableList<T> Tail) { 160e378d833489476f68485a64dc437da325e75ee71reed@google.com // Profile the new list to see if it already exists in our cache. 161e378d833489476f68485a64dc437da325e75ee71reed@google.com FoldingSetNodeID ID; 1624e73aa1566f2ee9a2525942cab4e885cb51b855cskia.committer@gmail.com void* InsertPos; 163e378d833489476f68485a64dc437da325e75ee71reed@google.com 164e378d833489476f68485a64dc437da325e75ee71reed@google.com const ListTy* TailImpl = Tail.getInternalPointer(); 165e378d833489476f68485a64dc437da325e75ee71reed@google.com ListTy::Profile(ID, Head, TailImpl); 166e378d833489476f68485a64dc437da325e75ee71reed@google.com ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos); 167e378d833489476f68485a64dc437da325e75ee71reed@google.com 168e378d833489476f68485a64dc437da325e75ee71reed@google.com if (!L) { 169e378d833489476f68485a64dc437da325e75ee71reed@google.com // The list does not exist in our cache. Create it. 1704d5c26de0a24f86c37c1da8b0e30d11a550ea67breed@google.com BumpPtrAllocator& A = getAllocator(); 1714d5c26de0a24f86c37c1da8b0e30d11a550ea67breed@google.com L = (ListTy*) A.Allocate<ListTy>(); 172acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com new (L) ListTy(Head, TailImpl); 173acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com 174d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com // Insert the new list into the cache. 17504018f37af9d1b231111dc557fa281689b8a4616commit-bot@chromium.org Cache.InsertNode(L, InsertPos); 17604018f37af9d1b231111dc557fa281689b8a4616commit-bot@chromium.org } 17704018f37af9d1b231111dc557fa281689b8a4616commit-bot@chromium.org 17804018f37af9d1b231111dc557fa281689b8a4616commit-bot@chromium.org return L; 17904018f37af9d1b231111dc557fa281689b8a4616commit-bot@chromium.org } 18004018f37af9d1b231111dc557fa281689b8a4616commit-bot@chromium.org 18104018f37af9d1b231111dc557fa281689b8a4616commit-bot@chromium.org ImmutableList<T> Add(const T& D, ImmutableList<T> L) { 182acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com return Concat(D, L); 183acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com } 184acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com 185acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com ImmutableList<T> GetEmptyList() const { 186acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com return ImmutableList<T>(0); 187acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com } 188acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com 189acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com ImmutableList<T> Create(const T& X) { 190acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com return Concat(X, GetEmptyList()); 191acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com } 192a48595d8633208b3e0d46f67a8d530ebbc452ad0skia.committer@gmail.com}; 193d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com 194d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com//===----------------------------------------------------------------------===// 195d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com// Partially-specialized Traits. 196d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com//===----------------------------------------------------------------------===// 197d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com 198acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.comtemplate<typename T> struct DenseMapInfo; 199d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.comtemplate<typename T> struct DenseMapInfo<ImmutableList<T> > { 200d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com static inline ImmutableList<T> getEmptyKey() { 201acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com return reinterpret_cast<ImmutableListImpl<T>*>(-1); 202acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com } 203acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com static inline ImmutableList<T> getTombstoneKey() { 204acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com return reinterpret_cast<ImmutableListImpl<T>*>(-2); 205acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com } 206acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com static unsigned getHashValue(ImmutableList<T> X) { 207d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer()); 208d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com return (unsigned((uintptr_t)PtrVal) >> 4) ^ 209d1f1b67f5eab110fa0c47c082776d9da1c5fba86reed@google.com (unsigned((uintptr_t)PtrVal) >> 9); 210acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com } 211acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) { 212acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com return X1 == X2; 213acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com } 214acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com static bool isPod() { return true; } 215acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com}; 216acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com 217acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com} // end llvm namespace 218acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com 219acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com#endif 220acb3d88cf84adf367c173a7a33cd3b0c379291dcreed@google.com