Common Lisp Package: B-TREE.IMPLEMENTATION

README:

FUNCTION

Public

B-TREE-CLOSE (BTREE)

Close open b-tree.

B-TREE-CREATE (FILESPEC &KEY (MINIMUM-DEGREE 3) (IF-EXISTS ERROR) (BLOCK-SIZE 4096))

Create new file based b-tree to given filespec.

B-TREE-INSERT (BTREE KEY VALUE)

Insert (key, value) pair to b-tree.

B-TREE-OPEN (FILESPEC &KEY (IF-EXISTS OVERWRITE) (IF-DOES-NOT-EXIST ERROR))

Open existing file based b-tree.

B-TREE-PRINT (BTREE &OPTIONAL (STREAM *STANDARD-OUTPUT*))

Write b-tree to stream.

B-TREE-ROOT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

STRING-B-TREE-CREATE (FILESPEC &KEY (MINIMUM-DEGREE 3) (IF-EXISTS ERROR) (BLOCK-SIZE 4096))

Create new file based b-tree to given filespec.

STRING-B-TREE-OPEN (FILESPEC &KEY (IF-EXISTS OVERWRITE) (IF-DOES-NOT-EXIST ERROR))

Open existing file based b-tree.

Undocumented

B-TREE-DELETE (BTREE KEY)

B-TREE-MAX (BTREE &OPTIONAL (START-NODE (B-TREE-ROOT BTREE)))

B-TREE-MIN (BTREE &OPTIONAL (START-NODE (B-TREE-ROOT BTREE)))

SETFB-TREE-ROOT (NEW-VALUE INSTANCE)

MAP-B-TREE (RET-TYPE BTREE FUNC)

Private

ALLOCATE-NODE (BTREE)

Returns swap file offset of allocated block for b-tree node.

