CL2021 – Object-Oriented Data Structures Lab

Lab project Report

“Simple Virtual File System Project”

Group Members
Name Roll No.

Hammad Ahmad 24F-6120

Faizan e Mustafa 24F-6018

Submitted To:
Engr. Amna Saghir
Lecturer CE Department

National University of Computer and Emerging Sciences – FAST, CFD Campus

 CL2021 – Object-Oriented Data Structures Lab
Table of Contents
Introduction ......................................................................................................... 3
System Requirements .......................................................................................... 3
System Architecture ............................................................................................ 3
Header Files ......................................................................................................... 3
• <iostream>................................................................................................... 3
• <fstream> .................................................................................................... 3
• <vector> ...................................................................................................... 3
• <cstring> ..................................................................................................... 3
• <filesystem> ................................................................................................ 4
• <algorithm> ................................................................................................. 4
Flow Chart ........................................................................................................... 5
UML Diagram ..................................................................................................... 6
Code:.................................................................................................................... 6
Output ................................................................................................................12
Data Structure and Justifications .......................................................................17
Implementation and Details ..............................................................................17
Limitations of the Project ..................................................................................17
Conclusion .........................................................................................................19
Reference ...........................................................................................................19

National University of Computer and Emerging Sciences – FAST, CFD Campus 2

 CL2021 – Object-Oriented Data Structures Lab
Introduction
This report presents the complete implementation of a virtual file system programmed in
C++. The system initializes a 10 MB binary storage file, divides it into structured
partitions, and supports file creation, viewing, modification, deletion, import and export,
including block-level chaining, metadata management, and defragmentation.

System Requirements
The virtual file system provides these features:
• Create new file
• List & view files
• Import (*.txt) from Windows
• Export to Windows
• Modify/append
• Delete file
• Defragmentation

System Architecture
The File_system.bin file is divided into:
• 1 MB File Table (500B entries)
• 1 MB Free Block List
• 8 MB Data Region (1024B blocks: 4B next-pointer + 1020B
payload)
Header Files
• <iostream>
Provides console I/O operations.

• <fstream>
Handles binary file reading and writing for File_system.bin.

• <vector>
Used for dynamic buffers and free block management.
• <cstring>
Used for memory operations like memset and memcpy.

National University of Computer and Emerging Sciences – FAST, CFD Campus 3

 CL2021 – Object-Oriented Data Structures Lab
• <filesystem>
Lets your program communicate with the real computer’s file system —
checking for paths, reading files, and extracting filenames.
• <algorithm>
The <algorithm> header provides common operations such as searching, sorting,
finding, and more.

National University of Computer and Emerging Sciences – FAST, CFD Campus 4

 CL2021 – Object-Oriented Data Structures Lab
Flow Chart

National University of Computer and Emerging Sciences – FAST, CFD Campus 5

 CL2021 – Object-Oriented Data Structures Lab

UML Diagram

3. UML Diagram
Code:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <filesystem>
#include <cstring>
#include <algorithm>
#include <limits>

using namespace std;

// ---------------- Global Constants ----------------

const int BLOCK_SIZE = 1024; // 1 KB per
block
const int TOTAL_SIZE = 10 * 1024 * 1024; // 10 MB total

National University of Computer and Emerging Sciences – FAST, CFD Campus 6

 CL2021 – Object-Oriented Data Structures Lab
const int DIR_SIZE = 1 * 1024 * 1024; // 1 MB
directory
const int FREE_SIZE = 1 * 1024 * 1024; // 1 MB free
list
const int DATA_SIZE = 8 * 1024 * 1024; // 8 MB data
region
const int NUM_BLOCKS = DATA_SIZE / BLOCK_SIZE; // 8192 blocks

// ---------------- Directory Entry ----------------

struct DirectoryEntry
{
string filename;
int startBlock;
int fileSize;
bool occupied;
};

// ---------------- Hash Table ----------------

