Loading...
Searching...
No Matches
linked_list.h
Go to the documentation of this file.
#ifndef HALIDE_RUNTIME_LINKED_LIST_H
#define HALIDE_RUNTIME_LINKED_LIST_H
#include "../HalideRuntime.h"
#include "memory_arena.h"
namespace Halide {
namespace Runtime {
namespace Internal {
// Doubly linked list container
// -- Implemented using MemoryArena for allocation
class LinkedList {
public:
// Disable copy support
LinkedList(const LinkedList &) = delete;
LinkedList &operator=(const LinkedList &) = delete;
// Default initial capacity
static constexpr uint32_t default_capacity = uint32_t(32); // smallish
// List entry
struct EntryType {
void *value = nullptr;
EntryType *prev_ptr = nullptr;
EntryType *next_ptr = nullptr;
};
LinkedList(void *user_context, uint32_t entry_size, uint32_t capacity = default_capacity,
const SystemMemoryAllocatorFns &allocator = default_allocator());
~LinkedList();
void initialize(void *user_context, uint32_t entry_size, uint32_t capacity = default_capacity,
const SystemMemoryAllocatorFns &allocator = default_allocator());
EntryType *front();
EntryType *back();
const EntryType *front() const;
const EntryType *back() const;
EntryType *prepend(void *user_context);
EntryType *prepend(void *user_context, const void *value);
EntryType *append(void *user_context);
EntryType *append(void *user_context, const void *value);
void pop_front(void *user_context);
void pop_back(void *user_context);
EntryType *insert_before(void *user_context, EntryType *entry_ptr);
EntryType *insert_before(void *user_context, EntryType *entry_ptr, const void *value);
EntryType *insert_after(void *user_context, EntryType *entry_ptr);
EntryType *insert_after(void *user_context, EntryType *entry_ptr, const void *value);
void remove(void *user_context, EntryType *entry_ptr);
void clear(void *user_context);
void destroy(void *user_context);
size_t size() const;
bool empty() const;
const SystemMemoryAllocatorFns &current_allocator() const;
static const SystemMemoryAllocatorFns &default_allocator();
private:
EntryType *reserve(void *user_context);
void reclaim(void *user_context, EntryType *entry_ptr);
MemoryArena *link_arena = nullptr;
MemoryArena *data_arena = nullptr;
EntryType *front_ptr = nullptr;
EntryType *back_ptr = nullptr;
size_t entry_count = 0;
};
LinkedList::LinkedList(void *user_context, uint32_t entry_size, uint32_t capacity,
const SystemMemoryAllocatorFns &sma) {
uint32_t arena_capacity = max(capacity, MemoryArena::default_capacity);
link_arena = MemoryArena::create(user_context, {sizeof(EntryType), arena_capacity, 0}, sma);
data_arena = MemoryArena::create(user_context, {entry_size, arena_capacity, 0}, sma);
front_ptr = nullptr;
back_ptr = nullptr;
entry_count = 0;
}
LinkedList::~LinkedList() {
destroy(nullptr);
}
void LinkedList::initialize(void *user_context, uint32_t entry_size, uint32_t capacity,
const SystemMemoryAllocatorFns &sma) {
uint32_t arena_capacity = max(capacity, MemoryArena::default_capacity);
link_arena = MemoryArena::create(user_context, {sizeof(EntryType), arena_capacity, 0}, sma);
data_arena = MemoryArena::create(user_context, {entry_size, arena_capacity, 0}, sma);
front_ptr = nullptr;
back_ptr = nullptr;
entry_count = 0;
}
void LinkedList::destroy(void *user_context) {
clear(nullptr);
if (link_arena) {
MemoryArena::destroy(nullptr, link_arena);
}
if (data_arena) {
MemoryArena::destroy(nullptr, data_arena);
}
link_arena = nullptr;
data_arena = nullptr;
front_ptr = nullptr;
back_ptr = nullptr;
entry_count = 0;
}
typename LinkedList::EntryType *LinkedList::front() {
return front_ptr;
}
typename LinkedList::EntryType *LinkedList::back() {
return back_ptr;
}
const typename LinkedList::EntryType *LinkedList::front() const {
return front_ptr;
}
const typename LinkedList::EntryType *LinkedList::back() const {
return back_ptr;
}
typename LinkedList::EntryType *
LinkedList::prepend(void *user_context) {
EntryType *entry_ptr = reserve(user_context);
if (empty()) {
front_ptr = entry_ptr;
back_ptr = entry_ptr;
entry_count = 1;
} else {
entry_ptr->next_ptr = front_ptr;
front_ptr->prev_ptr = entry_ptr;
front_ptr = entry_ptr;
++entry_count;
}
return entry_ptr;
}
typename LinkedList::EntryType *
LinkedList::append(void *user_context) {
EntryType *entry_ptr = reserve(user_context);
if (empty()) {
front_ptr = entry_ptr;
back_ptr = entry_ptr;
entry_count = 1;
} else {
entry_ptr->prev_ptr = back_ptr;
back_ptr->next_ptr = entry_ptr;
back_ptr = entry_ptr;
++entry_count;
}
return entry_ptr;
}
typename LinkedList::EntryType *
LinkedList::prepend(void *user_context, const void *value) {
EntryType *entry_ptr = prepend(user_context);
memcpy(entry_ptr->value, value, data_arena->current_config().entry_size);
return entry_ptr;
}
typename LinkedList::EntryType *
LinkedList::append(void *user_context, const void *value) {
EntryType *entry_ptr = append(user_context);
memcpy(entry_ptr->value, value, data_arena->current_config().entry_size);
return entry_ptr;
}
void LinkedList::pop_front(void *user_context) {
halide_debug_assert(user_context, (entry_count > 0));
EntryType *remove_ptr = front_ptr;
EntryType *next_ptr = remove_ptr->next_ptr;
if (next_ptr != nullptr) {
next_ptr->prev_ptr = nullptr;
}
front_ptr = next_ptr;
reclaim(user_context, remove_ptr);
--entry_count;
}
void LinkedList::pop_back(void *user_context) {
halide_debug_assert(user_context, (entry_count > 0));
EntryType *remove_ptr = back_ptr;
EntryType *prev_ptr = remove_ptr->prev_ptr;
if (prev_ptr != nullptr) {
prev_ptr->next_ptr = nullptr;
}
back_ptr = prev_ptr;
reclaim(user_context, remove_ptr);
--entry_count;
}
void LinkedList::clear(void *user_context) {
if (empty() == false) {
EntryType *remove_ptr = back_ptr;
while (remove_ptr != nullptr) {
EntryType *prev_ptr = remove_ptr->prev_ptr;
reclaim(user_context, remove_ptr);
remove_ptr = prev_ptr;
}
front_ptr = nullptr;
back_ptr = nullptr;
entry_count = 0;
}
}
void LinkedList::remove(void *user_context, EntryType *entry_ptr) {
halide_debug_assert(user_context, (entry_ptr != nullptr));
halide_debug_assert(user_context, (entry_count > 0));
if (entry_ptr->prev_ptr != nullptr) {
entry_ptr->prev_ptr->next_ptr = entry_ptr->next_ptr;
} else {
halide_debug_assert(user_context, (front_ptr == entry_ptr));
front_ptr = entry_ptr->next_ptr;
}
if (entry_ptr->next_ptr != nullptr) {
entry_ptr->next_ptr->prev_ptr = entry_ptr->prev_ptr;
} else {
halide_debug_assert(user_context, (back_ptr == entry_ptr));
back_ptr = entry_ptr->prev_ptr;
}
reclaim(user_context, entry_ptr);
--entry_count;
}
typename LinkedList::EntryType *
LinkedList::insert_before(void *user_context, EntryType *entry_ptr) {
if (entry_ptr != nullptr) {
EntryType *prev_ptr = entry_ptr->prev_ptr;
EntryType *new_ptr = reserve(user_context);
new_ptr->prev_ptr = prev_ptr;
new_ptr->next_ptr = entry_ptr;
entry_ptr->prev_ptr = new_ptr;
if (prev_ptr != nullptr) {
prev_ptr->next_ptr = new_ptr;
} else {
halide_debug_assert(user_context, (front_ptr == entry_ptr));
front_ptr = new_ptr;
}
++entry_count;
return new_ptr;
} else {
return append(user_context);
}
}
typename LinkedList::EntryType *
LinkedList::insert_after(void *user_context, EntryType *entry_ptr) {
if (entry_ptr != nullptr) {
EntryType *next_ptr = entry_ptr->next_ptr;
EntryType *new_ptr = reserve(user_context);
new_ptr->next_ptr = next_ptr;
new_ptr->prev_ptr = entry_ptr;
entry_ptr->next_ptr = new_ptr;
if (next_ptr != nullptr) {
next_ptr->prev_ptr = new_ptr;
} else {
halide_debug_assert(user_context, (back_ptr == entry_ptr));
back_ptr = new_ptr;
}
++entry_count;
return new_ptr;
} else {
return prepend(user_context);
}
}
typename LinkedList::EntryType *
LinkedList::insert_before(void *user_context, EntryType *entry_ptr, const void *value) {
EntryType *new_ptr = insert_before(user_context, entry_ptr);
memcpy(new_ptr->value, value, data_arena->current_config().entry_size);
return new_ptr;
}
typename LinkedList::EntryType *
LinkedList::insert_after(void *user_context, EntryType *entry_ptr, const void *value) {
EntryType *new_ptr = insert_after(user_context, entry_ptr);
memcpy(new_ptr->value, value, data_arena->current_config().entry_size);
return new_ptr;
}
size_t LinkedList::size() const {
return entry_count;
}
bool LinkedList::empty() const {
return entry_count == 0;
}
const SystemMemoryAllocatorFns &
LinkedList::current_allocator() const {
return link_arena->current_allocator();
}
const SystemMemoryAllocatorFns &
LinkedList::default_allocator() {
return MemoryArena::default_allocator();
}
typename LinkedList::EntryType *
LinkedList::reserve(void *user_context) {
EntryType *entry_ptr = static_cast<EntryType *>(
link_arena->reserve(user_context, true));
entry_ptr->value = data_arena->reserve(user_context, true);
entry_ptr->next_ptr = nullptr;
entry_ptr->prev_ptr = nullptr;
return entry_ptr;
}
void LinkedList::reclaim(void *user_context, EntryType *entry_ptr) {
void *value_ptr = entry_ptr->value;
entry_ptr->value = nullptr;
entry_ptr->next_ptr = nullptr;
entry_ptr->prev_ptr = nullptr;
data_arena->reclaim(user_context, value_ptr);
link_arena->reclaim(user_context, entry_ptr);
}
// --
} // namespace Internal
} // namespace Runtime
} // namespace Halide
#endif // HALIDE_RUNTIME_LINKED_LIST_H
HalideRuntime.h
This file declares the routines used by Halide internally in its runtime.
Halide::Runtime::Internal::LinkedList::initialize
void initialize(void *user_context, uint32_t entry_size, uint32_t capacity=default_capacity, const SystemMemoryAllocatorFns &allocator=default_allocator())
Definition linked_list.h:92
Halide::Runtime::Internal::LinkedList::prepend
EntryType * prepend(void *user_context)
Definition linked_list.h:134
Halide::Runtime::Internal::LinkedList::current_allocator
const SystemMemoryAllocatorFns & current_allocator() const
Definition linked_list.h:304
Halide::Runtime::Internal::LinkedList::back
EntryType * back()
Definition linked_list.h:121
Halide::Runtime::Internal::LinkedList::append
EntryType * append(void *user_context)
Definition linked_list.h:150
Halide::Runtime::Internal::LinkedList::empty
bool empty() const
Definition linked_list.h:299
Halide::Runtime::Internal::LinkedList::clear
void clear(void *user_context)
Definition linked_list.h:203
Halide::Runtime::Internal::LinkedList::pop_front
void pop_front(void *user_context)
Definition linked_list.h:179
Halide::Runtime::Internal::LinkedList::operator=
LinkedList & operator=(const LinkedList &)=delete
Halide::Runtime::Internal::LinkedList::default_allocator
static const SystemMemoryAllocatorFns & default_allocator()
Definition linked_list.h:309
Halide::Runtime::Internal::LinkedList::insert_after
EntryType * insert_after(void *user_context, EntryType *entry_ptr)
Definition linked_list.h:261
Halide::Runtime::Internal::LinkedList::remove
void remove(void *user_context, EntryType *entry_ptr)
Definition linked_list.h:217
Halide::Runtime::Internal::LinkedList::pop_back
void pop_back(void *user_context)
Definition linked_list.h:191
Halide::Runtime::Internal::LinkedList::size
size_t size() const
Definition linked_list.h:295
Halide::Runtime::Internal::LinkedList::destroy
void destroy(void *user_context)
Definition linked_list.h:102
Halide::Runtime::Internal::LinkedList::default_capacity
static constexpr uint32_t default_capacity
Definition linked_list.h:20
Halide::Runtime::Internal::LinkedList::LinkedList
LinkedList(const LinkedList &)=delete
Halide::Runtime::Internal::LinkedList::~LinkedList
~LinkedList()
Definition linked_list.h:88
Halide::Runtime::Internal::LinkedList::insert_before
EntryType * insert_before(void *user_context, EntryType *entry_ptr)
Definition linked_list.h:240
Halide::Runtime::Internal::LinkedList::front
EntryType * front()
Definition linked_list.h:117
Halide::Runtime::Internal::MemoryArena
Definition memory_arena.h:17
Halide::Runtime::Internal::MemoryArena::reserve
void * reserve(void *user_context, bool initialize=false)
Definition memory_arena.h:155
Halide::Runtime::Internal::MemoryArena::create
static MemoryArena * create(void *user_context, const Config &config, const SystemMemoryAllocatorFns &allocator=default_allocator())
Definition memory_arena.h:101
Halide::Runtime::Internal::MemoryArena::default_capacity
static constexpr uint32_t default_capacity
Definition memory_arena.h:24
Halide::Runtime::Internal::MemoryArena::destroy
static void destroy(void *user_context, MemoryArena *arena)
Definition memory_arena.h:115
Halide::Runtime::Internal::MemoryArena::reclaim
void reclaim(void *user_context, void *ptr)
Definition memory_arena.h:182
Halide::Runtime::Internal::MemoryArena::default_allocator
static const SystemMemoryAllocatorFns & default_allocator()
Definition memory_arena.h:303
memory_arena.h
Halide::Runtime::Internal
Definition constants.h:13
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::max
Expr max(const FuncRef &a, const FuncRef &b)
Definition Func.h:606
halide_debug_assert
#define halide_debug_assert(user_context, cond)
halide_debug_assert() is like halide_assert(), but only expands into a check when DEBUG_RUNTIME is de...
Definition runtime_internal.h:290
memcpy
void * memcpy(void *s1, const void *s2, size_t n)
uint32_t
unsigned __INT32_TYPE__ uint32_t
Definition runtime_internal.h:25
Halide::Runtime::Internal::LinkedList::EntryType
Definition linked_list.h:23
Halide::Runtime::Internal::LinkedList::EntryType::prev_ptr
EntryType * prev_ptr
Definition linked_list.h:25
Halide::Runtime::Internal::LinkedList::EntryType::next_ptr
EntryType * next_ptr
Definition linked_list.h:26
Halide::Runtime::Internal::LinkedList::EntryType::value
void * value
Definition linked_list.h:24
Halide::Runtime::Internal::SystemMemoryAllocatorFns
Definition memory_resources.h:193