<commit_before>/*
 * The "rubber" memory allocator.  It is a buffer for storing many
 * large objects.  Unlike heap memory, unused areas are given back to
 * the operating system.
 *
 * author: <NAME> <<EMAIL>>
 */

#include "rubber.hxx"
#include "mmap.h"
#include "AllocatorStats.hxx"

#include <inline/list.h>

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

struct RubberObject {
    /**
     * The next object index or 0 for end of list.
     */
    unsigned next;

    /**
     * The previous object index.  Not used for the "free" list.
     */
    unsigned previous;

    /**
     * The offset of this object within the memory map.
     */
    size_t offset;

    /**
     * The size of this object.
     */
    size_t size;

#ifndef NDEBUG
    bool allocated;
#endif
};

struct RubberTable {
    /**
     * The allocated size of the table (maximum number of objects).
     */
    unsigned max_entries;

    /**
     * The index after the last initialized table entry.  We avoid
     * initializing all entries on startup, because this may make the
     * kernel allocate physical memory for table areas we don't need
     * (yet).
     */
    unsigned initialized_tail;

    /**
     * The index of the allocated object with the largest offset (the
     * "head" is always 0, which points to the table).  The linked
     * list is sorted by offset.
     */
    unsigned allocated_tail;

    /**
     * The index of the first free table entry.  The linked list
     * contains all free entries in no specific order.  This is 0 if
     * the table is full.
     */
    unsigned free_head;

    /**
     * The first entry (index 0) is the table itself.
     */
    RubberObject entries[1];

    size_t Init(unsigned _max_entries);
    void Deinit();

    bool IsEmpty() const {
        return allocated_tail == 0;
    }

    /**
     * Calculate the size [in bytes] of a #rubber_table struct for the
     * given number of entries.
     */
    gcc_const
    static size_t RequiredSize(unsigned n) {
        assert(n > 0);

        const RubberTable *dummy = nullptr;
        return sizeof(*dummy) + sizeof(dummy->entries) * (n - 1);
    }

    /**
     * Calculate the capacity [in number of entries] of a #rubber_table
     * struct for the given size [in bytes].
     */
    gcc_const
    static unsigned Capacity(size_t size) {
        const RubberTable *dummy = nullptr;
        assert(size >= sizeof(*dummy));

        return (size - sizeof(*dummy)) / sizeof(dummy->entries) + 1;
    }

    /**
     * Returns the allocated size of the table object.  At the same time,
     * this is the offset of the first allocation.
     */
    gcc_pure
    size_t GetSize() const {
        assert(entries[0].offset == 0);

        return entries[0].size;
    }

    gcc_pure
    size_t GetBruttoSize() const {
        const RubberObject *tail = &entries[allocated_tail];

        return tail->offset + tail->size - GetSize();
    }

    RubberObject *GetHead() {
        return &entries[0];
    }

    RubberObject *GetNext(RubberObject *o) {
        return o->next != 0
            ? &entries[o->next]
            : nullptr;
    }

    gcc_pure
    size_t GetTailOffset() const {
        assert(allocated_tail < max_entries);

        const RubberObject *tail = &entries[allocated_tail];
        assert(tail->next == 0);

        return tail->offset + tail->size;
    }

    /**
     * Allocate a new object id.  The caller must initialise the object.
     */
    unsigned AddId();
    unsigned Add(size_t offset, size_t size);
    size_t Remove(unsigned id);

    gcc_pure
    size_t GetSizeOf(unsigned id) const;

    gcc_pure
    size_t GetOffsetOf(unsigned id) const;

    size_t Shrink(unsigned id, size_t new_size);
};

struct RubberHole {
    /**
     * The sibling holes in the list (#rubber.holes[i]).
     */
    list_head siblings;

    /**
     * The size of this hole (including the size of this struct).
     */
    size_t size;

