컴공 일기239
게시글 주소: https://dev.orbi.kr/00066243627
운영체제들이 사용하고 있는 파일시스템의 구조를 흉내내본 코드입니다.
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");
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
오랜만에 코트 입어야겟다 3 0
코트를 입을 일이 진짜 없거든요
-
붱모 베타 평도 좋고 해설도 거의 끝나가니 한시름 놨네 7 2
거의 3개월 걸린 프로젝트기도하니 진짜 진짜 많이 준비했기에 이젠 쉴 수 있다는 생각이 들기도하다
-
입술 잘못 뜯어서 아픔 0 0
ㅠ
-
왜 이렇게 2 1
2번 반응이 열광적이지? 이거 프사로 하면 약간 잘 안보이는데
-
내일 일찍일어나야하는데 3 0
10시에 일어나야해 지금자도 9시간도 못자네 곧 자야겠다
-
목금 연속으로 약속이군 0 0
내일 약속은 좀 기대가 되는구만
-
프사 농농한것도 해봤는데 14 0
이거 어떰? 지금 후보군 보여드림
-
근데 또 내가 완전 찐팬이고 그런건 아니라... 디오라마 이쪽은 또 내 취향 아님
-
친구가 말해준 썰ㅋㅋ 4 1
자취방 앞 건물에서 ㅅㅅ하는 커플 보고 경찰에 신고하고 잡혀가는거 실시간 관람했대ㅋㅋㅋ
-
귀여운 애니 캐릭터로 4 0
프사 바꾸고 싶어짐
-
지금 제 프사 어떰? 6 0
평가좀
-
문학이론쪽임 심지어 학자마다 평론가마다 정의나 판단이 다름;;
-
시대인재 가기 전 해야할 것 1 0
09년생이고 현재 약간 정시로 틀었습니다. 현재 대수(수1) 시발점 수분감만 끝냈고...
-
질문 3 0
에피 영어도 보나요?
-
아 이거 프사를 귀엽고 깜찍한 걸로 바꿔볼 건데 5 1
뭘 해야 할지 고민이네
-
잘자요 0 0
항시 건강하시구요
-
진짜 아무리노력해도 친구가 안생기는데 사회성장애가 있는듯
-
한달마다 콘서트 배치하기 9 0
3월 즛마 내한 (보고옴) 4월 토게토게 내한 (잡음) 5월 리라 내한 (잡음)...
-
정신병은 사실 엄청 심각한건데 사람이름에도막들어가고 그런것입니다
-
새터 어쩌고 글바메 어쩌고
-
현재 환율 상황) 6 0
이하 생략
-
원래는프사가고정이었는데 0 0
요즘그일러에살짝질려서 프사를막바꾸고잇늠
-
현역 기하런 1 0
문과고 확통하고있움. 12월부터 지금까지 학원에서 확통 개념원리+RPM하고 혼자서...
-
나 지금 외모 정병 왔음 7 0
말 걸지 마셈
-
누가봐도 멀쩡해보이는데 걍 잠시 생각 많아진거가지고 개나소나 정병이라면서 찡찡거림...
-
얼마나좋을까
-
요 이모티콘 너무 귀여움 6 0
-
영듣 어려운 번호 0 1
생각보다 영듣 칼럼도 도움이 될 것 같아서영어듣기 뷸안하신 분들이나 틀리시는...
-
지금이순간에도 3 0
나는실시간으로도태되고있는거임
-
외대 Lai >>>>> 고공 5 1
인정합니다
-
쿼티 볼 꼬집기 1 0
그래서 쿼티님은 정체가 뭔가요
-
존잘 찐따남이 되고 싶다 9 0
ㄹㅇ로… ㅠㅠㅠㅠ
-
우리처럼,,
-
청년 드립 넘 좋음 4 0
~했음 청년 이거 귀여움요 ㅋㅋㅋ
-
이태원 생각해서 그런다는데애초에 안전하게 돔이나 체육관 빌려서 하면 되는 거 아닌가..?
-
고평도 상당하네요 4 1
만만히 봐서는 안되겠습니다
-
구몬 수준 문제가 한 단원당 100문제 있고 2점~ㅈㄴ 쉬운 4점 100문제씩...
-
초 가구야 공주 보셈요 4 0
진짜 꿀잼 고트 애니
-
그냥 술자리 싫음 청년 7 3
그 뒤지게 시끄러운 곳에서 말도 제대로 안들리는데 처음 보는 사람하고 어색하게...
-
근데 더프 수학선택 범위 좁은건 3모대비라하면 이해되는데 4 3
투과목 << 얘넨 3모에도 안나오는데 전범위로 하면 될걸 왜 꾸득꾸득 초반부만 넣는거임
-
알림창 개폭력적이네 9 6
-
개강 3주차...아직 후배 얼굴도 본적없음
-
시발 뭘 할 수가 없네 9 1
친구 없어도 그래도 고대 왔으니 합응까진 갈까 했는데 허리 이 시발롬 좆도 안낫고 더 아파짐 아오
-
음주체스숙취수학 1 0
왜효고ㅓ좋냐
-
옾붕이들은 영어듣기 잘하나요 9 0
듣기 살면서 한번도 안툴린 사람 많으려나영듣칼럼 쓰려 하는데 수요 있으려나...
-
와 시벌 이게 얼마만인지 모르겟다 한달만에 같이 밥먹는거같은데 두달인가?
-
본인은 메인 두 번 가봄 3 1
한 번은 평가원 피셜 확정 등급컷 (영어) 네이버 블로그 감성 글로 가봤고 한 번은...
-
역시 약대생 3 1
난 시간 꽉꽉 채워 풀어서 88점인데
-
3덮 미적 풀어봤다 15 2
이렇다 전 글에서 맞춘사람 5000덕 보내줄게 생각보다 잘나왔네 22 30은 걍...
-
3모 ㅈ된거같으면 개추. 3 3
ㄱㄱ
B트리 학교에서 배웠는데.. 기억이...저도 아직 헷갈립니다… 비선형 자료구조라 아무래도 삭제 로직이 굉장히 복잡하고…
심지어 삽입 로직도 꽤 어려운 축에 속하고.. 하지만! 전공자라면 알고는 있어야 할 자료구조랄까요…
아 맞아요
remove 구현이 과제였던거로 기억해요
좀 까다로웠던 기억이..