/*
 * COMPILE: gcc -o filesystem filesystem.c -lm
 * Simulation of an inode file system. Supports multiple directories and manipulation
 * of files. Operations include file reading, writing, appending, deleting,
 * renaming, and copying and directory listing, creating, and a current working directory.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
#include <math.h>
#include <stdarg.h>


#define STR(s) ((s) ? (s) : "")
#define STR2(s1, s2) ((s1) ? (s2) : "")

#define ARG_DELIMS " \n"
#define BLOCK_SIZE 32
#define DIR_ENTRY_SIZE 8
#define DATA_PTR_COUNT 27
#define MAX_DIR_ENTRIES (BLOCK_SIZE / DIR_ENTRY_SIZE * DATA_PTR_COUNT)
#define DISKSIZE 32*256

typedef unsigned char byte;

typedef struct _inode
{
  int _block;
  unsigned int size;
  char type;
  byte data_blocks[DATA_PTR_COUNT];
} inode;

typedef struct _dir_entry
{
  char name[7];
  int inode_block;
} dir_entry;

typedef struct _dir
{
  int _block;
  unsigned int file_count;
  dir_entry files[MAX_DIR_ENTRIES];
} dir;

// Begin debugging code
//#define DEBUG 1

void debug(const char *fmt, ...)
{
#if DEBUG
  va_list ap;
  
  va_start(ap, fmt);
  vprintf(fmt, ap);
  va_end(ap);
#endif
}

void print_inode(inode inode)
{
  int i;
  
  debug("inode\n\t_block: %d\n\tsize: %u\ntype: %c\n", inode._block, inode.size, inode.type);
  for (i = 0; i < DATA_PTR_COUNT; ++i)
    debug("\tdata_blocks[%d]: %d\n", i, inode.data_blocks[i]);
}

// End debugging code

void initialize_new_disk();
void initialize_old_disk();

void cmd_read(char *file_name);
void cmd_write(char *cmd);
void cmd_append(char *cmd);
void cmd_copy(char *cmd);
void cmd_rename(char *cmd);
void cmd_delete(char *cmd);
void cmd_mkdir(char *cmd);
void cmd_chdir(char *cmd);

void list_files(dir d);
dir_entry *find_file(dir *d, const char *file_name);
int delete_file(dir *d, const char *file_name);
int delete_file3(dir *d, const char *file_name, int just_del_entry);

dir read_dir_at_block(int block);
dir read_dir(char *path);
void write_dir(dir d);
int make_dir(char *path);
int dir_exists(dir d);
int add_dir_entry(dir *d, const char *file_name, int inode_block);
int delete_dir_entry(dir *d, const char *file_name);
char *read_file(const char *file_name);
void write_file(const char *file_name, const char *data);
int write_file_at_block(int block, const char *data);

inode read_inode_at_path(const char *path);
inode read_inode(int block);
void write_inode(inode inode);
int inode_exists(inode inode);

int alloc_block();
void free_block(int block);
int free_block_count();

void split_path(char *path, char **dir_path, char **file_name);
char **tokenize_str(char *str, char *delims, unsigned int max_tokens);
char *trim(char *s, const char *charset);
char *str_rev_cfind(char *s, size_t index, const char *charset);
char *read_line(FILE *in);

void setbit(int num, int val);
int getbit(int num);
int initialize();
void shutdown();

unsigned char disk[256][32];
int g_free_block_count;
int g_cwd_block;

int main(int argc, char *argv[])
{
  int r;
  FILE *fp = stdin;
  
  r = initialize();
  if (r < 0)
  {
    fprintf(stderr,"error opening filesystem.txt\n");
    return 1;
  }
  else if (r == 0)
    initialize_new_disk();
  else
    initialize_old_disk();
  
  if (argc == 2)
  {
    fp = fopen(argv[1], "r");
    if (!fp)
    {
      perror("couldn't open script file");
      return 1;
    }
  }
  
  g_cwd_block = 1;
  while (1)
  {
    char *cmd, **argv;
    
    cmd = read_line(fp);
    if (!cmd)
      continue;
    argv = tokenize_str(cmd, ARG_DELIMS, 2);
    
    if (argv != NULL)
    {
      if (argv[0] != NULL)
      {
        if (!strcmp("read", argv[0]))
          cmd_read(argv[1]);
        else if (!strcmp("write", argv[0]))
          cmd_write(argv[1]);
        else if (!strcmp("append", argv[0]))
          cmd_append(argv[1]);
        else if (!strcmp("copy", argv[0]))
          cmd_copy(argv[1]);
        else if (!strcmp("rename", argv[0]))
          cmd_rename(argv[1]);
        else if (!strcmp("delete", argv[0]))
          cmd_delete(argv[1]);
        else if (!strcmp("list", argv[0]))
          list_files(read_dir_at_block(g_cwd_block));
        else if (!strcmp("mkdir", argv[0]))
          cmd_mkdir(argv[1]);
        else if (!strcmp("chdir", argv[0]))
          cmd_chdir(argv[1]);
        else if (!strcmp("quit", argv[0]))
        {
          shutdown();
          return 0;
        }
        else
        {
          fprintf(stderr, "unknown command '%s'\n", argv[0]);
        }
      }
      free(argv);
    }
  }
  return 0;
}

// Initialize the program for a new disk. The free block bitmap is initialized
// in block 0 and the rest of the disk is initialized to 0. Block 1 is
// reserved for the root directory inode. This function updates the free
// block counter. It's set to the number of blocks on the disk minus the 2.
// reserved blocks. It also iniializes the root directory in block 1.
void initialize_new_disk()
{
  // Initialize the root directory in block 1.
  // 2 blocks are reserved
  inode inode;
  dir d;
  
  g_free_block_count = DISKSIZE / BLOCK_SIZE - 2;
  inode = read_inode(1);
  inode.type = 'D';
  write_inode(inode);
  d = read_dir_at_block(inode._block);
  add_dir_entry(&d, "..", inode._block);
}

// Set a global to the number of free blocks.
void initialize_old_disk()
{
  int i, block_count;
  
  g_free_block_count = 0;
  block_count = DISKSIZE / BLOCK_SIZE;
  for (i = 0; i < block_count; ++i)
  {
    if (getbit(i) == 0)
    {
      ++g_free_block_count;
    }
  }
}

// Reads *file_name* and prints its contents to stdout.
void cmd_read(char *file_name)
{
  if (file_name)
  {
    char *data = read_file(file_name);
    
    if (data)
    {
      printf("%s\n", data);
      free(data);
    }
    else
      fprintf(stderr, "no such file '%s'\n", file_name);
  }
  else
    fprintf(stderr, "usage: read filename\n");
}

// Splits *cmd* into *file_name* and *data*.
// Clears *file_name*, creating it if it doesn't exist. Writes *data* to it.
void cmd_write(char *cmd)
{
  int success = 0;
  
  if (cmd)
  {
    char **args = tokenize_str(cmd, ARG_DELIMS, 2);
    
    if (args)
    {
      if (args[0] && args[1])
      {
        write_file(args[0], args[1]);
        success = 1;
      }
      free(args);
    }
  }
  
  if (!success)
    fprintf(stderr, "usage: write filename string\n");
}

// Splits *cmd* into *file_name* and *data*.
// Appends *data* to *file_name*. If *file_name* doesn't exist, it prints an error.
void cmd_append(char *cmd)
{
  int success = 0;
  
  if (cmd)
  {
    char **args = tokenize_str(cmd, ARG_DELIMS, 2);
    
    if (args)
    {
      if (args[0] && args[1] && !args[2])
      {
        char *old_data, *buffer;
        unsigned int max_size, size;
        
        success = 1;
        max_size = BLOCK_SIZE * DATA_PTR_COUNT;
        old_data = read_file(args[0]);
        if (old_data == NULL)
        {
          fprintf(stderr, "no such file: '%s'\n", args[0]);
          return;
        }
        if (strlen(old_data) > max_size || strlen(args[1]) > max_size
          || strlen(old_data) + strlen(args[1]) > max_size)
        {
          fprintf(stderr, "unable to append file: file is too big\n");
          free(old_data);
          return;
        }
        size = strlen(old_data) + strlen(args[1]);
        buffer = malloc(sizeof(char) * (size + 1));
        if (buffer == NULL)
        {
          perror("unable to append to file");
          free(old_data);
          return;
        }
        
        strcpy(buffer, old_data);
        strcat(buffer, args[1]);
        write_file(args[0], buffer);
        free(buffer);
        free(old_data);
      }
      free(args);
    }
  }
  
  if (!success)
    fprintf(stderr, "usage: append filename string\n");
}

// Splits *cmd* into *old_file_name* and *new_file_name*.
// Copies the contents of *old_file_name* to *new_file_name*, creating it if
// it doesn't exist. If *old_file_name* doesn't exist, it prints an error.
void cmd_copy(char *cmd)
{
  int success = 0;
  
  if (cmd)
  {
    char **args = tokenize_str(cmd, ARG_DELIMS, 0);
    
    if (args)
    {
      if (args[0] && args[1] && !args[2])
      {
        char *data = read_file(args[0]);
      
        success = 1;
        if (!data)
        {
          fprintf(stderr, "no such file: '%s'\n", args[0]);
          return;
        }
      
        write_file(args[1], data);
        free(data);
      }
      free(args);
    }
  }
  
  if (!success)
    fprintf(stderr, "usage: copy oldfilename newfilename\n");
}

// Splits *cmd* into *old_file_name* and *new_file_name*.
// Renames *old_file_name* to *new_file_name*. If *new_file_name* already
// exists and it's not a directory, it deletes this file.
void cmd_rename(char *cmd)
{
  int success = 0;
  
  if (cmd)
  {
    char **args = tokenize_str(cmd, ARG_DELIMS, 0);
    
    if (args)
    {
      if (args[0] && args[1] && !args[2])
      {
        char *from_path, *from_fn, *to_path, *to_fn;
        dir from_dir, to_dir;
        dir_entry *from_dirent, *to_dirent;
        
        split_path(args[0], &from_path, &from_fn);
        from_dir = (from_path) ? read_dir(from_path) : read_dir_at_block(g_cwd_block);
        split_path(args[1], &to_path, &to_fn);
        to_dir = (to_path) ? read_dir(to_path) : read_dir_at_block(g_cwd_block);
        
        if (!dir_exists(from_dir))
        {
          fprintf(stderr, "unable to rename file: no such directory '%s'\n", from_path);
          return;
        }
        if (!dir_exists(to_dir))
        {
          fprintf(stderr, "unable to rename file: no such directory '%s'\n", to_path);
          return;
        }
        
        // If they are the same path, do nothing.
        if (from_dir._block == to_dir._block && !strcmp(from_fn, to_fn))
          return;
        
        success = 1;
        if (strlen(to_fn) > 6)
        {
          fprintf(stderr, "unable to rename file: file name too long\n");
          return;
        }
        
        from_dirent = find_file(&from_dir, from_fn);
        if (!from_dirent)
        {
          fprintf(stderr, "unable to rename file: no such file '%s%s%s'\n", STR(from_path), STR2(from_path, "/"), from_fn);
          return;
        }
        
        to_dirent = find_file(&to_dir, to_fn);
        if (to_dirent)
        {
          inode inode = read_inode(to_dirent->inode_block);
          
          if (inode.type == 'D')
          {
            fprintf(stderr, "unable to rename file: '%s%s%s' is a directory\n", STR(to_path), STR2(to_path, "/"), to_fn);
            return;
          }
          delete_file(&to_dir, to_fn);
        }
        
        if (from_dir._block == to_dir._block)
        {
          // From and to are located in the same directory. Just change the
          // name of the entry.
          from_dirent = find_file(&to_dir, from_fn);
          strcpy(from_dirent->name, to_fn);
          write_dir(to_dir);
        }
        else
        {
          // From and to are in different directories. Add an entry to the
          // to directory to refer to the inode. Afterwards, remove the
          // original directory entry.
          if (add_dir_entry(&to_dir, to_fn, from_dirent->inode_block))
          {
            delete_dir_entry(&from_dir, from_fn);
          }
        }
      }
      free(args);
    }
  }
  
  if (!success)
    fprintf(stderr, "usage: rename oldfilename newfilename\n");
}

// Deletes the file named *cmd* from the root directory.
void cmd_delete(char *path)
{   
  if (path)
  {
    dir d;
    char *dir_path, *file_name;
  
    split_path(path, &dir_path, &file_name);
    d = (dir_path) ? read_dir(dir_path) : read_dir_at_block(g_cwd_block);
    
    if (!dir_exists(d))
      fprintf(stderr, "no such directory: '%s'\n", dir_path);
    else if (!delete_file(&d, file_name))
      fprintf(stderr, "no such file: '%s%s%s'\n", STR(dir_path), STR2(dir_path, "/"), file_name);
  }
  else
    fprintf(stderr, "usage: delete filename\n");
}

// Create the directory *cmd*.
void cmd_mkdir(char *cmd)
{
  make_dir(cmd);
}

// Change the current working directory to the path in *cmd*.
void cmd_chdir(char *cmd)
{
  if (cmd)
  {
    inode inode;
    
    inode = read_inode_at_path(cmd);
    if (!inode_exists(inode))
      fprintf(stderr, "no such directory '%s'\n", cmd);
    else if (inode.type != 'D')
      fprintf(stderr, "not a directory '%s'\n", cmd);
    else
      g_cwd_block = inode._block;
      
  }
  else
    fprintf(stderr, "usage: chdir dirname\n");
}

// Prints the name and size in bytes of each file in the directory *d*.
void list_files(dir d)
{
  int i;
  
  for (i = 0; i < d.file_count; ++i)
  {
    dir_entry file;
    inode inode;
    
    file = d.files[i];
    inode = read_inode(file.inode_block);
    debug("block: %d\n", file.inode_block);
    printf("%-9s", file.name);
    if (inode.type == 'R')
      printf("%d\n", inode.size);
    else
      printf("D\n");
    print_inode(inode);
  }
}

// Returns a pointer to the directory entry for *file_name* in *d*. If
// *file_name* is not found, NULL is returned.
dir_entry *find_file(dir *d, const char *file_name)
{
  int i;
  
  for (i = 0; i < d->file_count; ++i)
  {
    if (!strcmp(d->files[i].name, file_name))
    {
      return &(d->files[i]);
    }
  }
  
  return NULL;
}

// Removes the file specified by *file_name* from directory *d* and erases
// its data from the disk.
int delete_file(dir *d, const char *file_name)
{
  return delete_file3(d, file_name, 0);
}

// Deletes *file_name* from *d*. If *just_del_entry* is 0, also deletes the
// file's data from the disk. If *file_name* exists and is deleted, returns 1.
// Otherwise, returns 0. Directories can't be deleted.
int delete_file3(dir *d, const char *file_name, int just_del_entry)
{
  int i;
  
  for (i = 0; i < d->file_count; ++i)
  {
    if (!strcmp(d->files[i].name, file_name))
    {
      inode inode = read_inode(d->files[i].inode_block);
      if (inode.type == 'D')
        break;
      
      if (!just_del_entry)
      {
        write_file_at_block(d->files[i].inode_block, "");
        free_block(d->files[i].inode_block);
      }
      
      for (++i; i < d->file_count; ++i)
      {
        strcpy(d->files[i-1].name, d->files[i].name);
        d->files[i-1].inode_block = d->files[i].inode_block;
      }
      --d->file_count;
      write_dir(*d);
      return 1;
    }
  }
  return 0;
}

// Reads the directory at *path* from *disk* into a dir structure and returns it.
dir read_dir(char *path)
{
  inode inode;
  dir d;
  
  d._block = -1;
  inode = read_inode_at_path(path);
  if (inode_exists(inode))
    return read_dir_at_block(inode._block);
  else
    return d;
}

// Reads the directory at *block* from *disk* into a dir structure and returns it.
dir read_dir_at_block(int block)
{
  dir d;
  inode inode;
  unsigned int size, data_ptr_index, dir_entries_per_block, i;
  
  inode = read_inode(block);
  
  if (inode.type == 'D')
  {
    size = inode.size;
  
    d._block = block;
    d.file_count = inode.size / DIR_ENTRY_SIZE;
  
    dir_entries_per_block = BLOCK_SIZE / DIR_ENTRY_SIZE;
    for (data_ptr_index = 0, i = 0; size > 0; ++data_ptr_index)
    {
      unsigned int dir_entry_index;
    
      for (dir_entry_index = 0; dir_entry_index < dir_entries_per_block && size > 0;
        ++dir_entry_index, size -= DIR_ENTRY_SIZE, ++i)
      {
        unsigned char *raw_dir_entry;
      
        // disk + block offset + directory entry offset
        raw_dir_entry = (unsigned char *)(disk[inode.data_blocks[data_ptr_index]] + DIR_ENTRY_SIZE * dir_entry_index);
        memcpy(d.files[i].name, raw_dir_entry, 7);
        d.files[i].inode_block = *(raw_dir_entry + 7);
      }
    }
  }
  else
    d._block = -1;
  
  return d;
}

// Serializes the dir structure *d* and writes it to *disk*.
void write_dir(dir d)
{
  inode inode;
  unsigned int size, block_count, new_block_count;
  unsigned int block_index, entry_offset, i;
  
  inode = read_inode(d._block);
  size = d.file_count * DIR_ENTRY_SIZE;
  block_count = ceilf((float)inode.size / BLOCK_SIZE);
  new_block_count = ceilf((float)size / BLOCK_SIZE);
  
  if (new_block_count > block_count)
  {
    if (new_block_count - block_count > free_block_count())
    {
      fprintf(stderr, "couldn't save directory: the disk is full\n");
      return;
    }
    while (block_count < new_block_count)
      inode.data_blocks[block_count++] = alloc_block();
  }
  else
  {
    while (block_count > new_block_count)
      free_block(inode.data_blocks[--block_count]);
  }
  
  inode.size = size;
  write_inode(inode);
  for (block_index = 0, i = 0; i < d.file_count; ++block_index)
  {
    for (entry_offset = 0; entry_offset < BLOCK_SIZE && i < d.file_count; entry_offset += DIR_ENTRY_SIZE, ++i)
    {
      int block = inode.data_blocks[block_index];
      strncpy((char *)disk[block] + entry_offset, d.files[i].name, 7);
      disk[block][entry_offset + 6] = '\0';
      disk[block][entry_offset + 7] = d.files[i].inode_block;
    }
  }
}

// Create the directory at *path*. All of the intermediate directories must
// exist. *path* cannot exist before this function is called. Returns 1 if
// the directory is successfully created and 0 otherwise.
int make_dir(char *path)
{
  char *dir_path, *file_name;
  dir d, new_dir;
  dir_entry *ent;
  inode inode;
  
  split_path(path, &dir_path, &file_name);
  if (strlen(file_name) > 6)
  {
    fprintf(stderr, "unable to make directory: directory name too long\n");
    return 0;
  }
  
  d = (dir_path) ? read_dir(dir_path) : read_dir_at_block(g_cwd_block);
  if (!dir_exists(d))
  {
    fprintf(stderr, "unable to make directory: no such directory '%s'\n", dir_path);
    return 0;
  }
  
  ent = find_file(&d, file_name);
  if (ent)
  {
    fprintf(stderr, "unable to make directory: path already exists '%s%s%s'\n", STR(dir_path), STR2(dir_path, "/"), file_name);
    return 0;
  }
  
  inode._block = alloc_block();
  if (inode._block == 0)
  {
    fprintf(stderr, "unable to make directory: disk is full '%s'\n", dir_path);
    return 0;
  }
  inode.size = 0;
  inode.type = 'D';
  write_inode(inode);
  new_dir = read_dir_at_block(inode._block);
  
  if (!add_dir_entry(&d, file_name, inode._block))
  {
    free_block(inode._block);
    return 0;
  }
  else if (!add_dir_entry(&new_dir, "..", d._block))
  {
    delete_dir_entry(&d, file_name);
    free_block(inode._block);
    return 0;
  }
  
  return 1;
}

// Returns 1 if the structure *d* actually refers to a directory.
// Returns 0 otherwise.
int dir_exists(dir d)
{
  return d._block >= 0;
}

// Adds *file_name* with inode *inode_block* to directory *d* and writes
// *d* to disk. Returns 1 on success and 0 on error.
int add_dir_entry(dir *d, const char *file_name, int inode_block)
{
  dir_entry *file;
  
  if (d->file_count == MAX_DIR_ENTRIES)
  {
    fprintf(stderr, "couldn't add entry: directory is full\n");
    return 0;
  }
  file = &(d->files[d->file_count]);
  strcpy(file->name, file_name);
  file->inode_block = inode_block;
  debug("**(add_dir_entry) block = %d\n", file->inode_block);
  d->file_count++;
  write_dir(*d);
  
  return 1;
}

// Deletes the entry for *file_name* from directory *d*.
int delete_dir_entry(dir *d, const char *file_name)
{
  return delete_file3(d, file_name, 1);
}

// Reads the data in *file_name* in *disk* and returns it. The caller is
// responsible for freeing this memory. If *file_name* doesn't exist, NULL
// is returned.
char *read_file(const char *file_name)
{
  inode inode = read_inode_at_path(file_name);
  
  if (inode_exists(inode) && inode.type == 'R')
  {
    char *buffer;
    int offset, remaining_size, block_index;
    
    buffer = malloc(sizeof(char) * (inode.size + 1));
    remaining_size = inode.size;
    offset = 0;
    for (block_index = 0; remaining_size > 0; ++block_index)
    {
      int read_len = (BLOCK_SIZE < remaining_size) ? BLOCK_SIZE : remaining_size;
      memcpy(buffer + offset, disk[inode.data_blocks[block_index]], read_len);
      offset += read_len;
      remaining_size -= read_len;
    }
    buffer[offset] = '\0';
  
    return buffer;
  }
  
  return NULL;
}

// Writes *data* to *file_name*, truncating it if it exists and creating
// it if it doesn't. This will not overwrite directories.
void write_file(const char *file_path, const char *data)
{
  dir_entry *file;
  char *dir_path, *file_name, *fp;
  dir d;
  
  fp = strdup(file_path);
  split_path(fp, &dir_path, &file_name);
  d = (dir_path) ? read_dir(dir_path) : read_dir_at_block(g_cwd_block);
  if (!dir_exists(d))
  {
    fprintf(stderr, "couldn't write file: no such directory '%s'\n", dir_path);
    free(fp);
    return;
  }
  
  if (strlen(file_name) > 6)
  {
    fprintf(stderr, "couldn't write file: file name is too long\n");
    free(fp);
    return;
  }
  
  file = find_file(&d, file_name);
  if (file)
    write_file_at_block(file->inode_block, data);
  else
  {
    inode inode;
    
    inode._block = alloc_block();
    if (!inode._block)
    {
      fprintf(stderr, "couldn't write file: disk is full\n");
      free(fp);
      return;
    }
    inode.size = 0;
    inode.type = 'R';
    memset(inode.data_blocks, 0, DATA_PTR_COUNT);
    write_inode(inode);
    if (!add_dir_entry(&d, file_name, inode._block))
    {
      free_block(inode._block);
    }
    else if (!write_file_at_block(inode._block, data))
    {
      delete_dir_entry(&d, file_name);
      free_block(inode._block);
    }
  }
  
  free(fp);
}

// Write *data* to the file whose inode is at *block*. It will truncate files
// that already exist but won't touch directories. Returns 1 on success and 0
// on error.
int write_file_at_block(int block, const char *data)
{
  inode inode;
  int data_size, block_count, new_block_count;
  int offset, block_index;
  
  data_size = strlen(data);
  if (data_size > BLOCK_SIZE * DATA_PTR_COUNT)
  {
    fprintf(stderr, "couldn't write file: file is too large\n");
    return 0;
  }
  
  block_count = 0;
  new_block_count = ceilf((float)data_size / BLOCK_SIZE);
  inode = read_inode(block);
  block_count = ceilf((float)inode.size / BLOCK_SIZE);
  
  if (inode.type != 'R')
  {
    fprintf(stderr, "can't write to a directory\n");
    return 0;
  }
  
  if (new_block_count - block_count > free_block_count())
  {
    fprintf(stderr, "couldn't write file: disk is full\n");
    return 0;
  }
  
  while (block_count < new_block_count)
    inode.data_blocks[block_count++] = alloc_block();
  while (block_count > new_block_count)
    free_block(inode.data_blocks[--block_count]);
  
  inode.size = data_size;
  write_inode(inode);
  
  offset = 0;
  for (block_index = 0; data_size > 0; ++block_index)
  {
    int len = (BLOCK_SIZE < data_size) ? BLOCK_SIZE : data_size;
    
    memcpy(disk[inode.data_blocks[block_index]], data + offset, len);
    data_size -= len;
    offset += len;
  }
  
  return 1;
}

// Finds and returns the inode represented by *path*.
inode read_inode_at_path(const char *path)
{
  inode inode;
  char *path_tmp, **paths;
  dir current_dir;
  
  if (path[0] == '/' || path[0] == '\0')
  {
    current_dir = read_dir_at_block(1); // start at root
    if (path[0] == '/') ++path;
  }
  else
    current_dir = read_dir_at_block(g_cwd_block);  // start at current
  
  inode._block = -1;
  path_tmp = strdup(path);
  paths = tokenize_str(path_tmp, "/", 0);
  if (paths)
  {
    char *current_fn;
    int i;
    
    if (!paths[0])
      inode = read_inode(current_dir._block);
    else
    {
      for (i = 0, current_fn = paths[0]; current_fn; current_fn = paths[++i])
      {
        dir_entry *dir_ent;
      
        dir_ent = find_file(&current_dir, current_fn);
        if (dir_ent)
        {
          if (!paths[i+1])
            inode = read_inode(dir_ent->inode_block);
          else
          {
            current_dir = read_dir_at_block(dir_ent->inode_block);
            if (!dir_exists(current_dir)) break;
          }
        }
        else
          break;
      }
    }
  }
  
  free(path_tmp);
  return inode;
}

// Reads the data in *block* into an inode structure and returns it.
inode read_inode(int block)
{
  inode inode;
  int offset, i;
  
  inode._block = block;
  inode.size = *((unsigned int *)disk[block]);
  inode.type = disk[block][sizeof(unsigned int)];
  for (offset = sizeof(unsigned int) + sizeof(char), i = 0; offset < BLOCK_SIZE; ++offset, ++i)
    inode.data_blocks[i] = disk[block][offset];
  
  return inode;
}

// Saves *inode* to *disk*.
void write_inode(inode inode)
{
  int i, offset, block;
  
  print_inode(inode);
  
  block = inode._block;
  debug("(write_inode)block = %d\n", block);
  memcpy(disk[block], &(inode.size), 4);
  disk[block][4] = inode.type;
  for (i = 0, offset = sizeof(unsigned int) + sizeof(char); i < DATA_PTR_COUNT; ++i, ++offset)
    disk[block][offset] = inode.data_blocks[i];
}

int inode_exists(inode inode)
{
  return inode._block >= 0;
}

// Returns the index of a new block and marks it as in use. If no blocks are
// available, returns 0.
int alloc_block()
{
  int block, block_count;
  
  block_count = DISKSIZE / BLOCK_SIZE;
  // First 2 blocks are reserved.
  for (block = 2; block < block_count; ++block)
  {
    if (getbit(block) == 0)
    {
      setbit(block, 1);
      --g_free_block_count;
      debug("using block %d\n", block);
      int i;
      for (i = 0; i < 256; ++i)
        debug("%d", getbit(i) != 0);
      debug("\n");
      return block;
    }
  }
  
  return 0;
}

// Frees *block*.
void free_block(int block)
{
  if (getbit(block) == 0)
    abort();
    //fprintf(stderr, "Attempt to free already free block\n");
  else
    ++g_free_block_count;
  debug("freeing block %d\n", block);
  setbit(block, 0);
}

// Returns the number of free blocks in *disk*.
int free_block_count()
{
  return g_free_block_count;
}

void split_path(char *path, char **dir_path, char **file_name)
{
  char *last_slash;
  
  last_slash = strrchr(path, '/');
  if (!last_slash)
  {
    *dir_path = NULL;
    *file_name = path;
  }
  else
  {
    *dir_path = path;
    *last_slash = '\0';
    *file_name = last_slash + 1;
  }
}

// Breaks *str* into tokens separated by *delims*. On success, returns a
// null-terminated list of tokens. Otherwise, returns NULL. The caller is
// responsible for freeing this returned list. The function destructively
// modifies *str*.
char **tokenize_str(char *str, char *delims, unsigned int max_tokens)
{
  char *str_start = str;
  int span, token_count, i;
  char **toks;
    
  // The last iteration doesn't result in a new token so token_count starts
  // at -1
  for (token_count = -1, span = 1; span != 0; token_count++)
  {
    str += strspn(str, delims);     // Skip over leading delims.
    span = strcspn(str, delims);
    str += span;
  }
  
  if (max_tokens > 0)
    token_count = (token_count < max_tokens) ? token_count : max_tokens;
    
  str = str_start;
  // token_count + 1 to include null-terminating element
  toks = (char **)malloc(sizeof(char *) * (token_count + 1));
  if (toks == NULL)
  {
    perror("Not enough memory to tokenize string");
    return NULL;
  }
  for (i = 0; i < token_count && str != NULL;)
  {
    char *curr_tok;
    
    if (i + 1 == token_count)
      curr_tok = trim(str, delims);
    else
    {
      str += strspn(str, delims);     // Skip over leading delims.
      curr_tok = strsep(&str, delims);
    }
    toks[i++] = curr_tok;
  }
  toks[token_count] = NULL;
    
  return toks;
}

char *trim(char *s, const char *charset)
{
  char *end;
  
  // Skip leading delims.
  s += strspn(s, charset);
  // Remove following delims.
  end = str_rev_cfind(s, strlen(s) - 1, charset);
  if (end != NULL)
    *(end + 1 ) = '\0';
  
  return s;
}

// reverse complement search: Starting at *index* of *s*, searches backwards for
// the first character that isn't found in *charset* and returns a pointer to
// it. If no such charater is found, returns NULL.
char *str_rev_cfind(char *s, size_t index, const char *charset)
{
  char *curr;
  
  for (curr = s + index; curr >= s; --curr)
  {
    if (strchr(charset, *curr) == NULL)
      return curr;
  }
    
  return NULL;
}

// Reads a line from the standard input. Returns NULL on error/EOF and a pointer
// to the line on success. This pointer is used each time read_line is called so
// the pointer will be rendered useless on the next call to read_line. It is safe
// to modify the contents of the returned buffer.
char *read_line(FILE *in)
{
    static char *input_buffer = NULL;
    static size_t input_buffer_len = 0;
    char *get_line;
    size_t get_line_len;
    
    get_line = fgetln(in, &get_line_len);
    if (get_line == NULL)
    {
        if (feof(stdin))
        {
            printf("\n");
            clearerr(stdin);
        }
        else if (ferror(stdin))
            perror("Unable to get input from shell");
        else
            fprintf(stderr, "An unknown error occurred while getting input from the user\n");
        return NULL;
    }
    
    // input_buffer needs to be resized.
    // input_buffer_len needs to be one bigger than get_line_len to account
    // for the null terminator.
    if (input_buffer_len == 0 || input_buffer_len - 1 < get_line_len)
    {
        char *ret;
        
        if (get_line_len + 1 == 0)
        {
            fprintf(stderr, "Command is too long\n");
            return NULL;
        }
        
        if (input_buffer != NULL)
            ret = realloc(input_buffer, get_line_len + 1);
        else
            ret = malloc(get_line_len + 1);

        if (ret == NULL)
        {
            perror("Unable to acquire memory for input buffer");
            return NULL;
        }
        input_buffer = ret;
        input_buffer_len = get_line_len + 1;
    }
    
    strncpy(input_buffer, get_line, get_line_len);
    input_buffer[get_line_len] = '\0';
    
    return input_buffer;
}

/********* setbit *****************
 ** sets bit[num] to val in disk **
 ** 0 <= num < 256               **
 ** val is either 0 or 1         **
 **********************************/
