Simple File System Simulator ( Virtual File System on linux 2.6 )

Makefile

simple_file_system : main.o vfs.o shell.o disk.o
 gcc -o simple_file_system main.o vfs.o shell.o disk.o

main.o : main.c
 gcc -c main.c
vfs.o : vfs.h vfs.c
 gcc -c vfs.c
shell.o : shell.h shell.c
 gcc -c shell.c
disk.o : disk.h disk.c
 gcc -c disk.c

main.c

/* main.c */
#include "shell.h"

int main(void) {

 printf("\n");
 printf("\t-+- SFS with mini shell -+-\n");
 printf("\n");
 printf("\t    Command List:$ help\n");
 printf("\n");

 shell_main();

 return 0;
}

shell.h

/* shell.h */
#ifndef _SHELL_H_
#define _SHELL_H_

#include "vfs.h"

void shell_main();

#endif

shell.c

/* shell.c */

#include "shell.h"

char buf[4][MAX_CHAR];
char buf_line[MAX_CHAR * 4];
char user_name[MAX_CHAR] = "user";
char str[2][3] = {".", ".."};
int buf_size[4];

void shell_print_mode(int mode) {
 if(mode / 4) {
  putc('r', stdout);
 } else {
  putc('-', stdout);
 }
 if((mode % 4) / 2) {
  putc('w', stdout);
 } else {
  putc('-', stdout);
 }
 if((mode % 4) % 2) {
  putc('x', stdout);
 } else {
  putc('-', stdout);
 }

 return;
}

void shell_print_name(char name[]) {
 int i;
 for(i = 0; i < MAX_CHAR; ++i) {
  if(name[i] == '|') {
   break;
  }
  putc(name[i], stdout);
 }

 return;
}

void shell_print_path(struct dentry *d) {
 int i;

 if(d == d->parent) {
  putc('/', stdout);
  return;
 }

 shell_print_path(d->parent);
 shell_print_name(d->name);
 putc('/', stdout);

 return;
}

void shell_print_time(struct tm c) {
 printf("%04d-%02d-%02d %02d:%02d:%02d  ", 
  c.tm_year + 1900, c.tm_mon, c.tm_mday,
  c.tm_hour, c.tm_min, c.tm_sec);

 return;
}

void shell_command_ls(FILE *disk, struct dentry *d) {
 int i,x;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_read(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
  if(!vfs_mode_excute(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 }

 vfs_dentry_open(disk, d);
// printf("ls\n");
 x = 0;
 for(i = 0; i < MAX_D_INODE; ++i) {
  if(d->d_inode[i] != NULL) {
   shell_print_name(d->d_inode[i]->name);
   putc(' ', stdout);
   x = 1;
  }
 }
 if(x != 0) {
  putc('\n', stdout);
 }

// printf("inode:%d, dentry:%d\n", d->num_inode, d->num_dentry);

 return;
}

void shell_command_ll(FILE *disk, struct dentry *d) {
 int i;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_read(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
  if(!vfs_mode_excute(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 }

 vfs_dentry_open(disk, d);
 //printf("%s\n", d->name);
 printf("AUTH SIZE     CREATED              ACCESSED             NAME                  \n");
 
 for(i = -2; i < MAX_D_INODE; ++i) {
  if(i < 0) {
   shell_print_mode(d->d_dentry[i + 2]->d_mode);
   printf("           "); 
   shell_print_time(d->d_dentry[i + 2]->d_ctime);
   shell_print_time(d->d_dentry[i + 2]->d_atime);
   printf("%s/\n", str[i + 2]);
  } else {
   if(d->d_inode[i] != NULL) {
    shell_print_mode(d->d_inode[i]->i_mode);
    printf("  %7d  ", d->d_inode[i]->size); 
    shell_print_time(d->d_inode[i]->i_ctime);
    shell_print_time(d->d_inode[i]->i_atime);
    shell_print_name(d->d_inode[i]->name);
    if(d->d_inode[i]->i_type == INODE_DIRECTORY) {
     putc('/', stdout);
    }
    putc('\n', stdout);
   }
  }
 }

 return;
}

void shell_command_rmdir(FILE *disk, struct dentry *d, char name[]) {
 int i;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_excute(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 }

 i = vfs_inode_remove(disk, d, name, INODE_DIRECTORY);
 if(i < 0) {
  if(i == -1) {
   printf("rmdir: \'");
   shell_print_name(name);
   printf("\' cannot remove directory: 파일이 없습니다\n");
  }
  if(i == -2) {
   printf("rmdir: \'");
   shell_print_name(name);
   printf("\' cannot remove directory: 디렉토리가 아닙니다\n");
  }
  if(i == -3) {
   printf("rmdir: \'");
   shell_print_name(name);
   printf("\' cannot remove directory: 디렉토리가 비어있지 않습니다\n");
  }
  if(i == -8) {
   printf("Permission dennied\n");
  }
 }

 return;
}

void shell_command_rmfile(FILE *disk, struct dentry *d, char name[]) {
 int i;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_excute(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 }

 i = vfs_inode_remove(disk, d, name, INODE_FILE);
 if(i < 0) {
  if(i == -1) {
   printf("rmfile: \'");
   shell_print_name(name);
   printf("\' cannot remove file: 파일이 없습니다\n");
  }
  if(i == -4) {
   printf("rmfile: \'");
   shell_print_name(name);
   printf("\' cannot remove file: 파일이 아닙니다\n");
  }
  if(i == -8) {
   printf("Permission dennied\n");
  }
 }

 return;
}

void shell_command_mkdir(FILE *disk, struct dentry *d, char name[]) {
 int i;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_excute(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 }

 if(vfs_compare_name(".|", name) == 0 || vfs_compare_name("..|", name) == 0) {
  i = -2;
 } else {
  vfs_dentry_open(disk, d);
  i = vfs_inode_make(disk, d, name, 0, INODE_DIRECTORY);
 }
 if(i < 0) {
  if(i == -1) {
   printf("mkdir: \'");
   shell_print_name(name);
   printf("\' cannot make directory: 파일이 있습니다\n");
  }
  if(i == -2) {
   printf("mkdir: \'");
   shell_print_name(name);
   printf("\' cannot make directory: 사용할 수 없는 이름입니다\n");
  }
  if(i == -8) {
   printf("Permission dennied\n");
  }
  return;
 }

 return;
}

void shell_command_mkfile(FILE *disk, struct dentry *d, char name[], int size) {
 int i;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_excute(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 }

 if(vfs_compare_name(".|", name) == 0 || vfs_compare_name("..|", name) == 0) {
  i = -2;
 } else {
  vfs_dentry_open(disk, d);
  i = vfs_inode_make(disk, d, name, size, INODE_FILE);
 }
 if(i < 0) {
  if(i == -1) {
   printf("mkfile: \'");
   shell_print_name(name);
   printf("\' cannot make file: 파일이 있습니다\n");
  }
  if(i == -2) {
   printf("mkfile: \'");
   shell_print_name(name);
   printf("\' cannot make file: 사용할 수 없는 이름입니다\n");
  }
  if(i == -8) {
   printf("Permission dennied\n");
  }
 }

 return;
}

void* shell_command_cd(FILE *disk, struct dentry *d, char name[]) {
 struct dentry *child;
 int i;

 // init
 child = NULL;

 if(vfs_compare_name(".|", name) == 0) {
  child = d;
 } else if(vfs_compare_name("..|", name) == 0) {
  child = d->parent;
 } else {
  vfs_dentry_open(disk, d);
  for(i = 0; i < MAX_D_CHILD; ++i) {
   if(d->d_dentry[i] != NULL) {
    if(vfs_compare_name(d->d_dentry[i]->name, name) == 0) {
     break;
    }
   }
  }
  if(i == MAX_D_CHILD) { 
   printf("cd: ");
   shell_print_name(name);
   printf(": 디렉토리가 없습니다.\n");
   return child;
  }
  child = d->d_dentry[i];
 }

 // directory mode check
 if(child->sb->s_mode == USER_MODE) {
  if(!vfs_mode_excute(child->d_mode)) {
   printf("Permission dennied\n");
  }
 }
 
// vfs_dentry_open(disk, child);

 return child;
}

void shell_command_mv(FILE *disk, struct dentry *d, char name[], char new_name[]) {
 int i, j;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_write(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 // if(!vfs_mode_excute(d->d_mode)) {
 //  printf("Permission dennied\n");
 //  return;
 // }
 }

 // if name == new_name
 if(vfs_compare_name(name, new_name) == 0) {
  return;
 }

 // search by name
 for(i = 0; i < MAX_D_INODE; ++i) {
  if(d->d_inode[i] != NULL) {
   if(vfs_compare_name(d->d_inode[i]->name, new_name) == 0) { 
    break;
   }
  }
 }
 if(i != MAX_D_INODE) {
  printf("mv: ");
  shell_print_name(name);
  printf(": 이미 존재하는 파일명입니다\n");
  return;
 }

 // search by new_name
 for(i = 0; i < MAX_D_INODE; ++i) {
  if(d->d_inode[i] != NULL) {
   if(vfs_compare_name(d->d_inode[i]->name, name) == 0) {
    vfs_inode_rename(disk, d->d_inode[i], new_name);
    break;
   }
  }
 }
 if(i == MAX_D_INODE) {
  printf("mv: ");
  shell_print_name(name);
  printf(": 파일이 없습니다\n");
  return;
 }

 // if it is directory
 if(d->d_inode[i]->i_type == INODE_DIRECTORY) {
  for(j = 0; j < MAX_D_CHILD; ++i) {
   if(d->d_dentry[j] != NULL) {
    if(vfs_compare_name(d->d_dentry[j]->name, name) == 0) {
     vfs_dentry_rename(d->d_dentry[j], d->d_inode[i]);
     break;
    }
   }
  }
 }

 return;
}

void shell_command_chmod(FILE *disk, struct dentry *d, char mode_str[], char name[]) {
 int i, j, mode;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_write(d->d_mode)) {
   printf("Permission dennied\n");
   return;
  }
 // if(!vfs_mode_excute(d->d_mode)) {
 //  printf("Permission dennied\n");
 //  return;
 // }
 }

 // decoding option
 mode = 0;
 if(mode_str[0] == 'r') {
  mode += 4;
 } else if(mode_str[0] != '-') {
  mode = -8;
 }
 if(mode_str[1] == 'w') {
  mode += 2;
 } else if(mode_str[1] != '-') {
  mode = -8;
 }
 if(mode_str[2] == 'x') {
  mode += 1;
 } else if(mode_str[2] != '-') {
  mode = -8;
 }
 if(mode < 0) {
  printf("chmod: 옵션이 잘못되었습니다\n");
  return;
 }

 
 // search by name
 for(i = 0; i < MAX_D_INODE; ++i) {
  if(d->d_inode[i] != NULL) {
   if(vfs_compare_name(d->d_inode[i]->name, name) == 0) { 
    vfs_inode_chmod(disk, d->d_inode[i], mode);
    break;
   }
  }
 }
 if(i == MAX_D_INODE) {
  printf("chmod: ");
  shell_print_name(name);
  printf(": 파일이 없습니다\n");
  return;
 }

// printf("chmod\n");
 // if it is directory
 if(d->d_inode[i]->i_type == INODE_DIRECTORY) {
  for(j = 0; j < MAX_D_CHILD; ++j) {
   if(d->d_dentry[j] != NULL) {
    if(vfs_compare_name(d->d_dentry[j]->name, name) == 0) {
//     printf("chmod\n");
     vfs_dentry_chmod(d->d_dentry[j], d->d_inode[i]);
//     printf("chmod\n");
     break;
    }
   }
  }
 }

// printf("chmod\n");
 return;
}

void shell_command_df(FILE *disk, struct dentry *d) {
 printf("disk.img: %ld / %ld (%ld%%)\n", d->sb->s_blocksize, d->sb->s_maxbytes, (unsigned long)((d->sb->s_blocksize * 100) / d->sb->s_maxbytes));

 return;
}

char *indirect_type[] = {"", "single", "double", "triple"}; 
void shell_print_indirect_block(FILE *disk, int block_addr, int depth) {
 int k, addr;

 if(block_addr == 0) {
  return;
 }
 if(depth == 0) {
  if(block_addr != 0) {
   printf(" %08x", block_addr);
  }
  return;
 }

 printf("\n [%s:%08x]", indirect_type[depth], block_addr);
 for(k = 0; k < DISK_BLOCK_SIZE / 8; ++k) {
  fseek(disk, block_addr + k*8, SEEK_SET);
  addr = disk_read_int(disk);
  if(addr != 0) {
  shell_print_indirect_block(disk, addr, depth - 1);
  }
 }

 return;
}

void shell_command_blocks(FILE *disk, struct dentry *d, char name[]) {
 struct inode *in;
 int i; 

 // search by name
 for(i = 0; i < MAX_D_INODE; ++i) {
  if(d->d_inode[i] != NULL) {
   if(vfs_compare_name(d->d_inode[i]->name, name) == 0) { 
    break;
   }
  }
 }
 if(i == MAX_D_INODE) {
  printf("blocks: ");
  shell_print_name(name);
  printf(": 파일이 없습니다\n");
  return;
 }

 // mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_read(d->d_inode[i]->i_mode)) {
   printf("Permission dennied\n");
   return;
  }
 }
 // print
 in = d->d_inode[i];
 if(in->direct_block[0] == NULL) {
 printf("0 block");
 } else {
 printf("direct blocks:\n");
 for(i = 0; i < 12; ++i) {
  if(in->direct_block[i] != NULL) {
   printf(" %08x", (int)in->direct_block[i]);
  }
 }
 if(in->single_block != NULL) {
 printf("\nsingle indirect blocks:"); 
 shell_print_indirect_block(disk, (int)in->single_block, 1);
 }
 if(in->double_block != NULL) {
 printf("\ndouble indirect blocks:");
 shell_print_indirect_block(disk, (int)in->double_block, 2);
 }
 if(in->triple_block != NULL) {
 printf("\ntriple indirect blocks:");
 shell_print_indirect_block(disk, (int)in->triple_block, 3);
 }
 }
 printf("\n");

 return;
}

