Skip to content

Instantly share code, notes, and snippets.

@ony
Created October 10, 2012 07:02
Show Gist options
  • Save ony/3863607 to your computer and use it in GitHub Desktop.
Save ony/3863607 to your computer and use it in GitHub Desktop.
Sample of how to use generic pool of structs
//
// Main.cs
//
// Author:
// Nikolay Orlyuk <virkony@gmail.com>
//
// 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;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment