The cl-skip-list Reference Manual

Table of Contents

The cl-skip-list Reference Manual

This is the cl-skip-list Reference Manual, version 0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 12:48:26 2020 GMT+0.

1 Introduction

Concurrent lockless skip lists for Common Lisp.

Currently, "Common Lisp" means SBCL version 1.0.42 or higher.  If other Lisps 
support compare-and-swap and memory barriers, let me know and I will add macros 
for those Lisps.  There is also a need to sort update locations based on some 
global order, in this case the pointer addresses.  SBCL allows that via 
(logandc2 (sb-kernel:get-lisp-obj-address vector) sb-vm:lowtag-mask))
combined with sb-sys:with-pinned-objects to avoid a GC moving things around.
Do other Lisps have similar facilities?

TODO
1. Improve performance by reusing CCAS descriptors during the first phase of an MCAS
2. Add search fingers
2. Add skip list merges
3. Add splitting

DONE
1. Added a skip-list-based priority queue
2. Added memory barriers where necessary, making the code dependent on sbcl 1.0.42

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 cl-skip-list

Maintainer

Kevin Raison

Author

Kevin Raison <last name @ chatsubo dot net>

Description

Concurrent lock-free skip list.

Long Description

Concurrent lock-free skip list.

Version

0.1

Dependency

cffi

Source

cl-skip-list.asd (file)

Components

• cl-skip-list-package.lisp (file)
• random.lisp (file)
• utilities.lisp (file)
• gettimeofday.lisp (file)
• constants.lisp (file)
• mcas.lisp (file)
• skip-list.lisp (file)
• skip-pq.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 cl-skip-list.asd

Location

cl-skip-list.asd

Systems

cl-skip-list (system)

Packages

cl-skip-list-system

3.1.2 cl-skip-list/cl-skip-list-package.lisp

Parent

cl-skip-list (system)

Location

cl-skip-list-package.lisp

Packages

cl-skip-list

3.1.3 cl-skip-list/random.lisp

Dependency

cl-skip-list-package.lisp (file)

Parent

cl-skip-list (system)

Location

random.lisp

Internal Definitions

• *mt-k-inverse-2^32f* (constant)
• *mt-k2^32* (constant)
• *mt-lower-mask* (constant)
• *mt-m* (constant)
• *mt-n* (constant)
• *mt-random-state* (special variable)
• *mt-upper-mask* (constant)
• copy-mt-random-state (function)
• make-mt-random-state (function)
• mt-genrand (function)
• mt-internal-make-random-state (function)
• mt-make-random-state-integer (function)
• mt-make-random-state-random (function)
• mt-random (function)
• mt-random-state (structure)
• mt-random-state-arr (function)
• (setf mt-random-state-arr) (function)
• mt-random-state-mti (function)
• (setf mt-random-state-mti) (function)
• mt-random-state-p (function)
• mt-refill (function)
• mt-tempering-shift-l (function)
• mt-tempering-shift-s (function)
• mt-tempering-shift-t (function)
• mt-tempering-shift-u (function)

3.1.4 cl-skip-list/utilities.lisp

Dependency

cl-skip-list-package.lisp (file)

Parent

cl-skip-list (system)

Location

utilities.lisp

Exported Definitions

• less-than (generic function)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)

Internal Definitions

• get-prop (function)
• while (macro)

3.1.5 cl-skip-list/gettimeofday.lisp

Dependency

cl-skip-list-package.lisp (file)

Parent

cl-skip-list (system)

Location

gettimeofday.lisp

Internal Definitions

• %gettimeofday (function)
• gettimeofday (function)
• null-pointer-type (class)
• syscall-result-type (class)
• timeval-tclass (class)

3.1.6 cl-skip-list/constants.lisp

Dependency

cl-skip-list-package.lisp (file)

Parent

cl-skip-list (system)

Location

constants.lisp

Exported Definitions

• +mcas-failed+ (constant)
• +mcas-succeeded+ (constant)
• +mcas-undecided+ (constant)

Internal Definitions

• *mcas* (special variable)
• +mcas-make-durable+ (constant)

3.1.7 cl-skip-list/mcas.lisp

Dependencies

• utilities.lisp (file)
• constants.lisp (file)
• gettimeofday.lisp (file)

Parent

cl-skip-list (system)

Location

mcas.lisp

Internal Definitions