// shell command
const int num_command = 14;
const int num_command_without_permission = 5;
char *command[] = 
{"help", "sudo", "su", "cd", "df",
 "ls", "ll", "rmdir", "rmfile", "mkdir",
 "mkfile", "mv", "chmod", "blocks"};
char *command_help[] =
{"", "\t-Command", "", "\t-Directory", "",
 "", "", "\t-Directory", "\t-File", "\t-Directory",
 "\t-File\t-Size", "\t-File1\t-File2", "\t-(rwx)\t-File", ""};
void shell_command_help() {
 int i;

 for(i = 0; i < num_command; ++i) {
  printf("%s\t%s\n", command[i], command_help[i]);
 }
 return;
}
void* shell_command(FILE *disk, struct dentry *current, char buf[][MAX_CHAR], int buf_size[]) {
 struct dentry *child;
 int i;

 // init
 child = NULL;

 // mod buf
 if(buf_size[0] > 64) {
  buf_size[0] = 63;
 }
 buf[0][buf_size[0]] = '\0';
 if(buf_size[1] > 64) {
  buf_size[1] = 63;
 }
 buf[1][buf_size[1]] = '|';
 if(buf_size[2] > 64) {
  buf_size[2] = 63;
 }
 buf[2][buf_size[2]] = '|';

 // check command list
 for(i = 0; i < num_command; ++i) {
  if(strcmp(buf[0], command[i]) == 0) {
   break;
  }
 }
 if(i == num_command) {
  i = -1;
 }

 if(i >= num_command_without_permission) {
 // directory mode check
  if(current->sb->s_mode == USER_MODE) {
   if(!vfs_mode_excute(current->d_mode)) {
    printf("Permission dennied\n");
    return child;
   }
  }
 }

 // excute command
 switch(i) {
 case 0: shell_command_help(); break;
 case 1: current->sb->s_mode = ROOT_MODE;
  shell_command(disk, current, buf+1, buf_size+1);
  current->sb->s_mode = USER_MODE; break;
 case 2: current->sb->s_mode = ROOT_MODE; break;
 case 3: child = shell_command_cd(disk, current, buf[1]); break;
 case 4: shell_command_df(disk, current); break;
 case 5: shell_command_ls(disk, current); break;
 case 6: shell_command_ll(disk, current); break;
 case 7: shell_command_rmdir(disk, current, buf[1]); break;
 case 8: shell_command_rmfile(disk, current, buf[1]); break;
 case 9: shell_command_mkdir(disk, current, buf[1]); break;
 case 10: if(buf_size[2] > 8) {
   buf_size[2] = 8;
  }
  buf[2][buf_size[2]] = '\0';
 // printf("%d\n", atoi(buf[2]));
  shell_command_mkfile(disk, current, buf[1], atoi(buf[2])); break;
 case 11: shell_command_mv(disk, current, buf[1], buf[2]); break;
 case 12: shell_command_chmod(disk, current, buf[1], buf[2]); break;
 case 13: shell_command_blocks(disk, current, buf[1]); break;
 default: printf("%s: command not found\n", buf[0]); break;
 };

 //printf("shell_command\n");
 return child;
}

void shell_main() {
 FILE *disk;
 struct super_block *sb;
 struct dentry *root;
 struct dentry *current;
 struct dentry *child;
 int num_buf, i, j, k;

 // mount disk
 disk = disk_init("disk.img");

 sb = vfs_sb_init(disk);
 root = sb->s_root;
 current = root;

 while(1) {

  if(sb->s_mode == USER_MODE) {
   printf("%s:", user_name);
  } else {
   printf("%s:", "root");
  }
  shell_print_path(current);
  putc('$', stdout);
  putc(' ', stdout);

  //scanf("%s\n", buf_line);
  fgets(buf_line, MAX_CHAR * 4, stdin);

  i = 0;
  for(j = 0; j < MAX_CHAR * 4; ++j) {
   if(buf_line[j] == ' ') {
    continue;
   }
   for(k = 0; k < MAX_CHAR; ++k) {
    if(buf_line[j] == '\n' || buf_line[j] == '\0') {
     ++i;
     break;
    } else if(buf_line[j] == ' ') {
     ++i;
     break;
    }
    buf[i][k] = buf_line[j];
    ++j;
   }
  // printf("%d %d\n", k, i);
   if(k > 0) {
    buf_size[i - 1] = k;
   }
   if(i >= 4) {
    break;
   }
   if(buf_line[j] == '\n') {
    for(k = i; k < 4; ++k) {
     buf_size[k] = 0;
    }
    break;
   }
  }
  //num_buf = i + 1;
  //printf("num_buf: %d\n", num_buf);

  if(strncmp(buf[0], "exit", 4) == 0) {
   if(sb->s_mode == USER_MODE) {
    break;
   } else {
    sb->s_mode = USER_MODE;
   }
  } else if(buf[0][0] != '\n' && buf[0][0] != '\0') {
   //printf("sss\n");
   child = shell_command(disk, current, buf, buf_size);
   if(child != NULL) {
    current = child;
   }
  } else {
  }
  memset(buf_line, '\0', MAX_CHAR * 4);
  memset(buf[0], '\0', MAX_CHAR);
  memset(buf[1], '\0', MAX_CHAR);
  memset(buf[2], '\0', MAX_CHAR);
 }
 //fseek(disk, 0, SEEK_END);
 // unmount disk
 fclose(disk);
}

vfs.h

/* vfs.h */
#ifndef _FS_H_
#define _FS_H_

#include "disk.h"

#define MAX_D_CHILD (DISK_BLOCK_SIZE / BYTE) * DIRECTORY_ENTRY_BLOCK_NUM
#define MAX_D_INODE (DISK_BLOCK_SIZE / BYTE) * DIRECTORY_ENTRY_BLOCK_NUM
#define DENTRY_CLOSE 0
#define DENTRY_OPEN 1

#define USER_MODE 0
#define ROOT_MODE 1

// VFS Structure
struct dentry {
 int  d_type;
 int   d_mode;
 char   name[MAX_CHAR];

 struct super_block *sb;
 struct dentry  *parent;
 int   num_dentry;
 struct dentry *d_dentry[MAX_D_CHILD];
 int  num_inode;
 struct inode *d_inode[MAX_D_INODE];
 struct tm d_ctime;
 struct tm d_atime;
};

struct super_block {
 int  s_mode;

 struct dentry *s_root;
 struct inode *s_root_inode;
 unsigned long s_blocksize;
 unsigned long s_maxbytes;
};

struct inode {
 int  i_type;
 int  i_mode;

 int  id;
 char name[MAX_CHAR];

 struct tm i_ctime;
 struct tm i_atime;
 int  size;

 void*  direct_block[12];
 void*  single_block;
 void*  double_block;
 void*  triple_block;
};

