marionette-of-u/gc_shinchoku.cpp

## gc_shinchoku.cpp
#include <string>
#include <memory>
#include <exception>
#include <type_traits>
#include <cstdint>
#include <cctype>
#include <cstddef>
#include <cstdlib>
#include <cstdio>
#include <cstring>

namespace multi_precision{
    namespace gc{
        // 専用の例外を作っておく.
        struct out_of_memory : public std::bad_alloc{
            out_of_memory() : std::bad_alloc(){}
            out_of_memory(const out_of_memory &other) : std::bad_alloc(other){}
        };

        struct invalid_reference : public std::out_of_range{
            invalid_reference() : std::out_of_range("invalid reference."){}
            invalid_reference(const invalid_reference &other) : std::out_of_range(other){}
        };

        // 侵入式リンクリスト.
        // active な要素と free な要素に分かれており両者は区別される.
        // 最大要素数は初期化時の要素数指定に依存する.
        template<class Type>
        class intrusive_linked_list{
        public:
            intrusive_linked_list() = delete;
            intrusive_linked_list(const intrusive_linked_list&) = delete;

            intrusive_linked_list(std::size_t n) : pool(new Type[n]){
                active_dummy.next = active_dummy.prev = &active_dummy;
                for(std::size_t i = 0; i < n - 1; ++i){
                    pool.get()[i].next = &pool.get()[i + 1];
                    pool.get()[i + 1].prev = &pool.get()[i];
                }
                free->next = pool.get();
                pool.get()->prev = free;
                free->prev = (pool.get() + n - 1);
                (pool.get() + n - 1)->next = free;
            }

            ~intrusive_linked_list() = default;

            // 生成し, 取得する.
            Type *get(){
                if(free->next == free){
                    throw std::bad_alloc();
                }
                Type *ptr = free->next;
                free->next = free->next->next;
                free->next->prev = free;
                ptr->next = active->next;
                ptr->next->prev = ptr;
                ptr->prev = active;
                active->next = ptr;
                return ptr;
            }

            // 破棄する.
            void dispose(Type *ptr){
                ptr->next->prev = ptr->prev;
                ptr->prev->next = ptr->next;
                ptr->next = free;
                ptr->prev = free->prev;
                free->prev->next = ptr;
                free->prev = ptr;
            }

            // さっさと破棄する.
            void sassato_dispose(Type *ptr){
                ptr->next->prev = ptr->prev;
                ptr->prev->next = ptr->next;
                ptr->next = free->next;
                ptr->prev = free;
                free->next->prev = ptr;
                free->next = ptr;
            }

        private:
            std::unique_ptr<Type[]> pool;
            Type active_dummy, *active = &active_dummy, free_dummy, *free = &free_dummy;

        public:
            const Type *const active_dummy_ptr = &active_dummy;
        };

        template<class ValueType>
        struct header;

        template<class ValueType>
        struct reference_list{
            reference_list *next, *prev, *next_reference = nullptr;
            header<ValueType> *ptr;
        };

        template<class ValueType>
        struct header{
            header *next, *prev, *copied = nullptr;
            std::size_t size = 0;
            reference_list<ValueType> *linked_reference_list = nullptr;
            typename std::aligned_storage<
                sizeof(ValueType),
                std::alignment_of<ValueType>::value
            >::type *data = nullptr;
        };

        template<class ValueType>
        class storage{
        public:
            using element_type = typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type;
            static const std::size_t void_ptr_size_in_heap = sizeof(void*) / sizeof(element_type) + (sizeof(void*) % sizeof(element_type) ? 1 : 0);

            storage() = delete;
            storage(const storage&) = delete;
            storage(std::size_t n) : heap_1(new element_type[n]), heap_2(new element_type[n]), max(n){
                std::memset(heap_1.get(), 0, sizeof(element_type) * n);
                std::memset(heap_2.get(), 0, sizeof(element_type) * n);
                heap = heap_1.get();
                head = heap;
            }

            ~storage(){}

