Loading...
Searching...
No Matches
block_storage.h
Go to the documentation of this file.
#ifndef HALIDE_RUNTIME_BLOCK_STORAGE_H
#define HALIDE_RUNTIME_BLOCK_STORAGE_H
#include "../HalideRuntime.h"
#include "../printer.h"
#include "memory_resources.h"
namespace Halide {
namespace Runtime {
namespace Internal {
// Dynamically resizable array for block storage (eg plain old data)
// -- No usage of constructors/destructors for value type
// -- Assumes all elements stored are uniformly the same fixed size
// -- Allocations are done in blocks of a fixed size
// -- Implementation uses memcpy/memmove for copying
// -- Customizable allocator ... default uses NativeSystemAllocator
class BlockStorage {
public:
static constexpr size_t default_capacity = 32; // smallish
// Configurable parameters
struct Config {
uint32_t entry_size = 1; // bytes per entry
uint32_t block_size = 32; // bytes per each allocation block
uint32_t minimum_capacity = default_capacity;
};
BlockStorage(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma = default_allocator());
BlockStorage(const BlockStorage &other);
~BlockStorage();
void initialize(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma = default_allocator());
BlockStorage &operator=(const BlockStorage &other);
bool operator==(const BlockStorage &other) const;
bool operator!=(const BlockStorage &other) const;
void reserve(void *user_context, size_t capacity, bool free_existing = false);
void resize(void *user_context, size_t entry_count, bool realloc = true);
void assign(void *user_context, size_t index, const void *entry_ptr);
void insert(void *user_context, size_t index, const void *entry_ptr);
void prepend(void *user_context, const void *entry_ptr);
void append(void *user_context, const void *entry_ptr);
void remove(void *user_context, size_t index);
void fill(void *user_context, const void *array, size_t array_size);
void insert(void *user_context, size_t index, const void *array, size_t array_size);
void replace(void *user_context, size_t index, const void *array, size_t array_size);
void prepend(void *user_context, const void *array, size_t array_size);
void append(void *user_context, const void *array, size_t array_size);
void remove(void *user_context, size_t index, size_t entry_count);
void pop_front(void *user_context);
void pop_back(void *user_context);
void shrink_to_fit(void *user_context);
void clear(void *user_context);
void destroy(void *user_context);
bool empty() const;
bool full() const;
bool is_valid(size_t index) const;
size_t stride() const;
size_t size() const;
void *operator[](size_t index); ///< logical entry index (returns ptr = data() + (index * stride())
const void *operator[](size_t index) const;
void *data();
void *front();
void *back();
const void *data() const;
const void *front() const;
const void *back() const;
const Config &current_config() const;
static const Config &default_config();
const SystemMemoryAllocatorFns &current_allocator() const;
static const SystemMemoryAllocatorFns &default_allocator();
private:
void allocate(void *user_context, size_t capacity);
void *ptr = nullptr;
size_t count = 0;
size_t capacity = 0;
Config config;
SystemMemoryAllocatorFns allocator;
};
BlockStorage::BlockStorage(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma)
: config(cfg), allocator(sma) {
halide_abort_if_false(user_context, config.entry_size != 0);
halide_abort_if_false(user_context, allocator.allocate != nullptr);
halide_abort_if_false(user_context, allocator.deallocate != nullptr);
if (config.minimum_capacity) {
reserve(user_context, config.minimum_capacity);
}
}
BlockStorage::BlockStorage(const BlockStorage &other)
: BlockStorage(nullptr, other.config, other.allocator) {
if (other.count) {
resize(nullptr, other.count);
memcpy(this->ptr, other.ptr, count * config.entry_size);
}
}
BlockStorage::~BlockStorage() {
destroy(nullptr);
}
void BlockStorage::destroy(void *user_context) {
halide_abort_if_false(user_context, allocator.deallocate != nullptr);
if (ptr != nullptr) {
allocator.deallocate(user_context, ptr);
}
capacity = count = 0;
ptr = nullptr;
}
void BlockStorage::initialize(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma) {
allocator = sma;
config = cfg;
capacity = count = 0;
ptr = nullptr;
if (config.minimum_capacity) {
reserve(user_context, config.minimum_capacity);
}
}
BlockStorage &BlockStorage::operator=(const BlockStorage &other) {
if (&other != this) {
config = other.config;
resize(nullptr, other.count);
if (count != 0 && other.ptr != nullptr) {
memcpy(ptr, other.ptr, count * config.entry_size);
}
}
return *this;
}
bool BlockStorage::operator==(const BlockStorage &other) const {
if (config.entry_size != other.config.entry_size) {
return false;
}
if (count != other.count) {
return false;
}
return memcmp(this->ptr, other.ptr, this->size() * config.entry_size) == 0;
}
bool BlockStorage::operator!=(const BlockStorage &other) const {
return !(*this == other);
}
void BlockStorage::fill(void *user_context, const void *array, size_t array_size) {
if (array_size != 0) {
resize(user_context, array_size);
memcpy(this->ptr, array, array_size * config.entry_size);
count = array_size;
}
}
void BlockStorage::assign(void *user_context, size_t index, const void *entry_ptr) {
replace(user_context, index, entry_ptr, 1);
}
void BlockStorage::prepend(void *user_context, const void *entry_ptr) {
insert(user_context, 0, entry_ptr, 1);
}
void BlockStorage::append(void *user_context, const void *entry_ptr) {
append(user_context, entry_ptr, 1);
}
void BlockStorage::pop_front(void *user_context) {
halide_abort_if_false(user_context, count > 0);
remove(user_context, 0);
}
void BlockStorage::pop_back(void *user_context) {
halide_abort_if_false(user_context, count > 0);
resize(user_context, size() - 1);
}
void BlockStorage::clear(void *user_context) {
resize(user_context, 0);
}
void BlockStorage::reserve(void *user_context, size_t new_capacity, bool free_existing) {
new_capacity = max(new_capacity, count);
if ((new_capacity < capacity) && !free_existing) {
new_capacity = capacity;
}
allocate(user_context, new_capacity);
}
void BlockStorage::resize(void *user_context, size_t entry_count, bool realloc) {
size_t current_size = capacity;
size_t requested_size = entry_count;
size_t minimum_size = config.minimum_capacity;
size_t actual_size = current_size;
count = requested_size;
// increase capacity upto 1.5x existing (or at least min_capacity)
if (requested_size > current_size) {
actual_size = max(requested_size, max(current_size * 3 / 2, minimum_size));
} else if (!realloc) {
return;
}
#ifdef DEBUG_RUNTIME_INTERNAL
debug(user_context) << "BlockStorage: Resize ("
<< "requested_size=" << (int32_t)requested_size << " "
<< "current_size=" << (int32_t)current_size << " "
<< "minimum_size=" << (int32_t)minimum_size << " "
<< "actual_size=" << (int32_t)actual_size << " "
<< "entry_size=" << (int32_t)config.entry_size << " "
<< "realloc=" << (realloc ? "true" : "false") << ")...\n";
#endif
allocate(user_context, actual_size);
}
void BlockStorage::shrink_to_fit(void *user_context) {
if (capacity > count) {
void *new_ptr = nullptr;
if (count > 0) {
size_t actual_bytes = count * config.entry_size;
new_ptr = allocator.allocate(user_context, actual_bytes);
memcpy(new_ptr, ptr, actual_bytes);
}
allocator.deallocate(user_context, ptr);
capacity = count;
ptr = new_ptr;
}
}
void BlockStorage::insert(void *user_context, size_t index, const void *entry_ptr) {
insert(user_context, index, entry_ptr, 1);
}
void BlockStorage::remove(void *user_context, size_t index) {
remove(user_context, index, 1);
}
void BlockStorage::remove(void *user_context, size_t index, size_t entry_count) {
halide_abort_if_false(user_context, index < count);
const size_t last_index = size();
if (index < (last_index - entry_count)) {
size_t dst_offset = index * config.entry_size;
size_t src_offset = (index + entry_count) * config.entry_size;
size_t bytes = (last_index - index - entry_count) * config.entry_size;
#ifdef DEBUG_RUNTIME_INTERNAL
debug(user_context) << "BlockStorage: Remove ("
<< "index=" << (int32_t)index << " "
<< "entry_count=" << (int32_t)entry_count << " "
<< "entry_size=" << (int32_t)config.entry_size << " "
<< "last_index=" << (int32_t)last_index << " "
<< "src_offset=" << (int32_t)src_offset << " "
<< "dst_offset=" << (int32_t)dst_offset << " "
<< "bytes=" << (int32_t)bytes << ")...\n";
#endif
void *dst_ptr = offset_address(ptr, dst_offset);
void *src_ptr = offset_address(ptr, src_offset);
memmove(dst_ptr, src_ptr, bytes);
}
resize(user_context, last_index - entry_count);
}
void BlockStorage::replace(void *user_context, size_t index, const void *array, size_t array_size) {
halide_abort_if_false(user_context, index < count);
size_t offset = index * config.entry_size;
size_t remaining = count - index;
#if DEBUG
debug(user_context) << "BlockStorage: Replace ("
<< "index=" << (int32_t)index << " "
<< "array_size=" << (int32_t)array_size << " "
<< "entry_size=" << (int32_t)config.entry_size << " "
<< "offset=" << (int32_t)offset << " "
<< "remaining=" << (int32_t)remaining << " "
<< "capacity=" << (int32_t)capacity << ")...\n";
#endif
halide_abort_if_false(user_context, remaining > 0);
size_t copy_count = min(remaining, array_size);
void *dst_ptr = offset_address(ptr, offset);
memcpy(dst_ptr, array, copy_count * config.entry_size);
count = max(count, index + copy_count);
}
void BlockStorage::insert(void *user_context, size_t index, const void *array, size_t array_size) {
halide_abort_if_false(user_context, index <= count);
const size_t last_index = size();
resize(user_context, last_index + array_size);
if (index < last_index) {
size_t src_offset = index * config.entry_size;
size_t dst_offset = (index + array_size) * config.entry_size;
size_t bytes = (last_index - index) * config.entry_size;
void *src_ptr = offset_address(ptr, src_offset);
void *dst_ptr = offset_address(ptr, dst_offset);
memmove(dst_ptr, src_ptr, bytes);
}
replace(user_context, index, array, array_size);
}
void BlockStorage::prepend(void *user_context, const void *array, size_t array_size) {
insert(user_context, 0, array, array_size);
}
void BlockStorage::append(void *user_context, const void *array, size_t array_size) {
const size_t last_index = size();
insert(user_context, last_index, array, array_size);
}
bool BlockStorage::empty() const {
return count == 0;
}
bool BlockStorage::full() const {
return (count >= capacity);
}
bool BlockStorage::is_valid(size_t index) const {
return (index < capacity);
}
size_t BlockStorage::size() const {
return count;
}
size_t BlockStorage::stride() const {
return config.entry_size;
}
void *BlockStorage::operator[](size_t index) {
halide_abort_if_false(nullptr, index < capacity);
return offset_address(ptr, index * config.entry_size);
}
const void *BlockStorage::operator[](size_t index) const {
halide_abort_if_false(nullptr, index < capacity);
return offset_address(ptr, index * config.entry_size);
}
void *BlockStorage::data() {
return ptr;
}
void *BlockStorage::front() {
halide_abort_if_false(nullptr, count > 0);
return ptr;
}
void *BlockStorage::back() {
halide_abort_if_false(nullptr, count > 0);
size_t index = count - 1;
return offset_address(ptr, index * config.entry_size);
}
const void *BlockStorage::data() const {
return ptr;
}
const void *BlockStorage::front() const {
halide_abort_if_false(nullptr, count > 0);
return ptr;
}
const void *BlockStorage::back() const {
halide_abort_if_false(nullptr, count > 0);
size_t index = count - 1;
return offset_address(ptr, index * config.entry_size);
}
void BlockStorage::allocate(void *user_context, size_t new_capacity) {
if (new_capacity != capacity) {
halide_abort_if_false(user_context, allocator.allocate != nullptr);
size_t requested_bytes = new_capacity * config.entry_size;
size_t block_size = max(config.block_size, config.entry_size);
size_t block_count = (requested_bytes / block_size);
block_count += (requested_bytes % block_size) ? 1 : 0;
size_t alloc_size = block_count * block_size;
#ifdef DEBUG_RUNTIME_INTERNAL
debug(user_context) << "BlockStorage: Allocating ("
<< "requested_bytes=" << (int32_t)requested_bytes << " "
<< "block_size=" << (int32_t)block_size << " "
<< "block_count=" << (int32_t)block_count << " "
<< "alloc_size=" << (int32_t)alloc_size << ") ...\n";
#endif
void *new_ptr = alloc_size ? allocator.allocate(user_context, alloc_size) : nullptr;
if (count != 0 && ptr != nullptr && new_ptr != nullptr) {
memcpy(new_ptr, ptr, count * config.entry_size);
}
if (ptr != nullptr) {
halide_abort_if_false(user_context, allocator.deallocate != nullptr);
allocator.deallocate(user_context, ptr);
}
capacity = new_capacity;
ptr = new_ptr;
}
}
const SystemMemoryAllocatorFns &
BlockStorage::current_allocator() const {
return this->allocator;
}
const BlockStorage::Config &
BlockStorage::default_config() {
static Config default_cfg;
return default_cfg;
}
const BlockStorage::Config &
BlockStorage::current_config() const {
return this->config;
}
const SystemMemoryAllocatorFns &
BlockStorage::default_allocator() {
static SystemMemoryAllocatorFns native_allocator = {
native_system_malloc, native_system_free};
return native_allocator;
}
// --
} // namespace Internal
} // namespace Runtime
} // namespace Halide
#endif // HALIDE_RUNTIME_BLOCK_STORAGE_H
debug
#define debug(n)
For optional debugging during codegen, use the debug macro as follows:
Definition Debug.h:52
HalideRuntime.h
This file declares the routines used by Halide internally in its runtime.
Halide::Runtime::Internal::BlockStorage::stride
size_t stride() const
Definition block_storage.h:340
Halide::Runtime::Internal::BlockStorage::current_config
const Config & current_config() const
Definition block_storage.h:424
Halide::Runtime::Internal::BlockStorage::operator=
BlockStorage & operator=(const BlockStorage &other)
Definition block_storage.h:135
Halide::Runtime::Internal::BlockStorage::operator[]
void * operator[](size_t index)
logical entry index (returns ptr = data() + (index * stride())
Definition block_storage.h:344
Halide::Runtime::Internal::BlockStorage::front
void * front()
Definition block_storage.h:358
Halide::Runtime::Internal::BlockStorage::full
bool full() const
Definition block_storage.h:328
Halide::Runtime::Internal::BlockStorage::shrink_to_fit
void shrink_to_fit(void *user_context)
Definition block_storage.h:231
Halide::Runtime::Internal::BlockStorage::pop_front
void pop_front(void *user_context)
Definition block_storage.h:180
Halide::Runtime::Internal::BlockStorage::destroy
void destroy(void *user_context)
Definition block_storage.h:116
Halide::Runtime::Internal::BlockStorage::size
size_t size() const
Definition block_storage.h:336
Halide::Runtime::Internal::BlockStorage::back
void * back()
Definition block_storage.h:363
Halide::Runtime::Internal::BlockStorage::clear
void clear(void *user_context)
Definition block_storage.h:190
Halide::Runtime::Internal::BlockStorage::default_capacity
static constexpr size_t default_capacity
Definition block_storage.h:20
Halide::Runtime::Internal::BlockStorage::operator!=
bool operator!=(const BlockStorage &other) const
Definition block_storage.h:156
Halide::Runtime::Internal::BlockStorage::resize
void resize(void *user_context, size_t entry_count, bool realloc=true)
Definition block_storage.h:204
Halide::Runtime::Internal::BlockStorage::default_config
static const Config & default_config()
Definition block_storage.h:418
Halide::Runtime::Internal::BlockStorage::replace
void replace(void *user_context, size_t index, const void *array, size_t array_size)
Definition block_storage.h:278
Halide::Runtime::Internal::BlockStorage::prepend
void prepend(void *user_context, const void *entry_ptr)
Definition block_storage.h:172
Halide::Runtime::Internal::BlockStorage::remove
void remove(void *user_context, size_t index)
Definition block_storage.h:249
Halide::Runtime::Internal::BlockStorage::assign
void assign(void *user_context, size_t index, const void *entry_ptr)
Definition block_storage.h:168
Halide::Runtime::Internal::BlockStorage::data
void * data()
Definition block_storage.h:354
Halide::Runtime::Internal::BlockStorage::insert
void insert(void *user_context, size_t index, const void *entry_ptr)
Definition block_storage.h:245
Halide::Runtime::Internal::BlockStorage::initialize
void initialize(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma=default_allocator())
Definition block_storage.h:125
Halide::Runtime::Internal::BlockStorage::default_allocator
static const SystemMemoryAllocatorFns & default_allocator()
Definition block_storage.h:429
Halide::Runtime::Internal::BlockStorage::empty
bool empty() const
Definition block_storage.h:324
Halide::Runtime::Internal::BlockStorage::current_allocator
const SystemMemoryAllocatorFns & current_allocator() const
Definition block_storage.h:413
Halide::Runtime::Internal::BlockStorage::operator==
bool operator==(const BlockStorage &other) const
Definition block_storage.h:146
Halide::Runtime::Internal::BlockStorage::~BlockStorage
~BlockStorage()
Definition block_storage.h:112
Halide::Runtime::Internal::BlockStorage::append
void append(void *user_context, const void *entry_ptr)
Definition block_storage.h:176
Halide::Runtime::Internal::BlockStorage::BlockStorage
BlockStorage(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma=default_allocator())
Definition block_storage.h:94
Halide::Runtime::Internal::BlockStorage::is_valid
bool is_valid(size_t index) const
Definition block_storage.h:332
Halide::Runtime::Internal::BlockStorage::fill
void fill(void *user_context, const void *array, size_t array_size)
Definition block_storage.h:160
Halide::Runtime::Internal::BlockStorage::reserve
void reserve(void *user_context, size_t capacity, bool free_existing=false)
Definition block_storage.h:194
Halide::Runtime::Internal::BlockStorage::pop_back
void pop_back(void *user_context)
Definition block_storage.h:185
memory_resources.h
Halide::Runtime::Internal
Definition constants.h:13
Halide::Runtime::Internal::native_system_malloc
ALWAYS_INLINE void * native_system_malloc(void *user_context, size_t bytes)
Definition memory_resources.h:185
Halide::Runtime::Internal::native_system_free
ALWAYS_INLINE void native_system_free(void *user_context, void *ptr)
Definition memory_resources.h:189
Halide::Runtime::Internal::offset_address
ALWAYS_INLINE const void * offset_address(const void *address, size_t byte_offset)
Definition memory_resources.h:169
Halide::Runtime
Definition constants.h:12
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition AbstractGenerator.h:19
Halide::min
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition Func.h:603
Halide::max
Expr max(const FuncRef &a, const FuncRef &b)
Definition Func.h:606
printer.h
memmove
void * memmove(void *dest, const void *src, size_t n)
int32_t
signed __INT32_TYPE__ int32_t
Definition runtime_internal.h:24
memcpy
void * memcpy(void *s1, const void *s2, size_t n)
memcmp
int memcmp(const void *s1, const void *s2, size_t n)
uint32_t
unsigned __INT32_TYPE__ uint32_t
Definition runtime_internal.h:25
halide_abort_if_false
#define halide_abort_if_false(user_context, cond)
Definition runtime_internal.h:271
Halide::Runtime::Internal::BlockStorage::Config
Definition block_storage.h:23
Halide::Runtime::Internal::BlockStorage::Config::block_size
uint32_t block_size
Definition block_storage.h:25
Halide::Runtime::Internal::BlockStorage::Config::minimum_capacity
uint32_t minimum_capacity
Definition block_storage.h:26
Halide::Runtime::Internal::BlockStorage::Config::entry_size
uint32_t entry_size
Definition block_storage.h:24
Halide::Runtime::Internal::SystemMemoryAllocatorFns
Definition memory_resources.h:193
Halide::Runtime::Internal::SystemMemoryAllocatorFns::deallocate
DeallocateSystemFn deallocate
Definition memory_resources.h:195
Halide::Runtime::Internal::SystemMemoryAllocatorFns::allocate
AllocateSystemFn allocate
Definition memory_resources.h:194