// VFS PROC
struct tm vfs_set_time();
int vfs_mode_read(int mode);
int vfs_mode_write(int mode);
int vfs_mode_excute(int mode);
int vfs_compare_name(char name1[], char name2[]);
void vfs_inode_chmod(FILE *disk, struct inode *i, int mode);
void vfs_inode_rename(FILE *disk, struct inode *i, char name[]);
void* vfs_inode_read(FILE *disk, int addr);
int vfs_inode_remove(FILE *disk, struct dentry *d, char name[], int flag);
int vfs_inode_make(FILE *disk, struct dentry *d, char name[], int size, int flag);
void vfs_dentry_chmod(struct dentry *d, struct inode *i);
void vfs_dentry_rename(struct dentry *d, struct inode *i);
void* vfs_dentry_make(struct dentry *p, struct inode *i);
void vfs_dentry_open(FILE *disk, struct dentry *d);
void vfs_sb_refresh(FILE *disk, struct super_block *sb);
void* vfs_sb_init(FILE *disk);

#endif

vfs.c

/* vfs.c */
#include "vfs.h"

// VFS PROC
struct tm vfs_set_time() {
 time_t timer;
 struct tm *c;

 timer = time(NULL);
 c = localtime(&timer);
 //free(c);

 return *c;
}

int vfs_mode_read(int mode) {
 return (mode / 4);
}

int vfs_mode_write(int mode) {
 return ((mode % 4) / 2);
}

int vfs_mode_excute(int mode) {
 return (((mode % 4) % 2));
}

int vfs_compare_name(char name1[], char name2[]) {
 int i;
 
 for(i = 0; i < MAX_CHAR; ++i) {
  if(name1[i] == '|' && name2[i] == '|') {
   break;
  }
  if(name1[i] != name2[i]) {
   return -1;
  }

 }

 return 0;
}

void vfs_inode_chmod(FILE *disk, struct inode *i, int mode) {
 char buf[MAX_CHAR];

 i->i_mode = mode;
 i->i_atime = vfs_set_time();

// printf("inode_chmod\n");

 fseek(disk, i->id, SEEK_SET);
 disk_read_int(disk);
 disk = disk_write_int(disk,i->i_mode);
// printf("inode_chmod\n");
 disk_read_name(disk, buf);
// printf("inode_chmod\n");
 disk_read_time(disk);
 disk = disk_write_time(disk, i->i_atime);
// printf("inode_chmod\n");

 return;
}

void vfs_inode_rename(FILE *disk, struct inode *i, char name[]) {

 strncpy(i->name, name, MAX_CHAR);
 i->i_atime = vfs_set_time();

 fseek(disk, i->id, SEEK_SET);
 disk_read_int(disk);
 disk_read_int(disk);
 disk = disk_write_name(disk, i->name);
 disk_read_time(disk);
 disk = disk_write_time(disk, i->i_atime);

 return;
}

void* vfs_inode_read(FILE *disk, int addr) {
 struct inode *i;
 int disk_addr, k;

 if(addr == 0) {
  return NULL;
 }

 i = (struct inode*)malloc(sizeof(struct inode));

// disk_addr = addr / BYTE;
 disk_addr = addr;
 fseek(disk, disk_addr, SEEK_SET);
 
 i->i_type = disk_read_int(disk);
 i->i_mode = disk_read_int(disk);
// i->id = (disk_addr - INODE_TABLE_ADDR) / INODE_SIZE;
 i->id = disk_addr;
 disk_read_name(disk, i->name);
 i->i_ctime = disk_read_time(disk);
 i->i_atime = disk_read_time(disk);
 i->size = disk_read_int(disk);
 for(k = 0; k < 12; ++k) {
  i->direct_block[k] = (void*)disk_read_int(disk);
 }
 i->single_block = (void*)disk_read_int(disk);
 i->double_block = (void*)disk_read_int(disk);
 i->triple_block = (void*)disk_read_int(disk);

 return i;
}

int vfs_inode_remove(FILE *disk, struct dentry *d, char name[], int flag) {
 struct dentry *p, *i_dentry;
 struct inode *i, *d_inode;
 int i_addr, block_addr, remain_size, j, k, l;


 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_write(d->d_mode)) {
   //printf("inode_remove\n");
   return -8;
  }
 }
 
 // search inode with same name
 i = NULL;
 for(k = 0; k < MAX_D_INODE; ++k) {
  if(d->d_inode[k] != NULL) {
   //if(strncmp(d->d_inode[k]->name, name, MAX_CHAR) == 0) {
   if(vfs_compare_name(d->d_inode[k]->name, name) == 0) {
    i = d->d_inode[k];
    break;
   }
   //printf("%s\n", d->d_inode[k]->name);
  }
 }
 if(i == NULL) {
  return -1;
 }

 // inode mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_write(i->i_mode)) {
   return -8;
  }
 }

 // search dentry with same name
 i_dentry = NULL;
 for(k = 0; k < MAX_D_CHILD; ++k) {
  if(d->d_dentry[k] != NULL) {
   //if(strncmp(d->d_dentry[k]->name, name, MAX_CHAR) == 0) {
   if(vfs_compare_name(d->d_dentry[k]->name, name) == 0) {
    i_dentry = d->d_dentry[k];
    break;
   }
  }
 }
 if(flag == INODE_DIRECTORY) {
  if(i_dentry == NULL) {
   return -2;
  }
 
  vfs_dentry_open(disk, i_dentry);
  if(i_dentry->num_inode != 0) {
   return -3;
  }
 } else {
  if(i_dentry != NULL) {
   return -4;
  }
 }

 // search directory inode
 p = d->parent;
// if(p != NULL) { // not root directory
 if(p != d) { // not root directory
  for(k = 0; k < MAX_D_INODE; ++k) {
   if(vfs_compare_name(d->name, p->d_inode[k]->name) == 0) {
    d_inode = p->d_inode[k];
    break;
   } 
  }
 } else { // root directory
  d_inode = d->sb->s_root_inode;
 }

 // remove inode block addr 
 for(k = 0; k < DIRECTORY_ENTRY_BLOCK_NUM; ++k) {
//  fseek(disk, (int)d_inode->direct_block[k] / BYTE, SEEK_SET);
  fseek(disk, (int)d_inode->direct_block[k], SEEK_SET);
  for(l = 0; l < DISK_BLOCK_SIZE / BYTE; ++l) {
   i_addr = disk_read_int(disk);
   if(i_addr == i->id) {
    fseek(disk, -BYTE, SEEK_CUR);
    disk = disk_write_int(disk, 0);
    break;
   }
  }
  if(l != DISK_BLOCK_SIZE / BYTE) {
   break;
  }
 }

 // remove inode pointer
 --d->num_inode;
 for(k = 0; k < MAX_D_INODE; ++k) {
  if(d->d_inode[k] == i) {
   d->d_inode[k] = NULL;
   break;
  }
 }

 // remove dentry pointer
 if(flag == INODE_DIRECTORY) {
  --d->num_dentry;
  for(k = 0; k < MAX_D_CHILD; ++k) {
   if(d->d_dentry[k] == i_dentry) {
    d->d_dentry[k] = NULL;
    break;
   }
  }
 }


 // free inode's data blocks
 d->sb->s_blocksize -= i->size;
 // direct blocks
 for(k = 0; k < 12; ++k) {
  block_addr = (int)i->direct_block[k];
  if(block_addr != 0) {
   //d->sb->s_blocksize -= DISK_BLOCK_SIZE;
   disk_free_block(disk, (int)i->direct_block[k]);
  }
 }
 // indirect blocks
 disk_free_indirect_block(disk, (int)i->single_block, 1);
 disk_free_indirect_block(disk, (int)i->double_block, 2);
 disk_free_indirect_block(disk, (int)i->triple_block, 3);
 //free data block end

 // free inode block
 disk_free_inode(disk, i->id);

 // super_block refresh
 vfs_sb_refresh(disk, p->sb);

 // debug: inode table address 
// printf("%08x \n", i->id);

 // free pointers
 free(i);
 if(flag == INODE_DIRECTORY) {
  free(i_dentry);
 }

 return 0;
}

