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

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

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);
     }
  }

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);

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

Typedef Documentation

typedef void* SASIndex_t

Handle to an instance of binary index B-tree.

The type is SAS_RUNTIME_INDEX

Function Documentation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation