VListBlock implements the core functionality of FVList, VList, FWList and WList. It is not intended to be used directly. More...

Source file:

/Core/Loyc.Collections/VLists/VListBlock.cs

Inheritance diagram for Loyc.Collections.VListBlock< T >:

Remarks

VListBlock implements the core functionality of FVList, VList, FWList and WList. It is not intended to be used directly.

VList is a persistent list data structure described in Phil Bagwell's 2002 paper "Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays". I (David P) call the .NET equivalent "FVList" or "forward VList". In the forward VList, the "beginning" of the list (index 0) is by far the fastest place to insert items.

This is unnatural in .NET, so I also created a second data structure, the "reverse" VList, originally called RVList, in which the end of the list (index Count-1) is the natural location for adding items. To achieve this, the VList sees the same elements as a FVList, but in reverse order.

FWList and WList are the names I picked for the mutable (Writable) variants of FVList and VList.

A persistent list is a list that is normally considered immutable, so adding an item implies creating a new list rather than changing the one you've got. This is fast because persistent lists have a sort of copy-on-write semantics, so that "copying" a list is a trivial O(1) operation, but modifying a list is sometimes quite inefficient. My implementation of VLists presents a mutable IList(of T) interface, but this is only to adhere to .NET Framework conventions. FVList and VList are value types that update their own references to the list when they are modified. Thus, "Copying" a list is done with a simple assignment statement. For example:

VList<int> a = new VList<int>(), b = new VList<int>();
a.Add(1);
a.Add(2);
b = a;             // copy the list
a.Add(3);          // a[0] is 1, a[1] is 2, a[2] is 3
b.Add(97);         // b[0] is 1, b[1] is 2, b[2] is 97

Traditionally, this kind of behavior was accomplished with singly-linked lists, but FVList does it with (in essence) a singly-linked list of arrays and thereby saves memory while allowing some operations to be done faster than they were done with linked lists. In pathological cases, however, FVList can use much more memory than a linked list and degenerate so that its performance characteristics are almost as bad as a linked list. One major problem that comes to mind is if you keep changing the last item:

VList<int> list = new VList<int>();
... add some items to list ...
for(int n;; n++)
    list[list.Count-1] = n;

Unlike, for example, a C++-based FVList implementation, it is impossible for the FVList or VList, which are value types, to know if the list has been "copied" or not. In case the list has been copied, changing any element requires a copy to be made of the VListBlock that contains that element, as well as any subsequent blocks (in this example, only the last block must be copied). Thus, the above example produces a lot of garbage very quickly; in fact the rate of garbage production is (very roughly) proportional to the list length. The performance will be equally bad if you repeatedly remove the last item and then re-add it.

Since this kind of problem tends to get worse as the list gets larger, Phil Bagwell proposed using a two- or three-dimentional list arrangement so that no single block could exceed a certain size. I have not implemented that suggestion due to lack of free time and because I did not understand the details of his suggested implementation, but I have placed a size limit of 1024 elements on any given block. Unfortunately, this means that some operations listed below degrade toward O(N) when the list is large, most notably including the indexer, which requires over 1000 iterations to look up element zero in a VList that has one million elements.

Due to the slow performance you get from operations like this, I decided to implement FWList, a mutable version of the FVList, which I'll discuss later.

Similarly to a persistent linked list,

Adding an item to the front of a VList or the end of a VList is always O(1) in time, and often O(1) in space (though, unlike a linked list, it may be much more)
Removing an item from the front of a VList or the end of a VList is O(1) in time, although space not necessarily reclaimed.
Adding or removing an item at the end of a VList or the front of an VList is O(N) and requires making a copy of the entire list.
Inserting or removing a list of M items at the end of a VList or the front of a VList is O(N + M).
Changing an item at an arbitrary position should be avoided, as it performs as poorly as inserting or removing an item at that position.

VLists, however, offer some operations that singly-linked lists cannot provide efficiently:

Access by index averages O(1) in ideal conditions
Getting the list length is typically O(log N), but O(1) in my version
If a sublist points somewhere within a larger list, its index within the larger list can be obtained in between O(1) and O(log N) time. Consequently, reverse enumeration is possible without creating a temporary stack or list.

Also, VLists can (in the best cases) store data almost as compactly as ordinary arrays.