int vfs_inode_make(FILE *disk, struct dentry *d, char name[], int size, int flag) {
 struct dentry *p;
 struct inode *i, *d_inode;
 int i_addr, remain_size, real_size, block_num, j, k, l;

 // directory mode check
 if(d->sb->s_mode == USER_MODE) {
  if(!vfs_mode_write(d->d_mode)) {
   return -8;
  }
 }

 // check inode with same name
 for(k = 0; k < MAX_D_INODE; ++k) {
  if(d->d_inode[k] != NULL) {
   //if(strncmp(d->d_inode[k]->name, name, MAX_CHAR) == 0) {
   if(vfs_compare_name(d->d_inode[k]->name, name) == 0) {
    return -1;
   }
  }
 }

 // search directory inode
 p = d->parent;
 if(p != d) { // not root directory
  for(k = 0; k < MAX_D_INODE; ++k) {
   if(vfs_compare_name(d->name, p->d_inode[k]->name) == 0) {
    d_inode = p->d_inode[k];
    break;
   } 
  }
 } else { // root directory
  d_inode = d->sb->s_root_inode;
 }

 // make new inode
 i = (struct inode*)malloc(sizeof(struct inode));

 // inode block alloc
 i->id = disk_alloc_inode(disk);
 if(i->id == 0) {
  free(i);
  return -5;
 }

 i->i_type = flag;
 if(flag == INODE_FILE) {
  i->i_mode = 6;
 } else {
  i->i_mode = 7;
 }
 //i->id = (disk_addr - INODE_TABLE_ADDR) / INODE_SIZE;
 strncpy(i->name, name, MAX_CHAR);
// printf("%s\n", i->name);
 i->i_ctime = vfs_set_time();
 i->i_atime = i->i_ctime;
 // disk block alloc
 if(i->i_type == INODE_DIRECTORY) {
  i->size = DISK_BLOCK_SIZE * DIRECTORY_ENTRY_BLOCK_NUM;
  for(k = 0; k < DIRECTORY_ENTRY_BLOCK_NUM; ++k) {
   i->direct_block[k] = (void*)disk_alloc_block(disk);
   d->sb->s_blocksize += DISK_BLOCK_SIZE;
  }
  for(k = DIRECTORY_ENTRY_BLOCK_NUM; k < 12; ++k) {
   i->direct_block[k] = NULL;
  }
  i->single_block = NULL;
  i->double_block = NULL;
  i->triple_block = NULL;
 } else {
  i->size = size;
  remain_size = i->size; 
  k = remain_size % DISK_BLOCK_SIZE;
  remain_size = remain_size / DISK_BLOCK_SIZE;
  if(k != 0) {
   remain_size += 1;
  }
  // direct block
/*  for(k = 0; k < 12; ++k) {
   i->direct_block[k] = (void*)disk_alloc_block(disk);
   //d->sb->s_blocksize += DISK_BLOCK_SIZE;
//   fseek(disk, ((int)i->direct_block[k]) / BYTE , SEEK_SET);
   if(remain_size == 0 || (remain_size > 0 && i->direct_block[k] == NULL)) {
   } else {
   fseek(disk, (int)i->direct_block[k], SEEK_SET);
   for(l = 0; l < 1024; ++l) {
    if(remain_size == 0) {
     break;
    }
    --remain_size;
    disk = disk_write_char(disk, '1');
   }
   }
   if(remain_size == 0) {
    break;
   }
  } */
  for(k = 0; k < 12; ++k) {
   if(remain_size > 0) {
    i->direct_block[k] = (void*)disk_alloc_block(disk);
   } else {
    i->direct_block[k] = NULL;
   }
   if(i->direct_block[k] != NULL) {
    --remain_size;
   }
  }

  // indirect single block
  /*
  i->single_block = NULL;
  i->double_block = NULL;
  i->triple_block = NULL; */

  //printf("%d\n", remain_size);
  i->single_block = (void*)disk_alloc_indirect_block(disk, &remain_size, 1);
  //printf("%d\n", remain_size);
  // indirect double block
  i->double_block = (void*)disk_alloc_indirect_block(disk, &remain_size, 2);
  //printf("%d\n", remain_size);
  // indirect triple block
  i->triple_block = (void*)disk_alloc_indirect_block(disk, &remain_size, 3);
  //printf("%d\n", remain_size);
  if(remain_size > 0) {
   real_size = size / DISK_BLOCK_SIZE;
   if(size % DISK_BLOCK_SIZE != 0) {
    real_size += 1;
   }
   i->size = (real_size - remain_size) * DISK_BLOCK_SIZE;
  }
 }

 // write new inode
// fseek(disk, i->id / BYTE, SEEK_SET);
 fseek(disk, i->id, SEEK_SET);
 disk = disk_write_int(disk, i->i_type);
 disk = disk_write_int(disk, i->i_mode);
 disk = disk_write_name(disk, i->name);
 disk = disk_write_time(disk, i->i_ctime);
 disk = disk_write_time(disk, i->i_atime);
 disk = disk_write_int(disk, i->size);
 for(k = 0; k < 12; ++k) {
  disk = disk_write_int(disk, (int)i->direct_block[k]);
 }
 disk = disk_write_int(disk, (int)i->single_block);
 disk = disk_write_int(disk, (int)i->double_block);
 disk = disk_write_int(disk, (int)i->triple_block);
 
 // write inode block addr to d_inode
 for(k = 0; k < DIRECTORY_ENTRY_BLOCK_NUM; ++k) {
//  fseek(disk, (int)d_inode->direct_block[k] / BYTE, SEEK_SET);
  fseek(disk, (int)d_inode->direct_block[k], SEEK_SET);
  for(l = 0; l < DISK_BLOCK_SIZE / BYTE; ++l) {
   i_addr = disk_read_int(disk);
   if(i_addr == 0) {
    fseek(disk, -BYTE, SEEK_CUR);
    disk = disk_write_int(disk, i->id);
    break;
   }
  }
  if(l != DISK_BLOCK_SIZE / BYTE) {
   break;
  }
 }

 // add inode pointer to d
 for(k = 0; k < MAX_D_INODE; ++k) {
  if(d->d_inode[k] == NULL) {
   break;
  }
 }
 d->d_inode[k] = i;
 ++d->num_inode;

 //debug: p->d_dentry
// for(k = 0; k < MAX_D_CHILD; ++k) {
//  if(p->d_dentry[k] != NULL) {
//   printf("%s\n", p->d_dentry[k]->name);
//  }
// }
// for(k = 0; k < MAX_D_INODE; ++k) {
//  if(p->d_inode[k] != NULL) {
//   printf("%s\n", p->d_inode[k]->name);
//  }
// }

 // if i_type is DIRECTORY
 // make new dentry
 if(i->i_type == INODE_DIRECTORY) {
  for(k = 0; k < MAX_D_CHILD; ++k) {
   if(d->d_dentry[k] == NULL) {
    break;
   }
  }
  d->d_dentry[k] = vfs_dentry_make(d, i);
  ++d->num_dentry;
 }
 //endif
 d->sb->s_blocksize += i->size; 

 // super_block refresh
 vfs_sb_refresh(disk, d->sb);

 // debug: inode table address
// printf("%08x\n", i->id);

 //return i;
 return 0;
}

void vfs_dentry_chmod(struct dentry *d, struct inode *i) {
 d->d_mode = i->i_mode;
 d->d_atime = i->i_atime;

 return;
}

void vfs_dentry_rename(struct dentry *d, struct inode *i) {
 strncpy(d->name, i->name, MAX_CHAR);
 d->d_atime = i->i_atime;

 return;
}

void* vfs_dentry_make(struct dentry *p, struct inode *i) {
 struct dentry *d;
 int k;

 if(i == NULL) {
  return NULL;
 }

 if(i->i_type != INODE_DIRECTORY) {
// printf("ssss\n");
  return NULL;
 }

 d = (struct dentry*)malloc(sizeof(struct dentry));

 d->d_type = DENTRY_CLOSE;
 d->d_mode = i->i_mode;
 strncpy(d->name, i->name, MAX_CHAR);
 if(p != NULL) {
  d->sb = p->sb;
 } else {
  d->sb = 0;
 }
 d->parent = p;
 d->num_dentry = 0;
 for(k = 0; k < MAX_D_CHILD; ++k) {
  d->d_dentry[k] = NULL;
 }
 d->num_inode = 0;
 for(k = 0; k < MAX_D_INODE; ++k) {
  d->d_inode[k] = NULL;
 }
 d->d_ctime = i->i_ctime;
 d->d_atime = i->i_atime;

 return d;
}

void vfs_dentry_open(FILE *disk, struct dentry *d) {
 struct dentry *p;
 struct inode *in;
 int i, j, k, l, block_num;
 int inode_addr;

// printf("d_open %d\n", d->d_mode);

 if(d->d_type == DENTRY_OPEN) {
  return;
 }
// printf("dentry_open\n");

 p = d->parent;
 d->d_type = DENTRY_OPEN;

// for(i = 0; i < p->num_inode; ++i) {
 for(i = 0; i < MAX_D_INODE; ++i) {
  if(p->d_inode != NULL) {
   in = p->d_inode[i];
   if(vfs_compare_name(d->name, in->name) == 0) {
    break;
   }
  }
 }
 
// printf("d_open\n");
// block_num = (in->size / DISK_BLOCK_SIZE) + 1;
 block_num = in->size / DISK_BLOCK_SIZE;
 for(i = 0; i < block_num; ++i) {
  for(j = 0; j < DISK_BLOCK_SIZE / BYTE; ++j) {
//   fseek(disk, ((int)in->direct_block[i] / BYTE) + (j * 8), SEEK_SET);
   fseek(disk, (int)in->direct_block[i] + (j * 8), SEEK_SET);
   inode_addr = disk_read_int(disk);
   if(inode_addr != 0) {
    ++d->num_inode;
   }
   d->d_inode[(DISK_BLOCK_SIZE / BYTE)*i + j] = vfs_inode_read(disk, inode_addr);
  }
 }
 d->d_dentry[0] = d;
 d->d_dentry[1] = p;
 j = 2;
 for(i = 0; i < MAX_D_INODE; ++i) {
  d->d_dentry[j] = vfs_dentry_make(d, d->d_inode[i]);
  if(d->d_dentry[j] != NULL) {
   ++j;
  }
 }
 d->num_dentry = j;

// printf("d_open\n");
 return;
}

void vfs_sb_refresh(FILE *disk, struct super_block *sb) {
 int i, k;

 fseek(disk, 0, SEEK_SET);
 k = disk_read_int(disk);
 disk = disk_write_long(disk, sb->s_blocksize); 

 return;
}

void* vfs_sb_init(FILE *disk) {
 struct super_block *sb;
 struct dentry *d;
 struct inode *in;
 int root_inode_addr;
 int inode_id;
 int inode_addr;
 int block_num, i, j;

 sb = (struct super_block*)malloc(sizeof(struct super_block));
 sb->s_mode = USER_MODE;
 root_inode_addr = disk_read_int(disk);
// inode_id = ((root_inode_addr / BYTE) - INODE_TABLE_ADDR) / INODE_SIZE;
 inode_id = (root_inode_addr - INODE_TABLE_ADDR) / INODE_SIZE;
 sb->s_blocksize = disk_read_long(disk);
 sb->s_maxbytes = disk_read_long(disk);

 in = vfs_inode_read(disk, root_inode_addr);
 
 sb->s_root = vfs_dentry_make(NULL, in);
 d = sb->s_root;
 d->sb = sb;
 d->parent = d;

 d->d_type = DENTRY_OPEN;
 d->d_mode = in->i_mode;
 block_num = (in->size / DISK_BLOCK_SIZE);
// if(in->size % DISK_BLOCK_SIZE != 0) {
//  ++block_num;
// }
 for(i = 0; i < block_num; ++i) {
  for(j = 0; j < DISK_BLOCK_SIZE / BYTE; ++j) {
//   fseek(disk, ((int)in->direct_block[i] / BYTE) + (j * 8), SEEK_SET);
   fseek(disk, (int)in->direct_block[i] + (j * 8), SEEK_SET);
   inode_addr = disk_read_int(disk);
   if(inode_addr != 0) {
    ++d->num_inode;
   }
   d->d_inode[(DISK_BLOCK_SIZE / BYTE)*i + j] = vfs_inode_read(disk, inode_addr);
  }
 }
 d->d_dentry[0] = d;
 d->d_dentry[1] = d;
 j = 2;
 for(i = 0; i < MAX_D_INODE; ++i) {
  d->d_dentry[j] = vfs_dentry_make(d, d->d_inode[i]);
  if(d->d_dentry[j] != NULL) {
   ++j;
  }
 }
 d->num_dentry = j;

 sb->s_root_inode = in;

 return sb;
}

disk.h

/* disk.h */
#ifndef _DISK_H_
#define _DISK_H_

#define BYTE 8 
#define MAX_CHAR 64