    /**
     * The allocated objects before and after this hole.
     */
    unsigned previous_id, next_id;<commit_msg>rubber: update API documentation<commit_after>/*
 * The "rubber" memory allocator.  It is a buffer for storing many
 * large objects.  Unlike heap memory, unused areas are given back to
 * the operating system.
 *
 * author: <NAME> <<EMAIL>>
 */

#include "rubber.hxx"
#include "mmap.h"
#include "AllocatorStats.hxx"

#include <inline/list.h>

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

struct RubberObject {
    /**
     * The next object index or 0 for end of list.
     */
    unsigned next;

    /**
     * The previous object index.  Not used for the "free" list.
     */
    unsigned previous;

    /**
     * The offset of this object within the memory map.
     */
    size_t offset;

    /**
     * The size of this object.
     */
    size_t size;

#ifndef NDEBUG
    bool allocated;
#endif
};

struct RubberTable {
    /**
     * The allocated size of the table (maximum number of objects).
     */
    unsigned max_entries;

    /**
     * The index after the last initialized table entry.  We avoid
     * initializing all entries on startup, because this may make the
     * kernel allocate physical memory for table areas we don't need
     * (yet).
     */
    unsigned initialized_tail;

    /**
     * The index of the allocated object with the largest offset (the
     * "head" is always 0, which points to the table).  The linked
     * list is sorted by offset.
     */
    unsigned allocated_tail;

    /**
     * The index of the first free table entry.  The linked list
     * contains all free entries in no specific order.  This is 0 if
     * the table is full.
     */
    unsigned free_head;

    /**
     * The first entry (index 0) is the table itself.
     */
    RubberObject entries[1];

    size_t Init(unsigned _max_entries);
    void Deinit();

    bool IsEmpty() const {
        return allocated_tail == 0;
    }

    /**
     * Calculate the size [in bytes] of a #RubberTable struct for the
     * given number of entries.
     */
    gcc_const
    static size_t RequiredSize(unsigned n) {
        assert(n > 0);

        const RubberTable *dummy = nullptr;
        return sizeof(*dummy) + sizeof(dummy->entries) * (n - 1);
    }

    /**
     * Calculate the capacity [in number of entries] of a #RubberTable
     * struct for the given size [in bytes].
     */
    gcc_const
    static unsigned Capacity(size_t size) {
        const RubberTable *dummy = nullptr;
        assert(size >= sizeof(*dummy));

        return (size - sizeof(*dummy)) / sizeof(dummy->entries) + 1;
    }

    /**
     * Returns the allocated size of the table object.  At the same time,
     * this is the offset of the first allocation.
     */
    gcc_pure
    size_t GetSize() const {
        assert(entries[0].offset == 0);

        return entries[0].size;
    }

    gcc_pure
    size_t GetBruttoSize() const {
        const RubberObject *tail = &entries[allocated_tail];

        return tail->offset + tail->size - GetSize();
    }

    RubberObject *GetHead() {
        return &entries[0];
    }

    RubberObject *GetNext(RubberObject *o) {
        return o->next != 0
            ? &entries[o->next]
            : nullptr;
    }

    gcc_pure
    size_t GetTailOffset() const {
        assert(allocated_tail < max_entries);

        const RubberObject *tail = &entries[allocated_tail];
        assert(tail->next == 0);

        return tail->offset + tail->size;
    }

    /**
     * Allocate a new object id.  The caller must initialise the object.
     */
    unsigned AddId();
    unsigned Add(size_t offset, size_t size);
    size_t Remove(unsigned id);

    gcc_pure
    size_t GetSizeOf(unsigned id) const;

    gcc_pure
    size_t GetOffsetOf(unsigned id) const;

    size_t Shrink(unsigned id, size_t new_size);
};

struct RubberHole {
    /**
     * The sibling holes in the list (#Rubber.holes[i]).
     */
    list_head siblings;

    /**
     * The size of this hole (including the size of this struct).
     */
    size_t size;

    /**
     * The allocated objects before and after this hole.
     */
    unsigned previous_id, next_id;
{'fraction_non_alphanumeric': 0.10198610941878884, 'fraction_numerical': 0.0036554161082003166, 'mean_word_length': 2.2163009404388716, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '177277', 'n_tokens_mistral': 2547, 'n_tokens_neox': 2418, 'n_words': 848}