Class dynamic_allocation
Synopsis
#include <include/sajson.h>
class dynamic_allocation
Description
Allocation policy that uses dynamically-growing buffers for both the parse stack and the AST. This allocation policy minimizes peak memory usage at the cost of some allocation and copying churn.
Mentioned in
- Examples / main.cpp
Methods
dynamic_allocation | Creates a dynamic_allocation policy with the given initial AST and stack buffer sizes. |
Source
Lines 1161-1403 in include/sajson.h.
class dynamic_allocation {
public:
/// \cond INTERNAL
class stack_head {
public:
stack_head(stack_head&& other)
: stack_top(other.stack_top)
, stack_bottom(other.stack_bottom)
, stack_limit(other.stack_limit) {
other.stack_top = 0;
other.stack_bottom = 0;
other.stack_limit = 0;
}
~stack_head() { delete[] stack_bottom; }
bool push(size_t element) {
if (can_grow(1)) {
*stack_top++ = element;
return true;
} else {
return false;
}
}
size_t* reserve(size_t amount, bool* success) {
if (can_grow(amount)) {
size_t* rv = stack_top;
stack_top += amount;
*success = true;
return rv;
} else {
*success = false;
return 0;
}
}
void reset(size_t new_top) { stack_top = stack_bottom + new_top; }
size_t get_size() { return stack_top - stack_bottom; }
size_t* get_top() { return stack_top; }
size_t* get_pointer_from_offset(size_t offset) {
return stack_bottom + offset;
}
private:
stack_head(const stack_head&) = delete;
void operator=(const stack_head&) = delete;
explicit stack_head(size_t initial_capacity, bool* success) {
assert(initial_capacity);
stack_bottom = new (std::nothrow) size_t[initial_capacity];
stack_top = stack_bottom;
if (stack_bottom) {
stack_limit = stack_bottom + initial_capacity;
} else {
stack_limit = 0;
}
*success = !!stack_bottom;
}
bool can_grow(size_t amount) {
if (SAJSON_LIKELY(
amount <= static_cast<size_t>(stack_limit - stack_top))) {
return true;
}
size_t current_size = stack_top - stack_bottom;
size_t old_capacity = stack_limit - stack_bottom;
size_t new_capacity = old_capacity * 2;
while (new_capacity < amount + current_size) {
new_capacity *= 2;
}
size_t* new_stack = new (std::nothrow) size_t[new_capacity];
if (!new_stack) {
stack_top = 0;
stack_bottom = 0;
stack_limit = 0;
return false;
}
memcpy(new_stack, stack_bottom, current_size * sizeof(size_t));
delete[] stack_bottom;
stack_top = new_stack + current_size;
stack_bottom = new_stack;
stack_limit = stack_bottom + new_capacity;
return true;
}
size_t* stack_top; // stack grows up: stack_top >= stack_bottom
size_t* stack_bottom;
size_t* stack_limit;
friend class dynamic_allocation;
};
class allocator {
public:
allocator() = delete;
allocator(const allocator&) = delete;
void operator=(const allocator&) = delete;
explicit allocator(
size_t* buffer_,
size_t current_capacity,
size_t initial_stack_capacity_)
: ast_buffer_bottom(buffer_)
, ast_buffer_top(buffer_ + current_capacity)
, ast_write_head(ast_buffer_top)
, initial_stack_capacity(initial_stack_capacity_) {}
explicit allocator(std::nullptr_t)
: ast_buffer_bottom(0)
, ast_buffer_top(0)
, ast_write_head(0)
, initial_stack_capacity(0) {}
allocator(allocator&& other)
: ast_buffer_bottom(other.ast_buffer_bottom)
, ast_buffer_top(other.ast_buffer_top)
, ast_write_head(other.ast_write_head)
, initial_stack_capacity(other.initial_stack_capacity) {
other.ast_buffer_bottom = 0;
other.ast_buffer_top = 0;
other.ast_write_head = 0;
}
~allocator() { delete[] ast_buffer_bottom; }
stack_head get_stack_head(bool* success) {
return stack_head(initial_stack_capacity, success);
}
size_t get_write_offset() { return ast_buffer_top - ast_write_head; }
size_t* get_write_pointer_of(size_t v) { return ast_buffer_top - v; }
size_t* reserve(size_t size, bool* success) {
if (can_grow(size)) {
ast_write_head -= size;
*success = true;
return ast_write_head;
} else {
*success = false;
return 0;
}
}
size_t* get_ast_root() { return ast_write_head; }
internal::ownership transfer_ownership() {
auto p = ast_buffer_bottom;
ast_buffer_bottom = 0;
ast_buffer_top = 0;
ast_write_head = 0;
return internal::ownership(p);
}
private:
bool can_grow(size_t amount) {
if (SAJSON_LIKELY(
amount <= static_cast<size_t>(
ast_write_head - ast_buffer_bottom))) {
return true;
}
size_t current_capacity = ast_buffer_top - ast_buffer_bottom;
size_t current_size = ast_buffer_top - ast_write_head;
size_t new_capacity = current_capacity * 2;
while (new_capacity < amount + current_size) {
new_capacity *= 2;
}
size_t* old_buffer = ast_buffer_bottom;
size_t* new_buffer = new (std::nothrow) size_t[new_capacity];
if (!new_buffer) {
ast_buffer_bottom = 0;
ast_buffer_top = 0;
ast_write_head = 0;
return false;
}
size_t* old_write_head = ast_write_head;
ast_buffer_bottom = new_buffer;
ast_buffer_top = new_buffer + new_capacity;
ast_write_head = ast_buffer_top - current_size;
memcpy(
ast_write_head, old_write_head, current_size * sizeof(size_t));
delete[] old_buffer;
return true;
}
size_t*
ast_buffer_bottom; // base address of the ast buffer - it grows down
size_t* ast_buffer_top;
size_t* ast_write_head;
size_t initial_stack_capacity;
};
/// \endcond
/// Creates a dynamic_allocation policy with the given initial AST
/// and stack buffer sizes.
dynamic_allocation(
size_t initial_ast_capacity_ = 0, size_t initial_stack_capacity_ = 0)
: initial_ast_capacity(initial_ast_capacity_)
, initial_stack_capacity(initial_stack_capacity_) {}
/// \cond INTERNAL
allocator
make_allocator(size_t input_document_size_in_bytes, bool* succeeded) const {
size_t capacity = initial_ast_capacity;
if (!capacity) {
// TODO: guess based on input document size
capacity = 1024;
}
size_t* buffer = new (std::nothrow) size_t[capacity];
if (!buffer) {
*succeeded = false;
return allocator(nullptr);
}
size_t stack_capacity = initial_stack_capacity;
if (!stack_capacity) {
stack_capacity = 256;
}
*succeeded = true;
return allocator(buffer, capacity, stack_capacity);
}
/// \endcond
private:
size_t initial_ast_capacity;
size_t initial_stack_capacity;
};