#define INDEX_NUM 2
#define INODE_NUM 256
#define INODE_SIZE 512
#define INODE_FILE 0
#define INODE_DIRECTORY 1

#define DIRECTORY_ENTRY_BLOCK_NUM 1

#define DATA_BLOCK_NUM 893
#define DISK_BLOCK_NUM 1024

#define DISK_BLOCK_SIZE 1024

#define SUPER_BLOCK_ADDR 0
#define DISK_BLOCK_INDEX_ADDR 1024
#define INODE_INDEX_ADDR 2048
#define INODE_TABLE_ADDR 3072
#define DATA_BLOCK_ADDR (INODE_TABLE_ADDR + INODE_SIZE * INODE_NUM)

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

char disk_read_char(FILE *f);
int disk_read_int(FILE *f);
unsigned long disk_read_long(FILE *f);
char* disk_read_name(FILE *f, char buf[]);
struct tm disk_read_time(FILE *f);
FILE* disk_write_char(FILE *f, char value);
FILE* disk_write_int(FILE *f, int value);
FILE* disk_write_long(FILE *f, unsigned long value);
FILE* disk_write_name(FILE *f, char name[]);
FILE* disk_write_time(FILE *f, struct tm c);
int disk_alloc_inode(FILE *f);
void disk_free_inode(FILE *f, int inode_addr);
int disk_alloc_block(FILE *f);
int disk_alloc_indirect_block(FILE *f, int *block_num, int depth);
void disk_free_block(FILE *f, int block_addr);
void disk_free_indirect_block(FILE *f, int block_addr, int depth);
FILE* disk_init(char disk_name[]);

#endif

disk.c

/* disk.c */
#include "disk.h"

char buf_char[1];
char buf_int[8];
char buf_long[16];
char buf_name[MAX_CHAR];
char padding_64[MAX_CHAR] = "0000000000000000000000000000000000000000000000000000000000000000";

char disk_read_char(FILE *f) {
 fread(buf_char, 1, 1, f);

 return buf_char[0];
}

int disk_read_int(FILE *f) {
 int i, t;
 fread(buf_int, 1, 8, f);
 t = 0;
 for(i = 0; i < 8; ++i) {
  if(buf_int[i] < 'a') {
   t = (t * 16) + buf_int[i] - '0';
  } else {
   t = (t * 16) + buf_int[i] - 'a' + 10;
  }
 }
 
 return t;
}

unsigned long disk_read_long(FILE *f) {
 int i;
 unsigned long t;
 fread(buf_long, 1, 16, f);
 t = 0;
 for(i = 0; i < 16; ++i) {
  if(buf_long[i] < 'a') {
   t = (t * 16) + buf_long[i] - '0';
  } else {
   t = (t * 16) + buf_long[i] - 'a' + 10;
  }
 }

 return t;
}

char* disk_read_name(FILE *f, char buf[]) {
 int i;
 fread(buf_name, 1, MAX_CHAR, f);
 for(i = 0; i < MAX_CHAR; ++i) {
  buf[i] = buf_name[i];
  if(buf_name[i] == '|') {
   ++i;
   break;
  }
 }
 for(;i < MAX_CHAR; ++i) {
  buf[i] = '\0';
 }
 
 return buf;
}

struct tm disk_read_time(FILE *f) { 
 struct tm c;

 c.tm_sec = disk_read_int(f);
 c.tm_min = disk_read_int(f);
 c.tm_hour = disk_read_int(f);
 c.tm_mday = disk_read_int(f);
 c.tm_mon = disk_read_int(f);
 c.tm_year = disk_read_int(f);
 c.tm_wday = disk_read_int(f);
 c.tm_yday = disk_read_int(f);
 c.tm_isdst = disk_read_int(f);

 return c;
}

FILE* disk_write_char(FILE *f, char value) {
 buf_char[0] = value;
 fwrite(buf_char, 1, 1 ,f);

 return f;
}

FILE* disk_write_int(FILE *f, int value) {
 int i, t;
 for(i = 7; i >= 0; --i) {
  t = value % 16;
  if(t < 10) {
   buf_int[i] = '0' + t;
  } else {
   buf_int[i] = 'a' + (t - 10);
  }
  value = value / 16;
 }

 fwrite(buf_int, 1, 8, f);

 return f;
}

FILE* disk_write_long(FILE *f, unsigned long value) {
 int i;
 unsigned long t;
 for(i = 15; i >= 0; --i) {
  t = value % 16;
  if(t < 10) {
   buf_long[i] = '0' + t;
  } else {
   buf_long[i] = 'a' + (t - 10);
  }
  value = value / 16;
 }

 fwrite(buf_long, 1, 16, f);

 return f;
}

FILE* disk_write_name(FILE *f, char name[]) {
 int i;
 for(i = MAX_CHAR - 1; i >= 0; --i) {
  buf_name[i] = name[i];
 }

 fwrite(buf_name, 1, MAX_CHAR, f);

 return f;
}

FILE* disk_write_time(FILE *f, struct tm c) { 
 f = disk_write_int(f, c.tm_sec);
 f = disk_write_int(f, c.tm_min);
 f = disk_write_int(f, c.tm_hour);
 f = disk_write_int(f, c.tm_mday);
 f = disk_write_int(f, c.tm_mon);
 f = disk_write_int(f, c.tm_year);
 f = disk_write_int(f, c.tm_wday);
 f = disk_write_int(f, c.tm_yday);
 f = disk_write_int(f, c.tm_isdst);

 return f;
}

int disk_alloc_inode(FILE *f) {
 int i, inode_addr;
 char c;

 fseek(f, INODE_INDEX_ADDR, SEEK_SET);
 for(i = 0; i < INODE_NUM; ++i) {
  c = disk_read_char(f);
  if(c == '0') {
   break;
  }
 }
 if(i == INODE_NUM) {
  return 0;
 }
 fseek(f, -1, SEEK_CUR);
 f = disk_write_char(f, '1');

// inode_addr = (INODE_TABLE_ADDR + (INODE_SIZE * i)) * BYTE;
 inode_addr = INODE_TABLE_ADDR + (INODE_SIZE * i);
 return inode_addr;
}

void disk_free_inode(FILE *f, int inode_addr) {
 int i, index, addr;

 if(inode_addr == 0) {
  return;
 }

// addr = inode_addr / BYTE;
 addr = inode_addr;
 index = (addr - INODE_TABLE_ADDR) / INODE_SIZE;

 fseek(f, addr, SEEK_SET);
 for(i = 0; i < INODE_SIZE / 64; ++i) {
  f = disk_write_name(f, padding_64);
 }
 fseek(f, INODE_INDEX_ADDR + index, SEEK_SET);
 f = disk_write_char(f, '0');

 return;
}

int disk_alloc_block(FILE *f) {
 int i, block_addr;
 char c;

 fseek(f, DISK_BLOCK_INDEX_ADDR, SEEK_SET);
 for(i = 0; i < DISK_BLOCK_NUM; ++i) {
  c = disk_read_char(f);
  if(c == '0') {
   break;
  }
 }
 if(i == DISK_BLOCK_NUM) {
  return 0;
 }
 fseek(f, -1, SEEK_CUR);
 f = disk_write_char(f, '1');

// block_addr = DISK_BLOCK_SIZE * i * BYTE;
 block_addr = DISK_BLOCK_SIZE * i;

 return block_addr;
}

int disk_alloc_indirect_block(FILE *f, int *block_num, int depth) {
 int i, block_addr, parent_addr, addr, k;
 char c;

 if(*block_num == 0) {
  return 0;
 }
 if(depth == 0) {
  return disk_alloc_block(f);
 }
 
 parent_addr = disk_alloc_block(f);
 if(parent_addr == 0) {
  return parent_addr;
 }
 
  for(i = 0; i < DISK_BLOCK_SIZE / 8; ++i) {
   addr = (int)disk_alloc_indirect_block(f, block_num, depth - 1);
   if(addr == 0) {
    return parent_addr;
   } else {
    if(depth == 1) {
     --(*block_num);
    }
    fseek(f, parent_addr + i*8, SEEK_SET);
    f = disk_write_int(f, addr);
    if(block_num == 0) {
     return parent_addr;
    }
   }
  }
// }

 return parent_addr;
}

void disk_free_block(FILE *f, int block_addr) {
 int i, index, addr;

 if(block_addr == 0) {
  return;
 }

// addr = block_addr / BYTE;
 addr = block_addr;
 index = addr / DISK_BLOCK_SIZE;

 fseek(f, addr, SEEK_SET);
 for(i = 0; i < DISK_BLOCK_SIZE / 64; ++i) {
  f = disk_write_name(f, padding_64);
 }
 fseek(f, DISK_BLOCK_INDEX_ADDR + index, SEEK_SET);
 f = disk_write_char(f, '0');

 return;
}

void disk_free_indirect_block(FILE *f, int block_addr, int depth) {
 int i, index, addr, child_addr;

 if(block_addr == 0) {
  return;
 }
 if(depth == 0)
 {
  disk_free_block(f, block_addr);
  return;
 }

// addr = block_addr / BYTE;
 addr = block_addr;
 index = addr / DISK_BLOCK_SIZE;

 for(i = 0; i < DISK_BLOCK_SIZE / 8; ++i) {
  fseek(f, addr + i*8, SEEK_SET);
  child_addr = disk_read_int(f);
  disk_free_indirect_block(f, child_addr, depth - 1);
 }
 disk_free_block(f, addr);

 return;
}

