Enhanced C#
Language of your choice: library documentation
Properties | Public Member Functions | Static Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected fields | List of all members
Loyc.Collections.VListBlock< T > Class Template Referenceabstract

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


Source file:
Inheritance diagram for Loyc.Collections.VListBlock< T >:
Loyc.Collections.VListBlockArray< T > Loyc.Collections.VListBlockOfTwo< 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,

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

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
TThe 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, IList< 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, IList< 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, IList< 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...
 
const int MutableFlag = 0x40000000
 
const int ImmCountMask = MutableFlag - 1
 

Member Function Documentation

abstract VListBlock<T> Loyc.Collections.VListBlock< T >.Add ( int  localCount,
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(), and Loyc.Collections.VListBlock< T >.AddRange().

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

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

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.

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

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

Adds a list of items to an immutable FVList.

This method is for use by immutable VLists only.

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 >.AddRange(), and Loyc.Collections.FVList< T >.First.

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, and Loyc.Collections.VListBlock< T >.Add().

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
localCountNumber 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 >.Prior, and Loyc.Collections.VListBlock< T >.PriorIsOwned.

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

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
mutablesNeededNumber of mutable items required.

Referenced by Loyc.Collections.FWList< T >.AdjustWListIndex(), Loyc.Collections.WList< Loyc.Syntax.LNode >.AdjustWListIndex(), Loyc.Collections.WListProtected< T >.IndexOf(), and Loyc.Collections.WListProtected< T >.SetAt().

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 >.

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
subListSublist of list, or an empty list.
listThe larger, outer list. Can be an empty list if subList is empty.
localCountOfSubListThe 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().

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 >.

static VListBlock<T> Loyc.Collections.VListBlock< T >.Insert ( VListBlock< T >  self,
int  localCount,
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
IndexOutOfRangeExceptiondistanceFromFront 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.VListBlockOfTwo< T >.Add(), and Loyc.Collections.VListBlock< T >.AddRange().

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

static FVList<T> Loyc.Collections.VListBlock< T >.InsertRange ( VListBlock< T >  self,
int  localCount,
IList< 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
isRVListIndicates 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
IndexOutOfRangeExceptiondistanceFromFront was out of range.
Returns
The FVList containing the inserted items.

This method is for use by immutable VLists only.

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

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
wList that needs items
countNumber of items to add
newBlockSizeLimitLimit 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).

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)

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 >.

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
wList to modify
dffFromDistance from front of the beginning of the block to move
dffToDistance from front of destination location
countNumber of elements to copy

References Loyc.Collections.FVList< T >.Tail.

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

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.

FVList<T> Loyc.Collections.VListBlock< T >.ReplaceAt ( int  localCount,
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().

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 >.

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 >.

static T [] Loyc.Collections.VListBlock< T >.ToArray ( VListBlock< T >  self,
int  localCount,
bool  isRList 
)
inlinestatic
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
xMethod 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(), and Loyc.Collections.VListBlock< T >.PriorCount.

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

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.

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

Property Documentation

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

Returns the maximum number of elements in this block

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.

bool Loyc.Collections.VListBlock< T >.IsMutable
get

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

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().

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

Returns the number of immutable items in all previous blocks.

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

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().

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!

int Loyc.Collections.VListBlock< T >.TotalCount
get

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