Directory Structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253

/*
 * Single-Level Directory Implementation
 * Demonstrates the core data structures and operations of a flat directory.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>
 
#define MAX_FILENAME_LENGTH 32
#define MAX_FILES 256
#define BLOCK_SIZE 512
 
/*
 * Directory Entry Structure
 * Each file in the system has exactly one entry in the global directory.
 */
typedef struct {
    char name[MAX_FILENAME_LENGTH];  /* Unique file name */
    uint32_t size;                    /* File size in bytes */
    uint32_t first_block;             /* Starting disk block */
    uint16_t block_count;             /* Number of allocated blocks */
    time_t created;                   /* Creation timestamp */
    time_t modified;                  /* Last modification timestamp */
    uint8_t permissions;              /* Read/write/execute flags */
    bool in_use;                      /* Entry is active (not deleted) */
} DirectoryEntry;
 
/*
 * Single-Level Directory
 * The entire file system directory in one flat structure.
 */
typedef struct {
    DirectoryEntry entries[MAX_FILES];
    int file_count;
} SingleLevelDirectory;
 
/*
 * Initialize the directory system.
 * Clears all entries and sets up for first use.
 */
void init_directory(SingleLevelDirectory *dir) {
    memset(dir, 0, sizeof(SingleLevelDirectory));
    dir->file_count = 0;
    
    /* Mark all entries as unused */
    for (int i = 0; i < MAX_FILES; i++) {
        dir->entries[i].in_use = false;
    }
    
    printf("Directory initialized. Capacity: %d files\n", MAX_FILES);
}
 
/*
 * Find a file by name.
 * Returns: index of entry if found, -1 if not found.
 * 
 * Time Complexity: O(n) where n is the number of entries
 * This linear search is a fundamental limitation of flat directories.
 */
int find_file(SingleLevelDirectory *dir, const char *filename) {
    for (int i = 0; i < MAX_FILES; i++) {
        if (dir->entries[i].in_use && 
            strcmp(dir->entries[i].name, filename) == 0) {
            return i;
        }
    }
    return -1;  /* File not found */
}
 
/*
 * Create a new file in the directory.
 * 
 * Critical constraint: Filename must be UNIQUE across entire system.
 * This is the fundamental limitation that drives hierarchical design.
 */
