include/swift/Basic/DiverseList.h - third_party/swift - Git at Google

 //===--- DiverseList.h - List of variably-sized objects ---------*- C++ -*-===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines a data structure for representing a list of
 // variably-sized objects.  It is a requirement that the object type
 // be trivially movable, meaning that it has a trivial move
 // constructor and a trivial destructor.
 //
 //===----------------------------------------------------------------------===//

 #ifndef SWIFT_BASIC_DIVERSELIST_H
 #define SWIFT_BASIC_DIVERSELIST_H

 #include "swift/Basic/Malloc.h"
 #include <cassert>
 #include <cstring>
 #include <utility>

 namespace swift {

 template <class T> class DiverseListImpl;

 /// DiverseList - A list of heterogeneously-typed objects.
 ///
 /// \tparam T - A common base class of the objects in the list; must
 ///   provide an allocated_size() const method.
 /// \tparam InlineCapacity - the amount of inline storage to provide, in bytes.
 template <class T, unsigned InlineCapacity>
 class DiverseList : public DiverseListImpl<T> {
   char InlineStorage[InlineCapacity];

 public:
   DiverseList() : DiverseListImpl<T>(InlineStorage + InlineCapacity) {}
   DiverseList(const DiverseList &other)
     : DiverseListImpl<T>(other, InlineStorage + InlineCapacity) {}
   DiverseList(const DiverseListImpl<T> &other)
     : DiverseListImpl<T>(other, InlineStorage + InlineCapacity) {}
   DiverseList(DiverseList<T, InlineCapacity> &&other)
     : DiverseListImpl<T>(std::move(other), InlineStorage + InlineCapacity) {}
   DiverseList(DiverseListImpl<T> &&other)
     : DiverseListImpl<T>(std::move(other), InlineStorage + InlineCapacity) {}
 };

 /// A base class for DiverseListImpl.
 class DiverseListBase {
 public:
   /// The first element in the list and the beginning of the allocation.
   char *Begin;

   /// A pointer past the last element in the list.
   char *End;

   /// A pointer past the end of the allocation.
   char *EndOfAllocation;

   bool isAllocatedInline() const {
     return (Begin == reinterpret_cast<const char *>(this + 1));
   }

   void checkValid() const {
     assert(Begin <= End);
     assert(End <= EndOfAllocation);
   }

   void initialize(char *endOfAllocation) {
     EndOfAllocation = endOfAllocation;
     Begin = End = reinterpret_cast<char*>(this + 1);
   }
   void copyFrom(const DiverseListBase &other) {
     // Ensure that we're large enough to store all the data.
     std::size_t size = static_cast<std::size_t>(other.End - other.Begin);
     char *newStorage = addNewStorage(size);
     std::memcpy(newStorage, other.Begin, size);
   }
   char *addNewStorage(std::size_t needed) {
     checkValid();
     if (std::size_t(EndOfAllocation - End) >= needed) {
       char *newStorage = End;
       End += needed;
       return newStorage;
     }
     return addNewStorageSlow(needed);
   }
   char *addNewStorageSlow(std::size_t needed);

   /// A stable iterator is the equivalent of an index into the list.
   /// It's an iterator that stays stable across modification of the
   /// list.
   class stable_iterator {
     std::size_t Offset;
     friend class DiverseListBase;
     template <class T> friend class DiverseListImpl;
     stable_iterator(std::size_t offset) : Offset(offset) {}
   public:
     stable_iterator() = default;
     friend bool operator==(stable_iterator a, stable_iterator b) {
       return a.Offset == b.Offset;
     }
     friend bool operator!=(stable_iterator a, stable_iterator b) {
       return !operator==(a, b);
     }
   };
   stable_iterator stable_begin() const {
     return stable_iterator(0);
   }
   stable_iterator stable_end() {
     return stable_iterator(std::size_t(End - Begin));
   }

 protected:
   ~DiverseListBase() {
     checkValid();
     if (!isAllocatedInline())
       delete[] Begin;
   }
 };

 /// An "abstract" base class for DiverseList<T> which does not
 /// explicitly set the preferred inline capacity.  Most of the
 /// implementation is in this class.
 template <class T> class DiverseListImpl : private DiverseListBase {
   DiverseListImpl(const DiverseListImpl<T> &other) = delete;
   DiverseListImpl(DiverseListImpl<T> &&other) = delete;

 protected:
   DiverseListImpl(char *endOfAllocation) {
     initialize(endOfAllocation);
   }

   DiverseListImpl(const DiverseListImpl<T> &other, char *endOfAllocation) {
     initialize(endOfAllocation);
     copyFrom(other);
   }
   DiverseListImpl(DiverseListImpl<T> &&other, char *endOfAllocation) {
     // If the other is allocated inline, just initialize and copy.
     if (other.isAllocatedInline()) {
       initialize(endOfAllocation);
       copyFrom(other);
       return;
     }

     // Otherwise, steal its allocations.
     Begin = other.Begin;
     End = other.End;
     EndOfAllocation = other.EndOfAllocation;
     other.Begin = other.End = other.EndOfAllocation = (char*) (&other + 1);
     assert(other.isAllocatedInline());
   }

 public:
   /// Query whether the stack is empty.
   bool empty() const {
     checkValid();
     return Begin == End;
   }

   /// Return a reference to the first element in the list.
   T &front() {
     assert(!empty());
     return *reinterpret_cast<T*>(Begin);
   }

   /// Return a reference to the first element in the list.
   const T &front() const {
     assert(!empty());
     return *reinterpret_cast<const T*>(Begin);
   }

   class const_iterator;
   class iterator {
     char *Ptr;
     friend class DiverseListImpl;
     friend class const_iterator;
     iterator(char *ptr) : Ptr(ptr) {}

   public:
     iterator() = default;

     T &operator*() const { return *reinterpret_cast<T*>(Ptr); }
     T *operator->() const { return reinterpret_cast<T*>(Ptr); }
     iterator &operator++() {
       Ptr += (*this)->allocated_size();
       return *this;
     }
     iterator operator++(int _) {
       auto copy = *this;
       operator++();
       return copy;
     }

     /// advancePast - Like operator++, but asserting that the current
     /// object has a known type.
     template <class U> void advancePast() {
       assert((*this)->allocated_size() == sizeof(U));
       Ptr += sizeof(U);
     }

     friend bool operator==(iterator a, iterator b) { return a.Ptr == b.Ptr; }
     friend bool operator!=(iterator a, iterator b) { return !operator==(a, b); }
   };
   iterator begin() { checkValid(); return iterator(Begin); }
   iterator end() { checkValid(); return iterator(End); }
   iterator find(stable_iterator it) {
     checkValid();
     assert(it.Offset <= End - Begin);
     return iterator(Begin + it.Offset);
   }
   stable_iterator stabilize(iterator it) const {
     checkValid();
     assert(Begin <= it.Ptr && it.Ptr <= End);
     return stable_iterator(it.Ptr - Begin);
   }

   class const_iterator {
     const char *Ptr;
     friend class DiverseListImpl;
     const_iterator(const char *ptr) : Ptr(ptr) {}
   public:
     const_iterator() = default;
     const_iterator(iterator it) : Ptr(it.Ptr) {}

     const T &operator*() const { return *reinterpret_cast<const T*>(Ptr); }
     const T *operator->() const { return reinterpret_cast<const T*>(Ptr); }
     const_iterator &operator++() {
       Ptr += (*this)->allocated_size();
       return *this;
     }
     const_iterator operator++(int _) {
       auto copy = *this;
       operator++();
       return copy;
     }

     /// advancePast - Like operator++, but asserting that the current
     /// object has a known type.
     template <class U> void advancePast() {
       assert((*this)->allocated_size() == sizeof(U));
       Ptr += sizeof(U);
     }

     friend bool operator==(const_iterator a, const_iterator b) {
       return a.Ptr == b.Ptr;
     }
     friend bool operator!=(const_iterator a, const_iterator b) {
       return !operator==(a, b);
     }
   };
   const_iterator begin() const { checkValid(); return const_iterator(Begin); }
   const_iterator end() const { checkValid(); return const_iterator(End); }
   const_iterator find(stable_iterator it) const {
     checkValid();
     assert(it.Offset <= End - Begin);
     return const_iterator(Begin + it.Offset);
   }
   stable_iterator stabilize(const_iterator it) const {
     checkValid();
     assert(Begin <= it.Ptr && it.Ptr <= End);
     return stable_iterator(it.Ptr - Begin);
   }

   /// Add a new object onto the end of the list.
   template <class U, class... A> U &add(A && ...args) {
     char *storage = addNewStorage(sizeof(U));
     U &newObject = *::new (storage) U(::std::forward<A>(args)...);
     return newObject;
   }

   /// Add a new object onto the end of the list with some extra storage.
   template <class U, class... A> U &addWithExtra(size_t extra, A && ...args) {
     char *storage = addNewStorage(sizeof(U) + extra);
     U &newObject = *::new (storage) U(::std::forward<A>(args)...);
     return newObject;
   }
 };

 } // end namespace swift

 #endif // SWIFT_BASIC_DIVERSELIST_H
	//===--- DiverseList.h - List of variably-sized objects ---------- C++ --===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//
	//
	// This file defines a data structure for representing a list of
	// variably-sized objects. It is a requirement that the object type
	// be trivially movable, meaning that it has a trivial move
	// constructor and a trivial destructor.
	//
	//===----------------------------------------------------------------------===//

	#ifndef SWIFT_BASIC_DIVERSELIST_H
	#define SWIFT_BASIC_DIVERSELIST_H

	#include "swift/Basic/Malloc.h"
	#include <cassert>
	#include <cstring>
	#include <utility>

	namespace swift {

	template <class T> class DiverseListImpl;

	/// DiverseList - A list of heterogeneously-typed objects.
	///
	/// \tparam T - A common base class of the objects in the list; must
	/// provide an allocated_size() const method.
	/// \tparam InlineCapacity - the amount of inline storage to provide, in bytes.
	template <class T, unsigned InlineCapacity>
	class DiverseList : public DiverseListImpl<T> {
	char InlineStorage[InlineCapacity];

	public:
	DiverseList() : DiverseListImpl<T>(InlineStorage + InlineCapacity) {}
	DiverseList(const DiverseList &other)
	: DiverseListImpl<T>(other, InlineStorage + InlineCapacity) {}
	DiverseList(const DiverseListImpl<T> &other)
	: DiverseListImpl<T>(other, InlineStorage + InlineCapacity) {}
	DiverseList(DiverseList<T, InlineCapacity> &&other)
	: DiverseListImpl<T>(std::move(other), InlineStorage + InlineCapacity) {}
	DiverseList(DiverseListImpl<T> &&other)
	: DiverseListImpl<T>(std::move(other), InlineStorage + InlineCapacity) {}
	};

	/// A base class for DiverseListImpl.
	class DiverseListBase {
	public:
	/// The first element in the list and the beginning of the allocation.
	char *Begin;

	/// A pointer past the last element in the list.
	char *End;

	/// A pointer past the end of the allocation.
	char *EndOfAllocation;

	bool isAllocatedInline() const {
	return (Begin == reinterpret_cast<const char *>(this + 1));
	}

	void checkValid() const {
	assert(Begin <= End);
	assert(End <= EndOfAllocation);
	}

	void initialize(char *endOfAllocation) {
	EndOfAllocation = endOfAllocation;
	Begin = End = reinterpret_cast<char*>(this + 1);
	}
	void copyFrom(const DiverseListBase &other) {
	// Ensure that we're large enough to store all the data.
	std::size_t size = static_cast<std::size_t>(other.End - other.Begin);
	char *newStorage = addNewStorage(size);
	std::memcpy(newStorage, other.Begin, size);
	}
	char *addNewStorage(std::size_t needed) {
	checkValid();
	if (std::size_t(EndOfAllocation - End) >= needed) {
	char *newStorage = End;
	End += needed;
	return newStorage;
	}
	return addNewStorageSlow(needed);
	}
	char *addNewStorageSlow(std::size_t needed);

	/// A stable iterator is the equivalent of an index into the list.
	/// It's an iterator that stays stable across modification of the
	/// list.
	class stable_iterator {
	std::size_t Offset;
	friend class DiverseListBase;
	template <class T> friend class DiverseListImpl;
	stable_iterator(std::size_t offset) : Offset(offset) {}
	public:
	stable_iterator() = default;
	friend bool operator==(stable_iterator a, stable_iterator b) {
	return a.Offset == b.Offset;
	}
	friend bool operator!=(stable_iterator a, stable_iterator b) {
	return !operator==(a, b);
	}
	};
	stable_iterator stable_begin() const {
	return stable_iterator(0);
	}
	stable_iterator stable_end() {
	return stable_iterator(std::size_t(End - Begin));
	}

	protected:
	~DiverseListBase() {
	checkValid();
	if (!isAllocatedInline())
	delete[] Begin;
	}
	};

	/// An "abstract" base class for DiverseList<T> which does not
	/// explicitly set the preferred inline capacity. Most of the
	/// implementation is in this class.
	template <class T> class DiverseListImpl : private DiverseListBase {
	DiverseListImpl(const DiverseListImpl<T> &other) = delete;
	DiverseListImpl(DiverseListImpl<T> &&other) = delete;

	protected:
	DiverseListImpl(char *endOfAllocation) {
	initialize(endOfAllocation);
	}

	DiverseListImpl(const DiverseListImpl<T> &other, char *endOfAllocation) {
	initialize(endOfAllocation);
	copyFrom(other);
	}
	DiverseListImpl(DiverseListImpl<T> &&other, char *endOfAllocation) {
	// If the other is allocated inline, just initialize and copy.
	if (other.isAllocatedInline()) {
	initialize(endOfAllocation);
	copyFrom(other);
	return;
	}

	// Otherwise, steal its allocations.
	Begin = other.Begin;
	End = other.End;
	EndOfAllocation = other.EndOfAllocation;
	other.Begin = other.End = other.EndOfAllocation = (char*) (&other + 1);
	assert(other.isAllocatedInline());
	}

	public:
	/// Query whether the stack is empty.
	bool empty() const {
	checkValid();
	return Begin == End;
	}

	/// Return a reference to the first element in the list.
	T &front() {
	assert(!empty());
	return reinterpret_cast<T>(Begin);
	}

	/// Return a reference to the first element in the list.
	const T &front() const {
	assert(!empty());
	return reinterpret_cast<const T>(Begin);
	}

	class const_iterator;
	class iterator {
	char *Ptr;
	friend class DiverseListImpl;
	friend class const_iterator;
	iterator(char *ptr) : Ptr(ptr) {}

	public:
	iterator() = default;

	T &operator() const { return reinterpret_cast<T*>(Ptr); }
	T operator->() const { return reinterpret_cast<T>(Ptr); }
	iterator &operator++() {
	Ptr += (*this)->allocated_size();
	return *this;
	}
	iterator operator++(int _) {
	auto copy = *this;
	operator++();
	return copy;
	}

	/// advancePast - Like operator++, but asserting that the current
	/// object has a known type.
	template <class U> void advancePast() {
	assert((*this)->allocated_size() == sizeof(U));
	Ptr += sizeof(U);
	}

	friend bool operator==(iterator a, iterator b) { return a.Ptr == b.Ptr; }
	friend bool operator!=(iterator a, iterator b) { return !operator==(a, b); }
	};
	iterator begin() { checkValid(); return iterator(Begin); }
	iterator end() { checkValid(); return iterator(End); }
	iterator find(stable_iterator it) {
	checkValid();
	assert(it.Offset <= End - Begin);
	return iterator(Begin + it.Offset);
	}
	stable_iterator stabilize(iterator it) const {
	checkValid();
	assert(Begin <= it.Ptr && it.Ptr <= End);
	return stable_iterator(it.Ptr - Begin);
	}

	class const_iterator {
	const char *Ptr;
	friend class DiverseListImpl;
	const_iterator(const char *ptr) : Ptr(ptr) {}
	public:
	const_iterator() = default;
	const_iterator(iterator it) : Ptr(it.Ptr) {}

	const T &operator() const { return reinterpret_cast<const T*>(Ptr); }
	const T operator->() const { return reinterpret_cast<const T>(Ptr); }
	const_iterator &operator++() {
	Ptr += (*this)->allocated_size();
	return *this;
	}
	const_iterator operator++(int _) {
	auto copy = *this;
	operator++();
	return copy;
	}

	/// advancePast - Like operator++, but asserting that the current
	/// object has a known type.
	template <class U> void advancePast() {
	assert((*this)->allocated_size() == sizeof(U));
	Ptr += sizeof(U);
	}

	friend bool operator==(const_iterator a, const_iterator b) {
	return a.Ptr == b.Ptr;
	}
	friend bool operator!=(const_iterator a, const_iterator b) {
	return !operator==(a, b);
	}
	};
	const_iterator begin() const { checkValid(); return const_iterator(Begin); }
	const_iterator end() const { checkValid(); return const_iterator(End); }
	const_iterator find(stable_iterator it) const {
	checkValid();
	assert(it.Offset <= End - Begin);
	return const_iterator(Begin + it.Offset);
	}
	stable_iterator stabilize(const_iterator it) const {
	checkValid();
	assert(Begin <= it.Ptr && it.Ptr <= End);
	return stable_iterator(it.Ptr - Begin);
	}

	/// Add a new object onto the end of the list.
	template <class U, class... A> U &add(A && ...args) {
	char *storage = addNewStorage(sizeof(U));
	U &newObject = *::new (storage) U(::std::forward<A>(args)...);
	return newObject;
	}

	/// Add a new object onto the end of the list with some extra storage.
	template <class U, class... A> U &addWithExtra(size_t extra, A && ...args) {
	char *storage = addNewStorage(sizeof(U) + extra);
	U &newObject = *::new (storage) U(::std::forward<A>(args)...);
	return newObject;
	}
	};

	} // end namespace swift

	#endif // SWIFT_BASIC_DIVERSELIST_H