path: root/src/cli/runtime/PersistentArray.cs

/**
 *   Copyright (c) Rich Hickey. All rights reserved.
 *   The use and distribution terms for this software are covered by the
 *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
 *   which can be found in the file CPL.TXT at the root of this distribution.
 *   By using this software in any fashion, you are agreeing to be bound by
 * 	 the terms of this license.
 *   You must not remove this notice, or any other, from this software.
 **/

/* rich Jun 2, 2006 */

using System;
using System.Threading;
using System.Collections;

namespace clojure.lang
{
/**
 * Note that instances of this class are constant values
 * i.e. set() returns a new array, old one is intact
 *
 * Multiple revisions (thread-safely) share the same master array
 *
 * Constant time most-recent-revision lookups
 * Amortized constant-time sequential revisions (when loadFactor > 1)
 * where a sequential revision is a revision of the most recent revision
 *
 * Non-sequential revisions are O(length), but with a small constant multiplier of 1/32
 * Worst-case O(r) lookups for oldest revs where r is number of revisions
 * at index i since last (automatic or manual) isolate. If set()s are roughly evenly
 * distributed, r should be approximately == loadFactor, i.e. constant
 * In pathological case (all mods to same index), r == (loadFactor * length)
 *
 * (loadFactor * length) old values are retained, even if the array revisions aren't
 * Default loadFactor is 2.1
 * When the load exceeds (loadFactor * length) the next revision is automatically isolated
 * You can determine how many values are in the shared master by calling load()
 * and can trim them by calling isolate() or resize(), which yield a new array with no
 * sharing and no old values
 *
 * See Cohen for basic idea
 * I added hybrid most-recent-sequential-range + shared-bitset idea, multi-thread-safety
 * Java implementation is lock-free
 */

	public class PersistentArray : AnArray, IEnumerable
		{

	#region IEnumerable Members

	public IEnumerator GetEnumerator()
		{
		return new ValIter(this);
		}

	#endregion

	override public ISeq seq()
		{
		if (length() > 0)
			return new Seq(this, 0);
		return null;
		}



		
internal class Master{
	internal readonly Entry[] array;
	internal readonly Object defaultVal;
	internal int rev;
	internal int load;
	internal readonly int maxLoad;
	internal readonly float loadFactor;
    internal int[] basis;
    internal volatile Master next;
    
	internal Master(int size,Object defaultVal, float loadFactor){
		this.array = new Entry[size];
		this.defaultVal = defaultVal;
		this.rev = 0;
		this.load = 0;
		this.maxLoad = (int)(size * loadFactor);
		this.loadFactor = loadFactor;
		}
	internal Master(Master parent)
		{
		this.array = new Entry[parent.array.Length];
		this.defaultVal = parent.defaultVal;
		this.rev = 0;
		this.load = 0;
		this.maxLoad = parent.maxLoad;
		this.loadFactor = parent.loadFactor;
		this.next = null;

		this.basis = new int[parent.array.Length];
		}
	}

internal class Entry
	{
	internal readonly int rev;
	internal readonly Object val;

	internal Entry(int rev, Object val)
		{
		this.rev = rev;
		this.val = val;
		}

	internal virtual Entry rest()
		{
		return null;
		}

	internal static Entry create(int rev, Object val, Entry rest)
		{
		if (rest == null)
			return new Entry(rev, val);
		return new EntryLink(rev, val, rest);
		}
	}

internal class EntryLink : Entry
	{
	internal readonly Entry _rest;

	internal EntryLink(int rev, Object val, Entry rest) :base(rev,val)
		{
		this._rest = rest;
		}
		
	override internal Entry rest(){
		return _rest;
	}
}

internal class Seq : IndexedSeq{
	readonly PersistentArray p;
	readonly int i;

	internal Seq(PersistentArray p, int i){
		this.p = p;
		this.i = i;
	}

    public Object first() {
        return p.nth(i);
    }

    public ISeq rest() {
        if(i+1 < p.length())
            return new Seq(p, i + 1);
        return null;
    }

#region IndexedSeq Members

public int index()
	{
	return i;
	}

#endregion
	}

internal class ValIter : IEnumerator
	{
	internal PersistentArray p;
	internal int i;

	internal ValIter(PersistentArray p)
		{
	this.p = p;
	this.i = -1;
}

#region IEnumerator Members

public object Current
	{
	get { return p.nth(i); }
	}

public bool MoveNext()
	{
	++i;
	return i < p.length();
	}

public void Reset()
	{
	throw new Exception("The method or operation is not implemented.");
	}

#endregion
	}

internal class Data{
	internal Master master;
	internal readonly int rev;
	internal readonly int baseline;
	internal readonly BitArray history;
	public Data(Master master, int rev, int baseline, BitArray history)
		{
		this.master = master;
		this.rev = rev;
		this.baseline = baseline;
		this.history = history;
		}	
	}

internal volatile Data data;

public PersistentArray(int size)
		: this(size, (Object)null)
		{
		}
		
public PersistentArray(int size, Object defaultVal)
	:this(size,defaultVal,2.1f)
	{
	}

public PersistentArray(int size, Object defaultVal, float loadFactor){
	this.data = new Data(new Master(size, defaultVal, loadFactor), 0, 0, null);
}

	internal PersistentArray(Master master, int rev, int baseline, BitArray history)
		{
		this.data = new Data(master, rev, baseline, history);
}

public PersistentArray(int size, ISeq seq) : this(size){
    int load = 0;
    for(int i=0;seq != null && i < size;i++, seq=seq.rest())
        {
        data.master.array[i] = new Entry(0,seq.first());
        ++load;
        }

	data.master.load = load;
}

public PersistentArray(IArray init) :this(init.length()) {
    int load = 0;
    for(int i=0;i < init.length();i++)
        {
		data.master.array[i] = new Entry(0, init.nth(i));
        ++load;
        }

	data.master.load = load;
}

override public int count(){
return data.master.array.Length;
}

override public int length(){
return