N-항 트리를 이용한 파일 시스템 구조

 

N-항 트리란 무엇인가?

 
이번 포스팅에서 살펴볼 N-항 트리(N-ary tree)는 각 노드가 N개의 자식을 가질 수 있다.
N은 임의의 양수이므로 n개의 자식 노드는 벡터를 이용하여 저장할 수 있다.
그러므로 N-항 트리는 다음과 같이 구현할 수 있다.
 

struct nTree
{
    int data;
    std::vector<nTree*> children;
};

 
 
위 코드에서 각각의 노드는 임의 개수의 자식을 거느릴 수 있다.
그러므로 전체 트리도 임의의 형태를 가지게 된다.
평범한 이진 트리를 많이 사용하지 않는 것처럼 평범한 N-항 트리도 그다지 유용하지 않다.
그러나 응용 프로그램의 요구 사항에 맞는 형태의 트리를 만들어 사용해야 한다.
 
 

N항 트리의 예시와 컴퓨터 분야에서의 쓰임

회사의 조직도와 같은 경우를 N-항 트리의 예시로 들 수 있다.
 
컴퓨터 분야에서 N-항 트리를 사용하는 대표적인 예는 다음과 같다.
 

• 컴퓨터 파일 시스템 구조 : 
• 리눅스에서는 루트(/)부터, 윈도에서는 드라이브 이름 (C:\)부터 시작해서
• 다수의 파일과 폴더를 가질 수 있다.
• 파일 시스템 구조와 관련해서는 바로 다음에 나오는 
• 실습 코드의 파일 시스템 자료 구조 만들기에서 자세히 알아보자.
• 컴파일러 :
• 대부분의 컴파일러는 표준 문법에 근거하여 소스 코드부터 
• 추상 구문 트리(AST, Abstract Syntax Tree)를 구성한다.
• 그리고 AST를 다시 분석하여 하위 레벨 코드를 생성한다.

 

---

파일 시스템 자료 구조 만들기

 
N-항 트리를 이용하여 디렉터리 이동,
파일/디렉터리 검색, 파일/디렉터리 추가, 파일/디렉터리 목록 출력 등의 기능을 지원하는
파일 시스템 자료 구조를 구성해보자.
 
이 트리는 파일 시스템의 모든 원소(파일 또는 디렉터리)에 대한
계층 구조(경로)와 정보를 가지고 있어야 한다.
 
파일 시스템 자료 구조를 만들기 위해서는 아래와 같은 단계를 거치면 구현할 수 있다.
 

파일 시스템 자료 구조의 전반적인 흐름

1. 기본적인 N-항 트리를 생성한다.
   이 트리의 노드는 디렉터리 또는 파일의 이름,
   그리고 이것이 파일인지 디렉터리인지 분간하는 플래그를 멤버로 가진다.
   
   
2. 현재 디렉터리 루트(/)로 트리를 초기화한다.
   
   
3. 단일 디렉터리 루트(/)로 트리를 초기화한다.
   
   
4. 경로명(path)을 인자로 받는 디렉터리/파일 검색 함수를 추가한다.
   경로명은 /부터 시작하는 절대 경로와 상대 경로를 모두 지원해야 한다.
   
   
5. 지정된 경로에서 파일/디렉터리를 추가하는 함수와
   파일/디렉터리 목록을 출력하는 함수를 추가한다.
   
   
6. 현재 디렉터를 변경하는 함수를 추가한다.

#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

// 디렉터리/파일 정보를 저장할 노드 구조체 작성
struct n_ary_node
{
	std::string name;
	bool is_dir;
	std::vector<n_ary_node*> children;
};


// 사용하기 편하도록 n_ary_node를 사용하여 트리를 구성한다.
// 그리고 현재 디렉터리를 저장할 변수를 추가한다.
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;
	}
// 디렉터리/파일을 찾는 find() 함수를 추가한다.
	node_ptr find(const std::string& path)
	{
		if (path[0] == '/')	//절대 경로
		{
			return find_impl(root, path.substr(1));
		}
		else
		{
			return find_impl(cwd, path);
		}
	}