• cas (macro)
• ccas (function)
• ccas-descriptor? (function)
• ccas-help (function)
• ccas-read (function)
• cd-control-index (function)
• (setf cd-control-index) (function)
• cd-control-vector (function)
• (setf cd-control-vector) (function)
• cd-equality (function)
• (setf cd-equality) (function)
• cd-index (function)
• (setf cd-index) (function)
• cd-new (function)
• (setf cd-new) (function)
• cd-old (function)
• (setf cd-old) (function)
• cd-vector (function)
• (setf cd-vector) (function)
• get-vector-addr (function)
• make-ccas-descriptor (function)
• make-mcas-descriptor (function)
• make-safe-update (function)
• mcas (function)
• mcas-count (function)
• (setf mcas-count) (function)
• mcas-descriptor? (function)
• mcas-equality (function)
• (setf mcas-equality) (function)
• mcas-error (condition)
• mcas-help (function)
• mcas-read (function)
• mcas-retries (function)
• (setf mcas-retries) (function)
• mcas-set (function)
• mcas-status (function)
• (setf mcas-status) (function)
• mcas-success-actions (function)
• (setf mcas-success-actions) (function)
• mcas-successful? (generic function)
• mcas-successful? (method)
• mcas-successful? (method)
• mcas-timestamp (function)
• (setf mcas-timestamp) (function)
• mcas-updates (function)
• (setf mcas-updates) (function)
• reset-mcas (function)
• safe-update? (function)
• transaction-error (condition)
• update-index (function)
• (setf update-index) (function)
• update-new (function)
• (setf update-new) (function)
• update-old (function)
• (setf update-old) (function)
• update-vector (function)
• (setf update-vector) (function)
• with-mcas (macro)
• with-recursive-mcas (macro)

3.1.8 cl-skip-list/skip-list.lisp

Dependencies

• mcas.lisp (file)
• random.lisp (file)

Parent

cl-skip-list (system)

Location

skip-list.lisp

Exported Definitions

• make-skip-list (function)
• map-skip-list (method)
• map-skip-list-values (method)
• skip-list-add (method)
• skip-list-delete (method)
• skip-list-empty? (method)
• skip-list-fetch-all (method)
• skip-list-keys-cursor (method)
• skip-list-length (function)
• (setf skip-list-length) (function)
• skip-list-lookup (method)
• skip-list-range-cursor (method)
• skip-list-range-cursor (class)
• skip-list-replace-kv (method)
• skip-list-to-list (method)
• skip-list-values-cursor (method)
• skip-list? (function)
• sl-cursor-next (method)
• sl-cursor-next (method)
• sl-cursor-next (method)
• sl-cursor-next (method)

Internal Definitions

• +max-level+ (constant)
• +skip-node-forward+ (constant)
• +skip-node-key+ (constant)
• +skip-node-level+ (constant)
• +skip-node-value+ (constant)
• copy-skip-list (function)
• make-head (function)
• make-skip-node (function)
• node-forward (function)
• print-skip-list (function)
• random-level (function)
• skip-list (method)
• (setf skip-list) (method)
• skip-list (structure)
• skip-list-comparison (function)
• (setf skip-list-comparison) (function)
• skip-list-cursor (method)
• skip-list-cursor (class)
• skip-list-cursor-node (method)
• (setf skip-list-cursor-node) (method)
• skip-list-duplicate-error (condition)
• skip-list-duplicates-allowed? (function)
• (setf skip-list-duplicates-allowed?) (function)
• skip-list-head (function)
• (setf skip-list-head) (function)
• skip-list-key-cursor (class)
• skip-list-key-equal (function)
• (setf skip-list-key-equal) (function)
• skip-list-kv-not-found-error (condition)
• skip-list-node-fn (function)
• (setf skip-list-node-fn) (function)
• skip-list-search (method)
• skip-list-value-cursor (class)
• skip-list-value-equal (function)
• (setf skip-list-value-equal) (function)
• skip-node-forward (macro)
• skip-node-key (macro)
• skip-node-level (macro)
• skip-node-value (macro)
• sl-test (function)
• slrc-end (method)

3.1.9 cl-skip-list/skip-pq.lisp

Dependency

skip-list.lisp (file)

Parent

cl-skip-list (system)

Location

skip-pq.lisp

Exported Definitions

• delete-min (method)
• make-skip-pq (function)

Internal Definitions

• +skip-node-deleted+ (constant)
• +skip-node-timestamp+ (constant)
• make-skip-pq-node (function)
• skip-node-deleted? (macro)
• skip-node-timestamp (macro)
• skip-pq-add (method)
• skip-pq-delete (method)
• skip-pq-search (method)

4 Packages

Packages are listed by definition order.

4.1 cl-skip-list-system

Source

cl-skip-list.asd

Use List

• asdf/interface
• common-lisp

4.2 cl-skip-list

Source

cl-skip-list-package.lisp (file)

Use List

• cffi
• common-lisp

Exported Definitions