        private:
            // active_iter から参照しているアクティブなインスタンスを走査しコピーする.
            void copy(
                intrusive_linked_list<header<ValueType>> &intrusive_header_list,
                intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list,
                element_type *to_heap,
                header<ValueType> *active_iter
            ){
                for(std::size_t i = 0; i < void_ptr_size_in_heap; ++i){
                    *(head++) = reinterpret_cast<element_type*>(&active_iter)[i - void_ptr_size_in_heap];
                }
                for(std::size_t i = 0, n = active_iter->size; i < n; ++i){
                    *(head++) = active_iter->data[i];
                }
                active_iter->data = to_heap;
                active_iter->copied = active_iter;
                to_heap += void_ptr_size_in_heap + active_iter->size;
                for(reference_list<ValueType> *ref_iter = active_iter->linked_reference_list; ref_iter; ref_iter = ref_iter->next_reference){
                    if(!ref_iter->ptr->copied){
                        copy(intrusive_header_list, intrusive_reference_list, to_heap, ref_iter->ptr);
                    }
                }
            }

            // 指定された iter と iter の参照しているインスタンスを破棄する.
            static void dispose_impl(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *iter){
                reference_list<ValueType> *co = iter->linked_reference_list;
                intrusive_header_list.dispose(iter);
                for(; co; co = co->next_reference){
                    dispose_impl(intrusive_header_list, intrusive_reference_list, co->ptr);
                    intrusive_reference_list.dispose(co);
                }
            }

            // 指定された iter と iter の参照しているインスタンスをさっさと破棄する.
            static void sassato_dispose_impl(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *iter){
                reference_list<ValueType> *co = iter->linked_reference_list;
                intrusive_header_list.sassato_dispose(iter);
                for(; co; co = co->next_reference){
                    sassato_dispose_impl(intrusive_header_list, intrusive_reference_list, co->ptr);
                    intrusive_reference_list.sassato_dispose(co);
                }
            }

        public:
            void run(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *root){
                if(heap == heap_1.get()){
                    head = heap_2.get();
                    copy(intrusive_header_list, intrusive_reference_list, heap_2.get(), root);
                }else{
                    head = heap_1.get();
                    copy(intrusive_header_list, intrusive_reference_list, heap_1.get(), root);
                }

                for(header<ValueType> *iter = intrusive_header_list.active_dummy_ptr->next; iter != intrusive_header_list.active_dummy_ptr; iter = iter->next){
                    if(iter->copied){
                        iter->copied = nullptr;
                    }else{
                        header<ValueType> *t = iter->prev;
                        for(reference_list<ValueType> *jter = iter->linked_reference_list; jter; jter = jter->next_reference){
                            intrusive_reference_list.dispose(jter);
                        }
                        intrusive_header_list.dispose(iter);
                        iter = t;
                    }
                }
            }

            void *alloc(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *root, std::size_t chunk_size){
                header<ValueType> *header = intrusive_header_list.get();
                header->copied = nullptr;
                header->linked_reference_list = nullptr;
                if(header->size == 0){
                    header->size = chunk_size;
                    header->data = head + void_ptr_size_in_heap;
                    head += void_ptr_size_in_heap + chunk_size;
                }
                element_type *ptr = header->data;
                for(std::size_t i = 0; i < void_ptr_size_in_heap; ++i){
                    (ptr - void_ptr_size_in_heap)[i] = *reinterpret_cast<element_type*>(&header + i);
                }
                return ptr;
            }

            void free(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *ptr){
                dispose_impl(intrusive_header_list, intrusive_reference_list, ptr);
            }

            void sassato_free(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *ptr){
                sassato_dispose_impl(intrusive_header_list, intrusive_reference_list, ptr);
            }

        private:
            std::unique_ptr<element_type[]> heap_1, heap_2;
            element_type *heap, *head;
            const std::size_t max;
        };

        template<class ValueType>
        struct memory_manager{
        public:
            memory_manager() = delete;
            memory_manager(const memory_manager&) = delete;
            memory_manager(std::size_t n) : memory_storage(n), intrusive_header_list(n), intrusive_reference_list(n){}

