Blog

// tree.hpp — 순회 대상: 이진 탐색 트리
#pragma once
#include <memory>

struct TreeNode {
	int key;
	std::unique_ptr<TreeNode> left, right;
	explicit TreeNode(int k) : key(k) {}
};

inline void insert(std::unique_ptr<TreeNode> &n, int k)
{
	if (!n) { n = std::make_unique<TreeNode>(k); return; }
	insert(k < n->key ? n->left : n->right, k);
}

// internal_external.cpp — 내부 반복자(컬렉션이 돌린다) vs 외부 반복자(클라이언트가 돌린다)
#include <iostream>
#include <stack>
#include "tree.hpp"

// 내부 반복자: 순회 로직은 컬렉션에, 클라이언트는 원소마다 할 일만 넘긴다
template <class F>
void for_each_inorder(const TreeNode *n, F &&f)
{
	if (!n) return;
	for_each_inorder(n->left.get(), f);
	f(n->key);
	for_each_inorder(n->right.get(), f);
}

// 외부 반복자: 순회 상태(스택)를 반복자 객체가 들고, 클라이언트가 한 걸음씩 진행한다
class InorderIterator {
public:
	explicit InorderIterator(const TreeNode *root) { pushLeft(root); }
	bool done() const { return st_.empty(); }
	int current() const { return st_.top()->key; }
	void next()
	{
		const TreeNode *n = st_.top();
		st_.pop();
		pushLeft(n->right.get());
	}
private:
	void pushLeft(const TreeNode *n) { for (; n; n = n->left.get()) st_.push(n); }
	std::stack<const TreeNode *> st_;
};

int main()
{
	std::unique_ptr<TreeNode> a, b;
	for (int k : {50, 30, 70, 20, 40, 60, 80}) insert(a, k);
	for (int k : {45, 25, 65, 35, 55})         insert(b, k);

	std::cout << "internal: ";
	for_each_inorder(a.get(), [](int k) { std::cout << k << ' '; });
	std::cout << '\n';

	// 외부 반복자만 할 수 있는 일: 두 트리를 동시에 진행하며 병합, 중간에 멈추기
	std::cout << "merge   : ";
	InorderIterator x(a.get()), y(b.get());
	int printed = 0;
	while ((!x.done() || !y.done()) && printed < 9) {
		bool takeX = !x.done() && (y.done() || x.current() <= y.current());
		std::cout << (takeX ? x.current() : y.current()) << ' ';
		takeX ? x.next() : y.next();
		++printed;
	}
	std::cout << "... (stopped after " << printed << ")\n";
}

// generator.hpp — C++20 코루틴으로 만든 최소 제너레이터(C++23 std::generator의 축소판)
#pragma once
#include <coroutine>
#include <exception>
#include <utility>

template <class T>
class Generator {
public:
	struct promise_type {
		T value;
		std::exception_ptr error;
		Generator get_return_object() { return Generator{Handle::from_promise(*this)}; }
		std::suspend_always initial_suspend() noexcept { return {}; }   // 첫 next까지 대기
		std::suspend_always final_suspend() noexcept { return {}; }
		std::suspend_always yield_value(T v) { value = std::move(v); return {}; }
		void return_void() {}
		void unhandled_exception() { error = std::current_exception(); }
	};
	using Handle = std::coroutine_handle<promise_type>;

	struct iterator {                                   // range-for용 외부 반복자
		Handle h;
		iterator &operator++() { h.resume(); rethrow(); return *this; }
		const T &operator*() const { return h.promise().value; }
		bool operator==(std::default_sentinel_t) const { return !h || h.done(); }
		void rethrow() const { if (h.promise().error) std::rethrow_exception(h.promise().error); }
	};
	iterator begin() { h_.resume(); iterator it{h_}; it.rethrow(); return it; }
	std::default_sentinel_t end() { return {}; }

	explicit Generator(Handle h) : h_(h) {}
	Generator(Generator &&o) noexcept : h_(std::exchange(o.h_, {})) {}
	~Generator() { if (h_) h_.destroy(); }
private:
	Handle h_;
};

// coro.cpp — 순회 상태를 지역 변수와 실행 위치로 표현하는 반복자
#include <iostream>
#include "generator.hpp"
#include "tree.hpp"

Generator<long> fibonacci()                         // 끝이 없는 수열
{
	long a = 0, b = 1;
	for (;;) {
		co_yield a;
		a = std::exchange(b, a + b);
	}
}

Generator<int> inorder(const TreeNode *n)            // 재귀 순회를 그대로 쓴다
{
	if (!n)
		co_return;
	for (int k : inorder(n->left.get()))
		co_yield k;
	co_yield n->key;
	for (int k : inorder(n->right.get()))
		co_yield k;
}

int main()
{
	int count = 0;
	for (long f : fibonacci()) {                     // 필요한 만큼만 계산된다
		if (++count > 12)
			break;
		std::cout << f << ' ';
	}
	std::cout << '\n';

	std::unique_ptr<TreeNode> root;
	for (int k : {50, 30, 70, 20, 40, 60, 80})
		insert(root, k);
	for (int k : inorder(root.get())) {
		std::cout << k << ' ';
		if (k == 60)
			break;                                   // 중간에 멈추면 남은 코루틴 프레임은 소멸자가 정리
	}
	std::cout << '\n';
}

/* dir_iter.c — POSIX 디렉터리 스트림: opendir/readdir/closedir는 C 표준적인 외부 반복자다 */
#define _DEFAULT_SOURCE
#include <dirent.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv)
{
	const char *path = argc > 1 ? argv[1] : ".";
	DIR *d = opendir(path);                      /* 반복자 생성 */
	struct dirent *e;
	int files = 0, dirs = 0;

	if (!d) {
		perror(path);
		return 1;
	}
	while ((e = readdir(d)) != NULL) {           /* next() + done() */
		if (strcmp(e->d_name, ".") == 0 || strcmp(e->d_name, "..") == 0)
			continue;
		e->d_type == DT_DIR ? dirs++ : files++;
	}
	closedir(d);                                 /* 반복자 해제 */
	printf("%s: %d files, %d dirs\n", path, files, dirs);
	return 0;
}

/* list_iter.c — 커널식 침습 리스트와 순회 매크로(list_for_each_entry) 축소판 */
#include <stddef.h>
#include <stdio.h>

struct list_head { struct list_head *next, *prev; };

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define container_of(ptr, type, member) ((type *)((char *)(ptr) - offsetof(type, member)))
#define list_entry(ptr, type, member) container_of(ptr, type, member)
#define list_for_each_entry(pos, head, member)                                  \
	for (pos = list_entry((head)->next, __typeof__(*pos), member);         \
	     &pos->member != (head);                                            \
	     pos = list_entry(pos->member.next, __typeof__(*pos), member))

static void list_add_tail(struct list_head *n, struct list_head *head)
{
	n->prev = head->prev;
	n->next = head;
	head->prev->next = n;
	head->prev = n;
}

struct task {
	int pid;
	const char *comm;
	struct list_head node;                   /* 리스트 링크를 원소 안에 품는다 */
};

int main(void)
{
	struct list_head tasks = LIST_HEAD_INIT(tasks);
	struct task t[] = { {1, "systemd", {0}}, {512, "sshd", {0}}, {4096, "bash", {0}} };
	struct task *p;

	for (size_t i = 0; i < sizeof(t) / sizeof(t[0]); i++)
		list_add_tail(&t[i].node, &tasks);

	list_for_each_entry(p, &tasks, node)     /* 반복자 객체 없이 for문으로 펼쳐진다 */
		printf("%5d %s\n", p->pid, p->comm);
	return 0;
}