• +mcas-failed+ (constant)
• +mcas-succeeded+ (constant)
• +mcas-undecided+ (constant)
• delete-min (generic function)
• delete-min (method)
• less-than (generic function)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• less-than (method)
• make-skip-list (function)
• make-skip-pq (function)
• map-skip-list (generic function)
• map-skip-list (method)
• map-skip-list-values (generic function)
• map-skip-list-values (method)
• skip-list-add (generic function)
• skip-list-add (method)
• skip-list-delete (generic function)
• skip-list-delete (method)
• skip-list-empty? (generic function)
• skip-list-empty? (method)
• skip-list-fetch-all (generic function)
• skip-list-fetch-all (method)
• skip-list-keys-cursor (generic function)
• skip-list-keys-cursor (method)
• skip-list-length (function)
• (setf skip-list-length) (function)
• skip-list-lookup (generic function)
• skip-list-lookup (method)
• skip-list-range-cursor (generic function)
• skip-list-range-cursor (method)
• skip-list-range-cursor (class)
• skip-list-replace-kv (generic function)
• skip-list-replace-kv (method)
• skip-list-to-list (generic function)
• skip-list-to-list (method)
• skip-list-values-cursor (generic function)
• skip-list-values-cursor (method)
• skip-list? (function)
• sl-cursor-next (generic function)
• sl-cursor-next (method)
• sl-cursor-next (method)
• sl-cursor-next (method)
• sl-cursor-next (method)

Internal Definitions

• %gettimeofday (function)
• *mcas* (special variable)
• *mt-k-inverse-2^32f* (constant)
• *mt-k2^32* (constant)
• *mt-lower-mask* (constant)
• *mt-m* (constant)
• *mt-n* (constant)
• *mt-random-state* (special variable)
• *mt-upper-mask* (constant)
• +max-level+ (constant)
• +mcas-make-durable+ (constant)
• +skip-node-deleted+ (constant)
• +skip-node-forward+ (constant)
• +skip-node-key+ (constant)
• +skip-node-level+ (constant)
• +skip-node-timestamp+ (constant)
• +skip-node-value+ (constant)
• cas (macro)
• ccas (function)
• ccas-descriptor? (function)
• ccas-help (function)
• ccas-read (function)
• cd-control-index (function)
• (setf cd-control-index) (function)
• cd-control-vector (function)
• (setf cd-control-vector) (function)
• cd-equality (function)
• (setf cd-equality) (function)
• cd-index (function)
• (setf cd-index) (function)
• cd-new (function)
• (setf cd-new) (function)
• cd-old (function)
• (setf cd-old) (function)
• cd-vector (function)
• (setf cd-vector) (function)
• copy-ccas-descriptor (function)
• copy-mcas-descriptor (function)
• copy-mt-random-state (function)
• copy-safe-update (function)
• copy-skip-list (function)
• get-prop (function)
• get-vector-addr (function)
• gettimeofday (function)
• make-ccas-descriptor (function)
• make-head (function)
• make-mcas-descriptor (function)
• make-mt-random-state (function)
• make-safe-update (function)
• make-skip-node (function)
• make-skip-pq-node (function)
• mcas (function)
• mcas-count (function)
• (setf mcas-count) (function)
• mcas-descriptor? (function)
• mcas-equality (function)
• (setf mcas-equality) (function)
• mcas-error (condition)
• mcas-help (function)
• mcas-read (function)
• mcas-retries (function)
• (setf mcas-retries) (function)
• mcas-set (function)
• mcas-status (function)
• (setf mcas-status) (function)
• mcas-success-actions (function)
• (setf mcas-success-actions) (function)
• mcas-successful? (generic function)
• mcas-successful? (method)
• mcas-successful? (method)
• mcas-timestamp (function)
• (setf mcas-timestamp) (function)
• mcas-updates (function)
• (setf mcas-updates) (function)
• mt-genrand (function)
• mt-internal-make-random-state (function)
• mt-make-random-state-integer (function)
• mt-make-random-state-random (function)
• mt-random (function)
• mt-random-state (structure)
• mt-random-state-arr (function)
• (setf mt-random-state-arr) (function)
• mt-random-state-mti (function)
• (setf mt-random-state-mti) (function)
• mt-random-state-p (function)
• mt-refill (function)
• mt-tempering-shift-l (function)
• mt-tempering-shift-s (function)
• mt-tempering-shift-t (function)
• mt-tempering-shift-u (function)
• node-forward (function)
• null-pointer-type (class)
• print-skip-list (function)
• random-level (function)
• reset-mcas (function)
• safe-update? (function)
• skip-list (generic function)
• skip-list (method)
• (setf skip-list) (method)
• (setf skip-list) (generic function)
• skip-list (structure)
• skip-list-comparison (function)
• (setf skip-list-comparison) (function)
• skip-list-cursor (generic function)
• skip-list-cursor (method)
• skip-list-cursor (class)
• skip-list-cursor-node (generic function)
• skip-list-cursor-node (method)
• (setf skip-list-cursor-node) (method)
• (setf skip-list-cursor-node) (generic function)
• skip-list-duplicate-error (condition)
• skip-list-duplicates-allowed? (function)
• (setf skip-list-duplicates-allowed?) (function)
• skip-list-head (function)
• (setf skip-list-head) (function)
• skip-list-key-cursor (class)
• skip-list-key-equal (function)
• (setf skip-list-key-equal) (function)
• skip-list-kv-not-found-error (condition)
• skip-list-node-fn (function)
• (setf skip-list-node-fn) (function)
• skip-list-search (generic function)
• skip-list-search (method)
• skip-list-value-cursor (class)
• skip-list-value-equal (function)
• (setf skip-list-value-equal) (function)
• skip-node-deleted? (macro)
• skip-node-forward (macro)
• skip-node-key (macro)
• skip-node-level (macro)
• skip-node-timestamp (macro)
• skip-node-value (macro)
• skip-pq-add (generic function)
• skip-pq-add (method)
• skip-pq-delete (generic function)
• skip-pq-delete (method)
• skip-pq-search (generic function)
• skip-pq-search (method)
• sl-test (function)
• slrc-end (generic function)
• slrc-end (method)
• syscall-result-type (class)
• timeval-tclass (class)
• transaction-error (condition)
• update-index (function)
• (setf update-index) (function)
• update-new (function)
• (setf update-new) (function)
• update-old (function)
• (setf update-old) (function)
• update-vector (function)
• (setf update-vector) (function)
• while (macro)
• with-mcas (macro)
• with-recursive-mcas (macro)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Constants

