write_segregated_fit.cpp

#include "write.h"
#include <algorithm>
#include <random>
///////// "Segregated Fit" Allocation

//// Storage strategy: Allocate larger continuous spaces on disk to larger objects, and fragmented spaces to small objects

void Writer::do_segregated_fit(std::vector<int> &object_unit, std::vector<int> &disk_unit, int size, int object_id, int lower_bound, int upper_bound, int* current_write_point) {
    // 1. Scan for free space on disk
    std::vector<std::pair<int, int>> free_blocks; // {Start position, continuous free block length}
    int start = -1, length = 0;
    
    if(lower_bound > upper_bound){
        std::swap(lower_bound, upper_bound);
    }
    for (int i = lower_bound; i <= upper_bound; i++) {
        if (disk_unit[i] == 0) { // Free block
            if (start == -1) start = i;
            length++;
        } else { // Non-free block
            if (length > 0) {
                free_blocks.emplace_back(start, length);
            }
            start = -1;
            length = 0;
        }
    }
    if (length > 0) { // Handle the last free block
        free_blocks.emplace_back(start, length);
    }

    // 2. Sort by continuous free block length in ascending order
    std::sort(free_blocks.begin(), free_blocks.end(), [](const std::pair<int, int> &a, const std::pair<int, int> &b) {
        return a.second < b.second;
    });


   ///////////////// 3. Allocate space and write ////////////////////
    
    for (auto &block : free_blocks) {// block: {Start position, continuous free block length}
        int block_start = block.first;
        int block_length = block.second;
        int previous_write_point = *current_write_point;
        
        if(block_length >= size){
            for(int p = 0; p < size; p++){
                disk_unit[block_start + p] = object_id;
                object_unit[++*current_write_point] = block_start + p;
            }
            break;
        }
    }
}