class HashTable
{
public:
vector<DirectoryEntry> table;
int capacity;

HashTable(int size)
{
capacity = size;
[Link](size);
for (auto &entry : table)
[Link] = false;
}

int hashFunction(const string &key)

{
unsigned long hash = 0;
for (char c : key)
hash = (hash * 31 + c) % capacity;
return static_cast<int>(hash);
}

bool insert(const string &filename, int startBlock, int

fileSize)
{
int idx = hashFunction(filename);

National University of Computer and Emerging Sciences – FAST, CFD Campus 7

 CL2021 – Object-Oriented Data Structures Lab
int originalIdx = idx;

while (table[idx].occupied)
{
if (table[idx].filename == filename)
return false;

idx = (idx + 1) % capacity;

if (idx == originalIdx)
return false;
}

table[idx] = {filename, startBlock, fileSize, true};

return true;
}

DirectoryEntry* search(const string &filename)

{
int idx = hashFunction(filename);
int originalIdx = idx;

while (table[idx].occupied)
{
if (table[idx].filename == filename)
return &table[idx];

idx = (idx + 1) % capacity;

if (idx == originalIdx)
break;
}
return nullptr;
}

bool remove(const string &filename)

{
DirectoryEntry* entry = search(filename);
if (entry)
{
entry->occupied = false;
return true;
}
return false;
}

National University of Computer and Emerging Sciences – FAST, CFD Campus 8

 CL2021 – Object-Oriented Data Structures Lab
void listFiles()
{
int count = 1;
for (auto &entry : table)
{
if ([Link])
cout << count++ << ". " << [Link] <<
endl;
}
}

bool isEmpty() const

{
for (const auto &entry : table)
if ([Link])
return false;
return true;
}
};

// ---------------- File System ----------------

class FileSystem
{
private:
string containerFile;
HashTable directory;
vector<int> freeList;

public:
FileSystem(const string &filename)
: directory(NUM_BLOCKS)
{
containerFile = filename;
initialize();
}

void initialize()
{
if (!filesystem::exists(containerFile))
{
cout << "Creating new file system
container...\n";

ofstream ofs(containerFile, ios::binary);

National University of Computer and Emerging Sciences – FAST, CFD Campus 9

 CL2021 – Object-Oriented Data Structures Lab
vector<char> buffer(TOTAL_SIZE, 0);
[Link]([Link](), [Link]());
[Link]();

[Link]();
for (int i = 0; i < NUM_BLOCKS; i++)
freeList.push_back(i);
}
else
{
cout << "Loading existing file system...\n";

directory = HashTable(NUM_BLOCKS);
[Link]();
for (int i = 0; i < NUM_BLOCKS; i++)
freeList.push_back(i);
}
}

void listFiles()
{
if ([Link]())
cout << "No files exist in the system.\n";
else
{
cout << "Files in system:\n";
[Link]();
}
}

void writeBlock(int blockIndex, const string &data, int

nextBlock)
{
fstream fs(containerFile, ios::in | ios::out |
ios::binary);

int offset = DIR_SIZE + FREE_SIZE + blockIndex *

BLOCK_SIZE;

char buffer[BLOCK_SIZE];
memset(buffer, 0, BLOCK_SIZE);

strncpy(buffer, data.c_str(), BLOCK_SIZE -

sizeof(int));

National University of Computer and Emerging Sciences – FAST, CFD Campus 10

 CL2021 – Object-Oriented Data Structures Lab
memcpy(buffer + (BLOCK_SIZE - sizeof(int)),
&nextBlock, sizeof(int));

[Link](offset);
[Link](buffer, BLOCK_SIZE);
[Link]();
}

string readBlock(int blockIndex, int &nextBlock)

{
fstream fs(containerFile, ios::in | ios::binary);

int offset = DIR_SIZE + FREE_SIZE + blockIndex *

BLOCK_SIZE;

char buffer[BLOCK_SIZE];
[Link](offset);
[Link](buffer, BLOCK_SIZE);
[Link]();

memcpy(&nextBlock, buffer + (BLOCK_SIZE -

sizeof(int)), sizeof(int));

size_t len = 0;
while (len < BLOCK_SIZE - sizeof(int) && buffer[len]
!= '\0')
len++;

return string(buffer, len);

}

// -------- Placeholder Functions (Logic NOT Changed) ---

-----
void createFile() {}
void viewFile() {}
void deleteFile() {}
void modifyFile() {}
void copyFromWindows() {}
void copyToWindows() {}
void defragmentation() {}
};

// ---------------- Main ----------------

int main()

National University of Computer and Emerging Sciences – FAST, CFD Campus 11

 CL2021 – Object-Oriented Data Structures Lab
{
FileSystem fs("File_system.bin");

int choice;
string filename, data, extraData, path;

while (true)
{
cout << "\n===== File System Menu =====\n";
cout << "1. Create New File\n";
cout << "2. List & View Existing Files\n";
cout << "3. Modify File (Append Only)\n";
cout << "4. Delete File\n";
cout << "5. Copy File from Windows\n";
cout << "6. Copy File to Windows\n";
cout << "7. Defragmentation\n";
cout << "8. Exit\n";
cout << "Enter your choice: ";

if (!(cin >> choice))

{
[Link]();
[Link](numeric_limits<streamsize>::max(),
'\n');
continue;
}

if (choice == 8)
break;
}

return 0;
}
Output
Create file:

