Skip to content

Instantly share code, notes, and snippets.

@arobson
Created January 24, 2011 05:37
Show Gist options
  • Save arobson/792882 to your computer and use it in GitHub Desktop.
Save arobson/792882 to your computer and use it in GitHub Desktop.
This is a very different approach I took from initial attempts that relied on volatile arrays and a crap ton of pointers. This is more fun :)
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using Machine.Specifications;
namespace ringbuffer
{
public class RingBufferCell
: IDisposable
{
public object Value { get; set; }
public RingBuffer Ring { get; set; }
public int LastWriter { get; set; }
public RingBufferCell Next { get; set; }
public bool Tail { get; set; }
public static RingBufferCell Build(RingBuffer ring, int count)
{
var newCell = new RingBufferCell(ring);
ring.Head = ring.Head ?? newCell;
if ((newCell.Tail = (count == 0)))
newCell.Next = ring.Head;
else
newCell.Next = Build(ring, count - 1);
return newCell;
}
public void SetLastWrite(int lastWrittenBy)
{
LastWriter = lastWrittenBy;
if (!Tail)
Next.SetLastWrite(lastWrittenBy);
}
public bool Ready(int index)
{
return Ring.PreviousStepLookup[index] == LastWriter;
}
public RingBufferCell Transform(int index, Func<object, object> transform)
{
while (!Ready(index))
Thread.Sleep(1);
Value = transform(Value);
LastWriter = index;
return Next;
}
public RingBufferCell(RingBuffer ring)
{
Ring = ring;
LastWriter = 0;
}
public void Dispose()
{
Next = null;
Ring = null;
Value = null;
}
}
public class RingBuffer
{
public bool Running { get; protected set; }
public int Size { get; set; }
public int[] PreviousStepLookup { get; set; }
public RingBufferCell Head { get; set; }
public RingBufferCell[] Steps { get; set; }
public List<Func<object, object>> Transforms { get; protected set; }
public void Write<T>(T value)
{
Steps[0] = Steps[0].Transform(0, x => value);
}
public void AddTransform(Func<object, object> transform)
{
Transforms.Add(transform);
PreviousStepLookup[0] = Transforms.Count;
Head.SetLastWrite(Transforms.Count);
}
public void Process(int step, Func<object, object> transform)
{
while (Running)
Steps[step] = Steps[step].Transform(step, transform);
}
public void Start()
{
Running = true;
int step = 1;
Transforms
.ForEach(f => Task.Factory.StartNew(() => Process(step++, f), TaskCreationOptions.LongRunning));
}
public RingBuffer(int size)
{
Transforms = new List<Func<object, object>>();
Size = size;
Head = RingBufferCell.Build(this, Size);
var countUp = -1;
PreviousStepLookup = Enumerable.Range(countUp++, size).ToArray();
PreviousStepLookup[0] = Size -1;
Steps = Enumerable.Repeat(Head, 10).ToArray();
}
}
public class with_buffer
{
public static int Size = 5000;
public static RingBuffer Buffer { get; set; }
private Establish context = () =>
{
Buffer = new RingBuffer(Size);
};
}
public class when_instantiating_buffer
: with_buffer
{
public static int count;
private Because of = () =>
{
var cell = Buffer.Head;
while(!cell.Tail)
{
cell = cell.Next;
count++;
}
};
private It should_have_correct_cell_count = () => count.ShouldEqual(Size);
private It should_have_correct_previous_step_for_first_element = () => Buffer.PreviousStepLookup[0].ShouldEqual(Size - 1);
private It should_have_correct_previous_step_for_last_element = () => Buffer.PreviousStepLookup[Size - 1].ShouldEqual(Size - 2);
}
public class when_doing_simple_math
: with_buffer
{
private static int TOTAL_WRITES = 1000000;
public static List<int> Counts;
public static Stopwatch Watch { get; set; }
private Because of = () =>
{
Counts = new List<int>(TOTAL_WRITES);
Buffer.AddTransform(x => (int) x + 45);
Buffer.AddTransform(x => (int) x + 45);
Buffer.AddTransform(x =>
{
Counts.Add((int) x);
return x;
});
Watch = Stopwatch.StartNew();
Buffer.Start();
for (int i = 0; i < TOTAL_WRITES; i++)
{
Buffer.Write(10);
}
Watch.Stop();
};
private It should_have_completed_all_steps = () => Counts.All(x => x == 100).ShouldBeTrue();
private It should_have_all_items = () => Counts.Count.ShouldEqual(TOTAL_WRITES);
private It should_take_300ms = () => Watch.ElapsedMilliseconds.ShouldEqual(300);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment