sasindex.h File Reference

Shared Address Space B-tree based on binary values including virtual addresses. More...

`#include "sasindexkey.h"`
`#include "sasindexnode.h"`

Go to the source code of this file.

## Typedefs

typedef void * | SASIndex_t
| Handle to an instance of binary index B-tree. More...

## Functions

__C__ SASIndex_t | SASIndexFixedCreate (block_size_t block_size)
| Create a fixed SAS B-Tree of block_size size capacity. More...
__C__ SASIndex_t | SASIndexExpandCreate (SASIndex_t btree)
| Internal function that creates new block of B-Tree nodes for an expanding SAS B-Tree btree. More...
__C__ SASIndex_t | SASIndexCreatePageSize (block_size_t block_size, block_size_t page_size)
| Create a new expanding SAS B-Tree with heap_size size and page_size node size. More...
__C__ SASIndex_t | SASIndexCreate (block_size_t block_size)
| Create a new expanding SAS B-Tree with initial heap_size size and default page_size for nodes. More...
__C__ void | SASIndexDestroy (SASIndex_t btree)
| Destroy the SAS B-Tree btree. More...
__C__ long | SASIndexGetModCount (SASIndex_t btree)
| Return the number or insert/replace/remove operations performed on btree. More...
__C__ long | SASIndexGetModCount_nolock (SASIndex_t btree)
| Return the number or insert/replace/remove operations performed on btree. More...
__C__ SASIndexKey_t * | SASIndexGetMaxKey (SASIndex_t btree)
| Return the maximum key string from btree. More...
__C__ SASIndexKey_t * | SASIndexGetMaxKey_nolock (SASIndex_t btree)
| Return the maximum key string from btree. More...
__C__ SASIndexKey_t * | SASIndexGetMinKey (SASIndex_t btree)
| Return the minimum key string from btree. More...
__C__ SASIndexKey_t * | SASIndexGetMinKey_nolock (SASIndex_t btree)
| Return the minimum key string from btree. More...
__C__ int | SASIndexContainsKey (SASIndex_t btree, SASIndexKey_t *key)
| Return true if the SAS B-Tree btree contains the key key. More...
__C__ int | SASIndexContainsKey_nolock (SASIndex_t btree, SASIndexKey_t *key)
| Return true if the SAS B-Tree btree contains the key key. More...
__C__ void * | SASIndexGet (SASIndex_t btree, SASIndexKey_t *key)
| Return the memory address value associated with key in SAS B-Tree btree. More...
__C__ void * | SASIndexGet_nolock (SASIndex_t btree, SASIndexKey_t *key)
| Return the memory address value associated with key in SAS B-Tree btree. More...
__C__ int | SASIndexIsEmpty (SASIndex_t btree)
| Return true if the SAS B-Tree btree is empty. More...
__C__ int | SASIndexIsEmpty_nolock (SASIndex_t btree)
| Return true if the SAS B-Tree btree is empty. More...
__C__ int | SASIndexPut (SASIndex_t btree, SASIndexKey_t *key, void *value)
| Add a new element value with key key in the SAS B-Tree btree. More...
__C__ int | SASIndexPut_nolock (SASIndex_t btree, SASIndexKey_t *key, void *value)
| Add a new element value with key key in the SAS B-Tree btree. More...
__C__ void * | SASIndexReplace (SASIndex_t btree, SASIndexKey_t *key, void *value)
| Replace the associated value of the element with key key in SAS B-Tree btree with the value value. More...
__C__ void * | SASIndexReplace_nolock (SASIndex_t btree, SASIndexKey_t *key, void *value)
| Replace the associated value of the element with key key in SAS B-Tree btree with the value value. More...
__C__ void * | SASIndexRemove (SASIndex_t btree, SASIndexKey_t *key)
| Remove the key key and its associated value from SAS B-Tree btree. More...
__C__ void * | SASIndexRemove_nolock (SASIndex_t btree, SASIndexKey_t *key)
| Remove the key key and its associated value from SAS B-Tree btree. More...
__C__ SASIndex_t | SASIndexInit (void *btree_block, block_size_t btree_size, block_size_t page_size, int expanding)
| Internal function to initialize storage as a B-tree. More...
__C__ block_size_t | SASIndexAllocSize (SASIndex_t btree)
| Return the page size used for node allocation for btree. More...
__C__ block_size_t | SASIndexFreeSpace (SASIndex_t btree)
| Return the total available node free space for btree. More...

