ColaStore

Namespace: SnowBank.Collections.CacheOblivious · class

Helper methods used by ColaStore and derived implementations

Methods

FindBetween

static IEnumerable<T> FindBetween<T>(ColaStore<T> store, int count, T begin, bool beginOrEqual, T end, bool endOrEqual, int limit, IComparer<T> comparer)

Enumerates all the elements between two bounds of a store

store — Store to scan
count — Number of elements in the store
begin — Lower bound
beginOrEqual — If true the lower bound is included in the scan
end — Upper bound
endOrEqual — If true the upper bound is included in the scan
limit — Maximum number of elements to return
comparer — Element comparer

FindNext

static int FindNext<T>(ColaStore<T> store, int count, T value, bool orEqual, IComparer<T> comparer, out int offset, out T result)

Search for the smallest element that is larger than a reference element

store — Item store
value — Reference element
orEqual — If true, return the position of the value itself if it is found. If false, return the position of the closest value that is smaller.
offset — Receive the offset within the level of the next element, or 0 if not found
result — Receive the value of the next element, or default(T) if not found

Returns: Level of the next element, or -1 if result was already the largest

FindPrevious

static int FindPrevious<T>(ColaStore<T> store, int count, T value, bool orEqual, IComparer<T> comparer, out int offset, out T result)

Search for the largest element that is smaller than a reference element

store — Item store
value — Reference element
orEqual — If true, return the position of the value itself if it is found. If false, return the position of the closest value that is smaller.
offset — Receive the offset within the level of the previous element, or 0 if not found
result — Receive the value of the previous element, or default(T) if not found

Returns: Level of the previous element, or -1 if result was already the smallest

FromIndex

static (int, int) FromIndex(int index)

Finds the level that holds an absolute index

index — Absolute index in a COLA array where 0 is the root, 1 is the first item of level 1, and so on

Returns: Level and Offset that contains the specified location.

HighestBit

static int HighestBit(int value)

Returns the position of the highest bit set

LowestBit

static int LowestBit(int value)

Returns the position of the lowest bit set, or 0 if all bits are cleared

This method returns if value is

MapLocationToOffset

static int MapLocationToOffset(int count, int level, int offset)

Computes the absolute location from a (level, offset) pair (in the allocated levels)

MapOffsetToIndex

static int MapOffsetToIndex(int count, int arrayIndex)

Computes the absolute index from a value offset (in the allocated levels)

count — Number of items in the COLA array
arrayIndex — Offset of the value in the allocated levels of the COLA array, with 0 being the oldest (first item of the last allocated level)

Returns: Absolute index of the location where that value would be stored in the COLA array (from the top)

MapOffsetToLocation

static (int, int) MapOffsetToLocation(int count, int arrayIndex)

Computes the (level, offset) pair from a value offset (in the allocated levels)

count — Number of items in the COLA array
arrayIndex — Offset of the value in the allocated levels of the COLA array, with 0 being the oldest (first item of the last allocated level)

Returns: Absolute index of the location where that value would be stored in the COLA array (from the top)

ToIndex

static int ToIndex(int level, int offset)

Convert a (level, offset) pair into the corresponding absolute index

level — Level of the location (0 for the root)
offset — Offset within the level of the location

Returns: Absolute index where 0 is the root, 1 is the first item of level 1, and so on