Common Lisp Package: BKNR.SKIP-LIST

README:

FUNCTION

Private

FOLLOW-NODE (NODE KEY LEVEL)

Follow a skip-list node at level LEVEL, stopping when there is no next node or when the next node has a larger key.

RANDOM-LEVEL

Returns a random level for a new skip-list node, with SL-RANDOM p for each level.

SL-RANDOM

Pseudo-random number generator, returns NIL 3/4 of the time.

Undocumented

MAKE-HEADER (&KEY INITIAL-ELEMENT)

MAKE-NODE (KEY VALUE SIZE &KEY INITIAL-ELEMENT)

NODE-BEFORE (NODE KEY &OPTIONAL (LEVEL 0))

NODE-LEVEL (NODE)

MACRO

Private

Undocumented

NODE-FORWARD (NODE &OPTIONAL (I 0))

NODE-KEY (NODE)

NODE-VALUE (NODE)

GENERIC-FUNCTION

Public

Undocumented

MAP-SKIP-LIST (FUN SL)

MAP-SKIP-LIST-VALUES (FUN SL)

SKIP-LIST-CURSOR (SL &KEY CURSOR (CLASS 'SKIP-LIST-CURSOR))

SKIP-LIST-DELETE (SL KEY)

SKIP-LIST-GET (KEY SL)

SETFSKIP-LIST-GET (NEW-VALUE KEY SL)

SKIP-LIST-INSERT (SL KEY VALUE)

SKIP-LIST-KEYS-CURSOR (SL)

SKIP-LIST-RANGE-CURSOR (SL START END)

SKIP-LIST-REMOVE (KEY SL)

SKIP-LIST-VALUES-CURSOR (SL)

SL-CURSOR-NEXT (SLC &OPTIONAL EOC)

SL-CURSOR-PREV (SLC &OPTIONAL EOC)

Private

Undocumented

MAKE-UPDATE (SL KEY)

SKIP-LIST-AFTER-NODE (SL KEY)

SKIP-LIST-EMPTY-P (SL)

SKIP-LIST-REDUCE-HEADER (SL)

SKIP-LIST-SEARCH-NODE (SL KEY)

SKIP-LIST-TO-LIST (SL)

SLOT-ACCESSOR

Public

Undocumented

SKIP-LIST-LENGTH (OBJECT)

SETFSKIP-LIST-LENGTH (NEW-VALUE OBJECT)

Private

Undocumented

SKIP-LIST-CURSOR-NODE (OBJECT)

SETFSKIP-LIST-CURSOR-NODE (NEW-VALUE OBJECT)

SKIP-LIST-HEADER (OBJECT)

SKIP-LIST-LEVEL (OBJECT)

SETFSKIP-LIST-LEVEL (NEW-VALUE OBJECT)

SLRC-END (OBJECT)

VARIABLE

Private

*SL-RANDOM-STATE*

Internal status of the random number generator.

CLASS

Public

SKIP-LIST

Skip-list class, access to elements is done through the header node.

Undocumented

SKIP-LIST-CURSOR (SL &KEY CURSOR (CLASS 'SKIP-LIST-CURSOR))

SKIP-LIST-KEY-CURSOR

SKIP-LIST-RANGE-CURSOR (SL START END)

SKIP-LIST-VALUE-CURSOR

CONSTANT

Private

+MAX-LEVEL+

Maximum level of skip-list, should be enough for 2^32 elements.