FILE* disk_init(char disk_name[]) {
 time_t timer;
 struct tm c, *t;
 FILE *f;
 int i, j;
 
 f = fopen(disk_name, "r");
 if(!f) {
  f = fopen(disk_name, "w");

  // c_time
  timer = time(NULL);
  t = localtime(&timer);
  c = *t;
  //free(t);

  // super_block (1KB)
  //f = disk_write_name(f, "2009147093|");// disk_name,64byte
  f = disk_write_int(f, INODE_TABLE_ADDR);  // root_inode,8byte
  f = disk_write_long(f, DISK_BLOCK_SIZE * 132);// block_size,16byte
  f = disk_write_long(f, DISK_BLOCK_SIZE * DISK_BLOCK_NUM);// maxbytes,16byte
  f = disk_write_int(f, 0);   // padding,8byte 
  f = disk_write_long(f, 0);  // padding,16byte
  for(i = 0; i < 15; ++i) {
   f = disk_write_name(f, padding_64);
  }      // padding,1024-64

  // disk block index block (1KB)
  for(i = 0; i < 131; ++i) {
   f = disk_write_char(f, '1');
  }
  for(i = 131; i < 132; ++i) {
   f = disk_write_char(f, '1'); // root inode
  }
  for(i = 132; i < 1024; ++i) { // 0~DISK_BLOCK_NUM-1
   f = disk_write_char(f, '0');
   //f = disk_write_name(f, padding_64);
  }     // init by 0

  // inode index block (1KB)
  f = disk_write_char(f, '1');
  for(i = 1; i < 1024; ++i) { // INODE_NUM
   f = disk_write_char(f, '0');
   //f = disk_write_name(f, padding_64);
  }     // init by 0

  // inode table (inode = 512byte > 8+64+72+72+8+8*15 = 344)
  // root inode
  f = disk_write_int(f, INODE_DIRECTORY); // i_type,8byte
  f = disk_write_int(f, 7);  // i_mode,8byte
  f = disk_write_name(f, "|");  // i_name,64byte
  f = disk_write_time(f, c);  // i_ctime,72byte
  f = disk_write_time(f, c);  // i_atime,72byte
  f = disk_write_int(f, DISK_BLOCK_SIZE); // i_size,8byte
  for(i = 0; i < 1; ++i) {
//   f = disk_write_int(f, (DATA_BLOCK_ADDR + DISK_BLOCK_SIZE*i) * BYTE); 
   f = disk_write_int(f, DATA_BLOCK_ADDR + DISK_BLOCK_SIZE*i); 
  }
  for(i = 1; i < 15; ++i) {  // block,8*15byte
   f = disk_write_int(f, 0); // direct X 12
  }     // indirect X 3
  f = disk_write_name(f, padding_64); // padding,64byte
  f = disk_write_name(f, padding_64); // padding,64byte
  for(i = 0; i < 4; ++i) {  // padding
   f = disk_write_int(f, 0); 
  }     // 8byte X 4
  // root inode end

  for(j = 1; j < INODE_NUM; ++j) {
   for(i = 0; i < 8; ++i) {
    f = disk_write_name(f, padding_64);
   }
  }    // 128KB (INODE_NUM/2 byte)
  // inode table end

  // remain 1024 - 131 KB = 893KB
  // disk blocks
  for(j = 0; j < 893; ++j) {
   for(i = 0; i < 16; ++i) {
    f = disk_write_name(f, padding_64);
   }  // disk block = 1KB
  }    // 893KB

 }
 fclose(f);
 f = fopen(disk_name, "r+");
 

 return f;
}

지하철 노선 최단경로, 최소환승 찾기 ( Find the Shortest Path and Minimum Transfer for Seoul Metro )

main.cpp

#define MAX_STATION 398
// ㄴ 지하철 역 갯수
#include "Graph.h"

int main()
{
 Graph test; // 그래프 선언

 test.Subway("subway.txt",MAX_STATION); // 지하철 경로 찾기 프로그램 시작!

 return 0; // 끝
}

Graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include <stack> // 완성된 클라우드에서 리커시브함수로 경로를 저장할때 사용
#include <string> // 역이름 클래스


class Edge // 엣지 클래스..
{
public:
 int id; // 역 번호
 int time; // 이동시간
 int transfer; // 환승 횟수
 Edge* next;
 Edge() : next(NULL) {}
};

class Graph // 그래프 클래스..
{
private:
 ofstream outputfile;
 string* station; // 역 번호에 따른 역 이름
 Edge* graph; // 그래프 (adjacency list)
 int* route; // 음수면 클라우드에 포함되지 않은 버텍스, 음수가 아니면 클라우드에 포함된 버텍스
 int n; // 지하철 역 갯수
public:
 int Choose(bool t); // 클라우드에 포함되지 않은 버텍스 중, cost가 최소인 버텍스의 인덱스를 반환. t에따라 요소가 달라짐
 void DijkstraAlgorithm(int start,bool t); // Dijkstra Algorithm 구현부분
 void Subway(const char* name, int N); // 출발역,도착역을 입력 받고 Dijkstra Algorithm을 실행하여 최단시간,최소환승 경로를 출력해줌
 bool FindRoute(stack<int>& s, int start, int end); // Dijkstra Algorithm을 실행한 후의 그래프에서 경로를 스택에 옮겨주는 재귀함수
};

#endif

Graph.cpp

#include "Graph.h"

int Graph::Choose(bool t) // 최소인 버텍스의 인덱스를 반환
{
 int min=99999,min_transfer=9999,pos=-1; 

 if(t) // 최단시간 경로일떄 
 {

  for(int i=0;i<n;i++)
  {
   if(route[i] < 0)
   {
    if(graph[i].time < min) // 시간이 덜드는 버텍스를 선택
    {
     min = graph[i].time;
     min_transfer = graph[i].transfer;
     pos = i;
    }
    else if(graph[i].time == min)
    {
     if(graph[i].transfer < min_transfer)
     {
      min = graph[i].time;
      min_transfer = graph[i].transfer;
      pos = i;
     }
    }
   }
  }

 }
 else // 최소환승 경로일때
 {

  for(int i=0;i<n;i++)
  {
   if(route[i] < 0)
   {
    if(graph[i].transfer < min_transfer) // 환승 횟수가 작은 버텍스를 선택
    {
     min = graph[i].time;
     min_transfer = graph[i].transfer;
     pos = i;
    }
    else if(graph[i].transfer == min_transfer) // 환승 횟수가 같으면
    {
     if(graph[i].time < min) // 시간이 덜드는 버텍스를 선택
     {
      min = graph[i].time;
      min_transfer = graph[i].transfer;
      pos = i;
     }
    }
   }
  }

 }
 return pos; // 인덱스 반환
}

void Graph::DijkstraAlgorithm(int start, bool t) // Dijskstra Algorithm 
{
 int minpos; 


 // 그래프와 route배열 초기화
 for(int i=0;i<n;i++)
 {
  route[i] = -1;
  graph[i].id = -1;
  graph[i].time = 99999;
  graph[i].transfer = 9999;
 }

 // 시작점과 연결된 버텍스에 엣지의 코스트를 대입
 for(Edge* p=graph[start].next;p!=NULL;p=p->next)
 {
  
  if(station[start] == station[p->id]) // 시작점과 연결된 버텍스가 환승역일때
   // 출발역이 환승역인 경우는 환승 횟수와 시간을 0으로 따져야 한다.
  {
   graph[p->id].time = 0;
   graph[p->id].transfer = 0;
  }
  else // 일반적인 경우
  {
   graph[p->id].time = p->time;
   graph[p->id].transfer = p->transfer;
  }
 }


 // 출발역이 환승역인 경우. 출발역과 같은 이름을 가진 역 번호를 가진 엣지들의 값을 모두 0으로 만들어줘야한다
 // bug fix.. (환승역 -> 환승역 경로찾기시 경로 찾기 실패)
 for(int i=0;i<n;i++)
 {
  if(station[start] == station[i])
  {
   for(Edge* p=graph[i].next;p!=NULL;p=p->next)
   {
    if(station[i] == station[p->id])
    {
     p->time = 0;
     p->transfer = 0;
    }
   }
  }
 }


 // 시작점을 클라우드에 포함시킨다
 //route[start] = start;
 route[start] = 0;
 // 시작점 초기화
 graph[start].time = 0;
 graph[start].transfer = 0;


 for(int i=0,prev=start;i<n-2;i++)
 {
  // 최소인 버텍스 선택
  minpos = this->Choose(t);

  //route[minpos] = prev;

  // 최소인 버텍스 클라우드에 포함시킨다
  route[minpos] = 0;
  
  // 선택된 버텍스에 연결된 엣지들로 다른 버텍스의 값을 업데이트시킨다 
  for(Edge* p=graph[minpos].next;p!=NULL;p=p->next)
  {
   if(t) // 최단시간 경로일때
   {
    if(graph[minpos].time + p->time < graph[p->id].time) // 시간을 비교하여 업데이트
    {
     graph[p->id].time = graph[minpos].time + p->time;
     graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
    }
    else if(graph[minpos].time + p->time == graph[p->id].time) // 시간이 같을때.. 환승횟수가 적은게 좋겠죠?(상식..ㅠ)
    {
     if(graph[minpos].transfer + p->transfer < graph[p->id].transfer) // 환승횟수를 비교
     {
      graph[p->id].time = graph[minpos].time + p->time;
      graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
     }
    }
   }
   else // 최소환승 경로일때
   {
    if(graph[minpos].transfer + p->transfer < graph[p->id].transfer) // 환승횟수를 비교하여 업데이트
    {
     graph[p->id].time = graph[minpos].time + p->time;
     graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
    }
    else if(graph[minpos].transfer + p->transfer == graph[p->id].transfer) // 환승횟수가 같으면
    {
     if(graph[minpos].time + p->time < graph[p->id].time) // 시간을 비교
     {
      graph[p->id].time = graph[minpos].time + p->time;
      graph[p->id].transfer = graph[minpos].transfer+ p->transfer;
     }
    }
   }
   
  }

  //prev = minpos;

 }

}