## Detailed Description

Shared Address Space B-tree based on binary values including virtual addresses.

Allocate SAS block storage and manage it as a B-tree data structure using SASIndexKey_t struct as keys which are associated address value. This provides "map" (or association) between a binary value and an arbitrary address (an block or SPH object in SAS storage). One expected usage is to provide the reverse mapping from the address of a SAS block or SPH object back to its human readable label stored in a SASStringBTree_t. This is in fact the mechanism used by the SPHContext_t implementation.

The Index B-tree keeps the binary key data sorted and allows search/insert/delete in logarithmic time. The B-Tree is organized into page-size nodes to improve storage locality for search and minimize paging when very large B-Trees are needed.

A new Index can be constructed using the functions SASIndexCreate, SASIndexExpandCreate, or SASIndexCreatePageSize. The functions differs for the options provides. A SAS block can be initialized as a SBT by using the function SASIndexInit.

SASIndex_t indexBTree;
SASIndexKey_t mykey;
char *myorigdata, *myassocdata;
indexBTree = SASIndexCreate (blockSize);
if (indexBTree)
{ // Use index to associate addresses of myassocdata with myorigdata
SASIndexKeyInitRef(&mykey, myorigdata);
rc = SASIndexPut (indexBTree, &mykey, myassocdata);
if (rc)
{
printf("Associated @%p with @%p in BTree@%p",
myassocdata, myorigdata, stringBTree);
}
}
SASIndexPut
__C__ int SASIndexPut(SASIndex_t btree, SASIndexKey_t *key, void *value)
Add a new element value with key key in the SAS B-Tree btree.
SASIndexCreate
__C__ SASIndex_t SASIndexCreate(block_size_t block_size)
Create a new expanding SAS B-Tree with initial heap_size size and default page_size for nodes.
SASIndex_t
void * SASIndex_t
Handle to an instance of binary index B-tree.
Definition: sasindex.h:109
SASIndexKeyInitRef
static void SASIndexKeyInitRef(SASIndexKey_t *dest, void *value)
Initial a binary key @ destination with a address value.
Definition: sasindexkey.h:169
SASIndexKey_t
Index Key Handle structure for binary index B-trees.
Definition: sasindexkey.h:60

The helper functions SASIndexPut, SASIndexReplace, and SASIndexRemove can be used to insert, replace and remove a string/pointer tuple from SBT. Others useful functions are SASIndexContainsKey, which returns if a key exists; and SASIndexGet, which returns the value of a key.

The enumeration API from sasindexenum.h can be use to iterate over the (in whole or part) of contents of BTree in key order.

The functions above apply SASLock and SASUnlock around each Index operation to insure consistency of the Index.

If at process needs exclusive access or needs to scan or populate an Index quickly, the application can SASLock the SASIndex_t, then use the *_nolock forms of the function above for faster access.

SASIndex_t indexBTree;
SASIndexEnum_t senum;
unsigned long long *keyref;
SASLock (indexBTree, SasUserLock__READ);
senum = SASIndexEnumCreate (index);
if (!senum)
{
printf ("SASIndexEnumCreate (%p) failed", index);
return 1;
}
while (SASIndexEnumHasMore (senum))
{
keyref = (unsigned long long *) SASIndexEnumNext_nolock (senum);
if (keyref)
{
// process reference value associated with next enum
}
}
SASUnlock (indexBTree);
SASIndexEnumCreate
__C__ SASIndexEnum_t SASIndexEnumCreate(SASIndex_t btree)
Create a SASIndexEnum_t enumeration that can be used to iterate over the key space of a SASIndex_t.
SASIndexEnumHasMore
__C__ int SASIndexEnumHasMore(SASIndexEnum_t indexenum)
Return status of a SASIndexEnum_t enumeration.
SASIndexEnumNext_nolock
__C__ void * SASIndexEnumNext_nolock(SASIndexEnum_t indexenum)
Move the enumeration to the next binary BTree Index key entry and return the associated address value...
SASIndexEnum_t
void * SASIndexEnum_t
Handle to an instance of binary BTree Index Enumeration.
Definition: sasindexenum.h:59
SASUnlock
__C__ void SASUnlock(vm_address_t addr)
UnLock a SAS Address.
SASLock
__C__ void SASLock(vm_address_t addr, sas_userlock_request_t lockT)
Lock a SAS Address.

