컴공 일기239

운영체제들이 사용하고 있는 파일시스템의 구조를 흉내내본 코드입니다.

C++의 표준 라이브러리로 구현하기가 쉬운 관계로 자료구조를 N-항트리로 채택하긴 했습니다만 실제 다수의 운영체제에서는

B-트리를 채택하고 있지요. 개인적으로, 많은 자료구조 전공서적들이 B 트리를 다루어주었으면 하는데 좀 아쉽습니다. 물론 입문자 입장에서 꽤 어려운 구조이긴 합니다만.. 그래도, 당장 데이터베이스나 운영체제를 배울 때 무조건 나올 수밖에 없는 중요한 자료구존데…

그런 관계로, 연휴기간 동안에는 B트리 기반으로 자료구조를 바꾸어서, 이 코드를 약간 수정해볼까 합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

//N항 트리

struct n_ary_node

{

  string name;

  bool is_dir;

  vector<n_ary_node*> children;

};

struct file_system

{

    using node = n_ary_node;

    using node_ptr = node*;

private:

    node_ptr root;

    node_ptr cwd;

public:

    file_system()

    {

        root = new node{"/", true, {}};

        cwd = root; //처음에는 루트를 현재 디렉터리로 설정한다.

    }

    node_ptr find(const string& path)

    {

        if(path[0] == '/')

        {

            return find_impl(root, path.substr(1));        

        }

        else

        {

            return find_impl(cwd, path);

        }

    }

private:

    node_ptr find_impl(node_ptr directory, const string& path)

    {

        if(path.empty())

           return directory;

        auto sep = path.find('/');

        string current_path = sep == string::npos ? path : path.substr(0, sep);

        string rest_path = sep == string::npos ? "" : path.substr(sep+1);

        auto found = find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)

        {

            return child->name == current_path; 

        });

        //현재 디렉터리 내부가 current_path를 포함한다면 즉, path의 첫 번째 디렉터리를 찾았다면 

        if(found != directory->children.end())

        {

            //해당 경로로 접속한 후, 계속 탐색한다. 

            return find_impl(*found, rest_path);

        }

        //디렉터리나 파일을 찾지 못한 경우 NULL 반환

        return NULL;

    }

public:

    bool add(const string& path, bool is_dir)

    {

        if(path[0] == '/')

        {

            return add_impl(root, path.substr(1), is_dir);

        }

        else

        {

            return add_impl(cwd, path, is_dir);

        }

    }

private:

   bool add_impl(node_ptr directory, const string& path, bool is_dir)

   {

      if(not directory->is_dir)

      {

         cout << directory->name << "은(는) 파일입니다. " << endl;

         return false;

      }

      auto sep = path.find('/');

      //path에 '/'가 없는 경우

      if(sep == string::npos)

      {

          auto found = find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)

          {

            return child->name == path;

          });

          if(found != directory->children.end())

          {

             cout << directory->name << "에 이미" << path << "이름의 파일/디렉터리가 있습니다." << endl;

             return false;

          } 

          directory->children.push_back(new node{path, is_dir, {}});

          return true;

       } 

       //path에 '/'가 있는 경우, 즉, 디렉터리 이름을 포함하는 경우

       string next_dir = path.substr(0, sep);

       auto found = find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)

       {

         return child->name == next_dir && child->is_dir;

       });

       if(found != directory->children.end())

       {

          return add_impl(*found, path.substr(sep+1), is_dir);

       }

       //디렉토리 파일을 찾을 수 없는 경우

       cout << directory->name << "에 " << next_dir << "이름의 디렉터리가 없습니다. " << endl;

       return false;

    }

public:

    bool change_dir(const string& path)

    {

        auto found = find(path);

        if(found && found->is_dir)

        {

            cwd = found;

            cout << "현재 디렉토리를 " << cwd->name << "로 이동합니다." << endl;

            return true;

        }

        cout << path << "경로를 찾을 수 없습니다. " << endl;

        return false; 

    }

public:

   void show_path(const string& path)

   {

     auto found = find(path);

     if(not found)

     {

        cout << path <<  "경로가 존재하지 않습니다" << endl;

        return;

     }

     if(found->is_dir)

     {

        for(auto child : found->children)

        {

            cout << (child->is_dir ? "d " : "- ") << child->name << endl;

        }

     }

     else{

        cout << "- " << found->name << endl;

     }

   }

};

int main()

{

    file_system fs;

    fs.add("usr", true);

    fs.add("etc", true);

    fs.add("var", true);

    fs.add("tmp_file", false);

    cout << "\"/\"의 파일/디렉터리 목록: " << endl;

    fs.show_path("/");

    cout << endl;

    fs.change_dir("usr");

    fs.add("gilbut", true);

    fs.add("gilbut/Downloads", true);

    fs.add("gilbut/Downloads/newFile.cpp", false);

    cout << "현재 디렉터리에서 usr의 파일 / 디렉터리 목록: " << endl;

    fs.show_path("/usr"); // 현재 디렉터리에는 usr 디렉터리가 없으므로 정상적으로 출력하지 못한다.

    cout << "\"/usr/gilbut/Downloads\"의 파일/디렉터리 목록" << endl;

    fs.show_path("/usr/gilbut/Downloads");