private:
	// find_impl 함수는 주어진 디렉토리 노드(directory)에서,
	// 문자열 경로(path)에 해당하는 자식 노드를 재귀적으로 찾아 반환하는 함수이다.
	node_ptr find_impl(node_ptr directory, const std::string& path)
	{
		// 만약 입력받은 경로가 빈 문자열이라면, 더 이상 탐색할 경로가 없으므로
		// 현재 디렉토리 노드를 반환한다.
		if (path.empty())
		{
			return directory;
		}

		// 경로 문자열에서 '/' 문자의 위치를 찾는다.
		auto sep = path.find('/');

		// '/'가 없으면 전체 문자열이 현재 찾을 경로(current_path)가 되고,
		// '/'가 있으면 '/' 앞의 부분을 현재 경로(current_path)로 설정한다.
		std::string current_path = sep == std::string::npos ? path : path.substr(0, sep);

		// '/'가 없으면 나머지 경로(rest_path)는 빈 문자열이 되고,
		// '/'가 있으면 '/' 다음 부분을 나머지 경로(rest_path)로 설정한다.
		std::string rest_path = sep == std::string::npos ? "" : path.substr(sep + 1);

		// 현재 디렉토리의 자식 노드들 중에서,
		// 이름이 current_path와 일치하는 노드를 찾는다.
		auto found = std::find_if(directory->children.begin(), directory->children.end(),
			[&](const node_ptr child) {
				return child->name == current_path; // 자식 노드의 이름 비교
			});

		// 만약 일치하는 노드를 찾았다면,
		// 해당 노드를 대상으로 나머지 경로(rest_path)에 대해 재귀적으로 탐색한다.
		if (found != directory->children.end())
		{
			return find_impl(*found, rest_path);
		}

		// 만약 일치하는 노드가 없다면, 경로에 해당하는 노드가 없으므로 NULL을 반환한다.
		return NULL;
	}


public:
// 디렉터리 생성하는 add() 함수를 추가한다.
	bool add(const std::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 std::string& path, bool is_dir)
	{
		if (not directory->is_dir)
		{
			std::cout << directory->name << "은(는) 파일입니다." << std::endl;
			return false;
		}

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

		// path 에 '/'가 없는 경우.
		if (sep == std::string::npos)
		{
			auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child) {
				return child->name == path;
				});

			if (found != directory->children.end())
			{
				std::cout << directory->name << "에 이미" << path << " 이름의 파일/디렉터가 있습니다." << std::endl;
			}

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

		// path에 '/'가 있는 경우, 즉, 디렉터리 이름을 포함하고 있는 경우
		std::string next_dir = path.substr(0, sep);
		auto found = std::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);
		}

		//path에 디렉터리 이름이 포함되어 있지만, 해당 디렉터리가 없는 경우
		std::cout << directory->name << "에 " << next_dir << " 이름의 디렉터리가 없습니다." << std::endl;
		return false;
	}

// 디렉터리를 이동하는 change_dir() 함수를 추가한다.
// 이미 앞에서 find() 함수를 구현했기 때문에 change_dir() 함수는 쉽게 구현 가능하다.
public:
	bool change_dir(const std::string& path)
	{
		auto found = find(path);
		if (found && found->is_dir)
		{
			cwd = found;
			std::cout << "현재 디렉터리를 " << cwd->name << " 로 이동합니다." << std::endl;
			return true;
		}

		std::cout << path << " 경로를 찾을 수 없습니다." << std::endl;
		return true;
	}

// show_path 함수는 디렉터리와 파일 목록을 출력하는 함수이다.
// 함수 인자로 파일이 전달되면 단순히 파일 이름을 출려가혹,
// 디렉터리가 인자로 전달되면 해당 디렉터리의 하위 디렉터리와 파일을 모두 출력한다.
public:
	void show_path(const std::string& path)
	{
		auto found = find(path);
		if (not found)
		{
			std::cout << path << " 경로가 존재하지 않습니다." << std::endl;
			return;
		}

		if (found->is_dir)
		{
			for (auto child : found->children)
			{
				std::cout << (child->is_dir ? "d " : "- ") << child->name << std::endl;
			}
		}
		else
		{
			std::cout << "- " << found->name << std::endl;
		}
	}
};

int main()
{

	file_system fs;
	fs.add("usr", true);
	fs.add("etc", true);
	fs.add("var", true);
	fs.add("tmp_file", true);

	std::cout << "\"/\" 의 파일/디렉터리 목록 : " << std::endl;
	fs.show_path("/");		// "/"의 파일/디렉터리 목록 출력

	std::cout << std::endl;
	fs.change_dir("usr");
	fs.add("gilbut", true);
	fs.add("gilbut/Downloads", true);
	fs.add("gilbut/Downloads/newFile.cpp", false);

	std::cout << "현재 디렉터리에서 usr의 파일/디렉터리 목록: " << std::endl;
	fs.show_path("usr"); // 현재 디렉터리에는 usr 디렉터리가 없으므로 정상저긍로 출력하지 못한다.

	std::cout << "\"/usr\"의 파일/디렉터리 목록 : " << std::endl;
	fs.show_path("/usr");

	std::cout << "\"/usr/gilbut/Downloads\"의 파일/디렉터리 목록" << std::endl;
	fs.show_path("/usr/gilbut/Downloads");

	return 0;
}