Generic b-tree structure. Declaration macro for a b-tree structure named 'name', containing elem of type 'type', and having 'nb' maximum elem per node ('nb' odd and greater or equal to 3)

Generic b-tree structure. Definition macro for a b-tree structure named 'name', containing elem of type 'type', and having 'nbElem' maximum elem per node Create a b-tree

Input argument(s):

cmp: comparison function to sort elem

Output and side effect(s):

Return a b-tree containing elem of type 'type'

Allocate memory for a new b-tree and create it

Output and side effect(s):

Return a b-tree containing elem of type 'type'

Exception(s):

May raise CapyExc_MallocFailed.

Free the memory used by a b-tree.

Input argument(s):

that: the b-tree to free

Free the memory used by a pointer to a b-tree and reset '*that' to NULL

Input argument(s):

that: a pointer to the b-tree to free

Get the leaf node where an element should be

Input argument(s):

elem: the element

Output and side effect(s):

Traverse the BTree and return the first leaf that accomodate the element.

Split the root node in two

Output and side effect(s):

If the root node has less than three elements nothing happens. Else, the elements of the root node are split into two new nodes, one for those lower than the median element in the root and the other for those greater than the median element in the root. The median element remains in the root and the new nodes become its prior and posterior childs.

Insert a node into the elements of the tree

Input argument(s):

node: the node to insert

Output and side effect(s):

The node is inserted. This may trigger a restructuration of the BTree which invalidate the 'that' pointer. Then, this method returns 'that' if it's still valid, or its parent if 'that' doesn't exist any more.

Add an element to the b-tree

Input argument(s):

elem: the element to add

Rebalance the tree to ensure it has the required minimum number of elements

Output and side effect(s):

The tree is rebalanced.

Merge the children of a node into that node.

Output and side effect(s):

The children are merged into the node if possible. If not, nothing happen.

Remove an element at a given position in a node of a b-tree

Input argument(s):

iElem: the position of the element to remove

Output and side effect(s):

The element is removed.

Remove an element from the b-tree

Input argument(s):

elem: the element to remove

Output and side effect(s):

The element is removed if it exists, else nothing happens. If the element is removed it is destruct

Find an element in the b-tree

Input argument(s):

elem: the element to find

Output and side effect(s):

If the element is found return a pointer to it, else return null.

Find a node containing an element in the b-tree

Input argument(s):

elem: the element to find

Output and side effect(s):

If the element is actually in the tree, return the node containing the element, else return NULL.

Definition macro calling all the submacros at once for an array structure named 'name', containing 'size_' elements of type 'type'