dan

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define n 65
#define block 5

int indexToBlock(int cell);
int blockToIndex(int blk);
int powerExp(int exp);
int power(int value, int powerValue);
void deletefile(char* method, int *memArray);
int findReqBlocksWithPtr(int rows);
int *findFreeBlock(int reqBlocks, long decBitmap, char* method);
long decimalToBinary(long dec);
long binaryToDecimal(long bin);
int *getDirectoryData(int data, char* method);
int *newMemory();
int getFileName(int a);
void printDiskMap(char* method, int *memArray);






int foundStart, foundEnd;
int startIndex;




/* main function to call above defined function */
int main () {

    int *memory;
    char * allocMethod;

    allocMethod = "indexed";
    memory = newMemory();
    memory[1] = 10002;
    memory[blockToIndex(1)] = binaryToDecimal(11100111110);
    memory[10] = 8;
    memory[11] = 9;
    memory[40] = 101;
    memory[41] = 102;
    memory[42] = 103;
    memory[43] = 104;
    memory[44] = 105;
    memory[45] = 106;

    // printDiskMap(allocMethod,memory);

    free(memory);
    allocMethod = "contiguous";
    memory = newMemory();
    memory[40] = 40;

    memory[0]=1000202;
    memory[1]= 2000505;
    memory[10] =101;
    memory[11] =102;
    memory[12] =103;
    memory[13] =104;
    memory[14] =105;
    memory[15] =106;
    memory[16] =107;
    memory[17] =108;
    memory[18] =109;
    memory[19] =110;
    memory[20] =111;
    memory[21] =112;
    memory[22] =113;
    memory[23] =114;
    memory[24] =115;

    deletefile(allocMethod, memory);
    printDiskMap(allocMethod,memory);

    free(memory);
    allocMethod = "linked";
    memory = newMemory();

    memory[0]=1000204;
    memory[1]= 2000505;
    memory[10]= 101;
    memory[11]= 102;
    memory[12] = 103;
    memory[13] = 104;
    memory[14] = 4;
    memory[20] = 105;
    memory[21]= 106;
    memory[25] = 201;
    memory[26] = 202;
    memory[27] = 203;

    //deletefile(allocMethod, memory);
    //printDiskMap(allocMethod,memory);




    /* testing getDirectoryData function
    int *dataArray;
    dataArray = getDirectoryData(678911, "linked");
    printf("Filename: %d | start: %d | end: %d\n",dataArray[0],dataArray[1],dataArray[2]);
    */


    /* testing findFreeBlock function
    long todec = 1111100000;
    printf("%ld\n",todec);


    int *testArray;
    long bitmap = binaryToDecimal(todec);
    testArray = findFreeBlock(3, bitmap, "contiguous");
    //printf("Contiguous free block: %d\n\n",testArray[0]);

    testArray = findFreeBlock(6, bitmap, "linked");
    printf("linked free block: ");
    for (int i = 0; i < 6; i++){
        //printf("%d ",testArray[i]);
    }

    testArray = findFreeBlock(5, bitmap, "indexed");
    printf("\nindexed free block: ");
    for (int i = 0; i < 6; i++){
        printf("%d ",testArray[i]);
    }
    */

    return 0;
}

int indexToBlock(int cell){
    return cell/5;
}

int blockToIndex(int blk){
    return blk*5;
}

int powerExp(int exp){
    int result = 1;
    int base = 10;
    for (exp;exp>0;exp--){
        result *= base;
    }
    return result;

}

int power(int value, int powerValue){
    int result = 1;
    for (int i = 0; i < powerValue; i++){
        result *= value;
    }
    return result;
}

int getFileName(int a) {

    int fileName;
    return fileName = (a/100)*100;

}


int findReqBlocksWithPtr(int rows){
    int reqBlocks = 0;
    // if theres 5 or less rows, only 1 block is needed
    if (rows <= 5){
        reqBlocks = 1;
    }

        // if theres more than 5 rows, each block can only store
        // the location of 4 blocks, and 1 pointer
    else {
        while (rows > 0) {
            // if 1 block is remaining, it does not need 1 more index block, it can fit in the last index block
            // there is only 4 blocks used in the last index block and we dont need a pointer for it
            if (rows != 1){
                rows -= 4;
                reqBlocks++;
            }
            else {
                break;
            }
        }
    }
    return reqBlocks;
}

