To manage the memory storage of inter code.

• §1. Introduction
• §3. The resources
• §12. The bytecode storage

§1. Introduction. The data structure in this section may bring to mind the title of the Metallica song "The Thing That Should Not Be", but it works. It's also better than it used to be (which is more than you can say for Metallica).

Each inter tree needs to store data outside of its own inter_tree_node structures, data which falls into two categories:

• ● Bytecode for instructions, each having a unique address.
• ● Resources such as texts and symbols tables, each having a unique ID number.

This data is held in the inter_warehouse connected to the tree. Each inter_tree contains a pointer to its warehouse.

typedef struct inter_warehouse {
     bytecode storage
    struct inter_warehouse_room *first_room;
    struct inter_warehouse_room *last_room;

     resource storage
    inter_ti next_free_resource_ID;
    struct inter_warehouse_resource *stored_resources;
    inter_ti resources_capacity;

    CLASS_DEFINITION
} inter_warehouse;

• The structure inter_warehouse is private to this section.

§2. An implementation secret, though, is that (in the present implementation, anyway) there is only one warehouse. If there are multiple trees, they all share the use of a single warehouse, though they don't know it. This would cause thread-safety issues if Inter had any aspiration to be threaded, but it does not have. And this single-warehouse design makes it much faster to carry out "transmigration" — the movement of branches of Inter from one tree to another — since the associated bytecode and resources do not need to be copied from one warehouse to another.

In this description we continue to talk about "a" warehouse, regardless of the secret fact that there is only one.

inter_warehouse *the_only_warehouse = NULL;

inter_warehouse *InterWarehouse::new?Usage of InterWarehouse::new:
Inter Trees - §2(void) {
    if (the_only_warehouse == NULL) {
        inter_warehouse *warehouse = CREATE(inter_warehouse);

        warehouse->first_room = NULL;
        warehouse->last_room = NULL;

        warehouse->next_free_resource_ID = 1;
        warehouse->stored_resources = NULL;
        warehouse->resources_capacity = 0;

        the_only_warehouse = warehouse;
    }
    return the_only_warehouse;
}

§3. The resources. The warehouse provides an array associating ID numbers with "resources": for example, texts, or symbols tables. An ID is an unsigned integer with the lowest legal ID being 1, so that 0 can safely be used to mean "no resource". Once assigned, an ID is never reused.

Lookup needs tp be fast, so we store the list of resources as a flat array which doubles in size each time its capacity is exceeded. This typically happens about 10 times in a run of inform7, for example, to hold on the order of 100,000 resources.

typedef struct inter_warehouse_resource {
    struct general_pointer res;
    struct inter_package *resource_owner;
} inter_warehouse_resource;

• The structure inter_warehouse_resource is private to this section.

§4.

inter_ti InterWarehouse::create_resource?Usage of InterWarehouse::create_resource:
§8, §9, §11
Inter in Binary Files - §10.1.3.1(inter_warehouse *warehouse) {
    if (warehouse->next_free_resource_ID >= warehouse->resources_capacity)
        Double the resource list capacity4.1;
    inter_ti n = warehouse->next_free_resource_ID++;
    warehouse->stored_resources[n].res = NULL_GENERAL_POINTER;
    warehouse->stored_resources[n].resource_owner = NULL;
    return n;
}

§4.1. Double the resource list capacity4.1 =

    inter_ti new_size = 128;
    while (new_size < 2*warehouse->resources_capacity) new_size = 2*new_size;

    LOGIF(INTER_MEMORY, "Giving warehouse %d resource list of size %d (up from %d)\n",
        warehouse->allocation_id, new_size, warehouse->resources_capacity);

    inter_warehouse_resource *storage = (inter_warehouse_resource *)
        Memory::calloc((int) new_size, sizeof(inter_warehouse_resource), INTER_LINKS_MREASON);
    inter_warehouse_resource *old = warehouse->stored_resources;
    for (inter_ti i=0; i<warehouse->resources_capacity; i++) storage[i] = old[i];
    if (warehouse->resources_capacity > 0)
        Memory::I7_free(old, INTER_LINKS_MREASON, (int) warehouse->resources_capacity);
    warehouse->stored_resources = storage;
    warehouse->resources_capacity = new_size;

• This code is used in §4.

