infos.slots.md

To answer your question, neither remove_block or insert_block alters the pgd given to it.

So after a bit of reading of the code I think I finally understand why it uses pointers^squared. I hope I haven't overexplained anything but this might help someone. Someone else pls correct me if i'm wrong.

Blocks:

• Some .. block .. of memory.
• It's important to remember that a PageDescriptor is not a block itself, and neither is a PageDescriptor*. Read on.

Page Descriptors:

• The type is PageDescriptor* pgd. We should not be copying these around, so that's why we always have this one layer of pointer.
• A singular PageDescriptor is a way to refer to a block (so in a sense, a pointer to a block).
• But we only actually use PageDescriptor* because we want edits to PageDescriptors to propagate through the entire program.
• Example: when we modify pgd->next_free, it will affect any part of the program that has a hold of that individual PageDescriptor.
• This "one layer of pointer" is compulsory to make updates of next_free work properly, so just ignore the fact it's a pointer to a PageDescriptor.

Slots:

• The type is PageDescriptor** slot.
• The insert_block docstring describes slots as: "a pointer to the pointer that points to the block".
• We can interpret this as just a "location of something holding a page descriptor". (Remember, we always use PageDescriptor* but that doesn't matter)

Walking through remove_block:

void remove_block(PageDescriptor *pgd, int order) {
    // (1) Starting from the _free_area array, iterate until the block has been located in the linked-list.
    PageDescriptor **slot = &_free_areas[order];

    // (1) Qais: so slot is just a pointer to where the page descriptor is stored, so we can do `_free_areas[order] = x`
    //           without explicitly holding reference to _free_areas[order]
    //
    //          So doing _free_areas[order] = nullptr;
    //
    //          Is the same as doing this (using the slot from above):
    //              *slot = nullptr;
    //

    // Qais: now this for-loop is searching through the linked list to find a `some_pgd->next` that refers to the block we want to remove.
    //       We could immediately edit some_pgd->next by doing `some_pgd->next = x`, but we store the address of `next` so we can edit it later.
    while (*slot && pgd != *slot) {
        slot = &(*slot)->next_free;
    }

    // (2) Qais: Doing `*slot == pgd` is the same as doing `some_pgd->next == pgd`. Or `_free_areas[order] == pgd`. We use "slot" to abstract away this difference.

    // (2) Make sure the block actually exists.  Panic the system if it does not.
    assert(*slot == pgd);

    // (3) Qais: again, `some_pgd->next = pgd->next` or `_free_areas[order] = pgd->next_free`, using a "slot" to abstract away this difference.
    
    // (3) Remove the block from the free list.
    *slot = pgd->next_free;
    pgd->next_free = NULL;
}

If we reimplemented remove_block (untested, so probably wrong), it might be something like this. Hope this is easier to understand (without using slots):

void remove_block(PageDescriptor* pgd, int order) {
    // Check if the first free item is pgd...
    if (_free_areas[order] == pgd) {
        // ... if so, replace the first free area with the pgd->next_free
        _free_areas[order] = pgd->next_free;

        // done!
        return;
    }

    // Okay, so we need to loop through and find pgd then.
    // Lets start off with the first free area.
    PageDescriptor* curr = _free_areas[order];

    // While `curr` exists. This is the same as doing `while (curr)`
    while (curr != nullptr) {
        // If curr->next_free is pgd
        if (curr->next_free == pgd) {
            curr->next_free = pgd->next_free;
            pgd->next_free = nullptr;

            // done!
            return;
        }

        // Set the next `curr` to the next free item.
        // Note that the next free item may not exist, and could be nullptr.
        curr = curr->next_free;
    }

    panic(); // !!!!! we should have returned earlier!! the block does not exist anywhere
    return;
}