void Graph::Subway(const char* name, int N) 
{
 
 fstream file;
 int start=-1,end=-1;
 int min,v,prev;
 string t; // 임시 스트링 변수
 stack<int> s,r; // 스택 s,r
 Edge* temp; // 임시 엣지포인터 변수
 Edge* p; // 임시 엣지포인터 변수
 n = N; // 지하철 역 갯수 초기화

 // 클래스 데이터 초기화
 graph = new Edge[n];
 station = new string[n];
 route = new int[n];

 file.open(name,ios::in); // 파일 읽기 (ios::in -> 읽기)

 int t1,t2,time;
 string s1,s2;
 while(!file.eof())
 {
  // 임시 변수에 한 줄의 데이터 입력
  file >> t1;
  file >> t2;
  file >> time;
  file >> s1;

  // 버그방지용
  // 파일 마지막 공백문자 같은 엉뚱한 문자가 있을때 멈춘다
  if(file.eof())
   break;

  file >> s2;

  //끝

  // 인덱스에 넣기위해 역 번호에서 1씩 빼준다
  t1-=1;
  t2-=1;

  // 엣지를 만든다 (1)
  temp = new Edge();
  temp->id = t2;
  temp->time = time;
  if(s1==s2) temp->transfer = 1;
  else temp->transfer = 0;
 
  // 서로의 버텍스에 엣지를 연결한다 (1)
  p=&graph[t1];
  while(p->next!=NULL)
  {
   p=p->next;
  }
  p->next = temp;

  // 엣지를 만든다 (2)
  temp = new Edge();
  temp->id = t1;
  temp->time = time;
  if(s1==s2) temp->transfer = 1;
  else temp->transfer = 0;
 
  // 서로의 버텍스에 엣지를 연결한다 (2)
  p=&graph[t2];
  while(p->next!=NULL)
  {
   p=p->next;
  }
  p->next = temp;


  // 역 이름 배열에 역 이름을 저장한다
  station[t1] = s1;
  station[t2] = s2;


 }
  
 file.close();
 //끝-파일입력


 // 출발역,도착역 입력!!!!!!
 while(start==end)
 {

  while(start < 0)
  {
   std::cout << "출발역을 입력하세요...\n : ";
   cin >> t;
   std::cout << std::endl;  

   // 출발역 이름과 같은 역번호 아무거나 하나 찾는다
   for(int i=0;i<n;i++)
   {
    if(station[i] == t)
    {
     start = i;
     break;
    }
   }
 
   //없으면
   if(start < 0)
   {
    std::cout << "잘못 입력하셨습니다." << std::endl;
    
   }
  }

  while(end < 0)
  {

   std::cout <<  "도착역을 입력하세요...\n : ";
   cin >> t;
   std::cout << std::endl;

  
   // 도착역 이름과 같은 역번호 아무거나 하나 찾는다
   for(int i=0;i<n;i++)
   {
    if(station[i] == t)
    {
     end = i;
     break;
    }
   }
  
   //없으면
   if(end < 0)
   {
    std::cout << "잘못 입력하셨습니다." << std::endl;
    
   }

  }

  if(start==end)
  {
   std::cout << "출발역과 도착역이 같습니다...." << std::endl;
   start = end = -1;
  }
 }



 std::cout << "찾고자 하는 구간 : " << station[start] << " -> " << station[end] << std::endl << std::endl;
 std::cout << "* 최단시간 경로 :" << std::endl;
 this->DijkstraAlgorithm(start,true); // 알고리즘 실행 (true이므로 최단시간 경로)

 // 도착역 중, 가장 소요시간이 작은 버텍스를 선택한다
 min=graph[end].time;
 for(int i=0;i<n;i++)
 {
  if(station[end] == station[i])
  {
   if(graph[i].time < min)
   {
    min = graph[i].time;
    end = i;
   }
  }
 }

 // 출발역의 인덱스와 찾은 버텍스의 인덱스로 경로를 스택에 저장한다. 
 this->FindRoute(s,start,end);

 // 스택에서 스택으로 옮긴다 (순서 역순으로 바꾸기)
 while(!s.empty())
 {
  r.push(s.top());
  s.pop();
 }

 // 경로 출력
 for(v=0,prev=-1;!r.empty();v++)
 {
  if(prev != -1 && station[prev] == station[r.top()])
  {
   if(station[r.top()] != station[start])
    std::cout << "(환승)";

   v--;
   prev = r.top();
   r.pop();
  }
  else
  {
  if(v!=0)
   std::cout << " -> ";
  else
   std::cout << " ";

  std::cout << station[r.top()];
  prev = r.top();
  r.pop();

  }
 }
 std::cout << std::endl <<  "\t-->" << v-1 << "개역 지남" << std::endl
  << "\t-->" << graph[end].time/60 << "시간 " << graph[end].time%60 << "분 걸리고, " << graph[end].transfer << "번 환승합니다." << std::endl;

 std::cout << std::endl;
 std::cout << "* 최소환승 경로 :" << std::endl;
 this->DijkstraAlgorithm(start,false); // 알고리즘 실행 (false- 최소환승경로)

 // 도착역 버텍스 중에 환승횟수가 가장 작은 버텍스를 선택
 min=graph[end].transfer;
 for(int i=0;i<n;i++)
 {
  if(station[end] == station[i])
  {
   if(graph[i].transfer < min)
   {
    min = graph[i].transfer;
    end = i;
   }
  }
 }

 // 경로찾기
 this->FindRoute(s,start,end);

 // 스택에서 스택으로 옮김
 while(!s.empty())
 {
  r.push(s.top());
  s.pop();
 }

 //출력
 for(v=0,prev=-1;!r.empty();v++)
 {
  if(prev != -1 && station[prev] == station[r.top()])
  {
   if(station[r.top()] != station[start])
    std::cout << "(환승)";

   v--;
   prev = r.top();
   r.pop();
  }
  else
  {
  if(v!=0)
   std::cout << " -> ";
  else
   std::cout << " ";
  
  std::cout << station[r.top()];
  prev = r.top();
  r.pop();
  }
 }
 std::cout << std::endl <<  "\t-->" << v-1 << "개역 지남" << std::endl
  << "\t-->" << graph[end].time/60 << "시간 " << graph[end].time%60 << "분 걸리고, " << graph[end].transfer << "번 환승합니다." << std::endl;


}

bool Graph::FindRoute(stack<int> &s, int start, int end) // 완성된 클라우드 에서 경로찾기
{
 s.push(start); // 스택에 넣는다.

 if(start == end) // 시작=끝 일때 경로찾았다고 알려줌 (return true)
  return true;

 for(Edge* p=graph[start].next;p!=NULL;p=p->next) // 시작점에 연결된 엣지를 모두 조사한다
 { 
  // 시작점버텍스값 + 엣지값 과 엣지로연결된 버텍스의 값이 같으면 (DijkstraAlgorithm에서 클라우드에 포함시킬떄 연결한 경로)
  if(graph[start].time + p->time == graph[p->id].time && graph[start].transfer + p->transfer == graph[p->id].transfer)
  {
   if(!this->FindRoute(s,p->id,end)) // 다음 경로로 이동 했는데 경로가 없다면
   {
    s.pop(); // pop한다
   }
   else // 경로를 찾았으면 pop하지않고 유지
   {
    return true; // 경로를 찾았다고 알려줌
   }
  }
 }
 return false;
}

subway.txt