void setbit(int num, int val)
{
  int charnum = num/8;
  int bitnum = num - charnum*8;
  unsigned char c = disk[0][charnum];
  unsigned char masks[]={1,2,4,8,16,32,64,128};
  
  if (num < 0 || num > 255) {
    fprintf(stderr, "Error in setbit, bad block number\n");
    return;
  }
  if (val == 0)
    c = c & ~masks[bitnum];
  else if (val == 1)
    c = c | masks[bitnum];
  else {
      fprintf(stderr,"Error in setbitmap, bad value\n");
      return;
  }
  disk[0][charnum] = c;
}

/****** getbit ***************************
 ** returns the value of bit number num **
 ** 0 <= num < 256, return value is     **
 ** either 0 or 1                       **
 *****************************************/
int getbit(int num)
{
  int charnum = num/8;
  int bitnum = num - charnum*8;
  unsigned char c = disk[0][charnum];
  unsigned char masks[]={1,2,4,8,16,32,64,128};
  unsigned char d;

  if (num < 0 || num > 255) {
    fprintf(stderr,"Error in getbitmap, bad block number\n");
    return -1;
  }
  d = c & masks[bitnum];
  return (int)d;
}   

/******** initialize **************************
 **  tries to open the file filesystem.txt   **
 **  if successful, it copies the filesystem **
 **  into disk. Otherwise it initializes disk**
 **  It returns 0 if  filesystem.txt did     **
 **  not exist, 1 if it existed and was read **
 **  and -1 if an error occurred             **
 **********************************************/