Finally, a created SAS binary B-Tree SASIndex_t can be destroy with SASIndexDestroy.

## Typedef Documentation

## SASIndex_t

typedef void* SASIndex_t

Handle to an instance of binary index B-tree.

The type is SAS_RUNTIME_INDEX

## Function Documentation

## SASIndexAllocSize()

__C__ block_size_t SASIndexAllocSize | ( | SASIndex_t | btree | ) |

Return the page size used for node allocation for btree.

The sas_type_t must be SAS_RUNTIME_INDEX.

Parameters

  btree | Handle the to SASIndex_t.

Returns
  The page size value in bytes.

## SASIndexContainsKey()

__C__ int SASIndexContainsKey | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key
| ) |  |

Return true if the SAS B-Tree btree contains the key key.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a read lock over B-Tree btree. This function searches the B-Tree for a matching key and returns true if found.

Parameters

  btree | Handle to the SASIndex_t.
  key | Null terminated key string to search.

Returns
  1 if the key is within btree or 0 otherwise.

## SASIndexContainsKey_nolock()

__C__ int SASIndexContainsKey_nolock | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key
| ) |  |

Return true if the SAS B-Tree btree contains the key key.

The sas_type_t must be SAS_RUNTIME_INDEX. This function searches the B-Tree for a matching key and returns true if found.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Parameters

  btree | Handle to the SASIndex_t.
  key | Null terminated key string to search.

Returns
  1 if the key is within btree or 0 otherwise.

## SASIndexCreate()

__C__ SASIndex_t SASIndexCreate | ( | block_size_t | block_size | ) |

Create a new expanding SAS B-Tree with initial heap_size size and default page_size for nodes.

Create and initialize a B-Tree. The storage block must be power of two in size and SAS type returned is SAS_RUNTIME_INDEX. The internal page size used is the default one defined in sasalloc.h (4096).

Parameters

  block_size | Size of the B-Tree to create.

Returns
  A handle to created SASIndex_t or 0 if creation fails.

## SASIndexCreatePageSize()

__C__ SASIndex_t SASIndexCreatePageSize | ( | block_size_t | block_size,
|  | block_size_t | page_size
| ) |  |

Create a new expanding SAS B-Tree with heap_size size and page_size node size.

Similar to SASIndexCreate but with additional option to set the internal node page size.

Parameters

  block_size | Size of the B-Tree to create.
  page_size | Size of the internal node pages.

Returns
  A handle to created SASCompoundHeap_t or 0 if creation fails.

## SASIndexDestroy()

__C__ void SASIndexDestroy | ( | SASIndex_t | btree | ) |

Destroy the SAS B-Tree btree.

The type must be SAS_RUNTIME_INDEX. Destroy holds an exclusive write lock while clearing the control blocks and freeing the SAS block (or blocks for a expanding B-Tree).

Parameters

  btree | Handle of the SASIndex_t to be destroyed.

## SASIndexExpandCreate()

__C__ SASIndex_t SASIndexExpandCreate | ( | SASIndex_t | btree | ) |

Internal function that creates new block of B-Tree nodes for an expanding SAS B-Tree btree.

Create a block and initialize it to provide additional B-Tree node space to an existing expanding SAS B-Tree btree. This block is added the internal block list of the B-Tree.

Parameters

  btree | The SAS B-Tree to be expanded by one block.

Returns
  A new SASStringBtree_t handle or 0 if the block allocate or initialization fails.

## SASIndexFixedCreate()

__C__ SASIndex_t SASIndexFixedCreate | ( | block_size_t | block_size | ) |

Create a fixed SAS B-Tree of block_size size capacity.

Create and initialize a B-Tree. The storage block must be power of two in size and the SAS type returned is SAS_RUNTIME_STRINGBTREE. The internal page size used is the default one defined in sasalloc.h (4096).

Parameters

  block_size | Size of the B-Tree to create.

Returns
  A handle to created SASStringBtree_t or 0 if creation fails.

## SASIndexFreeSpace()

__C__ block_size_t SASIndexFreeSpace | ( | SASIndex_t | btree | ) |

Return the total available node free space for btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a write lock while calculating the total node free space from B-Tree.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  The total available free node space in bytes.

## SASIndexGet()

__C__ void * SASIndexGet | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key
| ) |  |