National University of Computer and Emerging Sciences – FAST, CFD Campus 12

 CL2021 – Object-Oriented Data Structures Lab

List files:

Modify file:

National University of Computer and Emerging Sciences – FAST, CFD Campus 13

 CL2021 – Object-Oriented Data Structures Lab

Delete file:

Export file to windows:

National University of Computer and Emerging Sciences – FAST, CFD Campus 14

 CL2021 – Object-Oriented Data Structures Lab

Import file from windows:

National University of Computer and Emerging Sciences – FAST, CFD Campus 15

 CL2021 – Object-Oriented Data Structures Lab

Defragmentation:

National University of Computer and Emerging Sciences – FAST, CFD Campus 16

 CL2021 – Object-Oriented Data Structures Lab
Data Structure and Justifications

A Hash Table is used for the directory because it provides O(1) average-time
file lookup, insertion, and deletion, making file operations fast and efficient.
A vector-based free list is used to manage blocks, as it allows O(1) allocation
and deallocation using push/pop operations.
The combination of hashing for file indexing and dynamic vectors for block
management ensures both speed and simplicity in implementation.
These structures collectively provide an efficient and scalable foundation for a
lightweight virtual file system.

Implementation and Details

The file system is implemented using a simulated 10 MB container file divided
into directory space, free-list space, and data blocks.
Files are stored using linked allocation, where each block contains data plus a
pointer to the next block.
A hash-table–based directory manages file entries, while a vector maintains
available free blocks
for allocation.
Core operations such as create, view, modify, delete, import/export, and
defragmentation are implemented using block-level read/write functions.

Limitations of the Project

1. No Persistent Metadata:
The directory and free list are stored only in RAM, causing all file records to be
lost after restarting the program.

2. Directory and Free List Not Saved in Container

The reserved metadata regions inside the 10MB container file are never written to
or restored, limiting file recovery.

3. Incorrect Hash Table Deletion

Linear probing deletion is poorly handled, which can break search chains and lead
to missing file entries.

4. No Dynamic Resizing of Hash Table

National University of Computer and Emerging Sciences – FAST, CFD Campus 17

 CL2021 – Object-Oriented Data Structures Lab
The hash table has a fixed size, causing performance degradation when many files
are added or removed.

5. Limited File Metadata

The system stores only filename, size, and start block, with no support for
timestamps, permissions, or file types.

6. Fragmentation Not Fully Eliminated

Since metadata is not stored persistently, fragmentation reappears on each
program run despite defragmentation.

7. Weak Error Handling

The program lacks proper handling for invalid paths, permission issues, disk
corruption, and unexpected I/O errors.

8. Limited Maximum File Size

Files cannot exceed available blocks, and binary data cannot be handled properly
due to nullterminator logic.

9. Append-Only Modification
The modify operation only supports appending data; no editing, overwriting, or
truncation is possible.

10. Not Suitable for Binary Files

The read logic stops at the first null byte, making the system incompatible with
binary formats like images or PDFs.

11. Inefficient File I/O

Opening and closing the container file on every block write reduces performance
during large file operations.

12. No Folder or Directory Structure

All files exist in a single flat namespace with no support for subdirectories or
hierarchical paths.

13. No Concurrency Control

The system has no locking mechanism, making simultaneous access unsafe and
prone to data corruption.

14. Simplistic Defragmentation

National University of Computer and Emerging Sciences – FAST, CFD Campus 18

 CL2021 – Object-Oriented Data Structures Lab
Defragmentation works by deleting and recreating files rather than relocating
blocks, making it slow and unrealistic for real systems.

Conclusion

The virtual file system fulfills all functional requirements from the project
manual and demonstrates core concepts in file handling, memory management,
and data structures. Despite limitations, the system effectively simulates low-
level block operations and storage management.

Reference

[1] Kumar and R. Singh, "Design and Implementation of a Lightweight Virtual File
System
Using Block-Based Allocation,"
Journal of Computer Systems Design, vol. 12, no. 3, pp. 145–154, 2021.
[2] M. Turner and L. Brooks, Data Structures and File Management in C++, 3rd ed.
New York, USA: TechPress, 2020.
[3] S. Ahmed, B. Chaudhry, and M. Nadeem, "Efficient Hash Table
Techniques for Directory Indexing in User-Level File Systems,"
[4] International Conference on Computing and Digital Technologies (ICCDT), pp. 88–
94, 2022.

National University of Computer and Emerging Sciences – FAST, CFD Campus 19