int create_file(SingleLevelDirectory *dir, const char *filename, 
                uint32_t initial_size) {
    /* Check for naming collision - the core single-level problem */
    if (find_file(dir, filename) != -1) {
        printf("ERROR: File '%s' already exists. Names must be unique!\n", 
               filename);
        return -1;
    }
    
    /* Check filename length constraint */
    if (strlen(filename) >= MAX_FILENAME_LENGTH) {
        printf("ERROR: Filename exceeds %d character limit.\n", 
               MAX_FILENAME_LENGTH - 1);
        return -1;
    }
    
    /* Find an empty slot in the directory */
    int slot = -1;
    for (int i = 0; i < MAX_FILES; i++) {
        if (!dir->entries[i].in_use) {
            slot = i;
            break;
        }
    }
    
    if (slot == -1) {
        printf("ERROR: Directory full. Cannot create more files.\n");
        return -1;
    }
    
    /* Initialize the new directory entry */
    DirectoryEntry *entry = &dir->entries[slot];
    strncpy(entry->name, filename, MAX_FILENAME_LENGTH - 1);
    entry->name[MAX_FILENAME_LENGTH - 1] = '\0';
    entry->size = initial_size;
    entry->first_block = slot * 100;  /* Simplified block allocation */
    entry->block_count = (initial_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    entry->created = time(NULL);
    entry->modified = entry->created;
    entry->permissions = 0x07;  /* rwx for simplicity */
    entry->in_use = true;
    
    dir->file_count++;
    
    printf("Created file '%s' (size: %u bytes, blocks: %u)\n",
           filename, initial_size, entry->block_count);
    
    return slot;
}
 
/*
 * Delete a file from the directory.
 * Marks the entry as unused; does not physically erase data.
 */
bool delete_file(SingleLevelDirectory *dir, const char *filename) {
    int index = find_file(dir, filename);
    
    if (index == -1) {
        printf("ERROR: File '%s' not found.\n", filename);
        return false;
    }
    
    dir->entries[index].in_use = false;
    dir->file_count--;
    
    printf("Deleted file '%s'.\n", filename);
    return true;
}
 
/*
 * List all files in the directory.
 * With a single-level directory, this means ALL files in the system.
 * 
 * Notice: No way to filter or organize this list.
 * Every file ever created is visible to every user.
 */
void list_files(SingleLevelDirectory *dir) {
    printf("\n========== DIRECTORY LISTING ==========\n");
    printf("%-20s %10s %20s\n", "FILENAME", "SIZE", "MODIFIED");
    printf("----------------------------------------\n");
    
    int shown = 0;
    for (int i = 0; i < MAX_FILES; i++) {
        if (dir->entries[i].in_use) {
            DirectoryEntry *e = &dir->entries[i];
            char time_str[20];
            strftime(time_str, sizeof(time_str), "%Y-%m-%d %H:%M", 
                     localtime(&e->modified));
            
            printf("%-20s %10u %20s\n", e->name, e->size, time_str);
            shown++;
        }
    }
    
    printf("----------------------------------------\n");
    printf("Total: %d files\n\n", shown);
}
 
/*
 * Demonstrate the naming collision problem.
 */
void demonstrate_naming_problem(SingleLevelDirectory *dir) {
    printf("\n=== Demonstrating Naming Collision Problem ===\n\n");
    
    /* User A creates their budget file */
    printf("[User A]: Creating personal budget...\n");
    create_file(dir, "budget.txt", 1024);
    
    /* User B tries to create their own budget file */
    printf("\n[User B]: Attempting to create work budget...\n");
    create_file(dir, "budget.txt", 2048);  /* Will fail! */
    
    printf("\n[Problem]: User B cannot use the natural name 'budget.txt'!\n");
    printf("           They must use an artificial name like 'budget_userb.txt'.\n");
    
    /* The workaround */
    printf("\n[Workaround]: User B creates 'budget_work.txt' instead...\n");
    create_file(dir, "budget_work.txt", 2048);
    
    list_files(dir);
}
 
/*
 * Demonstrate the scalability problem.
 */
void demonstrate_scalability_problem(SingleLevelDirectory *dir) {
    printf("\n=== Demonstrating Scalability Problem ===\n\n");
    
    char filename[MAX_FILENAME_LENGTH];
    
    /* Create many files to simulate a growing system */
    printf("Creating 50 test files...\n");
    for (int i = 0; i < 50; i++) {
        snprintf(filename, sizeof(filename), "file_%03d.dat", i);
        create_file(dir, filename, 512 + i * 100);
    }
    
    printf("\nDirectory now has %d files.\n", dir->file_count);
    printf("Finding file 'file_049.dat'...\n");
    
    /* Measure search time conceptually */
    int iterations = 0;
    for (int i = 0; i < MAX_FILES; i++) {
        iterations++;
        if (dir->entries[i].in_use && 
            strcmp(dir->entries[i].name, "file_049.dat") == 0) {
            printf("Found after checking %d entries (O(n) search).\n", iterations);
            break;
        }
    }
    
    printf("\n[Problem]: As files increase, search time grows linearly.\n");
    printf("           With thousands of files, this becomes unacceptable.\n");
}
 
int main() {
    SingleLevelDirectory directory;
    
    printf("=== Single-Level Directory Demonstration ===\n\n");
    
    init_directory(&directory);
    
    /* Create some initial files */
    create_file(&directory, "system.log", 4096);
    create_file(&directory, "readme.txt", 256);
    create_file(&directory, "data.csv", 10240);
    
    list_files(&directory);
    
    /* Demonstrate the fundamental problems */
    demonstrate_naming_problem(&directory);
    demonstrate_scalability_problem(&directory);
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

/*
 * Comparison of Directory Search Strategies
 * Demonstrates why optimization alone can't save single-level directories.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
#define NUM_FILES 10000
#define NAME_LENGTH 32
 
/*
 * Directory entry (simplified)
 */
typedef struct {
    char name[NAME_LENGTH];
    int data;
} DirEntry;
 
DirEntry directory[NUM_FILES];
 
/*
 * Initialize directory with random file names
 */
void init_directory() {
    for (int i = 0; i < NUM_FILES; i++) {
        snprintf(directory[i].name, NAME_LENGTH, "file_%08d.txt", rand());
        directory[i].data = i;
    }
}
 
/*
 * Linear Search: O(n)
 * The baseline approach in simple single-level directories.
 */
int linear_search(const char *target) {
    for (int i = 0; i < NUM_FILES; i++) {
        if (strcmp(directory[i].name, target) == 0) {
            return i;
        }
    }
    return -1;
}
 
/*
 * Binary Search: O(log n)
 * Requires sorted directory; demonstrates improvement potential.
 */
int compare_entries(const void *a, const void *b) {
    return strcmp(((DirEntry*)a)->name, ((DirEntry*)b)->name);
}
 
int binary_search(const char *target) {
    DirEntry key;
    strncpy(key.name, target, NAME_LENGTH);
    
    DirEntry *result = bsearch(&key, directory, NUM_FILES, 
                                sizeof(DirEntry), compare_entries);
    
    return result ? (result - directory) : -1;
}
 
/*
 * Benchmark: Compare search strategies
 */
void benchmark() {
    const int SEARCHES = 1000;
    clock_t start, end;
    
    /* Pick random targets from the directory */
    int targets[SEARCHES];
    for (int i = 0; i < SEARCHES; i++) {
        targets[i] = rand() % NUM_FILES;
    }
    
    /* Linear Search Benchmark */
    start = clock();
    for (int i = 0; i < SEARCHES; i++) {
        linear_search(directory[targets[i]].name);
    }
    end = clock();
    double linear_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    
    /* Sort for binary search */
    qsort(directory, NUM_FILES, sizeof(DirEntry), compare_entries);
    
    /* Binary Search Benchmark */
    start = clock();
    for (int i = 0; i < SEARCHES; i++) {
        /* Note: we need to search for names that exist in sorted order */
        binary_search(directory[targets[i] % NUM_FILES].name);
    }
    end = clock();
    double binary_time = ((double)(end - start)) / CLOCKS_PER_SEC;
    
    printf("\n=== Search Performance Comparison ===\n");
    printf("Directory size: %d files\n", NUM_FILES);
    printf("Searches performed: %d\n\n", SEARCHES);
    
    printf("Linear Search:  %.4f seconds\n", linear_time);
    printf("Binary Search:  %.4f seconds\n", binary_time);
    printf("Speedup:        %.1fx faster\n\n", linear_time / binary_time);
    
    printf("Even with binary search (%.1fx faster),\n", 
           linear_time / binary_time);
    printf("the user still sees ALL %d files in one flat list!\n", 
           NUM_FILES);
    printf("\nThe ORGANIZATIONAL problem remains unsolved.\n");
}
 
int main() {
    srand(time(NULL));
    
    printf("Initializing directory with %d files...\n", NUM_FILES);
    init_directory();
    
    benchmark();
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

/*
 * Embedded System Flat Directory Example
 * Appropriate use case: Simple IoT sensor with minimal storage.
 * 
 * This design makes sense because:
 * 1. Only ~10 files maximum
 * 2. No user interaction with file system
 * 3. Files are accessed by known, fixed names
 * 4. Minimal memory footprint
 */
 
#include <stdint.h>
#include <stdbool.h>
 
#define MAX_FILES 16
#define MAX_NAME_LEN 16
#define FLASH_BASE 0x08000000  /* Typical embedded flash address */
 
/*
 * Compact directory entry for embedded use
 * Only 24 bytes per entry - minimal footprint
 */
typedef struct __attribute__((packed)) {
    char name[MAX_NAME_LEN];  /* 16 bytes */
    uint32_t offset;           /* 4 bytes: offset in flash */
    uint16_t size;             /* 2 bytes: file size (max 64KB) */
    uint16_t flags;            /* 2 bytes: read-only, valid, etc. */
} EmbeddedDirEntry;
 
/*
 * Entire directory fits in 384 bytes + header
 */
typedef struct __attribute__((packed)) {
    uint32_t magic;            /* 0xDIRECTRY */
    uint8_t version;
    uint8_t entry_count;
    uint16_t reserved;
    EmbeddedDirEntry entries[MAX_FILES];
} EmbeddedDirectory;
 
/* Directory instance - typically in RAM, backed by flash */
static EmbeddedDirectory g_directory;
 
/*
 * Initialize directory from flash storage
 */
bool dir_init(void) {
    /* In real embedded code, this reads from flash */
    const EmbeddedDirectory *flash_dir = (EmbeddedDirectory*)FLASH_BASE;
    
    if (flash_dir->magic != 0xDIRECTRY) {
        /* Initialize empty directory */
        g_directory.magic = 0xDIRECTRY;
        g_directory.version = 1;
        g_directory.entry_count = 0;
        return true;
    }
    
    /* Copy from flash to RAM for faster access */
    g_directory = *flash_dir;
    return true;
}
 
/*
 * Find file by name - simple linear search
 * With < 16 entries, optimization isn't needed
 */
int dir_find(const char *name) {
    for (int i = 0; i < g_directory.entry_count; i++) {
        bool match = true;
        for (int j = 0; j < MAX_NAME_LEN; j++) {
            if (g_directory.entries[i].name[j] != name[j]) {
                match = false;
                break;
            }
            if (name[j] == '\0') break;
        }
        if (match) return i;
    }
    return -1;
}
 
/*
 * Typical embedded file set - all well-known names
 */
void create_system_files(void) {
    /* Device configuration */
    dir_create("config.bin", 256);
    
    /* Calibration data */
    dir_create("calib.dat", 128);
    
    /* Event log */
    dir_create("events.log", 4096);
    
    /* Firmware update staging */
    dir_create("update.bin", 32768);
    
    /* These 4 files serve all device needs */
    /* No user ever browses this directory */
    /* No naming conflicts possible - hardcoded names */
}
 
/*
 * For embedded systems with known file sets,
 * a flat directory is OPTIMAL:
 * - Minimal memory (< 400 bytes)
 * - Simple implementation (< 100 lines)
 * - No dynamic allocation
 * - Predictable performance
 */