B-TREE-KEY-READER (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-KEY-WRITER (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-MAX-CHILDREN (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-MAX-KEYS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-MIN-KEYS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-MINIMUM-DEGREE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-NODE-CHILD-COUNT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-NODE-CONTENTS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-NODE-FILE-POSITION (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-NODE-KEY-COUNT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-REF-FILE-POSITION (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-SWAP-FILE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-VALUE-READER (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-VALUE-WRITER (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

B-TREE-VERSION (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BACKTRACKING-LIST-ITERATOR-CURRENT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BACKTRACKING-LIST-ITERATOR-NEXT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BACKTRACKING-LIST-ITERATOR-PREV (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

COUNT-CHILDREN (BTREE-NODE)

Returns number of children in B-tree node. Children are counted from contents list.

COUNT-KEYS (BTREE-NODE)

Returns number of keys in B-tree node. Keys are counted from contents list.

CURRENT-POSITION (ITERATOR)

Returns iterator's current list position. Returns nil, if iterator is nil or position is at the beginning or end of the list.

CURRENT-VALUE (ITERATOR)

Returns iterator's current value.

EMPTY-P (BTREE-NODE)

Returns t if node has no contents (no keys nor children), nil otherwise.

FIND-CORRECT-CHILD (BTREE-NODE ITEM)

Returns given B-tree node's child.

FREE-NODE (BTREE NODE)

Free allocated B-tree node.

FULL-P (BTREE-NODE BTREE)

Returns t if b-tree node number of keys has reached or exceeded the max keys, nil otherwise.

KEY (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

KEYS-P (BTREE-NODE)

Returns t if btree-node has any keys, nil otherwise.

LEAF-P (BTREE-NODE)

Returns t if B-tree node is a leaf, nil otherwise.

MAX-KEY (CONTENTS)

Returns position of maximum key from contents, or nil, if no key found.

MIN-KEY (CONTENTS)

Returns position of minimum key from contents, or nil, if no key found.

MIN-KEYS-P (BTREE-NODE BTREE)

Returns t if B-tree node has exactly minimum required amount of keys, nil otherwise.

NEXT (ITERATOR)

Advances iterator to next position in list. Returns modified iterator.

NEXT-ITEM (CONTENTS-ITERATOR)

Advances contents iterator to next B-tree item. Returns modified iterator.

NEXT-P (ITERATOR)

Returns t if iterator has next, nil otherwise.

PREV (ITERATOR)

Backtracks iterator to previous position in list. Returns modified iterator.

PREV-P (ITERATOR)

Returns t if iterator has previous, nil otherwise.

READ-B-TREE-ITEM (STREAM KEY-READER VALUE-READER)

Reads and returns B-tree item from stream.

READ-B-TREE-REF (STREAM)

Reads and returns B-tree reference from stream.

READ-HEADER (BTREE)

Reads b-tree header from swap file and fills b-tree structure with read information.

READ-NODE (BTREE BTREE-REF &KEY SKIP-CHECK)

Reads b-tree node from disk. Node is organized on disk so that every second element is child ref and the other is key value pair.

READ-NODE-CONTENTS (STREAM KEY-READER VALUE-READER)

Reads and returns a list of B-tree references and items from stream.

ROOT-P (BTREE-NODE BTREE)

Returns t if node is root of B-tree, nil otherwise.

SEARCH-DELETE-POSITION (KEY BTREE NODE)

Search B-tree node containing the key. The B-tree structure is altered on the way down to prepare item deletion.

SPLIT-ROOT-NODE (BTREE)

Splits root node contents half and creates a new root node.

VALUE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

VALUE-OR-NIL (ITEM)

Returns values value and key of B-tree item or nil if item is nil.

WRITE-HEADER (BTREE)

Writes b-tree header to swap file.

WRITE-NODE (BTREE BTREE-NODE)

Write B-tree node to swap file.

WRITE-ROOT-OFFSET (BTREE)

Write root offset to swap file.

Undocumented

B-TREE-ITEM-P (OBJECT)

SETFB-TREE-KEY-READER (NEW-VALUE INSTANCE)

SETFB-TREE-KEY-WRITER (NEW-VALUE INSTANCE)

B-TREE-MAPPER (BTREE NODE FUNC)

SETFB-TREE-MAX-CHILDREN (NEW-VALUE INSTANCE)

SETFB-TREE-MAX-KEYS (NEW-VALUE INSTANCE)

SETFB-TREE-MIN-KEYS (NEW-VALUE INSTANCE)

SETFB-TREE-MINIMUM-DEGREE (NEW-VALUE INSTANCE)

SETFB-TREE-NODE-CHILD-COUNT (NEW-VALUE INSTANCE)

SETFB-TREE-NODE-CONTENTS (NEW-VALUE INSTANCE)

SETFB-TREE-NODE-FILE-POSITION (NEW-VALUE INSTANCE)

SETFB-TREE-NODE-KEY-COUNT (NEW-VALUE INSTANCE)

B-TREE-NODE-P (OBJECT)

B-TREE-P (OBJECT)

SETFB-TREE-REF-FILE-POSITION (NEW-VALUE INSTANCE)

B-TREE-REF-P (OBJECT)

B-TREE-SEARCHER (BTREE KEY SEARCH-NODE)

SETFB-TREE-SWAP-FILE (NEW-VALUE INSTANCE)

SETFB-TREE-VALUE-READER (NEW-VALUE INSTANCE)

SETFB-TREE-VALUE-WRITER (NEW-VALUE INSTANCE)

SETFB-TREE-VERSION (NEW-VALUE INSTANCE)

SETFBACKTRACKING-LIST-ITERATOR-CURRENT (NEW-VALUE INSTANCE)

SETFBACKTRACKING-LIST-ITERATOR-NEXT (NEW-VALUE INSTANCE)

BACKTRACKING-LIST-ITERATOR-P (OBJECT)

SETFBACKTRACKING-LIST-ITERATOR-PREV (NEW-VALUE INSTANCE)

COPY-B-TREE (INSTANCE)

COPY-B-TREE-ITEM (INSTANCE)

COPY-B-TREE-NODE (INSTANCE)

COPY-B-TREE-REF (INSTANCE)

COPY-BACKTRACKING-LIST-ITERATOR (INSTANCE)

DELETE-FROM-CONTENTS (NODE KEY)

DELETE-FROM-INTERNAL (KEY BTREE NODE)

DELETE-FROM-LEAF (KEY BTREE NODE)

DELETE-FROM-ROOT (KEY BTREE)

DELETE-KEY (KEY BTREE NODE)

ELEMENT-COUNT (BTREE)

ENSURE-B-TREE-NODE (NODE-SPEC BTREE)

ENSURE-CHILD-HAS-MORE-THAN-MIN-KEYS (CHILD PARENT BTREE)

FIND-CHILD-POS (CHILD-OFFSET CONTENTS)

FIND-IMMEDIATE-SIBLINGS (CHILD PARENT)

FIND-MEDIAN-KEY-POSITION (BTREE-NODE)

FIND-PREVIOUS (KEY CONTENTS)

FORMAT-B-TREE-BLOCKS (BTREE)

GET-INSERT-POSITION (BTREE-NODE FOR-KEY)

INITIALIZE-B-TREE (BTREE)

INSERT-ITEM (BTREE-NODE ITEM)

INSERT-TO-NONFULL (BTREE BTREE-NODE ITEM)

INSERT-TO-NONFULL-INTERNAL (BTREE BTREE-NODE ITEM)

INSERT-TO-NONFULL-LEAF (BTREE BTREE-NODE ITEM)

SETFKEY (NEW-VALUE INSTANCE)

MAKE-B-TREE (&KEY ((VERSION DUM158) 1) ((MINIMUM-DEGREE DUM159) 2) ((MIN-KEYS DUM160) 0) ((MAX-KEYS DUM161) 0) ((MAX-CHILDREN DUM162) 0) ((SWAP-FILE DUM163) NIL) ((ROOT DUM164) NIL) ((KEY-WRITER DUM165) #'WRITE-UINT32) ((KEY-READER DUM166) #'READ-UINT32) ((VALUE-WRITER DUM167) #'WRITE-UINT32) ((VALUE-READER DUM168) #'READ-UINT32))

MAKE-B-TREE-BLOCK-FORMATTER

MAKE-B-TREE-ITEM (&KEY ((KEY DUM0) NIL) ((VALUE DUM1) NIL))

MAKE-B-TREE-NODE (&KEY (FILE-POSITION 0) (CONTENTS NIL) (KEY-COUNT (COUNT-IF #'B-TREE-ITEM-P CONTENTS)) (CHILD-COUNT (COUNT-IF #'B-TREE-REF-P CONTENTS)))

MAKE-B-TREE-REF (&KEY ((FILE-POSITION DUM50) 0))

MAKE-BACKTRACKING-LIST-ITERATOR (LIST &AUX (CURRENT NIL) (NEXT LIST) (PREV NIL))

MAX-FINDER (BTREE &OPTIONAL (SEARCH-NODE (B-TREE-ROOT BTREE)))

MERGE-CHILDREN (PREV-REF ITEM NEXT-REF BTREE PARENT-NODE)

MIN-FINDER (BTREE &OPTIONAL (SEARCH-NODE (B-TREE-ROOT BTREE)))

MOVE-KEY-FROM-LEFT-SIBLING (CHILD PARENT LEFT-SIBLING-REF-POS ITEM-ON-LEFT-POS BTREE)

MOVE-KEY-FROM-RIGHT-SIBLING (CHILD PARENT RIGHT-SIBLING-REF-POS ITEM-ON-RIGHT-POS BTREE)

REMOVE-KEYLESS-ROOT (BTREE &AUX (OLD-ROOT (B-TREE-ROOT BTREE)))

REPLACE-WITH-PREDECESSOR (CUR PREV BTREE NODE)

REPLACE-WITH-SUCCESSOR (CUR NEXT BTREE NODE)

SEARCH-FROM-CONTENTS (POS KEY)

SPLIT-CHILD (BTREE PARENT-NODE CHILD-NODE)

SPLIT-CONTENTS (BTREE-NODE)

SPLIT-MAX-KEY (B-TREE-NODE)

SPLIT-MIN-KEY (B-TREE-NODE)

VALID-NODE-P (BTREE-NODE BTREE)

SETFVALUE (NEW-VALUE INSTANCE)

GENERIC-FUNCTION

Private

Undocumented

KEY< (A B)

KEY<= (A B)

KEY= (A B)

KEY> (A B)

KEY>= (A B)

CLASS

Public

Undocumented

B-TREE

B-TREE-NODE

Private

Undocumented

B-TREE-ITEM

B-TREE-REF

BACKTRACKING-LIST-ITERATOR

CONSTANT

Private

Undocumented

+B-TREE-EOF+

+B-TREE-ITEM+

+B-TREE-REF+