I suspect FVList(of T) and VList(of T) almost always outperforms LinkedList(of T) in both time and space, if you are always adding and removing items at the correct end of the list. And it should perform as well as List(of T) in some situations while providing an illusion of immutability that List(of T) can't. For lists of 0 to 2 items, FVList and VList use less space than List(of T) (in fact, no object is allocated for an empty FVList or VList.)

The FWList is built on the same foundation as the FVList (a linked list of VListBlock objects whose size increases exponentially), but it allows you to modify the list just like List<T>. FWList is a hybrid mutable-immutable data structure: a single list can be partly mutable and partly immutable. More specifically, a FWList is conceptually divided into two "halves": the front half is mutable, and the tail half is immutable. The two halves need not be the same size (in fact, very often one half is zero-size).

Because some or all of a FWList can be immutable, a VList can be converted to a FWList, or vice versa, in typically O(log N) time. If you modify a FWList after calling its ToFVList() method, a portion of the list is first copied into a mutable block and then modified, and this copy operation typically takes O(N) time.

WList is like FWList except that new items are added at index Count instead of index zero. The head of a FWList is at index 0 and is returned from the First property; the head of an WList is at index Count-1 and is returned from the Last property.

VListBlock implements a single "node" or "sub-array" within a VList. It contains a fixed-size array. When adding a new item to a VListBlock that is already full, a new empty VListBlock is created (with a larger array), whose _prior reference points to the old VListBlock. See Phil Bagwell's paper (or Wikipedia) for details.

VListBlock adds one new member to the structure Phil Bagwell described, PriorCount, a count of elements in other (smaller) lists to which this list is linked. This makes TotalCount an O(1) operation instead of O(log N), which is necessary so that VList[i] and WList[i] are O(1) on average.

Independent instances of FVList, VList, FWList and WList can be accessed from independent threads even though they may share some of the same memory. Individual instances of these objects, however, are not synchronized.

A few LINQ-style methods like Select and Where are implemented on the four data structures. These are provided to optimize functional code that takes an input list and produces an output list, but might not actually change the list. If all, or the tail, of the output is the same as the output, then the output list will share memory with the input list.

Note that unlike LINQ methods, these methods are greedy. They perform the requested operation immediately, not as-needed.

Template Parameters

T	The type of elements in the list

Properties
bool	IsMutable `[get]`
	Returns true if part or all of the block is mutable. More...

abstract int	PriorCount `[get]`
	Returns the number of immutable items in all previous blocks. More...

abstract FVList< T >	Prior `[get]`
	Returns a FVList representing the tail of the chain of VListBlocks. More...

VListBlock< T >	PriorBlock `[get]`

bool	PriorIsOwned `[get]`
	Returns true if this block has exclusive ownership of mutable items in the prior block. Returns false if the prior block is entirely immutable, if we don't have ownership, or if there is no prior block. More...

int	ImmCount `[get]`
	Gets the number of immutable elements in-use in our local array. More...

int	TotalCount `[get]`
	Returns the number of immutable elements in-use in the entire chain More...

abstract int	Capacity `[get]`
	Returns the maximum number of elements in this block More...

abstract T	this[int localIndex] `[get, set]`
	Gets/sets the specified value at the specified index of this block's array, or, if localIndex is negative, searches recursively in previous blocks for the desired index. More...

int	ChainLength `[get]`

Public Member Functions
abstract T	FGet (int index, int localCount)
	Gets an item at distance 'index' from the front (beginning of an FVList) More...

abstract bool	FGet (int index, int localCount, ref T value)

abstract T	RGet (int index, int localCount)
	Gets an item at distance 'index' from the back (beginning of a VList) More...

abstract bool	RGet (int index, int localCount, ref T value)

abstract VListBlock< T >	Add (int localCount, T item)
	Inserts a new item at the "front" of a FVList where localCount is the number of items currently in the FVList's first block. More...

abstract FVList< T >	SubList (int localIndex)
	Returns a list in which this[localIndex-1] is the first item. Nonpositive indexes are allowed and refer to prior lists; SubList returns an empty list if localIndex is so low that it goes past the back of the list. More...

FVList< T >	ReplaceAt (int localCount, T item, int distanceFromFront)
	Replaces an item in a FVList with another, where localCount is the number of items in the FVList's first block and distanceFromFront is the element index to replace (0=front). More...

FVList< T >	RemoveAt (int localCount, int distanceFromFront)
	Removes the specified number of items from a FVList where localCount is the number of items in the FVList's first block, distanceFromFront is the first removal position (minimum 0) and count is the number of items to remove. Of course, the terminology used here is to be understood in the context of a FVList (in which items are inserted at the front of the list). More...