§5. Every resource is tied to a package which owns it. This is only in fact used to determine the tree which owns it — but we store the package, not the tree, because when material transmigrates from one tree to another, the owning package can then stay the same: it is just that InterPackage::tree will return a different tree after the movement has taken place.

The following conveniently loops through all valid resource IDs for a given tree:

define LOOP_OVER_RESOURCE_IDS(n, I)
    for (inter_ti n = 1; n < I->housed->next_free_resource_ID; n++)
        if ((I->housed->stored_resources[n].resource_owner == NULL) ||
            (InterPackage::tree(I->housed->stored_resources[n].resource_owner) == I))

§6. So what can a resource be? The following types are supported, and can be deduced by looking at what class is stored in the general pointer res; this saves redundantly storing a type field in inter_warehouse_resource.

enum TEXT_IRSRC from 1
enum SYMBOLS_TABLE_IRSRC
enum NODE_LIST_IRSRC
enum PACKAGE_REF_IRSRC

inter_ti InterWarehouse::resource_type_code?Usage of InterWarehouse::resource_type_code:
Inter in Binary Files - §10.2.3.2(inter_warehouse *warehouse, inter_ti n) {
    if ((n == 0) || (n >= warehouse->next_free_resource_ID)) internal_error("bad resource ID");
    switch (warehouse->stored_resources[n].res.run_time_type_code) {
        case text_stream_CLASS:         return TEXT_IRSRC;
        case inter_symbols_table_CLASS: return SYMBOLS_TABLE_IRSRC;
        case inter_node_list_CLASS:     return NODE_LIST_IRSRC;
        case inter_package_CLASS:       return PACKAGE_REF_IRSRC;
    }
    return 0;
}

int InterWarehouse::known_type_code?Usage of InterWarehouse::known_type_code:
Verifying Inter - §7, §8, §9, §10(inter_warehouse *warehouse, inter_ti n) {
    if ((n == 0) || (n >= warehouse->next_free_resource_ID)) return 0;
    switch (warehouse->stored_resources[n].res.run_time_type_code) {
        case text_stream_CLASS:         return TEXT_IRSRC;
        case inter_symbols_table_CLASS: return SYMBOLS_TABLE_IRSRC;
        case inter_node_list_CLASS:     return NODE_LIST_IRSRC;
        case inter_package_CLASS:       return PACKAGE_REF_IRSRC;
    }
    return 0;
}

§7. First, it can be a text:

inter_ti InterWarehouse::create_text?Usage of InterWarehouse::create_text:
Annotations - §6, §15
Inter Value Pairs - §6, §8, §9, §11, §15
The Insert Construct - §2(inter_warehouse *warehouse, inter_package *owner) {
    return InterWarehouse::create_ref(warehouse, STORE_POINTER_text_stream(Str::new()), owner);
}

inter_ti InterWarehouse::create_text_at?Usage of InterWarehouse::create_text_at:
The Comment Construct - §2
The Origin Construct - §2
The Pragma Construct - §2
The Inv Construct - §3
The Splat Construct - §2(inter_bookmark *IBM, text_stream *text) {
    inter_warehouse *warehouse = InterBookmark::warehouse(IBM);
    inter_ti text_ID = InterWarehouse::create_text(warehouse, InterBookmark::package(IBM));
    text_stream *to = InterWarehouse::get_text(warehouse, text_ID);
    Str::copy(to, text);
    return text_ID;
}

text_stream *InterWarehouse::get_text?Usage of InterWarehouse::get_text:
Inter Nodes - §14
Annotations - §6, §7, §15
Inter in Binary Files - §10.2.3.2.1
Inter Value Pairs - §6, §8, §9, §11, §15
The Insert Construct - §2(inter_warehouse *warehouse, inter_ti n) {
    general_pointer gp = InterWarehouse::get_ref(warehouse, n);
    if (gp.run_time_type_code != text_stream_CLASS) return NULL;
    return RETRIEVE_POINTER_text_stream(gp);
}

§8. Second, a symbols table. Uniquely, this one does not specify an owning package when the resource is created: that's because a package can only be made when a symbols table for it already exists, so we need the table first. The owner is therefore initially not set, and must be explicitly set after the package has been created, using InterWarehouse::set_symbols_table_owner.

