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

Methods

dynamic_allocationCreates 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;
};





Add Discussion as Guest

Log in