Common Lisp Package: PLANKS.BTREE

README:

FUNCTION

Public

Undocumented

ADD-FUNCTION-BTREE (BTREE FUNCTION-NAME &REST ARGS)

BTREE-FILE-SIZE (BTREE)

CLOSE-BTREE (PATH)

FIND-BTREE (PATH)

FIND-FUNCTION-BTREE (BTREE FUNCTION-NAME)

MAKE-BTREE (PATHNAME &REST ARGS &KEY (IF-EXISTS ERROR) (CLASS 'SINGLE-FILE-BTREE) &ALLOW-OTHER-KEYS)

Private

FIND-KEY-POSITION-IN-INDEX (BTREE INDEX KEY)

Returns the position of the subnode that contains more information for the given key.

FIND-SUBNODE (BTREE NODE KEY)

Returns the subnode that contains more information for the given key.

Undocumented

%UPDATE-BTREE (BTREE &KEY (ROOT (SLOT-VALUE BTREE 'ROOT)))

BTREE-NODE-BINDING (NODE I)

BTREE-NODE-BINDING-COUNT (NODE)

BTREE-NODE-FILE-POSITION (NODE)

CALL-WITH-BTREE-STREAM (BTREE FN &OPTIONAL (DIRECTION IO))

CURRENT-BTREE

LOAD-BTREE-NODE (BTREE ADDRESS)

LOAD-BTREE-NODE-FROM-STREAM (BTREE STREAM &OPTIONAL (ADDRESS (FILE-POSITION STREAM)))

MAKE-BTREE-LOCK (BTREE)

NODE-ALMOST-FULL-P (BTREE NODE)

NOT-FOUND (BTREE KEY ERRORP DEFAULT-VALUE)

READ-BTREE-FROM-FILE-STREAM (STREAM)

SPLIT-BINDING-NODE (BTREE NODE KEY VALUE LEAF-P)

UPDATE-BINDING-FOR-INSERT (BTREE BINDING KEY VALUE LEAF-P)

UPDATE-BNODE (BTREE NODE KEY VALUE)

UPDATE-INDEX-FOR-INSERT (BTREE INDEX KEY VALUE LEAF-P)

GENERIC-FUNCTION

Public

BTREE-INSERT (BTREE KEY VALUE &KEY IF-EXISTS (IF-EXISTS OVERWRITE))

Adds an association from KEY to VALUE to a btree. IF-EXISTS can be either :OVERWRITE (default) or :ERROR. If the btree has unique keys (see BTREE-UNIQUE-KEYS-P) and KEY is already associated with another (according to BTREE-VALUE=) value, the result depends on the IF-EXISTS option: if IF-EXISTS is :OVERWRITE, the old value is overwriten; if IF-EXISTS is :ERROR, a BTREE-KEY-ALREADY-PRESENT-ERROR is signaled. For btrees with non-unique keys, the IF-EXISTS option is ignored and VALUE is just added to the list of values associated with KEY (unless VALUE is already associated with KEY; in that case nothing happens).

MAP-BTREE (BTREE FUNCTION &KEY MIN MAX INCLUDE-MIN INCLUDE-MAX ORDER ADDRESS-ONLY (ORDER ASCENDING) &ALLOW-OTHER-KEYS)

Calls FUNCTION for all key/value associations in the btree where key is in the specified interval (this means that FUNCTION can be called with the same key more than once for btrees with non-unique keys). FUNCTION must be a binary function; the first argument is the btree key, the second argument is an associated value. MIN, MAX, INCLUDE-MIN and INCLUDE-MAX specify the interval. The interval is left-open if MIN is nil, right-open if MAX is nil. The interval is inclusive on the left if INCLUDE-MIN is true (and exclusive on the left otherwise). The interval is inclusive on the right if INCLUDE-MAX is true (and exclusive on the right otherwise). ORDER is either :ASCENDING (default) or :DESCENDING.

UPDATE-BTREE (BTREE &KEY KEY VALUE ACTION VALUE-THUNK &ALLOW-OTHER-KEYS)

This is the function that implements the functional b+tree. It is not meant to be called by users, but is specialized when extending

Undocumented

BTREE-ERROR-BTREE (CONDITION)

BTREE-ERROR-KEY (CONDITION)

BTREE-ERROR-VALUE (CONDITION)

BTREE-KEY< (OBJECT)

BTREE-KEY= (OBJECT)

BTREE-VALUE= (OBJECT)

Private

Undocumented

ALLOCATE-HEAP (BTREE START STREAM)

ALLOCATE-OBJECT (BTREE OBJECT OBJECT-START HEAP-START STREAM)

BTREE-BALANCED-P (BTREE)

BTREE-DEPTHS (BTREE)

BTREE-HEAP-FREE-SPACE-START (BTREE)

BTREE-HEAP-START (BTREE)

BTREE-KEY<= (BTREE)

BTREE-KEY> (BTREE)

BTREE-KEY>= (BTREE)

BTREE-NODE-BINDING-KEY (NODE BINDING)

BTREE-NODE-BINDING-VALUE (NODE BINDING)

BTREE-NODE-MAX-DEPTH (NODE)

BTREE-NODE-MIN-DEPTH (NODE)

FIND-HEAP-OBJECT (HEAP ADDRESS)

LARGEST-KEY-IN-NODE (NODE)

MAKE-ROOT-NODE (BTREE KEY VAL)

MAP-BTREE-KEYS (BTREE FUNCTION &KEY MIN MAX INCLUDE-MIN INCLUDE-MAX (ORDER ASCENDING))

MAP-BTREE-KEYS-FOR-NODE (BTREE NODE FUNCTION MIN MAX INCLUDE-MIN INCLUDE-MAX ORDER)

MAP-BTREE-NODE (BTREE FUNCTION POINTER)

PERSIST (NODE &KEY (STREAM *BTREE-STREAM*))

READ-NODE-TAG (NODE &KEY (STREAM *BTREE-STREAM*))

UPDATE-NODE (NODE &KEY (INDEX (BTREE-NODE-INDEX NODE)) (LEAF-P (BTREE-NODE-LEAF-P NODE)) &ALLOW-OTHER-KEYS)

UPDATE-NODE-FOR-INSERT (BTREE NODE BINDING-KEY KEY VALUE LEAF-P)

WRITE-NODE-TAG (NODE &KEY (STREAM *BTREE-STREAM*))

SLOT-ACCESSOR

Public

BTREE-KEY-TYPE (OBJECT)

The type of all keys.

BTREE-MAX-NODE-SIZE (OBJECT)

An integer specifying the preferred maximum number of keys per btree node.

BTREE-UNIQUE-KEYS-P (OBJECT)

If false, one key can correspond to more than one value.

BTREE-VALUE-TYPE (OBJECT)

The type of all values.

Undocumented

BTREE-NODE-CLASS (OBJECT)

BTREE-ROOT (OBJECT)

SETFBTREE-ROOT (NEW-VALUE OBJECT)

Private

BTREE-KEY-KEY (OBJECT)

A unary function that is applied to a btree key before comparing it to another key with a key comparison predicate like BTREE-KEY<.

BTREE-NODE-INDEX (OBJECT)

A vector of key/value pairs. The keys are sorted by KEY<. No two keys can be the same. For leaf nodes of btrees with non-unique-keys, the value part is actually a list of values. For intermediate nodes, the value is a child node. All keys in the child node will be KEY< the child node's key in the parent node.

SETFBTREE-NODE-INDEX (NEW-VALUE OBJECT)

A vector of key/value pairs. The keys are sorted by KEY<. No two keys can be the same. For leaf nodes of btrees with non-unique-keys, the value part is actually a list of values. For intermediate nodes, the value is a child node. All keys in the child node will be KEY< the child node's key in the parent node.

BTREE-VALUE-KEY (OBJECT)

A unary function that is applied to a btree value before comparing it to another value with the BTREE-VALUE= predicate.

Undocumented

BTREE-CLASS-PATHNAME (OBJECT)

SETFBTREE-CLASS-PATHNAME (NEW-VALUE OBJECT)

BTREE-FUNCTION-NAME (OBJECT)

SETFBTREE-FUNCTION-NAME (NEW-VALUE OBJECT)

BTREE-HEAP-SIZE (OBJECT)

SETFBTREE-HEAP-SIZE (NEW-VALUE OBJECT)

BTREE-LOCK (OBJECT)

SETFBTREE-LOCK (NEW-VALUE OBJECT)

BTREE-NODE-ADDRESS (OBJECT)

SETFBTREE-NODE-ADDRESS (NEW-VALUE OBJECT)

BTREE-NODE-LEAF-P (OBJECT)

SETFBTREE-NODE-LEAF-P (NEW-VALUE OBJECT)

BTREE-OBJECT-ID (OBJECT)

SETFBTREE-OBJECT-ID (NEW-VALUE OBJECT)

BTREE-PATHNAME (OBJECT)

SETFBTREE-PATHNAME (NEW-VALUE OBJECT)

PERSISTENT-STANDARD-CLASS-BTREE (OBJECT)

SETFPERSISTENT-STANDARD-CLASS-BTREE (NEW-VALUE OBJECT)

PERSISTENT-STANDARD-OBJECT-SLOT-BTREE (OBJECT)

SETFPERSISTENT-STANDARD-OBJECT-SLOT-BTREE (NEW-VALUE OBJECT)

PERSISTENT-STANDARD-OBJECT-SLOT-BTREE-CLASS-NAME (OBJECT)

SETFPERSISTENT-STANDARD-OBJECT-SLOT-BTREE-CLASS-NAME (NEW-VALUE OBJECT)

ROOT-NODE-FILE-POSITION (OBJECT)

SETFROOT-NODE-FILE-POSITION (NEW-VALUE OBJECT)

SLOT-DEFINITION-PERSISTENTP (SLOT)

SETFSLOT-DEFINITION-PERSISTENTP (NEW-VALUE OBJECT)

VARIABLE

Private

Undocumented

*BTREE-FILE-ROOT*

*BTREES*

=BIG-BTREE-LOCK=

CLASS

Public

Undocumented

BTREE

BTREE-NODE

HEAP-BTREE

MULTI-BTREE

Private

Undocumented

BTREE-CLASS

BTREE-OBJECT

FILE-BTREE

FILE-BTREE-NODE

FUNCTION-BTREE

NESTED-BTREE

OBJECT-STORAGE-BTREE

PERSISTENT-STANDARD-CLASS

PERSISTENT-STANDARD-CLASS-DIRECT-SLOT-DEFINITION

PERSISTENT-STANDARD-CLASS-EFFECTIVE-SLOT-DEFINITION

PERSISTENT-STANDARD-CLASS-SLOT-DEFINITION

PERSISTENT-STANDARD-OBJECT

PERSISTENT-STANDARD-OBJECT-SLOT-BTREE (OBJECT)

SINGLE-FILE-BTREE

CONDITION

Public

Undocumented

BTREE-ERROR

BTREE-INSERTION-ERROR

BTREE-KEY-ALREADY-PRESENT-ERROR

BTREE-SEARCH-ERROR

BTREE-TYPE-ERROR

CONSTANT

Private

Undocumented

+PERSISTENT-STANDARD-OBJECT-MARKER+