inter_ti InterWarehouse::create_symbols_table?Usage of InterWarehouse::create_symbols_table:
Inter Trees - §2.1
The Package Construct - §4(inter_warehouse *warehouse) {
    inter_ti n = InterWarehouse::create_resource(warehouse);
    inter_symbols_table *new_table = InterSymbolsTable::new(n);
    return InterWarehouse::create_ref_at(warehouse, n,
        STORE_POINTER_inter_symbols_table(new_table), NULL);
}

void InterWarehouse::set_symbols_table_owner?Usage of InterWarehouse::set_symbols_table_owner:
Inter Trees - §2.1
The Package Construct - §4(inter_warehouse *warehouse, inter_ti n,
    inter_package *owner) {
    if (InterWarehouse::get_symbols_table(warehouse, n) == NULL)
        internal_error("not a symbols table");
    warehouse->stored_resources[n].resource_owner = owner;
}

inter_symbols_table *InterWarehouse::get_symbols_table?Usage of InterWarehouse::get_symbols_table:
Inter Trees - §2.1
Inter Nodes - §14
Inter in Binary Files - §10.1.3.2.2, §10.2.3.2.2, §10.1.3.2.3, §10.1.4, §10.2.4
The Package Construct - §4(inter_warehouse *warehouse,
    inter_ti n) {
    general_pointer gp = InterWarehouse::get_ref(warehouse, n);
    if (gp.run_time_type_code != inter_symbols_table_CLASS) return NULL;
    return RETRIEVE_POINTER_inter_symbols_table(gp);
}

§9. Third, a resource can be a package — or, really, a pointer to a package, a form of resource which allows bytecode to contain cross-references to packages.

This may as well be its own owner, since it can be valid only if the package pointed to is in the same tree as the bytecode instruction using the resource.

inter_ti InterWarehouse::create_package?Usage of InterWarehouse::create_package:
Inter Trees - §2.1
The Package Construct - §4(inter_warehouse *warehouse, inter_tree *I) {
    inter_ti n = InterWarehouse::create_resource(warehouse);
    inter_package *new_pack = InterPackage::new(I, n);
    return InterWarehouse::create_ref_at(warehouse, n, STORE_POINTER_inter_package(new_pack),
        new_pack);
}

inter_package *InterWarehouse::get_package?Usage of InterWarehouse::get_package:
Inter Trees - §2.1
Inter Nodes - §14
Inter in Binary Files - §10.1.3.2.3, §10.2.3.2.3, §10.1.5.2
The Package Construct - §4(inter_warehouse *warehouse, inter_ti n) {
    general_pointer gp = InterWarehouse::get_ref(warehouse, n);
    if (gp.run_time_type_code != inter_package_CLASS) return NULL;
    return RETRIEVE_POINTER_inter_package(gp);
}

§10. Finally, a node list.

inter_ti InterWarehouse::create_node_list?Usage of InterWarehouse::create_node_list:
The Instance Construct - §2
The Property Construct - §2
The Typename Construct - §2(inter_warehouse *warehouse, inter_package *owner) {
    return InterWarehouse::create_ref(warehouse,
        STORE_POINTER_inter_node_list(InterNodeList::new()), owner);
}

inter_node_list *InterWarehouse::get_node_list?Usage of InterWarehouse::get_node_list:
Inter Nodes - §14
Inter in Binary Files - §10.1.3.2.4(inter_warehouse *warehouse, inter_ti n) {
    general_pointer gp = InterWarehouse::get_ref(warehouse, n);
    if (gp.run_time_type_code != inter_node_list_CLASS) return NULL;
    return RETRIEVE_POINTER_inter_node_list(gp);
}

§11. All of which use the following:

general_pointer InterWarehouse::get_ref?Usage of InterWarehouse::get_ref:
§7, §8, §9, §10(inter_warehouse *warehouse, inter_ti n) {
    if ((n == 0) || (n >= warehouse->next_free_resource_ID)) return NULL_GENERAL_POINTER;
    return warehouse->stored_resources[n].res;
}

inter_ti InterWarehouse::create_ref?Usage of InterWarehouse::create_ref:
§7, §10(inter_warehouse *warehouse,
    general_pointer ref, inter_package *owner) {
    inter_ti n = InterWarehouse::create_resource(warehouse);
    return InterWarehouse::create_ref_at(warehouse, n, ref, owner);
}