int *findFreeBlock(int reqBlocks, long decBitmap, char* method){
    // convert dec bitmap to bin bitmap
    long binBitmap = decimalToBinary(decBitmap);
    // how many bits the bitmap have
    int nDigits = 1;
    long countData = binBitmap;
    // divide by 10 until countData is left with a single digit
    while (countData > 9) {
        nDigits++;
        countData /= 10;
    }
    //printf("digits: %d\n", nDigits);

    int freeBlocksCount = 0, counter = 0;

    long remainder;
    // finding free blocks for contiguous
    if (strcmp(method, "contiguous") == 0){
        // create array of size 1 and set it to -1
        static int freeBlockFound[1] = {-1};
        while(binBitmap != 0) {
            remainder = binBitmap%10;
            if (remainder == 1){
                // free block found
                if (freeBlocksCount == 0){
                    // new free block
                    freeBlockFound[0] = counter+2;
                }
                freeBlocksCount +=1;
                if (freeBlocksCount == reqBlocks){
                    return freeBlockFound;
                }
            }
            else {
                freeBlocksCount = 0;
                freeBlockFound[0] = -1;
            }

            binBitmap /= 10;
            counter++;
        }
        // no space for conti allocation
        freeBlockFound[0] = -1;
        return freeBlockFound;
    }

        // finding free blocks for linked
    else if (strcmp(method, "linked") == 0){
        // static int freeBlockFound[reqBlocks];
        // create array of size required blocks size and set it to -1
        int *freeBlockFound = malloc(reqBlocks * sizeof *freeBlockFound);

        while(binBitmap != 0) {
            remainder = binBitmap%10;
            if (remainder == 1){
                // free block found
                freeBlocksCount++;
                freeBlockFound[freeBlocksCount-1] = counter + 2;
                if (freeBlocksCount == reqBlocks){
                    return freeBlockFound;
                }
            }

            binBitmap /= 10;
            counter++;
        }
        // no space for linked allocation
        freeBlockFound[0] = -1;
        return freeBlockFound;
    }

        // finding free blocks for indexed
    else {
        // calculate number of index blocks required for index allocation
        int reqIndexBlocks = findReqBlocksWithPtr(reqBlocks);

        // create array of and set it to -1. Every free data and index block found will be stored here
        int *freeBlockFound = malloc((reqBlocks + reqIndexBlocks) * sizeof *freeBlockFound);
        int enoughFreeIndex = 0;
        while(binBitmap != 0) {
            remainder = binBitmap%10;
            // 5 blocks for index, find free index blocks
            if (counter < 5){
                // dont need to check already once we know we have enough index blocks
                if (enoughFreeIndex == 0){
                    printf("\nChecking indexed block");
                    if (remainder == 1) {
                        printf ("\nfree index block found at: %d",counter+2);
                        // free index block found
                        freeBlocksCount++;
                        freeBlockFound[freeBlocksCount-1] = counter + 2;
                        if (freeBlocksCount == reqIndexBlocks) {
                            enoughFreeIndex = 1;
                            printf("enough index");
                        }
                    }
                }

            }
                // will run below code once done checking for free index blocks
            else if (enoughFreeIndex == 0) {
                // no space in index blocks
                freeBlockFound[0] = -1;
                printf("not enough index");
                return freeBlockFound;
            }
            else {
                if (remainder == 1) {
                    printf ("\nfree data block found at: %d",counter+2);
                    freeBlocksCount++;
                    freeBlockFound[freeBlocksCount-1] = counter + 2;
                    if (freeBlocksCount == reqBlocks + reqIndexBlocks){
                        return freeBlockFound;
                    }
                }
            }
            binBitmap /= 10;
            counter++;
        }
        // no space for indexed allocation
        freeBlockFound[0] = -1;
        return freeBlockFound;


    }
}

/* Function to convert a decinal number to binary number */
long decimalToBinary(long dec) {
    long remainder;
    long binary = 0, i = 1;

    while(dec != 0) {
        remainder = dec % 2;
        dec /= 2;
        binary += (remainder*i);
        i = i*10;
    }
    return binary;
}

/* Function to convert a binary number to decimal number */
long binaryToDecimal(long bin) {
    long remainder;
    long decimal = 0, i = 0;
    while(bin != 0) {
        remainder = bin % 10;
        bin /= 10;
        decimal += (remainder*power(2,i));
        ++i;
    }
    return decimal;
}




void deletefile(char* method, int *memArray) {

    //link

    int userinput = 100;


//compare with method name.
    for (int i = 0; i < 5; i++) {

        if (userinput == getDirectoryData(memArray[i], method)[0]) {

            foundStart = getDirectoryData(memArray[i], method)[1];// start block;
            foundEnd = getDirectoryData(memArray[i], method)[2];
            memArray[i] = -1;
            startIndex = blockToIndex(foundStart);
            //printf("%d", startIndex);

        }

    }
    if (strcmp(method, "linked") == 0) {

        while (foundStart != foundEnd) {

            foundStart = memArray[startIndex + 4];

            for (int i = startIndex; i < startIndex + 5; i++) {
                memArray[i] = 2;

            }

            startIndex = blockToIndex(foundStart);

            printf("%d", foundStart);

        }

        for (int i = startIndex; i <  (foundEnd-foundStart) ; i++) {
            memArray[i] = 2;

        }

    } else if (strcmp(method, "contiguous") == 0) {
        for (int i = startIndex; i < (15                                                                        ); i++) {
            memArray[i] = 1;

        }
    }
}