FVList< T >	RemoveRange (int localCount, int distanceFromFront, int count)

abstract void	MuClear (int localCountWithMutables)
	Clears all mutable items in this chain, and clears the mutable flag. If this block owns mutable items in prior blocks, they are cleared too. More...

abstract T	Front (int localCount)
	Returns the "front" item in a FVList/FWList associated with this block (or back item of a VList) where localCount is the number of items in the FVList's first block. More...

virtual FVList< T >	Where (int _localCount, Func< T, bool > filter, WListProtected< T > forWList)

virtual FVList< T >	SelectMany (int _localCount, Func< T, IReadOnlyList< T >> map, bool isRList, WListProtected< T > forWList)

virtual FVList< T >	SmartSelect (int _localCount, Func< T, T > map, WListProtected< T > forWList)

Static Public Member Functions
static VListBlock< T >	Add (VListBlock< T > self, int localCount, T item)
	Adds an item to the "front" of an immutable FVList. More...

static FVList< T >	SubList (VListBlock< T > self, int localCount, int offset)

static FVList< T >	TailOf (FVList< T > list)

static VListBlock< T >	Insert (VListBlock< T > self, int localCount, T item, int distanceFromFront)
	Inserts a new item in a FVList where localCount is the number of items in the FVList's first block and distanceFromFront is the insertion position (0=front). More...

static FVList< T >	InsertRange (VListBlock< T > self, int localCount, IReadOnlyList< T > items, int distanceFromFront, bool isRVList)
	Inserts a list of items in the middle of a FVList, where localCount is the number of items in the FVList's first block and distanceFromFront is the insertion position (0=front). More...

static VList< T >	AddRange (VListBlock< T > self, int localCount, IEnumerator< T > items)
	Adds a list of items to an immutable VList (not a FVList). More...

static FVList< T >	AddRange (VListBlock< T > self, int localCount, IReadOnlyList< T > items, bool isRVList)
	Adds a list of items to an immutable FVList. More...

static FVList< T >	AddRange (VListBlock< T > self, int localCount, FVList< T > front, FVList< T > back)
	Adds a range of items to a FVList where localCount is the number of items in the FVList's first block, front points to the beginning of the range to add and back points to the end of the range. More...

static FVList< T >	FindNextBlock (ref FVList< T > subList, FVList< T > list, out int localCountOfSubList)
	Finds the block that comes before 'subList' in the direction of the larger list, 'list'. More...

static VList< T >	FindNextBlock (ref VList< T > subList, VList< T > list, out int localCountOfSubList)

static FVList< T >	BackUpOnce (FVList< T > subList, FVList< T > list)

static VList< T >	BackUpOnce (VList< T > subList, VList< T > list)

static FVList< T >	EnsureImmutable (VListBlock< T > self, int localCount)
	Returns an immutable FVList with the specified parameters, modifying blocks if necessary. More...

static void	EnsureMutable (WListProtected< T > w, int mutablesNeeded)
	Ensures that at least the specified number of items at the front of a FWList or WList are mutable and owned by the list. More...

static int	MutableCount (WListProtected< T > w)

static void	MuAdd (WListProtected< T > w, T item)

static void	MuAddEmpty (WListProtected< T > w, int count)

static void	MuAddEmpty (WListProtected< T > w, int count, int newBlockSizeLimit)
	Adds empty item(s) to the front of the list. More...

static void	MuMove (WListProtected< T > w, int dffFrom, int dffTo, int count)
	Moves a series of elements from one location to another in a mutable block. More...

static void	MuRemoveFront (WListProtected< T > w, int count)

static T[]	ToArray (VListBlock< T > self, int localCount, bool isRList)
	Converts any kind of FVList to an array, quickly. More...

static FVList< T >	Transform (VListBlock< T > _block, int _localCount, VListTransformer< T > x, bool isRList, WListProtected< T > forWList)
	Transforms a list (combines filtering with selection and more). More...

Protected Member Functions
VListBlock< T >	AddRange (FVList< T > front, FVList< T > back)
	Appends a range of items to the "front" of this block. More...

void	MuAddEmpty2 (WListProtected< T > w, int count, int newBlockSizeLimit)

abstract void	BlockToArray (T[] array, int arrayOffset, int localCount, bool isRList)