inter_ti InterWarehouse::create_ref_at?Usage of InterWarehouse::create_ref_at:
§8, §9
Inter in Binary Files - §10.1.3.2.1, §10.1.3.2.2, §10.1.3.2.3, §10.1.3.2.4(inter_warehouse *warehouse, inter_ti n,
    general_pointer ref, inter_package *owner) {
    warehouse->stored_resources[n].res = ref;
    warehouse->stored_resources[n].resource_owner = owner;
    return n;
}

§12. The bytecode storage. Conceptually, a warehouse stores bytecode at (word) addresses which begin from 0. Each instruction occupies a contiguous run of addresses. That all sounds like a typical machine-code arrangement, but:

• (a) the instructions themselves contain neither absolute addresses nor address offsets — they are oblivious to where they are stored, and refer to code positions using labels instead;
• (b) some storage may remain unused, and the addresses of instructions do not correspond to their order in the code.

typedef struct inter_warehouse_room {
    struct inter_warehouse *owning_warehouse;
    int room_usage;
    int room_capacity;
    inter_ti *bytecode;
    struct inter_warehouse_room *next_room;
    CLASS_DEFINITION
} inter_warehouse_room;

• The structure inter_warehouse_room is accessed in 2/in and here.

§13. The warehouse is divided into a series of rooms of steadily telescoping sizes. Unless an improbably large demand is made for a very long single instruction, they will typically look like:

    room 0      addresses 0x000000 to 0x000fff (4K words)
    room 1      addresses 0x001000 to 0x002fff (8K words)
    room 2      addresses 0x003000 to 0x006fff (16K words)
    room 3      addresses 0x007000 to 0x00efff (32K words)
    ...

though probably not with boundaries as neat as that, since there will be a few words of unused space at the end of each room.

In a typical inform7 run, we reach about the 9th room, so that the address space amounts to around 2 million words.

§14. A single instruction will occupy a contiguous run of addresses, and will consist of a preframe (always PREFRAME_SIZE words) and then a frame (of a variable size, though always at least 2 words). This will always lie inside a single room: this is why, if we ask for an instruction with a 50000-word frame, we would force larger rooms to be created.

The following represents where an instruction is stored. The address of the preframe will be index plus the sum of room_usage for previous rooms; the address of the frame will be PREFRAME_SIZE more than that, since the frame always immediately follows the preframe. instruction points to the first word of the frame, and the extent is the size of the frame, so the size of the whole instruction is extent + PREFRAME_SIZE.

Note that instruction and extent are both in principle redundant in this structure. If you know in_room and index you know everything, because:

    W.instruction == W.in_room->bytecode + W.index + PREFRAME_SIZE
    W.extent == W.in_room->bytecode[W.index + PREFRAME_SKIP_AMOUNT] - PREFRAME_SIZE

But speed of access is so important that we store these two fields redundantly in order to cache the results of those two calculations.

typedef struct warehouse_floor_space {
    struct inter_warehouse_room *in_room;
    int index;
    inter_ti *instruction;
    int extent;
} warehouse_floor_space;

• The structure warehouse_floor_space is accessed in 2/in, 2/bkm, 2/st, 2/ann, 2/trn, 3/ic, 3/iibf, 3/iitf, 3/vi, 3/ivp, 3/idt, 4/tcc, 4/tcc2, 4/tic, 4/tic2, 4/toc, 4/tpc, 4/tpc3, 4/tpc4, 4/tpc5, 4/tpc6, 4/tpc8, 4/ttc, 5/tac, 5/tcc, 5/tcc2, 5/tec, 5/tic, 5/trc2, 5/tsc and here.

§15. We provide an API of just two functions to handle all this. Firstly, InterWarehouse::make_floor_space makes room for an instruction of n words. (This is the frame extent, and does not include the PREFRAME_SIZE.)

Note that this function always succeeds, because an internal error is thrown if the system is out of memory.