Constant: +mcas-failed+

Package

cl-skip-list

Source

constants.lisp (file)

Constant: +mcas-succeeded+

Package

cl-skip-list

Source

constants.lisp (file)

Constant: +mcas-undecided+

Package

cl-skip-list

Source

constants.lisp (file)

5.1.2 Functions

Function: make-skip-list &key (HEAD HEAD) (KEY-EQUAL KEY-EQUAL) (VALUE-EQUAL VALUE-EQUAL) (COMPARISON COMPARISON) (DUPLICATES-ALLOWED? DUPLICATES-ALLOWED?) (NODE-FN NODE-FN) (LENGTH LENGTH)

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: make-skip-pq &key KEY-EQUAL VALUE-EQUAL COMPARISON HEAD-VALUE

Package

cl-skip-list

Source

skip-pq.lisp (file)

Function: skip-list-length INSTANCE

Function: (setf skip-list-length) VALUE INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: skip-list? OBJECT

Package

cl-skip-list

Source

skip-list.lisp (file)

5.1.3 Generic functions

Generic Function: delete-min SL

Package

cl-skip-list

Methods

Method: delete-min (SL skip-list)

Source

skip-pq.lisp (file)

Generic Function: less-than X Y

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

Package

cl-skip-list

Source

utilities.lisp (file)

Methods

Method: less-than (X symbol) (Y symbol)

Method: less-than (X symbol) (Y string)

Method: less-than (X symbol) (Y number)

Method: less-than (X number) (Y number)

Method: less-than (X number) (Y symbol)

Method: less-than (X number) (Y string)

Method: less-than (X string) (Y string)

Method: less-than (X string) (Y symbol)

Method: less-than (X string) (Y number)

Generic Function: map-skip-list FUN SL

Package

cl-skip-list

Methods

Method: map-skip-list FUN (SL skip-list)

Source

skip-list.lisp (file)

Generic Function: map-skip-list-values FUN SL

Package

cl-skip-list

Methods

Method: map-skip-list-values FUN (SL skip-list)

Source

skip-list.lisp (file)

Generic Function: skip-list-add SL KEY VALUE

Package

cl-skip-list

Methods

Method: skip-list-add (SL skip-list) KEY VALUE

Adds a new k/v pair to the skip list. Will not overwrite existing nodes or values. Use skip-list-replace-kv for that. Be prepared to catch a ’skip-list-duplicate-error.

Source

skip-list.lisp (file)

Generic Function: skip-list-delete SL KEY &optional VALUE

Package

cl-skip-list

Methods

Method: skip-list-delete (SL skip-list) KEY &optional VALUE

Delete a key or k/v pair from the skip list. If no value is specified and duplicates are allowed, it will delete the first key it finds.

Source

skip-list.lisp (file)

Generic Function: skip-list-empty? SL

Package

cl-skip-list

