Common Lisp Package: HH-REDBLACK

README:

FUNCTION

Public

Undocumented

MAKE-MEMORY-PERSISTENT-RED-BLACK-TREE

MAKE-RED-BLACK-TREE

MAKE-TEXT-FILE-RED-BLACK-TREE (FILE-NAME)

Private

Undocumented

CLEAR-CHANGES

CLOSE-STORAGE-STREAM (TREE)

MAKE-STORAGE-HEADER (TREE)

OPEN-STORAGE-STREAM (TREE)

READ-STORED-OBJECT (STREAM)

REQUIRE-RB-TRANSACTION

SORT-INTO-SAVE-ORDER (CHANGES)

WRITE-STORED-OBJECT (STREAM OBJECT)

MACRO

Public

Undocumented

WITH-RB-KEYS-AND-DATA ((KEY-VAR DATA-VAR &OPTIONAL (STARTING-POINT FIRST)) TREE &REST BODY)

WITH-RB-TRANSACTION ((TREE) &REST BODY)

Private

Undocumented

FORM (NUMBER CONTENTS)

LOC (FORM OFFSET)

NODE (&KEY LEFT RIGHT COLOR KEY DATA)

NODE-DATA (CONTENT)

GENERIC-FUNCTION

Public

RB-GET (TREE KEY &OPTIONAL DEFAULT)

Returns 2 values, just like gethash: if the key is present, returns the associated data and t (indicating data was present), otherwise returns the default and nil

RB-KEY-COMPARE (LEFT-KEY RIGHT-KEY)

Compare 2 keys used in a red-black tree, return :less, :equal, or :greater, depending on the result of the comparison. Definitions exist for common types such as numbers, strings, and symbols.

RB-KEYS (TREE)

Return all keys of the tree as an ordered list; not recommended for large trees

RB-PUT (TREE KEY DATA)

Equivalent to sethash with a hashtable: set the data for a given key in the provided tree

RB-REMOVE (TREE KEY)

Remove the node with the indicated key from the tree

RB-SIZE (TREE)

Calculate the number of nodes in the tree

Private

ALLOCATION-SIZE (TREE OBJECT)

Size of the object persisted in the tree's storage; the units of measures for the size depend on the tree's storage implementation

EQUALITY (LEFT RIGHT)

The equality test is important for detecting consistency of the footer and its backup

PRB-ABORT (TRANSACTION-OR-TREE)

Abandon any changes in the tree; note that any nodes held should be reacquired after an abort

PRB-CLOSE-STORAGE (STORAGE)

Release storage from use; further load & save operations cannot succeed without a subsequent open call

PRB-COMMIT (TRANSACTION-OR-TREE)

Orchestrate the persisting of all changes to a tree, including all changed nodes

PRB-FETCH-DATA (TREE LOCATION)

Return data from the indicated location

PRB-FETCH-NODE (TREE LOCATION)

Return the state of a node as multiple values: -- location of left child, or location for nil sentinel -- location of right child, or location for nil sentinel -- color value -- key value -- location of data

PRB-LEAF-LOCATION-P (TREE LOCATION)

Return true if the location points to the nil or leaf sentinel

PRB-LOAD-DATA (TREE DATA)

Load data from storage, if not already loaded

PRB-LOAD-NODE (TREE NODE)

Load the node's state from storage, if not already loaded

PRB-LOCATION (TREE)

Return the current location within storage where new objects would be written

PRB-OPEN-STORAGE (TREE)

Prepare tree for use; after this call load & save operations should succeed, the root should be loaded, and the leaf sentinel identified

PRB-SAVE-DATA (TREE DATA)

Save the indicated data in storage

PRB-SAVE-NODE (TREE NODE)

Save the indicated node in storage, using prb-stash-node. Tree implementations are free to implement either prb-save-node (high-level) or prb-stash-node (low-level), depending on their needs. Typical implementations may want to implement prb-stash-node to write their own storage, but implementing prb-save-node would permit extending what node state is saved.

PRB-SAVE-ROOT (TREE ROOT)

Save the indicated root to storage; after this call, any subsequent transaction should see this object as the root of the tree

PRB-STASH-DATA (TREE CONTENTS)

Save the indicated contents of a data object in storage

PRB-STASH-NODE (TREE LEFT-LOCATION RIGHT-LOCATION COLOR-VALUE KEY-VALUE DATA-LOCATION)

Save node state into storage

RB-DATA-CLASS (TREE)

Return the class to be used for storing data in the tree

RB-MAKE-NODE (TREE &KEY KEY DATA ((DATA DATA) NIL) ((KEY KEY) NIL) ((DATA DATA) NIL) ((KEY KEY) NIL))

Return a node suitable for insertion within the tree

RB-NEXT (TREE NODE)

Return the node with the next higher key in the tree

RB-NODE-CLASS (TREE)

Return the class to be used for creating nodes in the tree