bool	IsSame (T old, Maybe< T > @new)

Static Protected Member Functions
static int	MuAllocBlock (WListProtected< T > w, int newBlockSizeLimit)
	Used by MuAddEmpty to allocate an empty mutable block. More...

static FVList< T >	MakeResult (VListBlock< T > _block, int _localCount, WListProtected< T > forWList)

static FVList< T >	MakeResult (T item, WListProtected< T > forWList)

static FVList< T >	MakeResult (T _1, T _2, WListProtected< T > forWList)

Protected fields
int	_immCount
	number of immutable elements in our local array, plus a "mutable" flag in bit 30. More...

Protected static fields
const int	MutableFlag = 0x40000000

const int	ImmCountMask = MutableFlag - 1

Member Function Documentation

◆ Add() [1/2]

abstract VListBlock<T> Loyc.Collections.VListBlock< T >.Add	(	int	localCount,
		T	item
	)

pure virtual

Inserts a new item at the "front" of a FVList where localCount is the number of items currently in the FVList's first block.

Implemented in Loyc.Collections.VListBlockArray< T >, and Loyc.Collections.VListBlockOfTwo< T >.

Referenced by Loyc.Collections.VList< Loyc.Syntax.LNode >.Add(), Loyc.Collections.FVList< T >.Add(), Loyc.Collections.VListBlock< T >.AddRange(), and Loyc.Collections.VListBlock< T >.Insert().

◆ Add() [2/2]

static VListBlock<T> Loyc.Collections.VListBlock< T >.Add	(	VListBlock< T >	self,
		int	localCount,
		T	item
	)

inlinestatic

Adds an item to the "front" of an immutable FVList.

◆ AddRange() [1/4]

VListBlock<T> Loyc.Collections.VListBlock< T >.AddRange	(	FVList< T >	front,
		FVList< T >	back
	)

inlineprotected

Appends a range of items to the "front" of this block.

Returns: This block, or a new block if a new block had to be allocated.

This method is for use by immutable VLists only.

References Loyc.Collections.VListBlock< T >._immCount, Loyc.Collections.VListBlock< T >.Add(), and Loyc.Collections.VListBlock< T >.IsMutable.

◆ AddRange() [2/4]

static FVList<T> Loyc.Collections.VListBlock< T >.AddRange	(	VListBlock< T >	self,
		int	localCount,
		FVList< T >	front,
		FVList< T >	back
	)

inlinestatic

Adds a range of items to a FVList where localCount is the number of items in the FVList's first block, front points to the beginning of the range to add and back points to the end of the range.

Returns: A new list with the specified range added to it.

back.Front is NOT included in the range (in fact back can be an empty list) but front.Front is included unless front is also empty.

The elements of the range are inserted in "reverse" (from back to front) so that the order of the elements in the range is preserved (adding them front-first to our front would reverse their order).

This method is for use by immutable VLists only.

References Loyc.Collections.VListBlock< T >._immCount, Loyc.Collections.VListBlock< T >.Add(), Loyc.Collections.VListBlock< T >.AddRange(), and Loyc.Collections.FVList< T >.First.

◆ AddRange() [3/4]

static VList<T> Loyc.Collections.VListBlock< T >.AddRange	(	VListBlock< T >	self,
		int	localCount,
		IEnumerator< T >	items
	)

inlinestatic

Adds a list of items to an immutable VList (not a FVList).

This method is for use by immutable RVLists only.

References Loyc.Collections.VListBlock< T >.Add().

Referenced by Loyc.Collections.VListBlock< T >.AddRange(), Loyc.Collections.VListBlock< T >.Insert(), and Loyc.Collections.VListBlock< T >.InsertRange().

◆ AddRange() [4/4]

static FVList<T> Loyc.Collections.VListBlock< T >.AddRange	(	VListBlock< T >	self,
		int	localCount,
		IReadOnlyList< T >	items,
		bool	isRVList
	)

inlinestatic

Adds a list of items to an immutable FVList.

This method is for use by immutable VLists only.

References Loyc.Collections.VListBlock< T >.Add().

◆ EnsureImmutable()

static FVList<T> Loyc.Collections.VListBlock< T >.EnsureImmutable	(	VListBlock< T >	self,
		int	localCount
	)

inlinestatic

Returns an immutable FVList with the specified parameters, modifying blocks if necessary.

Parameters