Methods

Method: skip-list-empty? (SL skip-list)

Source

skip-list.lisp (file)

Generic Function: skip-list-fetch-all SL KEY

Package

cl-skip-list

Methods

Method: skip-list-fetch-all (SL skip-list) KEY

Return all values for a key in a skip list where duplicates are allowed.

Source

skip-list.lisp (file)

Generic Function: skip-list-keys-cursor SL

Package

cl-skip-list

Methods

Method: skip-list-keys-cursor (SL skip-list)

Source

skip-list.lisp (file)

Generic Function: skip-list-lookup SL KEY &optional VALUE

Package

cl-skip-list

Methods

Method: skip-list-lookup (SL skip-list) KEY &optional VALUE

Source

skip-list.lisp (file)

Generic Function: skip-list-range-cursor SL START END

Package

cl-skip-list

Methods

Method: skip-list-range-cursor (SL skip-list) START END

Source

skip-list.lisp (file)

Generic Function: skip-list-replace-kv SL KEY NEW-VALUE &optional OLD-VALUE

Package

cl-skip-list

Methods

Method: skip-list-replace-kv (SL skip-list) KEY NEW-VALUE &optional OLD-VALUE

Replaces a node’s value with new-value. If old-value is supplied, will only replace the value if it matches old-value, otherwise throws ’skip-list-kv-not-found-error.

Source

skip-list.lisp (file)

Generic Function: skip-list-to-list SL

Package

cl-skip-list

Methods

Method: skip-list-to-list (SL skip-list)

Source

skip-list.lisp (file)

Generic Function: skip-list-values-cursor SL

Package

cl-skip-list

Methods

Method: skip-list-values-cursor (SL skip-list)

Source

skip-list.lisp (file)

Generic Function: sl-cursor-next SLC &optional EOC

Package

cl-skip-list

Methods

Method: sl-cursor-next (SLC skip-list-range-cursor) &optional EOC around

Source

skip-list.lisp (file)

Method: sl-cursor-next (SLC skip-list-key-cursor) &optional EOC around

Source

skip-list.lisp (file)

Method: sl-cursor-next (SLC skip-list-value-cursor) &optional EOC around

Source

skip-list.lisp (file)

Method: sl-cursor-next (SLC skip-list-cursor) &optional EOC

Source

skip-list.lisp (file)

5.1.4 Classes

Class: skip-list-range-cursor ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Direct superclasses

skip-list-cursor (class)

Direct methods

• sl-cursor-next (method)
• slrc-end (method)

Direct slots

Slot: end

Initargs

:end

Readers

slrc-end (generic function)

5.2 Internal definitions

5.2.1 Constants

Constant: *mt-k-inverse-2^32f*

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

Package

cl-skip-list

Source

random.lisp (file)

Constant: *mt-k2^32*

Package

cl-skip-list

Source

random.lisp (file)

Constant: *mt-lower-mask*

least significant r bits

Package

cl-skip-list

Source

random.lisp (file)

Constant: *mt-m*

Package

cl-skip-list

Source

random.lisp (file)

Constant: *mt-n*

Package

cl-skip-list

Source

random.lisp (file)

Constant: *mt-upper-mask*

most significant w-r bits

Package

cl-skip-list

Source

random.lisp (file)

Constant: +max-level+

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

Package

cl-skip-list

Source

skip-list.lisp (file)

Constant: +mcas-make-durable+

Package

cl-skip-list

Source

constants.lisp (file)

Constant: +skip-node-deleted+

Package

cl-skip-list

Source

skip-pq.lisp (file)

Constant: +skip-node-forward+

Package

cl-skip-list

Source

skip-list.lisp (file)

Constant: +skip-node-key+

Package

cl-skip-list

Source

skip-list.lisp (file)

Constant: +skip-node-level+

Package

cl-skip-list

Source

skip-list.lisp (file)

Constant: +skip-node-timestamp+

Package

cl-skip-list

Source

skip-pq.lisp (file)

Constant: +skip-node-value+

Package

cl-skip-list

Source

skip-list.lisp (file)

5.2.2 Special variables

Special Variable: *mcas*

Package

cl-skip-list

Source

constants.lisp (file)

Special Variable: *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)

Package

cl-skip-list

Source

random.lisp (file)

5.2.3 Macros

Macro: cas PLACE OLD NEW

Package

cl-skip-list

Source

mcas.lisp (file)

Macro: skip-node-deleted? NODE

Package

cl-skip-list

Source

skip-pq.lisp (file)

Macro: skip-node-forward NODE

Package

cl-skip-list

Source

skip-list.lisp (file)

Macro: skip-node-key NODE

Package

cl-skip-list

Source

skip-list.lisp (file)