RB-PREVIOUS (TREE NODE)

Return the node with the next lower (aka previous) key in the tree

RB< (LEFT-KEY RIGHT-KEY)

Return t if the left key is less than the right key, nil otherwise

RB= (LEFT-KEY RIGHT-KEY)

Return t if the left key and right key are equivalent

REFRESH-NODE (TREE NODE)

Refresh a node's state from storage, if necessary

Undocumented

ADD-CHANGED-OBJECT (TRANSACTION OBJECT)

ADD-CHILD-OBJECT (TRANSACTION PARENT CHILD)

ADD-NEW-OBJECT (TRANSACTION OBJECT)

ANCESTOR-P (NODE POSSIBLE-ANCESTOR)

CHANGEDP (TRANSACTION OBJECT)

COMPARE-SAVE-ORDER (LEFT RIGHT)

LEAFP (TREE NODE)

LOADED-P (OBJECT)

PRB-SAVE-OBJECT (TREE OBJECT)

RB-DELETE (TREE NODE)

RB-DELETE-FIXUP (TREE NODE)

RB-FIND (TREE KEY)

RB-FIRST (TREE)

RB-INSERT (TREE NODE)

RB-INSERT-FIXUP (TREE NODE)

RB-LAST (TREE)

RB-LEFT-ROTATE (TREE NODE)

RB-MAKE-DATA (TREE &KEY LOCATION CONTENTS)

RB-RIGHT-ROTATE (TREE NODE)

RB-TRANSPLANT (TREE U V)

RB-TREE-MAXIMUM (TREE NODE)

RB-TREE-MINIMUM (TREE NODE)

SLOT-ACCESSOR

Private

PARENTS (OBJECT)

For mapping objects to their parent objects

SETFPARENTS (NEW-VALUE OBJECT)

For mapping objects to their parent objects

Undocumented

CHANGES (OBJECT)

SETFCHANGES (NEW-VALUE OBJECT)

COLOR (NODE)

SETFCOLOR (VALUE NODE)

CONTENT (OBJECT)

SETFCONTENT (NEW-VALUE OBJECT)

CONTENTS (OBJECT)

SETFCONTENTS (NEW-VALUE OBJECT)

DATA (NODE)

SETFDATA (VALUE NODE)

FILE-NAME (OBJECT)

SETFFILE-NAME (NEW-VALUE OBJECT)

FORM-NUMBER (OBJECT)

SETFFORM-NUMBER (NEW-VALUE OBJECT)

KEY (NODE)

SETFKEY (VALUE NODE)

LEAF (OBJECT)

SETFLEAF (NEW-VALUE OBJECT)

LEFT (NODE)

SETFLEFT (VALUE NODE)

LOCATION (OBJECT)

SETFLOCATION (NEW-VALUE OBJECT)

NEW-ROOT (OBJECT)

SETFNEW-ROOT (NEW-VALUE OBJECT)

NEXT-FORM-NUMBER (OBJECT)

SETFNEXT-FORM-NUMBER (NEW-VALUE OBJECT)

OBJECTS (OBJECT)

SETFOBJECTS (NEW-VALUE OBJECT)

OFFSET (OBJECT)

SETFOFFSET (NEW-VALUE OBJECT)

PARENT (NODE)

SETFPARENT (VALUE NODE)

SETFRIGHT (VALUE NODE)

ROOT (TREE)

SETFROOT (VALUE TREE)

STATE (OBJECT)

SETFSTATE (NEW-VALUE OBJECT)

STORAGE-STREAM (OBJECT)

SETFSTORAGE-STREAM (NEW-VALUE OBJECT)

TREE (OBJECT)

SETFTREE (NEW-VALUE OBJECT)

VERSION (OBJECT)

SETFVERSION (NEW-VALUE OBJECT)

VARIABLE

Private

*RB-TRANSACTION*

The currently active transaction on a red-black tree

CLASS

Private

Undocumented

MEMORY-PERSISTENT-RED-BLACK-TREE

MEMORY-RED-BLACK-NODE

MEMORY-RED-BLACK-TREE

PERSISTENT-RED-BLACK-DATA

PERSISTENT-RED-BLACK-NODE

PERSISTENT-RED-BLACK-OBJECT

PERSISTENT-RED-BLACK-TREE

RED-BLACK-NODE

RED-BLACK-TREE

RED-BLACK-TREE-TRANSACTION

STORAGE-DATA

STORAGE-FORM

STORAGE-HEADER

STORAGE-LOCATION

STORAGE-NODE

TEXT-FILE-RED-BLACK-DATA

TEXT-FILE-RED-BLACK-NODE

TEXT-FILE-RED-BLACK-OBJECT

TEXT-FILE-RED-BLACK-TREE

CONDITION

Public

Undocumented

REQUIRES-RED-BLACK-TRANSACTION

Private

Undocumented

INCONSISTENT-STORAGE

TRANSACTION-ABORTED