localCount Number of items in 'self' that belong to the list that you want to make immutable. Nonpositive values of localCount are allowed and refer to blocks prior to 'self'.

This method may change self and/or other blocks in the chain so that the returned FVList contains no mutable items.

References Loyc.Collections.VListBlock< T >._immCount, Loyc.Collections.VListBlock< T >.ImmCount, Loyc.Collections.VListBlock< T >.IsMutable, Loyc.Collections.VListBlock< T >.Prior, and Loyc.Collections.VListBlock< T >.PriorIsOwned.

Referenced by Loyc.Collections.WListProtected< T >.ToFVList(), Loyc.Collections.WList< Loyc.Syntax.LNode >.ToFWList(), Loyc.Collections.WListProtected< T >.ToVList(), Loyc.Collections.FWList< T >.ToWList(), and Loyc.Collections.VListBlock< T >.Transform().

◆ EnsureMutable()

static void Loyc.Collections.VListBlock< T >.EnsureMutable	(	WListProtected< T >	w,
		int	mutablesNeeded
	)

inlinestatic

Ensures that at least the specified number of items at the front of a FWList or WList are mutable and owned by the list.

Parameters

mutablesNeeded Number of mutable items required.

Referenced by Loyc.Collections.WListProtected< T >.SetAt().

◆ FGet()

abstract T Loyc.Collections.VListBlock< T >.FGet	(	int	index,
		int	localCount
	)

pure virtual

Gets an item at distance 'index' from the front (beginning of an FVList)

FGet and RGet were added as an optimization, to reduce the minimum number of virtual calls from 2 to 1 and to decrease the number of calculations involved in looking up an item.

Implemented in Loyc.Collections.VListBlockArray< T >, and Loyc.Collections.VListBlockOfTwo< T >.

◆ FindNextBlock()

static FVList<T> Loyc.Collections.VListBlock< T >.FindNextBlock	(	ref FVList< T >	subList,
		FVList< T >	list,
		out int	localCountOfSubList
	)

inlinestatic

Finds the block that comes before 'subList' in the direction of the larger list, 'list'.

Parameters

subList	Sublist of list, or an empty list.
list	The larger, outer list. Can be an empty list if subList is empty.
localCountOfSubList	The value of r._block.Prior._localCount where r is the return value, or, if r is empty, the value of list._localCount.

Returns: The list prior to subList, or an empty block if (1) list and subList are in the same block (2) list._localCount==0 and list._block.Prior is in the same block as subList

Because of the copy-causing-sharing-failure problem (described in a comment in RVListTests.TestSublistProblem()), FindNextBlock may have to change subList in certain cases so that it really is a sublist of list. Therefore it is a ref argument.

References Loyc.Localize.Localized().

◆ Front()

abstract T Loyc.Collections.VListBlock< T >.Front ( int localCount )

pure virtual

Returns the "front" item in a FVList/FWList associated with this block (or back item of a VList) where localCount is the number of items in the FVList's first block.

Implemented in Loyc.Collections.VListBlockArray< T >, and Loyc.Collections.VListBlockOfTwo< T >.

◆ Insert()

static VListBlock<T> Loyc.Collections.VListBlock< T >.Insert	(	VListBlock< T >	self,
		int	localCount,
		T	item,
		int	distanceFromFront
	)

inlinestatic

Inserts a new item in a FVList where localCount is the number of items in the FVList's first block and distanceFromFront is the insertion position (0=front).

Exceptions

IndexOutOfRangeException distanceFromFront was out of range.

Returns: The block resulting from the insert (may or may not be 'this')

This method is for use by immutable VLists only.

References Loyc.Collections.VListBlock< T >.Add(), Loyc.Collections.VListBlock< T >.AddRange(), and Loyc.Collections.VListBlock< T >.PriorCount.

◆ InsertRange()

static FVList<T> Loyc.Collections.VListBlock< T >.InsertRange	(	VListBlock< T >	self,
		int	localCount,
		IReadOnlyList< T >	items,
		int	distanceFromFront,
		bool	isRVList
	)

inlinestatic

Inserts a list of items in the middle of a FVList, where localCount is the number of items in the FVList's first block and distanceFromFront is the insertion position (0=front).

Parameters

isRVList Indicates the insertion order. If isRVList==true, the items[0] is inserted first (which is appropriate for a VList), otherwise it is inserted last (which is appropriate for a FVList)

Exceptions

IndexOutOfRangeException distanceFromFront was out of range.