Macro: skip-node-level NODE

Package

cl-skip-list

Source

skip-list.lisp (file)

Macro: skip-node-timestamp NODE

Package

cl-skip-list

Source

skip-pq.lisp (file)

Macro: skip-node-value NODE

Package

cl-skip-list

Source

skip-list.lisp (file)

Macro: while TEST &rest BODY

Package

cl-skip-list

Source

utilities.lisp (file)

Macro: with-mcas LAMBDA-LIST &body BODY

Package

cl-skip-list

Source

mcas.lisp (file)

Macro: with-recursive-mcas LAMBDA-LIST &body BODY

Package

cl-skip-list

Source

mcas.lisp (file)

5.2.4 Functions

Function: %gettimeofday TP TZP

Package

cl-skip-list

Source

gettimeofday.lisp (file)

Function: ccas VECTOR INDEX CONTROL-VECTOR CONTROL-INDEX OLD NEW &optional EQUALITY

Package

cl-skip-list

Source

mcas.lisp (file)

Function: ccas-descriptor? X

Package

cl-skip-list

Source

mcas.lisp (file)

Function: ccas-help CD

Package

cl-skip-list

Source

mcas.lisp (file)

Function: ccas-read VECTOR INDEX

Package

cl-skip-list

Source

mcas.lisp (file)

Function: cd-control-index STRUCTURE

Function: (setf cd-control-index) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: cd-control-vector STRUCTURE

Function: (setf cd-control-vector) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: cd-equality STRUCTURE

Function: (setf cd-equality) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: cd-index STRUCTURE

Function: (setf cd-index) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: cd-new STRUCTURE

Function: (setf cd-new) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: cd-old STRUCTURE

Function: (setf cd-old) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: cd-vector STRUCTURE

Function: (setf cd-vector) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: copy-ccas-descriptor SEQUENCE

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

Package

cl-skip-list

Source

SYS:SRC;CODE;SEQ.LISP (not found)

Function: copy-mcas-descriptor SEQUENCE

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

Package

cl-skip-list

Source

SYS:SRC;CODE;SEQ.LISP (not found)

Function: copy-mt-random-state INSTANCE

Package

cl-skip-list

Source

random.lisp (file)

Function: copy-safe-update SEQUENCE

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

Package

cl-skip-list

Source

SYS:SRC;CODE;SEQ.LISP (not found)

Function: copy-skip-list INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: get-prop PLIST PROP

Package

cl-skip-list

Source

utilities.lisp (file)

Function: get-vector-addr VECTOR

Package

cl-skip-list

Source

mcas.lisp (file)

Function: gettimeofday ()

Package

cl-skip-list

Source

gettimeofday.lisp (file)

Function: make-ccas-descriptor &key (VECTOR VECTOR) (CONTROL-VECTOR CONTROL-VECTOR) (CONTROL-INDEX CONTROL-INDEX) (INDEX INDEX) (OLD OLD) (NEW NEW) (EQUALITY EQUALITY)

Package

cl-skip-list

Source

mcas.lisp (file)

Function: make-head &key INITIAL-ELEMENT

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: make-mcas-descriptor &key (STATUS STATUS) (COUNT COUNT) (UPDATES UPDATES) (EQUALITY EQUALITY) (SUCCESS-ACTIONS SUCCESS-ACTIONS) (RETRIES RETRIES) (TIMESTAMP TIMESTAMP)

Package

cl-skip-list

Source

mcas.lisp (file)

Function: 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.

Package

cl-skip-list

Source

random.lisp (file)

Function: make-safe-update &key (VECTOR VECTOR) (INDEX INDEX) (OLD OLD) (NEW NEW)

Package

cl-skip-list

Source

mcas.lisp (file)

Function: make-skip-node KEY VALUE SIZE &key INITIAL-ELEMENT

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: make-skip-pq-node KEY VALUE SIZE &key INITIAL-ELEMENT TIMESTAMP

Package

cl-skip-list

Source

skip-pq.lisp (file)

Function: mcas MD

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-count STRUCTURE

Function: (setf mcas-count) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-descriptor? X

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-equality STRUCTURE

Function: (setf mcas-equality) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-help MD

This is the bulk of the transaction logic.

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-read VECTOR INDEX

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-retries STRUCTURE

Function: (setf mcas-retries) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-set VECTOR INDEX OLD NEW

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-status STRUCTURE

Function: (setf mcas-status) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-success-actions STRUCTURE

Function: (setf mcas-success-actions) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-timestamp STRUCTURE

Function: (setf mcas-timestamp) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mcas-updates STRUCTURE

Function: (setf mcas-updates) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: mt-genrand ()

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-internal-make-random-state &key (MTI MTI) (ARR ARR)