int initialize()
{
  int fd, r, bytesread, target;
  char buffer[DISKSIZE+1];

  memset(disk,0,DISKSIZE+1);  /* set the entire disk to zeros */
  fd = open("filesystem.txt",O_RDONLY);
  if (fd < 0) {
    setbit(0,1);  // turn on the first bit because the 
                  // freelist is in the first block
    setbit(1,1); // turn on the second bit because this
                 // will be the inode of the root directory
    return 0;
  }
  else { 
    target = DISKSIZE;
    bytesread = 0;
    while (bytesread < target) {
      r = read(fd,buffer+bytesread,target-bytesread);        
      if (r < 0) {
         perror("error reading filesystem.txt: ");
         close(fd);
         return -1;
      }
      if (r == 0) {
         fprintf(stderr,"Error reading filesystem.txt\n");
         close(fd);
         return -1;
      }
      bytesread += r;
    }
    memcpy(disk,buffer,DISKSIZE);
    close(fd);
    return 1;
  }
}

/***** shutdown **********************
 ** copies the contents of disk to  **
 ** the file filesystem.txt         **
 *************************************/

void shutdown()
{
  int fd, r, byteswritten, target;

  fd = open("filesystem.txt",O_WRONLY | O_TRUNC | O_CREAT, S_IRUSR | S_IWUSR);
  if (fd < 0) {
    perror("Error opening filesystem.txt:");
    exit(0);
  }
  target = DISKSIZE;
  byteswritten = 0;
  while (byteswritten < target) {
      r = write(fd,disk+byteswritten,target-byteswritten);
      if (r < 0) {
 	perror("Error writing to the file: ");
        exit(0);
      }
      byteswritten += r;
  }
  close(fd);
}