            ~memory_manager(){
                if(root){
                    memory_storage.run(intrusive_header_list, intrusive_reference_list, root);
                    memory_storage.free(intrusive_header_list, intrusive_reference_list, root);
                    intrusive_header_list.dispose(root);
                }
            }

            ValueType *alloc(std::size_t s){
                return static_cast<ValueType*>(memory_storage.alloc(intrusive_header_list, intrusive_reference_list, root, s));
            }

            void free(ValueType *ptr){
                header<ValueType> *p = value_to_header(ptr);
                memory_storage.dispose_impl(p);
            }

            void sassato_free(ValueType *ptr){
                header<ValueType> *p = value_to_header(ptr);
                memory_storage.sassato_dispose_impl(p);
            }

            // join.
            // left -> right
            void join(ValueType *left, ValueType *right){
                header<ValueType> *p = value_to_header(left), *q = value_to_header(right);
                if(p->linked_reference_list){
                    if(p->linked_reference_list->ptr == q){ return; }
                    for(reference_list<ValueType> *s = p->linked_reference_list; s->next_reference; s = s->next_reference){
                        if(s->next_reference->ptr == q){ return; }
                    }
                }
                reference_list<ValueType> *t = p->linked_reference_list;
                p->linked_reference_list = intrusive_reference_list.get();
                p->linked_reference_list->ptr = q;
                p->linked_reference_list->next_reference = t;
            }

            // disjoin.
            // left -X-> right
            void disjoin(ValueType *left, ValueType *right){
                header<ValueType> *p = value_to_header(left), *q = value_to_header(right);
                if(p->linked_reference_list->ptr == q){
                    reference_list<ValueType> *r = p->linked_reference_list;
                    p->linked_reference_list = p->linked_reference_list->next_reference;
                    intrusive_reference_list.dispose(r);
                    return;
                }
                for(reference_list<ValueType> *s = p->linked_reference_list; s->next_reference; s = s->next_reference){
                    if(s->next_reference->ptr == q){
                        reference_list<ValueType> *r = s->next_reference;
                        s->next_reference = s->next_reference->next_reference;
                        intrusive_reference_list.dispose(r);
                        return;
                    }
                }
                throw invalid_reference();
            }

            // GC を起動する.
            void run(){
                memory_storage.run(intrusive_header_list, intrusive_reference_list, root);
            }

            void set_root(ValueType *ptr){
                root = value_to_header(ptr);
            }

        private:
            header<ValueType> *value_to_header(ValueType *ptr){
                return reinterpret_cast<header<ValueType>*>(*(ptr - memory_storage.void_ptr_size_in_heap));
            }

            storage<ValueType> memory_storage;
            intrusive_linked_list<header<ValueType>> intrusive_header_list;
            intrusive_linked_list<reference_list<ValueType>> intrusive_reference_list;
            header<ValueType> *root = nullptr;
        };
    }
}

//#include "integer.hpp"

#include <iostream>