Returns: The FVList containing the inserted items.

This method is for use by immutable VLists only.

References Loyc.Collections.VListBlock< T >.AddRange(), and Loyc.Collections.VListBlock< T >.PriorCount.

◆ MuAddEmpty()

static void Loyc.Collections.VListBlock< T >.MuAddEmpty	(	WListProtected< T >	w,
		int	count,
		int	newBlockSizeLimit
	)

inlinestatic

Adds empty item(s) to the front of the list.

Parameters

w	List that needs items
count	Number of items to add
newBlockSizeLimit	Limit on size of new block(s); normally VListBlockArray.MAX_BLOCK_LEN (this parameter is used by EnsureMutable()).

This method doesn't actually clear the items, because all items that are not in use should already have been set to default(T).

◆ MuAllocBlock()

static int Loyc.Collections.VListBlock< T >.MuAllocBlock	(	WListProtected< T >	w,
		int	newBlockSizeLimit
	)

inlinestaticprotected

Used by MuAddEmpty to allocate an empty mutable block.

Returns: Capacity of the new block

w is changed to point to the new block (w._localCount is set to 0)

◆ MuClear()

abstract void Loyc.Collections.VListBlock< T >.MuClear ( int localCountWithMutables )

pure virtual

Clears all mutable items in this chain, and clears the mutable flag. If this block owns mutable items in prior blocks, they are cleared too.

Clearing items is unnecessary if ImmCount is zero, as there there are no shared copies and the caller is going to discard the block, so it'll be garbage anyway.

Implemented in Loyc.Collections.VListBlockArray< T >, and Loyc.Collections.VListBlockOfTwo< T >.

◆ MuMove()

static void Loyc.Collections.VListBlock< T >.MuMove	(	WListProtected< T >	w,
		int	dffFrom,
		int	dffTo,
		int	count
	)

inlinestatic

Moves a series of elements from one location to another in a mutable block.

Parameters

w	List to modify
dffFrom	Distance from front of the beginning of the block to move
dffTo	Distance from front of destination location
count	Number of elements to copy

References Loyc.Collections.VListBlock< T >.SubList(), and Loyc.Collections.FVList< T >.Tail.

◆ RemoveAt()

FVList<T> Loyc.Collections.VListBlock< T >.RemoveAt	(	int	localCount,
		int	distanceFromFront
	)

inline

Removes the specified number of items from a FVList where localCount is the number of items in the FVList's first block, distanceFromFront is the first removal position (minimum 0) and count is the number of items to remove. Of course, the terminology used here is to be understood in the context of a FVList (in which items are inserted at the front of the list).

Returns: The modified list.

This method is for use by immutable VLists only.

◆ ReplaceAt()

FVList<T> Loyc.Collections.VListBlock< T >.ReplaceAt	(	int	localCount,
		T	item,
		int	distanceFromFront
	)

inline

Replaces an item in a FVList with another, where localCount is the number of items in the FVList's first block and distanceFromFront is the element index to replace (0=front).

Returns: The list resulting from the change. Note that this operation is inefficient; it aways allocates a new block.

This method is for use by immutable VLists only.

References Loyc.Collections.FVList< T >.Add(), Loyc.Collections.VListBlock< T >.PriorCount, and Loyc.Collections.VListBlock< T >.SubList().

◆ RGet()

abstract T Loyc.Collections.VListBlock< T >.RGet	(	int	index,
		int	localCount
	)

pure virtual

Gets an item at distance 'index' from the back (beginning of a VList)

Implemented in Loyc.Collections.VListBlockArray< T >, and Loyc.Collections.VListBlockOfTwo< T >.

◆ SubList()

abstract FVList<T> Loyc.Collections.VListBlock< T >.SubList ( int localIndex )

pure virtual

Returns a list in which this[localIndex-1] is the first item. Nonpositive indexes are allowed and refer to prior lists; SubList returns an empty list if localIndex is so low that it goes past the back of the list.

Warning: Normally FVList can only contain a reference to an immutable list, but this method can return a reference that includes mutable items.

Implemented in Loyc.Collections.VListBlockArray< T >, and Loyc.Collections.VListBlockOfTwo< T >.

Referenced by Loyc.Collections.VListBlock< T >.MuMove(), Loyc.Collections.VListBlock< T >.ReplaceAt(), and Loyc.Collections.VListBlock< T >.Transform().

◆ ToArray()