1 2 3 소요산 동두천
2 3 3 동두천 보산
3 4 3 보산 동두천중앙
4 5 3 동두천중앙 지행
5 6 3 지행 덕정
6 7 3 덕정 덕계
7 8 3 덕계 주내
8 9 3 주내 녹양
9 10 3 녹양 가능
10 11 3 가능 의정부
11 12 2 의정부 회룡
12 13 3 회룡 망월사
13 14 2 망월사 도봉산
14 15 3 도봉산 도봉
15 16 2 도봉 방학
16 17 2 방학 창동
17 18 3 창동 녹천
18 19 2 녹천 월계
19 20 2 월계 성북
20 21 2 성북 석계
21 22 2 석계 신이문
22 23 2 신이문 외대앞
23 24 3 외대앞 회기
24 25 2 회기 청량리
25 26 2 청량리 제기동
26 27 1 제기동 신설동
27 28 1 신설동 동묘앞
28 29 1 동묘앞 동대문
29 30 1 동대문 종로5가
30 31 2 종로5가 종로3가
31 32 2 종로3가 종각
32 33 3 종각 시청
33 34 2 시청 서울역
34 35 3 서울역 남영
35 36 2 남영 용산
36 37 3 용산 노량진
37 38 3 노량진 대방
38 39 2 대방 신길
39 40 2 신길 영등포
40 41 2 영등포 신도림
41 42 2 신도림 구로
42 43 3 구로 구일
43 44 2 구일 개봉
44 45 2 개봉 오류동
45 46 3 오류동 온수
46 47 1 온수 역곡
47 48 2 역곡 소사
48 49 2 소사 부천
49 50 2 부천 중동
50 51 2 중동 송내
51 52 1 송내 부개
52 53 2 부개 부평
53 54 2 부평 백운
54 55 3 백운 동암
55 56 2 동암 간석
56 57 2 간석 주안
57 58 2 주안 도화
58 59 3 도화 제물포
59 60 3 제물포 도원
60 61 3 도원 동인천
61 62 2 동인천 인천
42 63 5 구로 가산
63 64 3 가산 독산
64 65 3 독산 시흥
65 66 3 시흥 석수
66 67 3 석수 관악
67 68 3 관악 안양
68 69 3 안양 명학
69 70 4 명학 금정
70 71 4 금정 군포
71 72 4 군포 의왕
72 73 4 의왕 성균관대
73 74 4 성균관대 화서
74 75 4 화서 수원
75 76 4 수원 세류
76 77 4 세류 병점
77 78 4 병점 세마
78 79 4 세마 오산대
79 80 4 오산대 오산
80 81 4 오산 진위
81 82 4 진위 송탄
82 83 4 송탄 서정리
83 84 4 서정리 지제
84 85 4 지제 평택
85 86 4 평택 선환
86 87 4 선환 직산
87 88 4 직산 두정
88 89 4 두정 천안
65 90 5 시흥 광명
91 92 2 낙성대 사당
92 93 3 사당 방배
93 94 2 방배 서초
94 95 2 서초 교대
95 96 2 교대 강남
96 97 1 강남 역삼
97 98 2 역삼 선릉
98 99 2 선릉 삼성
99 100 2 삼성 종합운동장
100 101 2 종합운동장 신천
101 102 2 신천 잠실
102 103 2 잠실 성내
103 104 3 성내 강변
104 105 1 강변 구의
105 106 3 구의 건대입구
106 107 2 건대입구 성수
107 108 2 성수 뚝섬
108 109 3 뚝섬 한양대
109 110 2 한양대 왕십리
110 111 1 왕십리 상왕십리
111 112 2 상왕십리 신당
112 113 2 신당 동대문운동장
113 114 2 동대문운동장 을지로4가
114 115 2 을지로4가 을지로3가
115 116 2 을지로3가 을지로입구
116 117 1 을지로입구 시청
117 118 1 시청 충정로
118 119 3 충정로 아현
119 120 2 아현 이대
120 121 1 이대 신촌
121 122 2 신촌 홍대입구
122 123 2 홍대입구 합정
123 124 2 합정 당산
124 125 2 당산 영등포구청
125 126 2 영등포구청 문래
126 127 2 문래 신도림
127 128 3 신도림 대림
128 129 2 대림 구로디
129 130 2 구로디 신대방
130 131 2 신대방 신림
131 132 2 신림 봉천
132 133 2 봉천 서울대입구
133 91 2 서울대입구 낙성대
134 135 3 수서 일원
135 136 2 일원 대청
136 137 2 대청 학여울
137 138 1 학여울 대치
138 139 2 대치 도곡
139 140 2 도곡 매봉
140 141 2 매봉 양재
141 142 3 양재 남부터미널
142 143 2 남부터미널 교대
143 144 2 교대 고속터미널
144 145 2 고속터미널 잠원
145 146 2 잠원 신사
146 147 3 신사 압구정
147 148 2 압구정 옥수
148 149 2 옥수 금호
149 150 1 금호 약수
150 151 2 약수 동대입구
151 152 2 동대입구 충무로
152 153 1 충무로 을지로3가
153 154 1 을지로3가 종로3가
154 155 2 종로3가 안국
155 156 2 안국 경복궁
156 157 3 경복궁 독립문
157 158 2 독립문 무악재
158 159 2 무악재 홍제
159 160 2 홍제 녹번
160 161 2 녹번 불광
161 162 2 불광 연신내
162 163 3 연신내 구파발
163 164 3 구파발 지축
164 165 4 지축 삼송
165 166 4 삼송 원당
166 167 3 원당 화정
167 168 4 화정 대곡
168 169 3 대곡 백석
169 170 3 백석 마두
170 171 2 마두 정발산
171 172 3 정발산 주엽
172 173 2 주엽 대화
174 175 4 오이도 정왕
175 176 4 정왕 신길온천
176 177 4 신길온천 안산
177 178 2 안산 공단
178 179 3 공단 고잔
179 180 2 고잔 중앙
180 181 3 중앙 한대앞
181 182 3 한대앞 상록수
182 183 3 상록수 반월
183 184 4 반월 대야미
184 185 3 대야미 수리산
185 186 2 수리산 산본
186 187 3 산본 금정
187 188 3 금정 범계
188 189 2 범계 평촌
189 190 4 평촌 인덕원
190 191 3 인덕원 정부종합청사
191 192 2 정부종합청사 과천
192 193 2 과천 대공원
193 194 2 대공원 경마공원
194 195 3 경마공원 선바위
195 196 3 선바위 남태령
196 197 1 남태령 사당
197 198 2 사당 이수
198 199 3 이수 동작
199 200 4 동작 이촌
200 201 2 이촌 신용산
201 202 1 신용산 삼각지
202 203 2 삼각지 숙대입구
203 204 2 숙대입구 서울역
204 205 2 서울역 회현
205 206 2 회현 명동
206 207 1 명동 충무로
207 208 2 충무로 동대문운동장
208 209 2 동대문운동장 동대문
209 210 2 동대문 혜화
210 211 2 혜화 한성대입구
211 212 3 한성대입구 성신여대입구
212 213 2 성신여대입구 길음
213 214 2 길음 미아삼거리
214 215 2 미아삼거리 미아
215 216 3 미아 수유
216 217 2 수유 쌍문
217 218 2 쌍문 창동
218 219 2 창동 노원
219 220 2 노원 중계
220 221 3 중계 상계
221 222 3 상계 당고개
223 224 2 용산 이촌
224 225 2 이촌 서빙고
225 226 2 서빙고 한남
226 227 2 한남 옥수
227 228 2 옥수 응봉
228 229 2 응봉 왕십리
229 230 2 왕십리 청량리상
230 231 2 청량리상 회기
231 232 2 회기 중랑
232 233 3 중랑 상봉
233 234 3 상봉 망우
234 235 3 망우 양원
235 236 4 양원 구리
236 237 4 구리 도농
237 238 4 도농 양정
238 239 4 양정 덕소
240 241 2 방화 개화산
241 242 2 개화산 김포공항
242 243 2 김포공항 송정
243 244 2 송정 마곡
244 245 2 마곡 발산
245 246 2 발산 우장산
246 247 2 우장산 화곡
247 248 2 화곡 까치산
248 249 2 까치산 신정
249 250 2 신정 목동
250 251 2 목동 오목교
251 252 2 오목교 양평
252 253 2 양평 영등포구청
253 254 2 영등포구청 문래
254 255 2 문래 영등포시장
255 256 2 영등포시장 신길
256 257 2 신길 여의도
257 258 2 여의도 여의나루
258 259 2 여의나루 마포
259 260 2 마포 공덕
260 261 2 공덕 애오개
261 262 2 애오개 충정로
262 263 2 충정로 서대문
263 264 2 서대문 광화문
264 265 2 광화문 종로3가
265 266 2 종로3가 을지로4가
266 267 2 을지로4가 동대문운동장
267 268 2 동대문운동장 청구
268 269 2 청구 신금호
269 270 2 신금호 행당
270 271 2 행당 왕십리
271 272 2 왕십리 마장
272 273 2 마장 답십리
273 274 2 답십리 장한평
274 275 2 장한평 군자
275 276 2 군자 아차산
276 277 2 아차산 광나루
277 278 2 광나루 천호
278 279 2 천호 강동
279 280 2 강동 둔촌동
280 281 2 둔촌동 올림픽공원
281 282 2 올림픽공원 방이
282 283 2 방이 오금
283 284 2 오금 개롱
284 285 2 개롱 거여
285 286 3 거여 마천
279 287 2 강동 길동
287 288 2 길동 굽은다리
288 289 2 굽은다리 명일
289 290 2 명일 고덕
290 291 3 고덕 상일동
292 293 2 봉화산 화랑대
293 294 2 화랑대 태릉입구
294 295 2 태릉입구 석계
295 296 2 석계 돌곶이
296 297 2 돌곶이 상월곡
297 298 2 상월곡 월곡
298 299 2 월곡 고려대
299 300 2 고려대 안암
300 301 2 안암 보문
301 302 2 보문 창신
302 303 2 창신 동묘앞
303 304 2 동묘앞 신당
304 305 2 신당 청구
305 306 2 청구 약수
306 307 2 약수 버티고개
307 308 2 버티고개 한강진
308 309 2 한강진 이태원
309 310 2 이태원 녹사평
310 311 2 녹사평 삼각지
311 312 2 삼각지 효창공원앞
312 313 2 효창공원앞 공덕
313 314 2 공덕 대흥
314 315 2 대흥 광흥창
315 316 2 광흥창 상수
316 317 2 상수 합정
317 318 2 합정 망원
318 319 2 망원 마포구청
319 320 2 마포구청 성산
320 321 2 성산 수색
321 322 2 수색 증산
322 323 2 증산 새절
323 324 2 새절 응암
324 325 2 응암 역촌
325 326 2 역촌 불광
326 327 2 불광 독바위
327 328 2 독바위 연신내
328 329 2 연신내 구산
329 324 2 구산 응암
330 331 2 장암 도봉산
331 332 2 도봉산 수락산
332 333 2 수락산 마들
333 334 2 마들 노원
334 335 2 노원 중계
335 336 2 중계 하계
336 337 2 하계 공릉
337 338 2 공릉 태릉입구
338 339 2 태릉입구 먹골
339 340 2 먹골 중화
340 341 2 중화 상봉
341 342 2 상봉 면목
342 343 2 면목 사가정
343 344 2 사가정 용마산
344 345 2 용마산 중곡
345 346 2 중곡 군자
346 347 2 군자 어린이대공원
347 348 2 어린이대공원 건대입구
348 349 2 건대입구 뚝섬유원지
349 350 2 뚝섬유원지 청담
350 351 2 청담 강남구청
351 352 2 강남구청 학동
352 353 2 학동 논현
353 354 2 논현 반포
354 355 2 반포 고속터미널
355 356 2 고속터미널 내방
356 357 2 내방 이수
357 358 2 이수 남성
358 359 2 남성 숭실대입구
359 360 2 숭실대입구 상도
360 361 2 상도 장승배기
361 362 2 장승배기 신대방삼거리
362 363 2 신대방삼거리 보라매
363 364 2 보라매 신풍
364 365 2 신풍 대림
365 366 2 대림 남구로
366 367 2 남구로 가산
367 368 2 가산 철산
368 369 2 철산 광명사거리
369 370 2 광명사거리 천왕
370 371 2 천왕 온수
372 373 2 암사 천호
373 374 2 천호 강동구청
374 375 2 강동구청 몽촌토성
375 376 2 몽촌토성 잠실
376 377 2 잠실 석촌
377 378 2 석촌 송파
378 379 2 송파 가락시장
379 380 2 가락시장 문정
380 381 2 문정 장지
381 382 2 장지 복정
382 383 2 복정 산성
383 384 2 산성 남한산성입구
384 385 2 남한산성입구 단대오거리
385 386 2 단대오거리 신흥
386 387 2 신흥 수진
387 388 2 수진 모란
389 390 3 신설동 용두
390 391 3 용두 신답
391 392 3 신답 용답
392 393 3 용답 성수
394 395 2 까치산 신정네거리
395 396 2 신정네거리 양천구청
396 397 2 양천구청 도림천
397 398 2 도림천 신도림
398 41 5 신도림 신도림
41 127 5 신도림 신도림
398 127 3 신도림 신도림
393 107 3 성수 성수
389 27 5 신설동 신설동
394 248 5 까치산 까치산
63 367 5 가산 가산
106 348 5 건대입구 건대입구
144 355 5 고속터미널 고속터미널
313 260 5 공덕 공덕
95 143 5 교대 교대
275 346 5 군자 군자
70 187 5 금정 금정
287 287 5 길동 길동
219 334 5 노원 노원
128 365 5 대림 대림
14 331 5 도봉산 도봉산
29 209 5 동대문 동대문
113 208 5 동대문운동장 동대문운동장
208 267 5 동대문운동장 동대문운동장
113 267 5 동대문운동장 동대문운동장
28 303 5 동묘앞 동묘앞
126 254 5 문래 문래
161 326 5 불광 불광
92 197 5 사당 사당
202 311 5 삼각지 삼각지
34 204 5 서울역 서울역
21 295 5 석계 석계
33 117 5 시청 시청
39 256 5 신길 신길
112 304 5 신당 신당
150 306 5 약수 약수
162 328 5 연신내 연신내
125 253 5 영등포구청 영등포구청
148 227 5 옥수 옥수
46 371 5 온수 온수
110 229 5 왕십리 왕십리
229 271 5 왕십리 왕십리
271 110 5 왕십리 왕십리
36 223 5 용산 용산
115 153 5 을지로3가 을지로3가
114 266 5 을지로4가 을지로4가
198 357 5 이수 이수
200 224 5 이촌 이촌
102 376 5 잠실 잠실
31 154 5 종로3가 종로3가
154 265 5 종로3가 종로3가
265 31 5 종로3가 종로3가
17 218 5 창동 창동
278 373 5 천호 천호
268 305 5 청구 청구
152 207 5 충무로 충무로
118 262 5 충정로 충정로
294 338 5 태릉입구 태릉입구
123 317 5 합정 합정
24 231 5 회기 회기