This project contains code I found useful for caching problems. It includes circular buffers, timout dictionaries, and persistent dictionaries.
A circular buffer is buffer of fixed length. When the buffer is full, subsequent writes wrap, overwriting previous values. It is useful when you are only interested in the most recent values.
To whet your appetite, here are some examples.
// Create a buffer with a capacity of 5 items.
var buffer = new CircularBuffer<long>(5);
// Add three.
foreach (var i in Enumerable.Range(1, 3))
buffer.Enqueue(i);
Debug.WriteLine(buffer);
// Capacity=5, Count=3, Buffer=[1,2,3]
// Add three more.
foreach (var i in Enumerable.Range(4, 3))
buffer.Enqueue(i);
Debug.WriteLine(buffer);
// Capacity=5, Count=5, Buffer=[2,3,4,5,6]
// Remove the third.
var value = buffer[3];
buffer.RemoveAt(3);
Debug.WriteLine(buffer);
// Capacity=5, Count=4, Buffer=[2,3,4,6]
// Re-insert it.
buffer.Insert(3, value);
Debug.WriteLine(buffer);
// Capacity=5, Count=5, Buffer=[2,3,4,5,6]
// Dequeue.
Debug.Print("Value = {0}", buffer.Dequeue());
// Value = 2
Debug.WriteLine(buffer);
// Capacity=5, Count=4, Buffer=[3,4,5,6]
// Increase the capacity.
buffer.Capacity = 6;
Debug.WriteLine(buffer);
// Capacity=6, Count=4, Buffer=[3,4,5,6]
// Add three more.
foreach (var i in Enumerable.Range(7, 3))
buffer.Enqueue(i);
Debug.WriteLine(buffer);
// Capacity=6, Count=6, Buffer=[4,5,6,7,8,9]
// Reduce the capacity.
buffer.Capacity = 4;
Debug.WriteLine(buffer);
// Capacity=4, Count=4, Buffer=[4,5,6,7]
// Clear the buffer.
buffer.Clear();
Debug.WriteLine(buffer);
// Capacity=4, Count=0, Buffer=[]
This is a circular buffer I needed as a component for a caching layer. It is largely a blatant ripoff of the many implementations previously published on the web, with a few changes which might prove useful to those with similar objectives.
My first specific requirement was to model the structure as a queue, so the
primary interaction is Enqueue
and Dequeue
. As my caching layer has an in
memory cache and a persistent cache, I needed the Enqueue
to return the
overwritten value (if there was one). Lastly I needed to be able to arbitrarily
move things around in the queue, so I could control the order and contents.
All the obvious candidates are in the interface ICircularBuffer<T>
.
You can see the queue style interaction. Also note the enqueue returns the
overwritten value if one exists (otherwise it will be default(T)
). The
indexer methods, IndexOf
, InsertAt
, and RemoveAt
provide the
mechanism to manipulate the queue directly.
I could have provided item lookups by value rather than index, but these would
have still required the indexing operators and I wanted to keep the class small.
It should be clear how a derived class, (possibly implementing IList<T>
)
could be trivially implemented.
The code for CircularBuffer<T>
follows the traditional circular buffer pattern of declaring a fixed
length array, then maintaining an index to the head and tail of the array.
Typically the size of the buffer is defined by the constructor, but I have
included a Capacity property, to allow more sympathetic subclassing.
Though not strictley necessary it seemed convenient to implement IEnumerable<T>
.
The amount of code required is small, and it provides Linq compatibility at
little extra cost.
Here are some simple tests
which also demonstrate how to use the class.
This section describes a heap data structure. In this implementation a heap manages a sequential array of data which grows upwards from the bottom. Blocks of this array can be allocated, freed, read and written to through handles. The heap attempts to keep itself small by managing a list of free blocks that can be reallocated.
The primary operations handled by the heap will be memory management: Allocate
and Deallocate
, and reading and writing: Read
and Write
. As will become
clear later on it is also useful to be able to discover allocations, so one
less obvious operation GetAllocatedBlock
is included.
Because the heap manages its data internally, we need some utility classes. First
a Handle
through which we can refer to a block that has been allocated. Second
we define the Block
which defines the area in the heap to which the Handle
refers.
The Handle
is irritatingly large for such a trivial data structure. This is
because it implements a couple of interfaces for equality, and a factory class
for generating new handles.
The Block
is rather more terse. It has the index offset into the heap, and a
length. Both the handle and the block are immutable.
Now we have our basic data structures we can define the interface IHeap<T>
.
At this stage we can be agnostic to the type of items in the array, although
most typically they will be bytes.
The tricky bit in a heap is managing the free list. As allocations are requested
and released, discarded blocks are gathered together to be re-allocated. With
the interface used here (where access is managed through a handle) the data
itself may be completely reorganised. This stops the heap growing unnecessarily.
There are many algorithms available for this, so I decided to create an
IHeapManager
to represent allocation, and allow this part too be pluggable.
My implementation of the heap manager (LightweightHeapManager
)
is fairly trivial, but it was sufficient for my purpose. The only optimisation
it performs is to merge adjacent freed blocks.
With most of the heavy lifting done, the Heap<T>
implementation looks pretty trivial. The class is abstract, as we have yet to
decide how to represent the array.
As my goal is to create a persistent cache the first step is to model the heap
with a byte stream (StreamHeap
).
There a couple of non-obvious choices here.
The first is the constructor. There is some confusion over the ownership of the stream. Should this class dispose of the stream or not? Is it the owner? I could have passed a flag in the public constructor, but it seemed more natural that the class would own the stream if it created it. This is why I have a factory method for stream construction.
Second we can see the reason for GetAllocatedBlock
and CreateFreeBlock
.
This class does the actual reading and writing, so it needs the information
provided by the heap to fulfil these duties. It also needs to know about the
free block creation, so it can manage the physical space.
Finally we can save it to disc with the FileStreamHeap
.
The same strategy (this time over file ownership) is used, with a factory class indicating ownership.
There follow some tests for the stream heap. They also demonstrate its usage.
Apart from the construction the file stream heap has exactly the same functionality as the stream heap, so all I test here is the ownership.
This describes the implementation of a persistent dictionary. There are a number of excellent solutions to this online, but most were highly complex. This is a simple implementation which was sufficient for my purpose. It uses the classes described in the Heap section.
First we defined the interface for the persistent cache, ICache<T>
.
This follows the traditional CRUD pattern.
Now we can implement a fairly straightforward cache SerializingCache
,
without making too many decisions about how it will be used. All we need
to provide is a heap, a serializer, and a deserializer.
The Update
method has some complexity. If the size of the object has changed
it will need to deallocate the old block and allocate a new one.
A trivial implementation of the serializers could be the following.
using System.Text;
using JetBlack.Patterns.Heaps;
namespace JetBlack.Patterns.Caching
{
public class StringCache : SerializingCache<string,byte>
{
public StringCache(IHeap<byte> heap, Encoding encoding)
: base(heap, encoding.GetBytes, encoding.GetString)
{
}
public StringCache(IHeap<byte> heap)
: this(heap, Encoding.Default)
{
}
}
}
All we need to do to create a PersistentDictionary
is to wrap a cache with a dictionary implementation. We keep and
index of keys to handles to map to the persistent cache.
The factory class at the top generates the dictionary with binary serializers so we can support a large population of possible objects.
This section describes an implementation of a local/persistent caching dictionary bringing together the classes discussed in the Heap, PersistentDictionary, and CircularBuffer sections.
The implementation uses an in memory dictionary and a persistent dictionary to
create the CachingDictionary<TKey,TValue>
.
The recently accessed items remain in the local dictionary, while the less
used are moved to the persistent store. As older values are accessed they
are moved back into the local store.