static T [] Loyc.Collections.VListBlock< T >.ToArray	(	VListBlock< T >	self,
		int	localCount,
		bool	isRList
	)

inlinestatic

Converts any kind of FVList to an array, quickly.

Referenced by Loyc.Collections.FVList< T >.ToArray(), Loyc.Collections.FWList< T >.ToArray(), Loyc.Collections.WList< Loyc.Syntax.LNode >.ToArray(), and Loyc.Collections.VList< Loyc.Syntax.LNode >.ToArray().

◆ Transform()

static FVList<T> Loyc.Collections.VListBlock< T >.Transform	(	VListBlock< T >	_block,
		int	_localCount,
		VListTransformer< T >	x,
		bool	isRList,
		WListProtected< T >	forWList
	)

inlinestatic

Transforms a list (combines filtering with selection and more).

Parameters

x	Method to apply to each item in the list

Returns: A list formed from transforming all items in the list

See the documentation of FVList.Transform() for more information.

References Loyc.Collections.VListBlock< T >._immCount, Loyc.Collections.FVList< T >.Add(), Loyc.Collections.VListBlock< T >.EnsureImmutable(), Loyc.Collections.VListBlock< T >.PriorCount, and Loyc.Collections.VListBlock< T >.SubList().

Referenced by Loyc.Collections.WList< Loyc.Syntax.LNode >.Transform(), Loyc.Collections.FWList< T >.Transform(), Loyc.Collections.VList< Loyc.Syntax.LNode >.Transform(), and Loyc.Collections.FVList< T >.Transform().

Member Data Documentation

◆ _immCount

int Loyc.Collections.VListBlock< T >._immCount

protected

number of immutable elements in our local array, plus a "mutable" flag in bit 30.

Aside from the mutable flag, this value only increases, never decreases.

If the some or all of the block is mutable, _immCount bit 30 is set (0x40000000), and the low bits contain the number of immutable items. In that case the total number of items in use, including mutable items, is only known by the FWList or WList that encapsulates the block.

The mutable flag is part of this field instead of being a separate flag for two reasons: (1) Saving space. A separate boolean would enlarge the object 4 bytes. (2) High-performance thread safety. Instead of using locks, I use interlocked changes to obtain thread safety.

I don't know how fast or slow .NET locking is, but I assume you can't get faster than a single Interlocked.CompareExchange, so I have designed thread safety around _immCount.

I hate trying to guarantee thread safety because I don't know how to prove correctness. I know that thread safety must be considered for at least the following operations:

Adding an item at the end of an immutable VListBlock: two VLists on different threads may try to add an item to the "front" of the same block at the same time.
Reserving mutable items in a list: two threads may do this at once, or an immutable VList may add an item at the same instant.

Interlocked.CompareExchange() is used in both cases, which ensures that only one thread succeeds and any threads that fail do not alter the value of the field.

A mutable block can be made immutable again by clearing bit 30. No interlocked exchange is required for this, since any thread that notices bit 30 is set will not attempt to modify this field in the first place.

We need not worry about thread safety in order to obtain the immutable tail of a list (or equivalently, to remove items from the "front") because that operation doesn't make use of this field (Remember, each instance of VList has its own private _localCount.) Nor do we need to worry about enumerating or modifying an immutable list (the latter is just an illusion, after all).

I have not concerned myself with thread safety when a single VList instance (whether mutable or immutable) is accessed from multiple threads, because doing so is not supported. It occurs to me, however, that there could be security concerns if untrusted code is given access to any kind of VList; e.g. perhaps malicious code could corrupt a VListBlock somehow by exploiting lack of thread safety.

Theoretically you shouldn't modify an FWList/WList while it is being enumerated, but the danger is limited to an incorrect sequence of items being returned from the enumerator; a "subList is not within list" exception is also possible.

Important things to note: (1) once items are switched from mutable to immutable, they can never be made mutable again, since there is no way to know if any immutable VList references still exist. (2) mutable items always belong to exactly one FWList or one WList, but a VListBlock doesn't know what FWList it belongs to. A FWList or WList is detached from its VListBlock when Clear() is called, making the block immutable again. (3) if not all the items in a VListBlock are mutable, then the Prior list is guaranteed to be immutable. In other words, mutable and immutable items are not interleaved; mutable items are always at the "front" and immutable items are always at the "back" (which is the beginning of a VList or end of an FVList). (4) When the mutable flag is set, _immCount appears to be a very large number. Code that uses _immCount directly instead of calling ImmCount is taking advantage of that fact.