Package

cl-skip-list

Source

random.lisp (file)

Function: 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.

Package

cl-skip-list

Source

random.lisp (file)

Function: 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.

Package

cl-skip-list

Source

random.lisp (file)

Function: 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!

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-random-state-arr INSTANCE

Function: (setf mt-random-state-arr) VALUE INSTANCE

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-random-state-mti INSTANCE

Function: (setf mt-random-state-mti) VALUE INSTANCE

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-random-state-p OBJECT

Package

cl-skip-list

Source

random.lisp (file)

Function: 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.

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-tempering-shift-l N

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-tempering-shift-s N

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-tempering-shift-t N

Package

cl-skip-list

Source

random.lisp (file)

Function: mt-tempering-shift-u N

Package

cl-skip-list

Source

random.lisp (file)

Function: node-forward NODE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: print-skip-list SL STREAM DEPTH

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: random-level ()

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

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: reset-mcas MCAS

Package

cl-skip-list

Source

mcas.lisp (file)

Function: safe-update? X

Package

cl-skip-list

Source

mcas.lisp (file)

Function: skip-list-comparison INSTANCE

Function: (setf skip-list-comparison) VALUE INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: skip-list-duplicates-allowed? INSTANCE

Function: (setf skip-list-duplicates-allowed?) VALUE INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: skip-list-head INSTANCE

Function: (setf skip-list-head) VALUE INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: skip-list-key-equal INSTANCE

Function: (setf skip-list-key-equal) VALUE INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: skip-list-node-fn INSTANCE

Function: (setf skip-list-node-fn) VALUE INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: skip-list-value-equal INSTANCE

Function: (setf skip-list-value-equal) VALUE INSTANCE

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: sl-test ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Function: update-index STRUCTURE

Function: (setf update-index) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: update-new STRUCTURE

Function: (setf update-new) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: update-old STRUCTURE

Function: (setf update-old) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

Function: update-vector STRUCTURE

Function: (setf update-vector) VALUE STRUCTURE

Package

cl-skip-list

Source

mcas.lisp (file)

5.2.5 Generic functions

Generic Function: mcas-successful? THING

Package

cl-skip-list

Source

mcas.lisp (file)

Methods

Method: mcas-successful? (S symbol)

Method: mcas-successful? (MD array)

Generic Function: skip-list OBJECT

Generic Function: (setf skip-list) NEW-VALUE OBJECT

Package

cl-skip-list

Methods

Method: skip-list (SKIP-LIST-CURSOR skip-list-cursor)

automatically generated reader method

Source

skip-list.lisp (file)

Method: (setf skip-list) NEW-VALUE (SKIP-LIST-CURSOR skip-list-cursor)

automatically generated writer method

Source

skip-list.lisp (file)

Generic Function: skip-list-cursor SL &key CURSOR CURSOR-CLASS

Package

cl-skip-list

Methods

Method: skip-list-cursor (SL skip-list) &key CURSOR CURSOR-CLASS

Source

skip-list.lisp (file)

Generic Function: skip-list-cursor-node OBJECT

Generic Function: (setf skip-list-cursor-node) NEW-VALUE OBJECT

Package

cl-skip-list

Methods

Method: skip-list-cursor-node (SKIP-LIST-CURSOR skip-list-cursor)

automatically generated reader method

Source

skip-list.lisp (file)

Method: (setf skip-list-cursor-node) NEW-VALUE (SKIP-LIST-CURSOR skip-list-cursor)

automatically generated writer method

Source

skip-list.lisp (file)

Generic Function: skip-list-search SL KEY &optional VALUE

Package

cl-skip-list

Methods

Method: skip-list-search (SL skip-list) KEY &optional VALUE

Source

skip-list.lisp (file)

Generic Function: skip-pq-add SL KEY VALUE

Package

cl-skip-list

Methods

Method: skip-pq-add (SL skip-list) KEY VALUE

Source

skip-pq.lisp (file)

Generic Function: skip-pq-delete SL NODE

Package

cl-skip-list

Methods

Method: skip-pq-delete (SL skip-list) NODE

Delete a key or k/v pair from the skip pq. If no value is specified and duplicates are allowed, it will delete the first key it finds.

Source

skip-pq.lisp (file)

Generic Function: skip-pq-search SL KEY ID

Package

cl-skip-list

Methods

Method: skip-pq-search (SL skip-list) KEY ID

Source

skip-pq.lisp (file)

Generic Function: slrc-end OBJECT

Package

cl-skip-list

Methods

Method: slrc-end (SKIP-LIST-RANGE-CURSOR skip-list-range-cursor)

automatically generated reader method

Source