Return the memory address value associated with key in SAS B-Tree btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a read lock over B-Tree btree. This function searches the B-Tree for a matching key and if found, returns the associated memory address value.

Parameters

  btree | Handle to the SASIndex_t.
  key | handle to maximum SASIndexKey_t key to search.

Returns
  The associated memory address with key or 0 if the B-Tree btree does not contain the key or if an error occurs.

## SASIndexGet_nolock()

__C__ void * SASIndexGet_nolock | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key
| ) |  |

Return the memory address value associated with key in SAS B-Tree btree.

The sas_type_t must be SAS_RUNTIME_INDEX. This function searches the B-Tree for a matching key and if found, returns the associated memory address value.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Parameters

  btree | Handle to the SASIndex_t.
  key | handle to maximum SASIndexKey_t key to search.

Returns
  The associated memory address with key or 0 if the B-Tree btree does not contain the key or if an error occurs.

## SASIndexGetMaxKey()

__C__ SASIndexKey_t * SASIndexGetMaxKey | ( | SASIndex_t | btree | ) |

Return the maximum key string from btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a read lock over B-Tree btree. The maximum key is the right most entry of the right most node.

Note
  this value it stored in the header of the SASIndex_t initial block and should never be modified by the application.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  handle to maximum SASIndexKey_t from B-Tree btree or 0 if the B-Tree does not have any key or if an error occurs.

## SASIndexGetMaxKey_nolock()

__C__ SASIndexKey_t * SASIndexGetMaxKey_nolock | ( | SASIndex_t | btree | ) |

Return the maximum key string from btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The maximum key is the right most entry of the right most node.

Note
  this value it stored in the header of the SASIndex_t initial block and should never be modified by the application.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  handle to maximum SASIndexKey_t from B-Tree btree or 0 if the B-Tree does not have any key or if an error occurs.

## SASIndexGetMinKey()

__C__ SASIndexKey_t * SASIndexGetMinKey | ( | SASIndex_t | btree | ) |

Return the minimum key string from btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a read lock over B-Tree btree. The minimum key is the left most entry of the left most node.

Note
  this value it stored in the header of the SASIndex_t initial block and should never be modified by the application.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  handle to maximum SASIndexKey_t from B-Tree btree or 0 if the B-Tree does not have any key or if an error occurs.

## SASIndexGetMinKey_nolock()

__C__ SASIndexKey_t * SASIndexGetMinKey_nolock | ( | SASIndex_t | btree | ) |

Return the minimum key string from btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The minimum key is the left most entry of the left most node.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Note
  this value it stored in the header of the SASIndex_t initial block and should never be modified by the application.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  handle to maximum SASIndexKey_t from B-Tree btree or 0 if the B-Tree does not have any key or if an error occurs.

## SASIndexGetModCount()

__C__ long SASIndexGetModCount | ( | SASIndex_t | btree | ) |

Return the number or insert/replace/remove operations performed on btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a read lock over B-Tree btree. An initialized SAS B-Tree starts with mod count 1 and it is incremented each time a insert/replace/remove operation is performed.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  The number of insert/replace/remove operations performed on btree.

## SASIndexGetModCount_nolock()

__C__ long SASIndexGetModCount_nolock | ( | SASIndex_t | btree | ) |

Return the number or insert/replace/remove operations performed on btree.

The sas_type_t must be SAS_RUNTIME_INDEX. An initialized SAS B-Tree starts with mod count 1 and it is incremented each time a insert/replace/remove operation is performed.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  The number of insert/replace/remove operations performed on btree.

## SASIndexInit()

__C__ SASIndex_t SASIndexInit | ( | void * | btree_block,
|  | block_size_t | btree_size,
|  | block_size_t | page_size,
|  | int | expanding
| ) |  |

Internal function to initialize storage as a B-tree.

An internal function used to initialize the control blocks within the specific storage block block as a SAS binary index B-tree. Both block_size and page_size must be power of two in size and have the same power of two (or better) alignment. The SAS type created is SAS_RUNTIME_STRINGBTREE.

Parameters

  btree_block | Block of allocated SAS storage.
  btree_size | Size of the B-tree within the block.
  page_size | Size of page size to use.
  expanding | boolean indicates if the B-tree is expand or fixed.

Returns
  A handle to the initialized SASIndex_t or 0 if an error occurs.

## SASIndexIsEmpty()

