Sample of how to use generic pool of structs

PoolSample.cs

//
//  Main.cs
//
//  Author:
//       Nikolay Orlyuk <[email protected]>
//
//  Copyright (c) 2012 (c) Nikolay Orlyuk
//
//  This program is free software; you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
using System;
using System.Collections.Generic;

namespace mpool
{
    public class Pool<T>
        where T : struct
    {
        private readonly T[] _heap;
        private int _brk;

        public Pool(int size)
        {
            _heap = new T[size];
        }

        private int Reserve(int count = 1)
        {
            if ((_brk + count) > _heap.Length)
                throw new ArgumentOutOfRangeException("count");
            var start = _brk;
            _brk += count;
            return start;
        }

        public static readonly Ref Null = default(Ref);


        public Ref.RefArray Alloc(int length)
        {
            return Ref.RefArray.AllocAt(this, length);
        }

        public Ref Alloc()
        {
            return Ref.AllocAt(this);
        }

    
        public struct Ref
        {
            private readonly T[] _heap;
            private readonly int _offset;

            private Ref(T[] heap, int offset)
            {
                _heap = heap;
                _offset = offset;
            }

            public bool IsNull
            {
                get { return _heap == null; }
            }

            public T Value
            {
                get { return _heap [_offset]; }
                set { _heap [_offset] = value; }
            }

            public static Ref AllocAt(Pool<T> pool)
            {
                return new Ref(pool._heap, pool.Reserve());
            }


            public struct RefArray
            {
                private readonly T[] _heap;
                private readonly int _offset;
                private readonly int _length;

                private RefArray(T[] heap, int offset, int length)
                {
                    _heap = heap;
                    _offset = offset;
                    _length = length;
                }

                public int Length { get { return _length; } }

                public T this [int i]
                {
                    get { return _heap [_offset + i]; }
                    set { _heap [_offset + i] = value; }
                }

                public Ref Ref(int i)
                {
                    return new Ref(_heap, i);
                }

                public static RefArray AllocAt(Pool<T> pool, int length)
                {
                    return new RefArray(pool._heap, pool.Reserve(length), length);
                }
            }
        }


        public struct Chunked
        {
            private Pool<T> _pool;

            public Chunked(int chunkSize)
            {
                _pool = new Pool<T>(chunkSize);
            }

            public Ref Alloc()
            {
                var chunkSize = _pool._heap.Length;
                if (_pool._brk < chunkSize) return Alloc();
                _pool = new Pool<T>(chunkSize);
                return _pool.Alloc();
            }
        }
    }


    public class BinaryTree<T>
    {
        public Pool<Node>.Ref Root { get; private set; }

        public BinaryTree()
        {
        }

        public BinaryTree(Pool<Node>.Ref root)
        {
            Root = root;
        }

        public static void AttachChildren(Pool<Node>.Ref parent, Pool<Node>.Ref left, Pool<Node>.Ref right)
        {
            var node = parent.Value;

            // detach old children
            if (!node.Left.IsNull) node.Left.Value = node.Left.Value.SetParent();
            if (!node.Right.IsNull) node.Right.Value = node.Right.Value.SetParent();

            parent.Value = node.SetLeft(left).SetRight(right);
        }

        public void AttachRightRoot(Pool<Node>.Ref root)
        {
            root.Value = root.Value.SetLeft(Root);
            Root = root;
        }

        public void AttachLeftRoot(Pool<Node>.Ref root)
        {
            root.Value = root.Value.SetRight(Root);
            Root = root;
        }

        public struct Node
        {
            public T Value;
            public Pool<Node>.Ref Parent, Left, Right;

            public Node(T value,
                        Pool<Node>.Ref parent = default(Pool<Node>.Ref),
                        Pool<Node>.Ref left = default(Pool<Node>.Ref),
                        Pool<Node>.Ref right = default(Pool<Node>.Ref)
                        )
            {
                Value = value;
                Parent = parent;
                Left = left;
                Right = right;
            }

            public Node SetParent(Pool<Node>.Ref parent = default(Pool<Node>.Ref))
            {
                Parent = parent;
                return this;
            }

            public Node SetLeft(Pool<Node>.Ref left)
            {
                Left = left;
                return this;
            }

            public Node SetRight(Pool<Node>.Ref right)
            {
                Right = right;
                return this;
            }
        }
    }

    public struct FibbonaciTree
    {
        private readonly BinaryTree<long> _tree;

        public FibbonaciTree(int depth)
        {
            var builder = new Builder(depth);
            _tree = builder.Build();
        }

        public bool Contains(long value)
        {
            var nodeRef = _tree.Root;
            while (!nodeRef.IsNull)
            {
                var node = nodeRef.Value;
                //Console.WriteLine("{0} ? {1}", value, node.Value);
                if (value == node.Value) return true;
                if (value < node.Value) nodeRef = node.Left;
                else nodeRef = node.Right;
            }
            return false;
        }

        private class Builder
        {
            private readonly int depth;
            private readonly Pool<BinaryTree<long>.Node> pool;
            public readonly BinaryTree<long> Tree = new BinaryTree<long>();
            private long a = 1, b = 1;

            public Builder(int depth)
            {
                this.depth = depth;
                pool = new Pool<BinaryTree<long>.Node>(1 << depth); // 2^depth
            }

            private long Next()
            {
                var t = a;
                a = b;
                b = t + a;
                //Console.WriteLine(t);
                return t;
            }

            public BinaryTree<long> Build()
            {
                return new BinaryTree<long>(Build(depth));
            }

            private Pool<BinaryTree<long>.Node>.Ref Build(int level)
            {
                if (level == 0) return Pool<BinaryTree<long>.Node>.Null;
                var left = Build(level - 1);
                var x = Next();
                var right = Build(level - 1);
                var node = pool.Alloc();
                node.Value = new BinaryTree<long>.Node(x);
                BinaryTree<long>.AttachChildren(node, left, right);
                return node;
            }

        }
    }

    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            var fib = new FibbonaciTree(6);
            var rng = new Random();
            for(int n = 0; n < 6557470319843; ++n)
            {
                //var value = rng.Next() * ((long)int.MaxValue + 1) + rng.Next();
                //value = value % 6557470319843;
                ///value = 6557470319842;
                if (!fib.Contains(n)) continue;
                Console.WriteLine(n);
                ++n;
            }
        }
    }
}