int *getDirectoryData(int data, char* method){

    // how many digits the data have
    int nDigits = 1, countData = data;
    while (countData > 9) {
        nDigits++;
        countData /= 10;
    }
    //  printf("digits: %d\n", nDigits);

    // extracting individual digits
    int digitsArray[nDigits];
    memset( digitsArray, 0,nDigits*sizeof(int) );
    int digitsArrayInd = nDigits - 1;

    int remainder;
    while(data != 0)
    {
        remainder = data%10;
        digitsArray[digitsArrayInd--] = remainder;
        data /= 10;
    }

    // converting individual digits into correct data
    static int dataArray[3] = {0};
    int dataArrayInd = nDigits -1;

    if (strcmp(method, "indexed") == 0){
        // INDEXED
        // e.g. [1,2,3,4,5] = filename: 123, indexedLocation: 45
        dataArray[0] = 0;
        dataArray[1] = digitsArray[dataArrayInd--] + (digitsArray[dataArrayInd--]*10);
        for (int i = 0; i < nDigits-2; i++){
            if (i == 0){
                dataArray[0] += digitsArray[dataArrayInd--];
            }
            else {
                dataArray[0] += (digitsArray[dataArrayInd--] * powerExp(i));
            }
        }
    }
    else {
        // CONTIGUOUS/LINKED
        // e.g. [1,2,3,4,5,6,7] = filename: 123, start: 45, end: 67
        dataArray[0] = 0;
        dataArray[2] = digitsArray[dataArrayInd--] + (digitsArray[dataArrayInd--]*10);
        dataArray[1] = digitsArray[dataArrayInd--] + (digitsArray[dataArrayInd--]*10);
        for (int i = 0; i < nDigits-4; i++){
            if (i == 0){
                dataArray[0] += digitsArray[dataArrayInd--];
            }
            else {
                dataArray[0] += (digitsArray[dataArrayInd--] * powerExp(i));
            }
        }
    }


    return dataArray;

}

int *newMemory(){

    int *mem = malloc(n * sizeof *mem);

    // all allocation methods will have 1 block reserved for directory
    for (int i = 0; i < block; i++){
        // -1 meaning empty
        mem[i] = -1;
    }

    // all allocation methods will have 1 block reserved for bitmap
    for (int i = block; i < 2*block; i++){
        // every entry is pointing to next entry (empty space)
        if (i == block){
            // only first cell of bitmap block will be used
            mem[i] = binaryToDecimal(11111111111);
        }
        else {
            // the rest set as -1
            mem[i] = -1;
        }
    }

    // everything else will be empty data blocks
    for (int i = 2*block; i < n; i++){
        mem[i] = -1;
    }

    return mem;
}

void printDiskMap(char* method, int *memArray){
    printf("-Disk map for %s allocation method-\n", method);

    int *dataArray;

    //printing directory
    if (strcmp("indexed",method) == 0){
        for (int i = 0; i < block; i++){
            if (memArray[i] < 0){
                printf("%2d - B%-2d - %s \n",i,indexToBlock(i),"empty");
            }
            else {
                dataArray = getDirectoryData(memArray[i],method);
                printf("%2d - B%-2d - %d, %d \n",i,indexToBlock(i),dataArray[0],dataArray[1]);
            }
        }
    }
    else {
        for (int i = 0; i < block; i++){
            if (memArray[i] < 0){
                printf("%2d - B%-2d - %s \n",i,indexToBlock(i),"empty");
            }
            else {
                dataArray = getDirectoryData(memArray[i],method);
                printf("%2d - B%-2d - %d, %d, %d \n",i,indexToBlock(i),dataArray[0],dataArray[1],dataArray[2]);
            }
        }
    }



    // printing bitmap block
    printf("%2d - B%-2d - %d\n",block,indexToBlock(block),memArray[block]);
    for (int i = block+1; i < 2*block; i++){
        printf("%2d - B%-2d - Unused\n",i,indexToBlock(i));
    }

    // printing index and data
    for (int i = 2*block; i < n; i++){
        printf("%2d - B%-2d - %d\n",i,indexToBlock(i),memArray[i]);
    }

}

/*****************************************************************
/* NOTES / TO-DO / QUESTIONS
/*****************************************************************

 [Directory data - Block 0]
    When empty: -1
    When not empty:
        Indexed: 543289
        (5432 - file name[1-4 digits], immediately followed by 89 - index location[MUST be 2 digits])

        Linked & Contiguous: 54326789
        (5432 - file name[1-4 digits], immediately followed by 67 - start[Must be 2 digits], then 89 - end[Must be 2 digits])

 [Bitmap - Block 1]
   1 representing empty space, 0 representing used space
   Read backwards - LSB is block 2


 [Index]
    When empty: -1
    When not empty: pointer to data location

  [File data]
    When empty: -1
    when not empty: a positive number




*/