__C__ int SASIndexIsEmpty | ( | SASIndex_t | btree | ) |

Return true if the SAS B-Tree btree is empty.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a read lock over B-Tree btree.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  1 if the B-Tree is not empty or 0 otherwise.

## SASIndexIsEmpty_nolock()

__C__ int SASIndexIsEmpty_nolock | ( | SASIndex_t | btree | ) |

Return true if the SAS B-Tree btree is empty.

The sas_type_t must be SAS_RUNTIME_INDEX.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Parameters

  btree | Handle to the SASIndex_t.

Returns
  1 if the B-Tree is not empty or 0 otherwise.

## SASIndexPut()

__C__ int SASIndexPut | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key,
|  | void * | value
| ) |  |

Add a new element value with key key in the SAS B-Tree btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a write lock over B-Tree btree. This function inserts the key and associated memory address value into the B-Tree. This B-Tree implementation does not allow duplicated key values.

Parameters

  btree | Handle to the SASIndex_t.
  key | Key to use as index for the value.
  value | Memory address to insert in the B-Tree.

Returns
  1 if the operation succeeds or 0 otherwise. For example if the key already exist in this B-Tree.

## SASIndexPut_nolock()

__C__ int SASIndexPut_nolock | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key,
|  | void * | value
| ) |  |

Add a new element value with key key in the SAS B-Tree btree.

The sas_type_t must be SAS_RUNTIME_INDEX. This function inserts the key and associated memory address value into the B-Tree. This B-Tree implementation does not allow duplicated key values.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Parameters

  btree | Handle to the SASIndex_t.
  key | Key to use as index for the value.
  value | Memory address to insert in the B-Tree.

Returns
  1 if the operation succeeds or 0 otherwise. For example if the key already exist in this B-Tree.

## SASIndexRemove()

__C__ void * SASIndexRemove | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key
| ) |  |

Remove the key key and its associated value from SAS B-Tree btree.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a write lock over B-Tree btree. This function searches the B-Tree for a matching key and if found, removes the key and associates value from this B-Tree.

Note
  removing the key and associated value from the B-Tree does not remove or alter the data at that memory address. It only removes the associated between the and key and the address from this B-Tree.

Parameters

  btree | Handle to the SASIndex_t.
  key | Key value to be removed from this B-Tree.

Returns
  The address of the previous item or 0 if an error occurs.

## SASIndexRemove_nolock()

__C__ void * SASIndexRemove_nolock | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key
| ) |  |

Remove the key key and its associated value from SAS B-Tree btree.

The sas_type_t must be SAS_RUNTIME_INDEX. This function searches the B-Tree for a matching key and if found, removes the key and associates value from this B-Tree.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Note
  removing the key and associated value from the B-Tree does not remove or alter the data at that memory address. It only removes the associated between the and key and the address from this B-Tree.

Parameters

  btree | Handle to the SASIndex_t.
  key | Key value to be removed from this B-Tree.

Returns
  The address of the previous item or 0 if an error occurs.

## SASIndexReplace()

__C__ void * SASIndexReplace | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key,
|  | void * | value
| ) |  |

Replace the associated value of the element with key key in SAS B-Tree btree with the value value.

The sas_type_t must be SAS_RUNTIME_INDEX. The function holds a write lock over B-Tree btree. This function searches the B-Tree for a matching key and if found, replaces the associated memory address value with value, and returns the previous associated value.

Parameters

  btree | Handle to the SASIndex_t.
  key | Key to use as index for the value.
  value | Memory address to replace in the B-Tree.

Returns
  The address of the previous associated value for the matching key, or 0 if an error occurs.

## SASIndexReplace_nolock()

__C__ void * SASIndexReplace_nolock | ( | SASIndex_t | btree,
|  | SASIndexKey_t * | key,
|  | void * | value
| ) |  |

Replace the associated value of the element with key key in SAS B-Tree btree with the value value.

The sas_type_t must be SAS_RUNTIME_INDEX. This function searches the B-Tree for a matching key and if found, replaces the associated memory address value with value, and returns the previous associated value.

This nolock form should only be used when the referenced SASIndex_t is known to be locked by the application or contained within a larger structure with a controlling lock.

Parameters

  btree | Handle to the SASIndex_t.
  key | Key to use as index for the value.
  value | Memory address to replace in the B-Tree.

Returns
  The address of the previous associated value for the matching key, or 0 if an error occurs.