warehouse_floor_space InterWarehouse::make_floor_space?Usage of InterWarehouse::make_floor_space:
§16.2
Inter Nodes - §2(inter_warehouse *warehouse, int n) {
    int total_extent = n + PREFRAME_SIZE;
    Make a new and bigger room if necessary15.1;

    inter_warehouse_room *IS = warehouse->last_room;
    int at = IS->room_usage;
    for (int i=0; i<total_extent; i++) IS->bytecode[at + i] = 0;
    IS->bytecode[at + PREFRAME_SKIP_AMOUNT] = (inter_ti) total_extent;
    IS->room_usage += total_extent;

    warehouse_floor_space W;
    W.in_room = IS; W.index = at;
    if ((IS) && (at >= 0) && (at < IS->room_usage)) {
        W.instruction = &(IS->bytecode[at + PREFRAME_SIZE]);
        W.extent = ((int) IS->bytecode[at + PREFRAME_SKIP_AMOUNT]) - PREFRAME_SIZE;
    } else {
        W.instruction = NULL; W.extent = 0;
    }
    return W;
}

§15.1. Make a new and bigger room if necessary15.1 =

    inter_warehouse_room *IS = warehouse->last_room;
    if ((IS == NULL) || (IS->room_usage + total_extent > IS->room_capacity)) {
        if (IS) IS->room_capacity = IS->room_usage;

        int new_capacity = 4096;
        if (IS) new_capacity = 2*IS->room_capacity;
        while (total_extent >= new_capacity) new_capacity = 2*new_capacity;

        inter_warehouse_room *new_room = CREATE(inter_warehouse_room);
        new_room->owning_warehouse = warehouse;
        new_room->room_usage = 0;
        new_room->room_capacity = new_capacity;
        new_room->bytecode = (inter_ti *)
            Memory::calloc(new_capacity, sizeof(inter_ti), INTER_BYTECODE_MREASON);
        LOGIF(INTER_MEMORY, "Created warehouse room %d with capacity %08x\n",
            new_room->allocation_id, new_room->room_capacity);
        if (IS) IS->next_room = new_room;
        else warehouse->first_room = new_room;
        warehouse->last_room = new_room;
    }

• This code is used in §15.

§16. Secondly, InterWarehouse::enlarge_floor_space adds extra length to an existing instruction — which may involve moving its bytecode to a bigger room, in the worst case, but is more typically very fast. Note that this function may only be called on the floor space for the most-recently creates instruction, so the floor space is guaranteed to be at the end of the space used in the current room.

by cannot be negative (it is unsigned). The instruction therefore always extends, not contracts. The values of the new words added are undefined: they will very likely be 0 but do not rely upon this.

Note that this function always succeeds, because an internal error is thrown if the system is out of memory.

warehouse_floor_space InterWarehouse::enlarge_floor_space?Usage of InterWarehouse::enlarge_floor_space:
Inter Nodes - §12(warehouse_floor_space FW,
    inter_ti by) {
     Have we already moved on to building further instructions?
    if (FW.in_room->next_room) internal_error("too late to extend instruction");

    if (FW.in_room->room_usage + (int) by <= FW.in_room->room_capacity)
        The existing room already has sufficient capacity to accommodate the extra16.1
    else
        The existing room is not big enough16.2;

    return FW;
}

§16.1. The existing room already has sufficient capacity to accommodate the extra16.1 =

    FW.in_room->bytecode[FW.index + PREFRAME_SKIP_AMOUNT] += by;
    FW.in_room->room_usage += by;
    FW.extent += by;

• This code is used in §16.

§16.2. The existing room is not big enough16.2 =

    warehouse_floor_space new_W =
        InterWarehouse::make_floor_space(FW.in_room->owning_warehouse, FW.extent + (int) by);

    FW.in_room->room_usage = FW.index;
    FW.in_room->room_capacity = FW.index;

    Copy the bytecode for the preframe and frame to its new home16.2.1;

• This code is used in §16.

§16.2.1. Copy the bytecode for the preframe and frame to its new home16.2.1 =

    for (int i=0; i<PREFRAME_SIZE; i++)
        if (i != PREFRAME_SKIP_AMOUNT)
            new_W.in_room->bytecode[new_W.index + i] = FW.in_room->bytecode[FW.index + i];

    for (int i=0; i<new_W.extent; i++)
        if (i < FW.extent)
            new_W.instruction[i] = FW.instruction[i];
        else
            new_W.instruction[i] = 0;

    FW = new_W;

• This code is used in §16.2.