skip-list.lisp (file)

5.2.6 Conditions

Condition: mcas-error ()

Package

cl-skip-list

Source

mcas.lisp (file)

Direct superclasses

error (condition)

Direct slots

Slot: instance

Initargs

:instance

Slot: reason

Initargs

:reason

Condition: skip-list-duplicate-error ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Direct superclasses

error (condition)

Direct slots

Slot: key

Initargs

:key

Slot: value

Initargs

:value

Condition: skip-list-kv-not-found-error ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Direct superclasses

error (condition)

Direct slots

Slot: key

Initargs

:key

Slot: value

Initargs

:value

Condition: transaction-error ()

Package

cl-skip-list

Source

mcas.lisp (file)

Direct superclasses

error (condition)

Direct slots

Slot: instance

Initargs

:instance

Slot: reason

Initargs

:reason

5.2.7 Structures

Structure: mt-random-state ()

Package

cl-skip-list

Source

random.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots

Slot: mti

Readers

mt-random-state-mti (function)

Writers

(setf mt-random-state-mti) (function)

Slot: arr

Readers

mt-random-state-arr (function)

Writers

(setf mt-random-state-arr) (function)

Structure: skip-list ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

• delete-min (method)
• skip-pq-delete (method)
• skip-pq-add (method)
• skip-pq-search (method)
• skip-list-fetch-all (method)
• map-skip-list-values (method)
• map-skip-list (method)
• skip-list-range-cursor (method)
• skip-list-keys-cursor (method)
• skip-list-values-cursor (method)
• skip-list-cursor (method)
• skip-list-delete (method)
• skip-list-add (method)
• skip-list-replace-kv (method)
• skip-list-lookup (method)
• skip-list-to-list (method)
• skip-list-empty? (method)
• skip-list-search (method)
• print-object (method)

Direct slots

Slot: head

Initform

(cl-skip-list::make-head)

Readers

skip-list-head (function)

Writers

(setf skip-list-head) (function)

Slot: key-equal

Initform

(function equal)

Readers

skip-list-key-equal (function)

Writers

(setf skip-list-key-equal) (function)

Slot: value-equal

Initform

(function equal)

Readers

skip-list-value-equal (function)

Writers

(setf skip-list-value-equal) (function)

Slot: comparison

Initform

(function cl-skip-list:less-than)

Readers

skip-list-comparison (function)

Writers

(setf skip-list-comparison) (function)

Slot: duplicates-allowed?

Readers

skip-list-duplicates-allowed? (function)

Writers

(setf skip-list-duplicates-allowed?) (function)

Slot: node-fn

Initform

(function cl-skip-list::make-skip-node)

Readers

skip-list-node-fn (function)

Writers

(setf skip-list-node-fn) (function)

Slot: length

Type

(unsigned-byte 64)

Initform

0

Readers

skip-list-length (function)

Writers

(setf skip-list-length) (function)

5.2.8 Classes

Class: null-pointer-type ()

Package

cl-skip-list

Source

gettimeofday.lisp (file)

Direct superclasses

enhanced-foreign-type (class)

Direct methods

translate-to-foreign (method)

Direct Default Initargs

Initarg	Value
:actual-type	(quote (:pointer))

Class: skip-list-cursor ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• skip-list-value-cursor (class)
• skip-list-key-cursor (class)
• skip-list-range-cursor (class)

Direct methods

• sl-cursor-next (method)
• skip-list (method)
• skip-list (method)
• skip-list-cursor-node (method)
• skip-list-cursor-node (method)

Direct slots

Slot: node

Initargs

:node

Readers

skip-list-cursor-node (generic function)

Writers

(setf skip-list-cursor-node) (generic function)

Slot: skip-list

Initargs

:skip-list

Readers

skip-list (generic function)

Writers

(setf skip-list) (generic function)

Class: skip-list-key-cursor ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Direct superclasses

skip-list-cursor (class)

Direct methods

sl-cursor-next (method)

Class: skip-list-value-cursor ()

Package

cl-skip-list

Source

skip-list.lisp (file)

Direct superclasses

skip-list-cursor (class)

Direct methods

sl-cursor-next (method)

Class: syscall-result-type ()

Package

cl-skip-list

Source

gettimeofday.lisp (file)

Direct superclasses

enhanced-foreign-type (class)

Direct methods

translate-from-foreign (method)

Direct Default Initargs

Initarg	Value
:actual-type	(quote (:int))

Class: timeval-tclass ()

Package

cl-skip-list

Source

gettimeofday.lisp (file)

Direct superclasses

• translatable-foreign-type (class)
• foreign-struct-type (class)

Appendix A Indexes

A.1 Concepts

A.2 Functions