int main(){
    using namespace multi_precision::gc;
    memory_manager<int> manager(256);

    // int[10] の alloc を行う.
    int *x = manager.alloc(10);

    //先程 alloc した空間を root として扱う.
    manager.set_root(x);

    // 普通に使う.
    for(int i = 0; i < 10; ++i){
        x[i] = i * 10;
    }
    int sum = 0;
    for(int i = 0; i < 10; ++i){
        sum += x[i];
    }
    std::cout << sum << std::endl;

    int *y = manager.alloc(1), *z = manager.alloc(2);

    // x と結びつける.
    manager.join(x, y);
    manager.join(y, z);
    manager.join(z, x);

    // int[5] の孤立した空間を alloc してみる.
    manager.alloc(5);

    // プログラマの決めたタイミングで gc を走らせる.
    // manager.alloc(5) した空間が消えている.
    manager.run();

    // x -X-> y -> z -> x の場合,
    // z が x に依存していても, x から最終的に z までの依存が切れているので
    // y, z は消える.
    manager.disjoin(x, y);
    manager.run();

    return 0;
}
	#include <string>
	#include <memory>
	#include <exception>
	#include <type_traits>
	#include <cstdint>
	#include <cctype>
	#include <cstddef>
	#include <cstdlib>
	#include <cstdio>
	#include <cstring>

	namespace multi_precision{
	namespace gc{
	// 専用の例外を作っておく.
	struct out_of_memory : public std::bad_alloc{
	out_of_memory() : std::bad_alloc(){}
	out_of_memory(const out_of_memory &other) : std::bad_alloc(other){}
	};

	struct invalid_reference : public std::out_of_range{
	invalid_reference() : std::out_of_range("invalid reference."){}
	invalid_reference(const invalid_reference &other) : std::out_of_range(other){}
	};

	// 侵入式リンクリスト.
	// active な要素と free な要素に分かれており両者は区別される.
	// 最大要素数は初期化時の要素数指定に依存する.
	template<class Type>
	class intrusive_linked_list{
	public:
	intrusive_linked_list() = delete;
	intrusive_linked_list(const intrusive_linked_list&) = delete;

	intrusive_linked_list(std::size_t n) : pool(new Type[n]){
	active_dummy.next = active_dummy.prev = &active_dummy;
	for(std::size_t i = 0; i < n - 1; ++i){
	pool.get()[i].next = &pool.get()[i + 1];
	pool.get()[i + 1].prev = &pool.get()[i];
	}
	free->next = pool.get();
	pool.get()->prev = free;
	free->prev = (pool.get() + n - 1);
	(pool.get() + n - 1)->next = free;
	}

	~intrusive_linked_list() = default;

	// 生成し, 取得する.
	Type *get(){
	if(free->next == free){
	throw std::bad_alloc();
	}
	Type *ptr = free->next;
	free->next = free->next->next;
	free->next->prev = free;
	ptr->next = active->next;
	ptr->next->prev = ptr;
	ptr->prev = active;
	active->next = ptr;
	return ptr;
	}

	// 破棄する.
	void dispose(Type *ptr){
	ptr->next->prev = ptr->prev;
	ptr->prev->next = ptr->next;
	ptr->next = free;
	ptr->prev = free->prev;
	free->prev->next = ptr;
	free->prev = ptr;
	}

	// さっさと破棄する.
	void sassato_dispose(Type *ptr){
	ptr->next->prev = ptr->prev;
	ptr->prev->next = ptr->next;
	ptr->next = free->next;
	ptr->prev = free;
	free->next->prev = ptr;
	free->next = ptr;
	}

	private:
	std::unique_ptr<Type[]> pool;
	Type active_dummy, active = &active_dummy, free_dummy, free = &free_dummy;

	public:
	const Type *const active_dummy_ptr = &active_dummy;
	};

	template<class ValueType>
	struct header;

	template<class ValueType>
	struct reference_list{
	reference_list next, prev, *next_reference = nullptr;
	header<ValueType> *ptr;
	};

	template<class ValueType>
	struct header{
	header next, prev, *copied = nullptr;
	std::size_t size = 0;
	reference_list<ValueType> *linked_reference_list = nullptr;
	typename std::aligned_storage<
	sizeof(ValueType),
	std::alignment_of<ValueType>::value
	>::type *data = nullptr;
	};

	template<class ValueType>
	class storage{
	public:
	using element_type = typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type;
	static const std::size_t void_ptr_size_in_heap = sizeof(void) / sizeof(element_type) + (sizeof(void) % sizeof(element_type) ? 1 : 0);

	storage() = delete;
	storage(const storage&) = delete;
	storage(std::size_t n) : heap_1(new element_type[n]), heap_2(new element_type[n]), max(n){
	std::memset(heap_1.get(), 0, sizeof(element_type) * n);
	std::memset(heap_2.get(), 0, sizeof(element_type) * n);
	heap = heap_1.get();
	head = heap;
	}

	~storage(){}

	private:
	// active_iter から参照しているアクティブなインスタンスを走査しコピーする.
	void copy(
	intrusive_linked_list<header<ValueType>> &intrusive_header_list,
	intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list,
	element_type *to_heap,
	header<ValueType> *active_iter
	){
	for(std::size_t i = 0; i < void_ptr_size_in_heap; ++i){
	(head++) = reinterpret_cast<element_type>(&active_iter)[i - void_ptr_size_in_heap];
	}
	for(std::size_t i = 0, n = active_iter->size; i < n; ++i){
	*(head++) = active_iter->data[i];
	}
	active_iter->data = to_heap;
	active_iter->copied = active_iter;
	to_heap += void_ptr_size_in_heap + active_iter->size;
	for(reference_list<ValueType> *ref_iter = active_iter->linked_reference_list; ref_iter; ref_iter = ref_iter->next_reference){
	if(!ref_iter->ptr->copied){
	copy(intrusive_header_list, intrusive_reference_list, to_heap, ref_iter->ptr);
	}
	}
	}

	// 指定された iter と iter の参照しているインスタンスを破棄する.
	static void dispose_impl(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *iter){
	reference_list<ValueType> *co = iter->linked_reference_list;
	intrusive_header_list.dispose(iter);
	for(; co; co = co->next_reference){
	dispose_impl(intrusive_header_list, intrusive_reference_list, co->ptr);
	intrusive_reference_list.dispose(co);
	}
	}

	// 指定された iter と iter の参照しているインスタンスをさっさと破棄する.
	static void sassato_dispose_impl(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *iter){
	reference_list<ValueType> *co = iter->linked_reference_list;
	intrusive_header_list.sassato_dispose(iter);
	for(; co; co = co->next_reference){
	sassato_dispose_impl(intrusive_header_list, intrusive_reference_list, co->ptr);
	intrusive_reference_list.sassato_dispose(co);
	}
	}

	public:
	void run(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *root){
	if(heap == heap_1.get()){
	head = heap_2.get();
	copy(intrusive_header_list, intrusive_reference_list, heap_2.get(), root);
	}else{
	head = heap_1.get();
	copy(intrusive_header_list, intrusive_reference_list, heap_1.get(), root);
	}

	for(header<ValueType> *iter = intrusive_header_list.active_dummy_ptr->next; iter != intrusive_header_list.active_dummy_ptr; iter = iter->next){
	if(iter->copied){
	iter->copied = nullptr;
	}else{
	header<ValueType> *t = iter->prev;
	for(reference_list<ValueType> *jter = iter->linked_reference_list; jter; jter = jter->next_reference){
	intrusive_reference_list.dispose(jter);
	}
	intrusive_header_list.dispose(iter);
	iter = t;
	}
	}
	}

	void alloc(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> root, std::size_t chunk_size){
	header<ValueType> *header = intrusive_header_list.get();
	header->copied = nullptr;
	header->linked_reference_list = nullptr;
	if(header->size == 0){
	header->size = chunk_size;
	header->data = head + void_ptr_size_in_heap;
	head += void_ptr_size_in_heap + chunk_size;
	}
	element_type *ptr = header->data;
	for(std::size_t i = 0; i < void_ptr_size_in_heap; ++i){
	(ptr - void_ptr_size_in_heap)[i] = reinterpret_cast<element_type>(&header + i);
	}
	return ptr;
	}

	void free(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *ptr){
	dispose_impl(intrusive_header_list, intrusive_reference_list, ptr);
	}

	void sassato_free(intrusive_linked_list<header<ValueType>> &intrusive_header_list, intrusive_linked_list<reference_list<ValueType>> &intrusive_reference_list, header<ValueType> *ptr){
	sassato_dispose_impl(intrusive_header_list, intrusive_reference_list, ptr);
	}

	private:
	std::unique_ptr<element_type[]> heap_1, heap_2;
	element_type heap, head;
	const std::size_t max;
	};

	template<class ValueType>
	struct memory_manager{
	public:
	memory_manager() = delete;
	memory_manager(const memory_manager&) = delete;
	memory_manager(std::size_t n) : memory_storage(n), intrusive_header_list(n), intrusive_reference_list(n){}

	~memory_manager(){
	if(root){
	memory_storage.run(intrusive_header_list, intrusive_reference_list, root);
	memory_storage.free(intrusive_header_list, intrusive_reference_list, root);
	intrusive_header_list.dispose(root);
	}
	}

	ValueType *alloc(std::size_t s){
	return static_cast<ValueType*>(memory_storage.alloc(intrusive_header_list, intrusive_reference_list, root, s));
	}

	void free(ValueType *ptr){
	header<ValueType> *p = value_to_header(ptr);
	memory_storage.dispose_impl(p);
	}

	void sassato_free(ValueType *ptr){
	header<ValueType> *p = value_to_header(ptr);
	memory_storage.sassato_dispose_impl(p);
	}

	// join.
	// left -> right
	void join(ValueType left, ValueType right){
	header<ValueType> p = value_to_header(left), q = value_to_header(right);
	if(p->linked_reference_list){
	if(p->linked_reference_list->ptr == q){ return; }
	for(reference_list<ValueType> *s = p->linked_reference_list; s->next_reference; s = s->next_reference){
	if(s->next_reference->ptr == q){ return; }
	}
	}
	reference_list<ValueType> *t = p->linked_reference_list;
	p->linked_reference_list = intrusive_reference_list.get();
	p->linked_reference_list->ptr = q;
	p->linked_reference_list->next_reference = t;
	}

	// disjoin.
	// left -X-> right
	void disjoin(ValueType left, ValueType right){
	header<ValueType> p = value_to_header(left), q = value_to_header(right);
	if(p->linked_reference_list->ptr == q){
	reference_list<ValueType> *r = p->linked_reference_list;
	p->linked_reference_list = p->linked_reference_list->next_reference;
	intrusive_reference_list.dispose(r);
	return;
	}
	for(reference_list<ValueType> *s = p->linked_reference_list; s->next_reference; s = s->next_reference){
	if(s->next_reference->ptr == q){
	reference_list<ValueType> *r = s->next_reference;
	s->next_reference = s->next_reference->next_reference;
	intrusive_reference_list.dispose(r);
	return;
	}
	}
	throw invalid_reference();
	}

	// GC を起動する.
	void run(){
	memory_storage.run(intrusive_header_list, intrusive_reference_list, root);
	}

	void set_root(ValueType *ptr){
	root = value_to_header(ptr);
	}

	private:
	header<ValueType> value_to_header(ValueType ptr){
	return reinterpret_cast<header<ValueType>>((ptr - memory_storage.void_ptr_size_in_heap));
	}

	storage<ValueType> memory_storage;
	intrusive_linked_list<header<ValueType>> intrusive_header_list;
	intrusive_linked_list<reference_list<ValueType>> intrusive_reference_list;
	header<ValueType> *root = nullptr;
	};
	}
	}

	//#include "integer.hpp"

	#include <iostream>

	int main(){
	using namespace multi_precision::gc;
	memory_manager<int> manager(256);

	// int[10] の alloc を行う.
	int *x = manager.alloc(10);

	//先程 alloc した空間を root として扱う.
	manager.set_root(x);

	// 普通に使う.
	for(int i = 0; i < 10; ++i){
	x[i] = i * 10;
	}
	int sum = 0;
	for(int i = 0; i < 10; ++i){
	sum += x[i];
	}
	std::cout << sum << std::endl;

	int y = manager.alloc(1), z = manager.alloc(2);

	// x と結びつける.
	manager.join(x, y);
	manager.join(y, z);
	manager.join(z, x);

	// int[5] の孤立した空間を alloc してみる.
	manager.alloc(5);

	// プログラマの決めたタイミングで gc を走らせる.
	// manager.alloc(5) した空間が消えている.
	manager.run();

	// x -X-> y -> z -> x の場合,
	// z が x に依存していても, x から最終的に z までの依存が切れているので
	// y, z は消える.
	manager.disjoin(x, y);
	manager.run();

	return 0;
	}