WebSVN – QNX 8.QNX8 LLVM/Clang compiler suite – Blame – /llvm-build/x86_64/include/llvm/Support/ArrayRecycler.h

Rev	Author	Line No.	Line
14	pmbaty	1	//==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------- C++ --==//
		2	//
		3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
		4	// See https://llvm.org/LICENSE.txt for license information.
		5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
		6	//
		7	//===----------------------------------------------------------------------===//
		8	//
		9	// This file defines the ArrayRecycler class template which can recycle small
		10	// arrays allocated from one of the allocators in Allocator.h
		11	//
		12	//===----------------------------------------------------------------------===//
		13
		14	#ifndef LLVM_SUPPORT_ARRAYRECYCLER_H
		15	#define LLVM_SUPPORT_ARRAYRECYCLER_H
		16
		17	#include "llvm/ADT/SmallVector.h"
		18	#include "llvm/Support/Allocator.h"
		19	#include "llvm/Support/MathExtras.h"
		20
		21	namespace llvm {
		22
		23	/// Recycle small arrays allocated from a BumpPtrAllocator.
		24	///
		25	/// Arrays are allocated in a small number of fixed sizes. For each supported
		26	/// array size, the ArrayRecycler keeps a free list of available arrays.
		27	///
		28	template <class T, size_t Align = alignof(T)> class ArrayRecycler {
		29	// The free list for a given array size is a simple singly linked list.
		30	// We can't use iplist or Recycler here since those classes can't be copied.
		31	struct FreeList {
		32	FreeList *Next;
		33	};
		34
		35	static_assert(Align >= alignof(FreeList), "Object underaligned");
		36	static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small");
		37
		38	// Keep a free list for each array size.
		39	SmallVector<FreeList*, 8> Bucket;
		40
		41	// Remove an entry from the free list in Bucket[Idx] and return it.
		42	// Return NULL if no entries are available.
		43	T *pop(unsigned Idx) {
		44	if (Idx >= Bucket.size())
		45	return nullptr;
		46	FreeList *Entry = Bucket[Idx];
		47	if (!Entry)
		48	return nullptr;
		49	__asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
		50	Bucket[Idx] = Entry->Next;
		51	__msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
		52	return reinterpret_cast<T*>(Entry);
		53	}
		54
		55	// Add an entry to the free list at Bucket[Idx].
		56	void push(unsigned Idx, T *Ptr) {
		57	assert(Ptr && "Cannot recycle NULL pointer");
		58	FreeList Entry = reinterpret_cast<FreeList>(Ptr);
		59	if (Idx >= Bucket.size())
		60	Bucket.resize(size_t(Idx) + 1);
		61	Entry->Next = Bucket[Idx];
		62	Bucket[Idx] = Entry;
		63	__asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
		64	}
		65
		66	public:
		67	/// The size of an allocated array is represented by a Capacity instance.
		68	///
		69	/// This class is much smaller than a size_t, and it provides methods to work
		70	/// with the set of legal array capacities.
		71	class Capacity {
		72	uint8_t Index;
		73	explicit Capacity(uint8_t idx) : Index(idx) {}
		74
		75	public:
		76	Capacity() : Index(0) {}
		77
		78	/// Get the capacity of an array that can hold at least N elements.
		79	static Capacity get(size_t N) {
		80	return Capacity(N ? Log2_64_Ceil(N) : 0);
		81	}
		82
		83	/// Get the number of elements in an array with this capacity.
		84	size_t getSize() const { return size_t(1u) << Index; }
		85
		86	/// Get the bucket number for this capacity.
		87	unsigned getBucket() const { return Index; }
		88
		89	/// Get the next larger capacity. Large capacities grow exponentially, so
		90	/// this function can be used to reallocate incrementally growing vectors
		91	/// in amortized linear time.
		92	Capacity getNext() const { return Capacity(Index + 1); }
		93	};
		94
		95	~ArrayRecycler() {
		96	// The client should always call clear() so recycled arrays can be returned
		97	// to the allocator.
		98	assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
		99	}
		100
		101	/// Release all the tracked allocations to the allocator. The recycler must
		102	/// be free of any tracked allocations before being deleted.
		103	template<class AllocatorType>
		104	void clear(AllocatorType &Allocator) {
		105	for (; !Bucket.empty(); Bucket.pop_back())
		106	while (T *Ptr = pop(Bucket.size() - 1))
		107	Allocator.Deallocate(Ptr);
		108	}
		109
		110	/// Special case for BumpPtrAllocator which has an empty Deallocate()
		111	/// function.
		112	///
		113	/// There is no need to traverse the free lists, pulling all the objects into
		114	/// cache.
		115	void clear(BumpPtrAllocator&) {
		116	Bucket.clear();
		117	}
		118
		119	/// Allocate an array of at least the requested capacity.
		120	///
		121	/// Return an existing recycled array, or allocate one from Allocator if
		122	/// none are available for recycling.
		123	///
		124	template<class AllocatorType>
		125	T *allocate(Capacity Cap, AllocatorType &Allocator) {
		126	// Try to recycle an existing array.
		127	if (T *Ptr = pop(Cap.getBucket()))
		128	return Ptr;
		129	// Nope, get more memory.
		130	return static_cast<T>(Allocator.Allocate(sizeof(T)Cap.getSize(), Align));
		131	}
		132
		133	/// Deallocate an array with the specified Capacity.
		134	///
		135	/// Cap must be the same capacity that was given to allocate().
		136	///
		137	void deallocate(Capacity Cap, T *Ptr) {
		138	push(Cap.getBucket(), Ptr);
		139	}
		140	};
		141
		142	} // end llvm namespace
		143
		144	#endif

Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

QNX 8.QNX8 LLVM/Clang compiler suite/llvm-build/x86_64/include/llvm/Support/ArrayRecycler.h – Rev 14