Property Documentation

◆ Capacity

abstract int Loyc.Collections.VListBlock< T >.Capacity

get

Returns the maximum number of elements in this block

◆ ImmCount

int Loyc.Collections.VListBlock< T >.ImmCount

get

Gets the number of immutable elements in-use in our local array.

Mutable items are not included in the count.

Referenced by Loyc.Collections.VListBlockArray< T >.Add(), Loyc.Collections.VListBlock< T >.EnsureImmutable(), Loyc.Collections.VListBlockOfTwo< T >.MuClear(), Loyc.Collections.VListBlockArray< T >.MuClear(), and Loyc.Collections.VListBlockOfTwo< T >.SubList().

◆ IsMutable

bool Loyc.Collections.VListBlock< T >.IsMutable

get

Returns true if part or all of the block is mutable.

Referenced by Loyc.Collections.VListBlockArray< T >.Add(), Loyc.Collections.VListBlock< T >.AddRange(), Loyc.Collections.VListBlock< T >.EnsureImmutable(), Loyc.Collections.VListBlockOfTwo< T >.MuClear(), and Loyc.Collections.VListBlockArray< T >.MuClear().

◆ Prior

abstract FVList<T> Loyc.Collections.VListBlock< T >.Prior

get

Returns a FVList representing the tail of the chain of VListBlocks.

Warning: Normally FVList can only contain a reference to an immutable list, but this property may return a reference to a mutable block if the current block is 100% mutable. Be careful with this value, as FVList is not designed to handle mutable contents!

Referenced by Loyc.Collections.VListBlock< T >.EnsureImmutable().

◆ PriorCount

abstract int Loyc.Collections.VListBlock< T >.PriorCount

get

Returns the number of immutable items in all previous blocks.

Referenced by Loyc.Collections.VListBlock< T >.Insert(), Loyc.Collections.VListBlock< T >.InsertRange(), Loyc.Collections.VListBlock< T >.ReplaceAt(), and Loyc.Collections.VListBlock< T >.Transform().

◆ PriorIsOwned

bool Loyc.Collections.VListBlock< T >.PriorIsOwned

get

Returns true if this block has exclusive ownership of mutable items in the prior block. Returns false if the prior block is entirely immutable, if we don't have ownership, or if there is no prior block.

This one's hard to explain without a diagram. Note: since there is no independent flag to indicate ownership, the logic in this property relies on the fact that a new mutable block is never created until the prior block is full; if one creates a new mutable block when there is free space but no mutable items allocated in the prior block, this property returns false because it assumes the free space was reserved by some other WList than the list that owns this block.

Referenced by Loyc.Collections.VListBlock< T >.EnsureImmutable(), and Loyc.Collections.VListBlockArray< T >.MuClear().

◆ this[int localIndex]

abstract T Loyc.Collections.VListBlock< T >.this[int localIndex]

getset

Gets/sets the specified value at the specified index of this block's array, or, if localIndex is negative, searches recursively in previous blocks for the desired index.

A FVList computes localIndex as FVList._localCount-1-index.

FVList/VList is responsible for checking that the user's index is valid and throwing IndexOutOfRangeException if not.

The setter can only be called on mutable indices!

◆ TotalCount

int Loyc.Collections.VListBlock< T >.TotalCount

get

Returns the number of immutable elements in-use in the entire chain

Remarks

Properties

Public Member Functions

Static Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected fields

Protected static fields

Member Function Documentation

◆ Add() [1/2]

◆ Add() [2/2]

◆ AddRange() [1/4]

◆ AddRange() [2/4]

◆ AddRange() [3/4]

◆ AddRange() [4/4]

◆ EnsureImmutable()

◆ EnsureMutable()

◆ FGet()

◆ FindNextBlock()

◆ Front()

◆ Insert()

◆ InsertRange()

◆ MuAddEmpty()

◆ MuAllocBlock()

◆ MuClear()

◆ MuMove()

◆ RemoveAt()

◆ ReplaceAt()

◆ RGet()

◆ SubList()

◆ ToArray()

◆ Transform()

Member Data Documentation

◆ _immCount

Property Documentation

◆ Capacity

◆ ImmCount

◆ IsMutable

◆ Prior

◆ PriorCount

◆ PriorIsOwned

◆ this[int localIndex]

◆ TotalCount