Common Lisp Package: CL-SKIP-LIST

README:

FUNCTION

Public

Undocumented

MAKE-SKIP-LIST (&KEY ((HEAD DUM200) (MAKE-HEAD)) ((KEY-EQUAL DUM201) #'EQUAL) ((VALUE-EQUAL DUM202) #'EQUAL) ((COMPARISON DUM203) #'LESS-THAN) ((DUPLICATES-ALLOWED? DUM204) NIL) ((NODE-FN DUM205) #'MAKE-SKIP-NODE) ((LENGTH DUM206) 0))

MAKE-SKIP-PQ (&KEY (KEY-EQUAL #'=) (VALUE-EQUAL #'EQUAL) (COMPARISON #'<) (HEAD-VALUE MOST-NEGATIVE-FIXNUM))

SKIP-LIST-LENGTH (INSTANCE)

SETFSKIP-LIST-LENGTH (NEW-VALUE INSTANCE)

SKIP-LIST? (OBJECT)

Private

COPY-CCAS-DESCRIPTOR (SEQUENCE)

Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.

COPY-MCAS-DESCRIPTOR (SEQUENCE)

Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.

COPY-SAFE-UPDATE (SEQUENCE)

Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.

MAKE-MT-RANDOM-STATE (&OPTIONAL STATE)

Analogous to Common Lisp's MAKE-RANDOM-STATE except that this function works on random states for JMT's Mersenne Twister implementation.

MCAS-HELP (MD)

This is the bulk of the transaction logic.

MT-MAKE-RANDOM-STATE-INTEGER (N)

Use the single integer to expand into a bunch of integers to use as an MT-RANDOM-STATE. Copied from the 'sgenrand' function in mt19937int.c. This is mostly an internal function. I recommend using MAKE-MT-RANDOM-STATE unless specific circumstances dictate otherwise.

MT-MAKE-RANDOM-STATE-RANDOM

Generate a new random state from a new, hopefully somewhat random, value. This is mostly an internal function. I recommend using MAKE-MT-RANDOM-STATE unless specific circumstances dictate otherwise.

MT-RANDOM (N &OPTIONAL STATE)

Generate a random number. WARNING: setting state here is not thread safe; *mt-random-state* will be set without any regard for what others are doing with it!

MT-RANDOM-STATE-ARR (INSTANCE)

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

MT-RANDOM-STATE-MTI (INSTANCE)

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

MT-REFILL

In the C program mt19937int.c, there is a function called 'genrand', & in that function there is a block of code to execute when the mt[] array is exhausted. This function is that block of code. I've removed it from my MT-GENRAND function for clarity.

RANDOM-LEVEL

Returns a random level for a new skip-list node, following Pugh's pattern of L1: 50%, L2: 25%, L3: 12.5%, ...

SKIP-LIST-COMPARISON (INSTANCE)

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

SKIP-LIST-DUPLICATES-ALLOWED? (INSTANCE)

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

SKIP-LIST-HEAD (INSTANCE)

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

SKIP-LIST-KEY-EQUAL (INSTANCE)

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

SKIP-LIST-NODE-FN (INSTANCE)

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

SKIP-LIST-VALUE-EQUAL (INSTANCE)

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

Undocumented

%GETTIMEOFDAY (TP TZP)

CCAS (VECTOR INDEX CONTROL-VECTOR CONTROL-INDEX OLD NEW &OPTIONAL (EQUALITY #'EQUAL))

CCAS-DESCRIPTOR? (G55)

CCAS-HELP (CD)

CCAS-READ (VECTOR INDEX)

CD-CONTROL-INDEX (STRUCTURE)

SETFCD-CONTROL-INDEX (NEW-VALUE STRUCTURE)

CD-CONTROL-VECTOR (STRUCTURE)

SETFCD-CONTROL-VECTOR (NEW-VALUE STRUCTURE)

CD-EQUALITY (STRUCTURE)

SETFCD-EQUALITY (NEW-VALUE STRUCTURE)

CD-INDEX (STRUCTURE)

SETFCD-INDEX (NEW-VALUE STRUCTURE)

CD-NEW (STRUCTURE)

SETFCD-NEW (NEW-VALUE STRUCTURE)

CD-OLD (STRUCTURE)

SETFCD-OLD (NEW-VALUE STRUCTURE)

CD-VECTOR (STRUCTURE)

SETFCD-VECTOR (NEW-VALUE STRUCTURE)

COPY-MT-RANDOM-STATE (INSTANCE)

COPY-SKIP-LIST (INSTANCE)

GET-PROP (PLIST PROP)

GET-VECTOR-ADDR (VECTOR)

GETTIMEOFDAY

MAKE-CCAS-DESCRIPTOR (&KEY ((VECTOR DUM56) NIL) ((CONTROL-VECTOR DUM57) NIL) ((CONTROL-INDEX DUM58) NIL) ((INDEX DUM59) NIL) ((OLD DUM60) NIL) ((NEW DUM61) NIL) ((EQUALITY DUM62) NIL))

MAKE-HEAD (&KEY INITIAL-ELEMENT)

MAKE-MCAS-DESCRIPTOR (&KEY ((STATUS DUM362) +MCAS-UNDECIDED+) ((COUNT DUM363) 0) ((UPDATES DUM364) NIL) ((EQUALITY DUM365) #'EQUAL) ((SUCCESS-ACTIONS DUM366) NIL) ((RETRIES DUM367) 0) ((TIMESTAMP DUM368) (GETTIMEOFDAY)))

MAKE-SAFE-UPDATE (&KEY ((VECTOR DUM239) NIL) ((INDEX DUM240) NIL) ((OLD DUM241) NIL) ((NEW DUM242) NIL))

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

MAKE-SKIP-PQ-NODE (KEY VALUE SIZE &KEY INITIAL-ELEMENT TIMESTAMP)

MCAS (MD)

MCAS-COUNT (STRUCTURE)

SETFMCAS-COUNT (NEW-VALUE STRUCTURE)

MCAS-DESCRIPTOR? (G361)

MCAS-EQUALITY (STRUCTURE)

SETFMCAS-EQUALITY (NEW-VALUE STRUCTURE)

MCAS-READ (VECTOR INDEX)

MCAS-RETRIES (STRUCTURE)

SETFMCAS-RETRIES (NEW-VALUE STRUCTURE)

MCAS-SET (VECTOR INDEX OLD NEW)

MCAS-STATUS (STRUCTURE)

SETFMCAS-STATUS (NEW-VALUE STRUCTURE)

MCAS-SUCCESS-ACTIONS (STRUCTURE)

SETFMCAS-SUCCESS-ACTIONS (NEW-VALUE STRUCTURE)

MCAS-TIMESTAMP (STRUCTURE)

SETFMCAS-TIMESTAMP (NEW-VALUE STRUCTURE)

MCAS-UPDATES (STRUCTURE)

SETFMCAS-UPDATES (NEW-VALUE STRUCTURE)

MT-GENRAND

MT-INTERNAL-MAKE-RANDOM-STATE (&KEY ((MTI DUM0) NIL) ((ARR DUM1) NIL))

SETFMT-RANDOM-STATE-ARR (NEW-VALUE INSTANCE)

SETFMT-RANDOM-STATE-MTI (NEW-VALUE INSTANCE)

MT-RANDOM-STATE-P (OBJECT)

MT-TEMPERING-SHIFT-L (N)

MT-TEMPERING-SHIFT-S (N)

MT-TEMPERING-SHIFT-T (N)

MT-TEMPERING-SHIFT-U (N)

NODE-FORWARD (NODE)

RESET-MCAS (MCAS)

SAFE-UPDATE? (G238)

SETFSKIP-LIST-COMPARISON (NEW-VALUE INSTANCE)

SETFSKIP-LIST-DUPLICATES-ALLOWED? (NEW-VALUE INSTANCE)

SETFSKIP-LIST-HEAD (NEW-VALUE INSTANCE)

SETFSKIP-LIST-KEY-EQUAL (NEW-VALUE INSTANCE)

SETFSKIP-LIST-NODE-FN (NEW-VALUE INSTANCE)

SETFSKIP-LIST-VALUE-EQUAL (NEW-VALUE INSTANCE)

SL-TEST

UPDATE-INDEX (STRUCTURE)

SETFUPDATE-INDEX (NEW-VALUE STRUCTURE)

UPDATE-NEW (STRUCTURE)

SETFUPDATE-NEW (NEW-VALUE STRUCTURE)

UPDATE-OLD (STRUCTURE)

SETFUPDATE-OLD (NEW-VALUE STRUCTURE)

UPDATE-VECTOR (STRUCTURE)

SETFUPDATE-VECTOR (NEW-VALUE STRUCTURE)

MACRO

Private

Undocumented

CAS (PLACE OLD NEW)

SKIP-NODE-DELETED? (NODE)

SKIP-NODE-FORWARD (NODE)

SKIP-NODE-KEY (NODE)

SKIP-NODE-LEVEL (NODE)

SKIP-NODE-TIMESTAMP (NODE)

SKIP-NODE-VALUE (NODE)

WHILE (TEST &REST BODY)

WITH-MCAS (LAMBDA-LIST &BODY BODY)

WITH-RECURSIVE-MCAS (LAMBDA-LIST &BODY BODY)

GENERIC-FUNCTION

Public

LESS-THAN (X Y)

Generic less-than operator. Allows comparison of apples and oranges.

Undocumented

DELETE-MIN (SL)

MAP-SKIP-LIST (FUN SL)

MAP-SKIP-LIST-VALUES (FUN SL)

SKIP-LIST-ADD (SL KEY VALUE)

SKIP-LIST-DELETE (SL KEY &OPTIONAL VALUE)

SKIP-LIST-EMPTY? (SL)

SKIP-LIST-FETCH-ALL (SL KEY)

SKIP-LIST-KEYS-CURSOR (SL)

SKIP-LIST-LOOKUP (SL KEY &OPTIONAL VALUE)

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

SKIP-LIST-REPLACE-KV (SL KEY NEW-VALUE &OPTIONAL OLD-VALUE)

SKIP-LIST-TO-LIST (SL)

SKIP-LIST-VALUES-CURSOR (SL)

SL-CURSOR-NEXT (SLC &OPTIONAL EOC)

Private

Undocumented

MCAS-SUCCESSFUL? (THING)

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

SKIP-PQ-ADD (SL KEY VALUE)

SKIP-PQ-DELETE (SL NODE)

SLOT-ACCESSOR

Private

Undocumented

SKIP-LIST (OBJECT)

SETFSKIP-LIST (NEW-VALUE OBJECT)

SKIP-LIST-CURSOR-NODE (OBJECT)

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

SLRC-END (OBJECT)

VARIABLE

Private

*MT-RANDOM-STATE*

Unlike the reference implementation, we'll initialize the random state to a hopefully somewhat random & unique value., but not until after defining (mt-make-random-state-random)

Undocumented

*MCAS*

CLASS

Public

Undocumented

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

Private

Undocumented

MT-RANDOM-STATE

NULL-POINTER-TYPE

SKIP-LIST (OBJECT)

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

SKIP-LIST-KEY-CURSOR

SKIP-LIST-VALUE-CURSOR

SYSCALL-RESULT-TYPE

TIMEVAL-TCLASS

CONDITION

Private

Undocumented

MCAS-ERROR

SKIP-LIST-DUPLICATE-ERROR

SKIP-LIST-KV-NOT-FOUND-ERROR

TRANSACTION-ERROR

CONSTANT

Public

Undocumented

+MCAS-FAILED+

+MCAS-SUCCEEDED+

+MCAS-UNDECIDED+

Private

*MT-K-INVERSE-2^32F*

1/(2^32), as a floating-point number

*MT-LOWER-MASK*

least significant r bits

*MT-UPPER-MASK*

most significant w-r bits

+MAX-LEVEL+

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

Undocumented

*MT-K2^32*

*MT-M*

*MT-N*

+MCAS-MAKE-DURABLE+

+SKIP-NODE-DELETED+

+SKIP-NODE-FORWARD+

+SKIP-NODE-KEY+

+SKIP-NODE-LEVEL+

+SKIP-NODE-TIMESTAMP+

+SKIP-NODE-VALUE+