The cl-skip-list Reference Manual

This is the cl-skip-list Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed May 15 04:29:26 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 cl-skip-list

Concurrent lock-free skip list.

Maintainer

Kevin Raison

Author

Kevin Raison <>

Long Description

Concurrent lock-free skip list.

Version

0.1

Dependency

cffi (system).

Source

cl-skip-list.asd.

Child Components

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/cl-skip-list.asd

Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

ASDF Systems

cl-skip-list.

Packages

cl-skip-list-system.


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

Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Packages

cl-skip-list.


3.1.3 cl-skip-list/random.lisp

Dependency

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

Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Internals

3.1.4 cl-skip-list/utilities.lisp

Dependency

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

Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Public Interface

less-than (generic function).

Internals

3.1.5 cl-skip-list/gettimeofday.lisp

Dependency

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

Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Public Interface
Internals

3.1.6 cl-skip-list/constants.lisp

Dependency

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

Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Public Interface
Internals

3.1.7 cl-skip-list/mcas.lisp

Dependencies
Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Internals

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

Dependencies
Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Public Interface
Internals

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

Dependency

skip-list.lisp (file).

Source

cl-skip-list.asd.

Parent Component

cl-skip-list (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 cl-skip-list

Source

cl-skip-list-package.lisp.

Use List
  • cffi.
  • common-lisp.
Public Interface
Internals

4.2 cl-skip-list-system

Source

cl-skip-list.asd.

Use List
  • asdf/interface.
  • common-lisp.

5 Definitions

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


5.1 Public Interface


5.1.1 Constants

Constant: +mcas-failed+
Package

cl-skip-list.

Source

constants.lisp.

Constant: +mcas-succeeded+
Package

cl-skip-list.

Source

constants.lisp.

Constant: +mcas-undecided+
Package

cl-skip-list.

Source

constants.lisp.


5.1.2 Ordinary functions

Function: make-skip-list (&key head key-equal value-equal comparison duplicates-allowed? node-fn length)
Package

cl-skip-list.

Source

skip-list.lisp.

Function: make-skip-pq (&key key-equal value-equal comparison head-value)
Package

cl-skip-list.

Source

skip-pq.lisp.

Reader: skip-list-length (instance)
Writer: (setf skip-list-length) (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Target Slot

length.

Function: skip-list? (object)
Package

cl-skip-list.

Source

skip-list.lisp.


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.

Generic Function: less-than (x y)

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

Package

cl-skip-list.

Source

utilities.lisp.

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.

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.

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.

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.

Generic Function: skip-list-empty? (sl)
Package

cl-skip-list.

Methods
Method: skip-list-empty? ((sl skip-list))
Source

skip-list.lisp.

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.

Generic Function: skip-list-keys-cursor (sl)
Package

cl-skip-list.

Methods
Method: skip-list-keys-cursor ((sl skip-list))
Source

skip-list.lisp.

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.

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.

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.

Generic Function: skip-list-to-list (sl)
Package

cl-skip-list.

Methods
Method: skip-list-to-list ((sl skip-list))
Source

skip-list.lisp.

Generic Function: skip-list-values-cursor (sl)
Package

cl-skip-list.

Methods
Method: skip-list-values-cursor ((sl skip-list))
Source

skip-list.lisp.

Generic Function: sl-cursor-next (slc &optional eoc)
Package

cl-skip-list.

Methods
Method: sl-cursor-next :around ((slc skip-list-range-cursor) &optional eoc)
Source

skip-list.lisp.

Method: sl-cursor-next :around ((slc skip-list-key-cursor) &optional eoc)
Source

skip-list.lisp.

Method: sl-cursor-next :around ((slc skip-list-value-cursor) &optional eoc)
Source

skip-list.lisp.

Method: sl-cursor-next ((slc skip-list-cursor) &optional eoc)
Source

skip-list.lisp.


5.1.4 Standalone methods

Method: print-object ((object skip-list) stream)
Source

skip-list.lisp.

Method: translate-from-foreign (value (type syscall-result-type))
Package

cffi.

Source

gettimeofday.lisp.

Method: translate-to-foreign (value (type null-pointer-type))
Package

cffi.

Source

gettimeofday.lisp.


5.1.5 Classes

Class: skip-list-range-cursor
Package

cl-skip-list.

Source

skip-list.lisp.

Direct superclasses

skip-list-cursor.

Direct methods
Direct slots
Slot: end
Initargs

:end

Readers

slrc-end.

Writers

This slot is read-only.


5.2 Internals


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.

Constant: *mt-k2^32*
Package

cl-skip-list.

Source

random.lisp.

Constant: *mt-lower-mask*

least significant r bits

Package

cl-skip-list.

Source

random.lisp.

Constant: *mt-m*
Package

cl-skip-list.

Source

random.lisp.

Constant: *mt-n*
Package

cl-skip-list.

Source

random.lisp.

Constant: *mt-upper-mask*

most significant w-r bits

Package

cl-skip-list.

Source

random.lisp.

Constant: +max-level+

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

Package

cl-skip-list.

Source

skip-list.lisp.

Constant: +mcas-make-durable+
Package

cl-skip-list.

Source

constants.lisp.

Constant: +skip-node-deleted+
Package

cl-skip-list.

Source

skip-pq.lisp.

Constant: +skip-node-forward+
Package

cl-skip-list.

Source

skip-list.lisp.

Constant: +skip-node-key+
Package

cl-skip-list.

Source

skip-list.lisp.

Constant: +skip-node-level+
Package

cl-skip-list.

Source

skip-list.lisp.

Constant: +skip-node-timestamp+
Package

cl-skip-list.

Source

skip-pq.lisp.

Constant: +skip-node-value+
Package

cl-skip-list.

Source

skip-list.lisp.


5.2.2 Special variables

Special Variable: *mcas*
Package

cl-skip-list.

Source

constants.lisp.

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.


5.2.3 Macros

Macro: cas (place old new)
Package

cl-skip-list.

Source

mcas.lisp.

Macro: skip-node-deleted? (node)
Package

cl-skip-list.

Source

skip-pq.lisp.

Macro: skip-node-forward (node)
Package

cl-skip-list.

Source

skip-list.lisp.

Macro: skip-node-key (node)
Package

cl-skip-list.

Source

skip-list.lisp.

Macro: skip-node-level (node)
Package

cl-skip-list.

Source

skip-list.lisp.

Macro: skip-node-timestamp (node)
Package

cl-skip-list.

Source

skip-pq.lisp.

Macro: skip-node-value (node)
Package

cl-skip-list.

Source

skip-list.lisp.

Macro: while (test &rest body)
Package

cl-skip-list.

Source

utilities.lisp.

Macro: with-mcas (lambda-list &body body)
Package

cl-skip-list.

Source

mcas.lisp.

Macro: with-recursive-mcas (lambda-list &body body)
Package

cl-skip-list.

Source

mcas.lisp.


5.2.4 Ordinary functions

Function: %gettimeofday (tp tzp)
Package

cl-skip-list.

Source

gettimeofday.lisp.

Function: ccas (vector index control-vector control-index old new &optional equality)
Package

cl-skip-list.

Source

mcas.lisp.

Function: ccas-descriptor? (x)
Package

cl-skip-list.

Source

mcas.lisp.

Function: ccas-help (cd)
Package

cl-skip-list.

Source

mcas.lisp.

Function: ccas-read (vector index)
Package

cl-skip-list.

Source

mcas.lisp.

Function: cd-control-index (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf cd-control-index) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: cd-control-vector (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf cd-control-vector) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: cd-equality (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf cd-equality) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: cd-index (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf cd-index) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: cd-new (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf cd-new) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: cd-old (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf cd-old) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: cd-vector (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf cd-vector) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: copy-ccas-descriptor (sequence)

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

Package

cl-skip-list.

Alias for

copy-seq.

Function: copy-mcas-descriptor (sequence)

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

Package

cl-skip-list.

Alias for

copy-seq.

Function: copy-mt-random-state (instance)
Package

cl-skip-list.

Source

random.lisp.

Function: copy-safe-update (sequence)

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

Package

cl-skip-list.

Alias for

copy-seq.

Function: copy-skip-list (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Function: get-prop (plist prop)
Package

cl-skip-list.

Source

utilities.lisp.

Function: get-vector-addr (vector)
Package

cl-skip-list.

Source

mcas.lisp.

Function: gettimeofday ()
Package

cl-skip-list.

Source

gettimeofday.lisp.

Function: make-ccas-descriptor (&key vector control-vector control-index index old new equality)
Package

cl-skip-list.

Source

mcas.lisp.

Function: make-head (&key initial-element)
Package

cl-skip-list.

Source

skip-list.lisp.

Function: make-mcas-descriptor (&key status count updates equality success-actions retries timestamp)
Package

cl-skip-list.

Source

mcas.lisp.

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.

Function: make-safe-update (&key vector index old new)
Package

cl-skip-list.

Source

mcas.lisp.

Function: make-skip-node (key value size &key initial-element)
Package

cl-skip-list.

Source

skip-list.lisp.

Function: make-skip-pq-node (key value size &key initial-element timestamp)
Package

cl-skip-list.

Source

skip-pq.lisp.

Function: mcas (md)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-count (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf mcas-count) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-descriptor? (x)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-equality (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf mcas-equality) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-help (md)

This is the bulk of the transaction logic.

Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-read (vector index)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-retries (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf mcas-retries) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-set (vector index old new)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-status (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf mcas-status) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-success-actions (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf mcas-success-actions) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-timestamp (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf mcas-timestamp) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mcas-updates (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf mcas-updates) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: mt-genrand ()
Package

cl-skip-list.

Source

random.lisp.

Function: mt-internal-make-random-state (&key mti arr)
Package

cl-skip-list.

Source

random.lisp.

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.

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.

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.

Reader: mt-random-state-arr (instance)
Writer: (setf mt-random-state-arr) (instance)
Package

cl-skip-list.

Source

random.lisp.

Target Slot

arr.

Reader: mt-random-state-mti (instance)
Writer: (setf mt-random-state-mti) (instance)
Package

cl-skip-list.

Source

random.lisp.

Target Slot

mti.

Function: mt-random-state-p (object)
Package

cl-skip-list.

Source

random.lisp.

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.

Function: mt-tempering-shift-l (n)
Package

cl-skip-list.

Source

random.lisp.

Function: mt-tempering-shift-s (n)
Package

cl-skip-list.

Source

random.lisp.

Function: mt-tempering-shift-t (n)
Package

cl-skip-list.

Source

random.lisp.

Function: mt-tempering-shift-u (n)
Package

cl-skip-list.

Source

random.lisp.

Function: node-forward (node)
Package

cl-skip-list.

Source

skip-list.lisp.

Function: print-skip-list (sl stream depth)
Package

cl-skip-list.

Source

skip-list.lisp.

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.

Function: reset-mcas (mcas)
Package

cl-skip-list.

Source

mcas.lisp.

Function: safe-update? (x)
Package

cl-skip-list.

Source

mcas.lisp.

Reader: skip-list-comparison (instance)
Writer: (setf skip-list-comparison) (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Target Slot

comparison.

Reader: skip-list-duplicates-allowed? (instance)
Writer: (setf skip-list-duplicates-allowed?) (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Target Slot

duplicates-allowed?.

Reader: skip-list-head (instance)
Writer: (setf skip-list-head) (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Target Slot

head.

Reader: skip-list-key-equal (instance)
Writer: (setf skip-list-key-equal) (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Target Slot

key-equal.

Reader: skip-list-node-fn (instance)
Writer: (setf skip-list-node-fn) (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Target Slot

node-fn.

Reader: skip-list-value-equal (instance)
Writer: (setf skip-list-value-equal) (instance)
Package

cl-skip-list.

Source

skip-list.lisp.

Target Slot

value-equal.

Function: sl-test ()
Package

cl-skip-list.

Source

skip-list.lisp.

Function: update-index (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf update-index) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: update-new (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf update-new) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: update-old (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf update-old) (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: update-vector (structure)
Package

cl-skip-list.

Source

mcas.lisp.

Function: (setf update-vector) (structure)
Package

cl-skip-list.

Source

mcas.lisp.


5.2.5 Generic functions

Generic Function: mcas-successful? (thing)
Package

cl-skip-list.

Source

mcas.lisp.

Methods
Method: mcas-successful? ((s symbol))
Method: mcas-successful? ((md array))
Generic Reader: skip-list (object)
Package

cl-skip-list.

Methods
Reader Method: skip-list ((skip-list-cursor skip-list-cursor))

automatically generated reader method

Source

skip-list.lisp.

Target Slot

skip-list.

Generic Writer: (setf skip-list) (object)
Package

cl-skip-list.

Methods
Writer Method: (setf skip-list) ((skip-list-cursor skip-list-cursor))

automatically generated writer method

Source

skip-list.lisp.

Target Slot

skip-list.

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.

Generic Reader: skip-list-cursor-node (object)
Package

cl-skip-list.

Methods
Reader Method: skip-list-cursor-node ((skip-list-cursor skip-list-cursor))

automatically generated reader method

Source

skip-list.lisp.

Target Slot

node.

Generic Writer: (setf skip-list-cursor-node) (object)
Package

cl-skip-list.

Methods
Writer Method: (setf skip-list-cursor-node) ((skip-list-cursor skip-list-cursor))

automatically generated writer method

Source

skip-list.lisp.

Target Slot

node.

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.

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.

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.

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.

Generic Reader: slrc-end (object)
Package

cl-skip-list.

Methods
Reader Method: slrc-end ((skip-list-range-cursor skip-list-range-cursor))

automatically generated reader method

Source

skip-list.lisp.

Target Slot

end.


5.2.6 Conditions

Condition: mcas-error
Package

cl-skip-list.

Source

mcas.lisp.

Direct superclasses

error.

Direct slots
Slot: instance
Initargs

:instance

Slot: reason
Initargs

:reason

Condition: skip-list-duplicate-error
Package

cl-skip-list.

Source

skip-list.lisp.

Direct superclasses

error.

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.

Direct superclasses

error.

Direct slots
Slot: key
Initargs

:key

Slot: value
Initargs

:value

Condition: transaction-error
Package

cl-skip-list.

Source

mcas.lisp.

Direct superclasses

error.

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.

Direct superclasses

structure-object.

Direct slots
Slot: mti
Readers

mt-random-state-mti.

Writers

(setf mt-random-state-mti).

Slot: arr
Readers

mt-random-state-arr.

Writers

(setf mt-random-state-arr).

Structure: skip-list
Package

cl-skip-list.

Source

skip-list.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: head
Initform

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

Readers

skip-list-head.

Writers

(setf skip-list-head).

Slot: key-equal
Initform

(function equal)

Readers

skip-list-key-equal.

Writers

(setf skip-list-key-equal).

Slot: value-equal
Initform

(function equal)

Readers

skip-list-value-equal.

Writers

(setf skip-list-value-equal).

Slot: comparison
Initform

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

Readers

skip-list-comparison.

Writers

(setf skip-list-comparison).

Slot: duplicates-allowed?
Readers

skip-list-duplicates-allowed?.

Writers

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

Slot: node-fn
Initform

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

Readers

skip-list-node-fn.

Writers

(setf skip-list-node-fn).

Slot: length
Package

common-lisp.

Type

(unsigned-byte 64)

Initform

0

Readers

skip-list-length.

Writers

(setf skip-list-length).


5.2.8 Classes

Class: null-pointer-type
Package

cl-skip-list.

Source

gettimeofday.lisp.

Direct superclasses

enhanced-foreign-type.

Direct methods

translate-to-foreign.

Direct Default Initargs
InitargValue
:actual-type(quote (pointer))
Class: skip-list-cursor
Package

cl-skip-list.

Source

skip-list.lisp.

Direct subclasses
Direct methods
Direct slots
Slot: node
Initargs

:node

Readers

skip-list-cursor-node.

Writers

(setf skip-list-cursor-node).

Slot: skip-list
Initargs

:skip-list

Readers

skip-list.

Writers

(setf skip-list).

Class: skip-list-key-cursor
Package

cl-skip-list.

Source

skip-list.lisp.

Direct superclasses

skip-list-cursor.

Direct methods

sl-cursor-next.

Class: skip-list-value-cursor
Package

cl-skip-list.

Source

skip-list.lisp.

Direct superclasses

skip-list-cursor.

Direct methods

sl-cursor-next.

Class: syscall-result-type
Package

cl-skip-list.

Source

gettimeofday.lisp.

Direct superclasses

enhanced-foreign-type.

Direct methods

translate-from-foreign.

Direct Default Initargs
InitargValue
:actual-type(quote (int))
Class: timeval-tclass
Package

cl-skip-list.

Source

gettimeofday.lisp.

Direct superclasses
  • foreign-struct-type.
  • translatable-foreign-type.

Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
C   D   F   G   L   M   N   P   R   S   T   U   W  
Index Entry  Section

%
%gettimeofday: Private ordinary functions

(
(setf cd-control-index): Private ordinary functions
(setf cd-control-vector): Private ordinary functions
(setf cd-equality): Private ordinary functions
(setf cd-index): Private ordinary functions
(setf cd-new): Private ordinary functions
(setf cd-old): Private ordinary functions
(setf cd-vector): Private ordinary functions
(setf mcas-count): Private ordinary functions
(setf mcas-equality): Private ordinary functions
(setf mcas-retries): Private ordinary functions
(setf mcas-status): Private ordinary functions
(setf mcas-success-actions): Private ordinary functions
(setf mcas-timestamp): Private ordinary functions
(setf mcas-updates): Private ordinary functions
(setf mt-random-state-arr): Private ordinary functions
(setf mt-random-state-mti): Private ordinary functions
(setf skip-list): Private generic functions
(setf skip-list): Private generic functions
(setf skip-list-comparison): Private ordinary functions
(setf skip-list-cursor-node): Private generic functions
(setf skip-list-cursor-node): Private generic functions
(setf skip-list-duplicates-allowed?): Private ordinary functions
(setf skip-list-head): Private ordinary functions
(setf skip-list-key-equal): Private ordinary functions
(setf skip-list-length): Public ordinary functions
(setf skip-list-node-fn): Private ordinary functions
(setf skip-list-value-equal): Private ordinary functions
(setf update-index): Private ordinary functions
(setf update-new): Private ordinary functions
(setf update-old): Private ordinary functions
(setf update-vector): Private ordinary functions

C
cas: Private macros
ccas: Private ordinary functions
ccas-descriptor?: Private ordinary functions
ccas-help: Private ordinary functions
ccas-read: Private ordinary functions
cd-control-index: Private ordinary functions
cd-control-vector: Private ordinary functions
cd-equality: Private ordinary functions
cd-index: Private ordinary functions
cd-new: Private ordinary functions
cd-old: Private ordinary functions
cd-vector: Private ordinary functions
copy-ccas-descriptor: Private ordinary functions
copy-mcas-descriptor: Private ordinary functions
copy-mt-random-state: Private ordinary functions
copy-safe-update: Private ordinary functions
copy-skip-list: Private ordinary functions

D
delete-min: Public generic functions
delete-min: Public generic functions

F
Function, %gettimeofday: Private ordinary functions
Function, (setf cd-control-index): Private ordinary functions
Function, (setf cd-control-vector): Private ordinary functions
Function, (setf cd-equality): Private ordinary functions
Function, (setf cd-index): Private ordinary functions
Function, (setf cd-new): Private ordinary functions
Function, (setf cd-old): Private ordinary functions
Function, (setf cd-vector): Private ordinary functions
Function, (setf mcas-count): Private ordinary functions
Function, (setf mcas-equality): Private ordinary functions
Function, (setf mcas-retries): Private ordinary functions
Function, (setf mcas-status): Private ordinary functions
Function, (setf mcas-success-actions): Private ordinary functions
Function, (setf mcas-timestamp): Private ordinary functions
Function, (setf mcas-updates): Private ordinary functions
Function, (setf mt-random-state-arr): Private ordinary functions
Function, (setf mt-random-state-mti): Private ordinary functions
Function, (setf skip-list-comparison): Private ordinary functions
Function, (setf skip-list-duplicates-allowed?): Private ordinary functions
Function, (setf skip-list-head): Private ordinary functions
Function, (setf skip-list-key-equal): Private ordinary functions
Function, (setf skip-list-length): Public ordinary functions
Function, (setf skip-list-node-fn): Private ordinary functions
Function, (setf skip-list-value-equal): Private ordinary functions
Function, (setf update-index): Private ordinary functions
Function, (setf update-new): Private ordinary functions
Function, (setf update-old): Private ordinary functions
Function, (setf update-vector): Private ordinary functions
Function, ccas: Private ordinary functions
Function, ccas-descriptor?: Private ordinary functions
Function, ccas-help: Private ordinary functions
Function, ccas-read: Private ordinary functions
Function, cd-control-index: Private ordinary functions
Function, cd-control-vector: Private ordinary functions
Function, cd-equality: Private ordinary functions
Function, cd-index: Private ordinary functions
Function, cd-new: Private ordinary functions
Function, cd-old: Private ordinary functions
Function, cd-vector: Private ordinary functions
Function, copy-ccas-descriptor: Private ordinary functions
Function, copy-mcas-descriptor: Private ordinary functions
Function, copy-mt-random-state: Private ordinary functions
Function, copy-safe-update: Private ordinary functions
Function, copy-skip-list: Private ordinary functions
Function, get-prop: Private ordinary functions
Function, get-vector-addr: Private ordinary functions
Function, gettimeofday: Private ordinary functions
Function, make-ccas-descriptor: Private ordinary functions
Function, make-head: Private ordinary functions
Function, make-mcas-descriptor: Private ordinary functions
Function, make-mt-random-state: Private ordinary functions
Function, make-safe-update: Private ordinary functions
Function, make-skip-list: Public ordinary functions
Function, make-skip-node: Private ordinary functions
Function, make-skip-pq: Public ordinary functions
Function, make-skip-pq-node: Private ordinary functions
Function, mcas: Private ordinary functions
Function, mcas-count: Private ordinary functions
Function, mcas-descriptor?: Private ordinary functions
Function, mcas-equality: Private ordinary functions
Function, mcas-help: Private ordinary functions
Function, mcas-read: Private ordinary functions
Function, mcas-retries: Private ordinary functions
Function, mcas-set: Private ordinary functions
Function, mcas-status: Private ordinary functions
Function, mcas-success-actions: Private ordinary functions
Function, mcas-timestamp: Private ordinary functions
Function, mcas-updates: Private ordinary functions
Function, mt-genrand: Private ordinary functions
Function, mt-internal-make-random-state: Private ordinary functions
Function, mt-make-random-state-integer: Private ordinary functions
Function, mt-make-random-state-random: Private ordinary functions
Function, mt-random: Private ordinary functions
Function, mt-random-state-arr: Private ordinary functions
Function, mt-random-state-mti: Private ordinary functions
Function, mt-random-state-p: Private ordinary functions
Function, mt-refill: Private ordinary functions
Function, mt-tempering-shift-l: Private ordinary functions
Function, mt-tempering-shift-s: Private ordinary functions
Function, mt-tempering-shift-t: Private ordinary functions
Function, mt-tempering-shift-u: Private ordinary functions
Function, node-forward: Private ordinary functions
Function, print-skip-list: Private ordinary functions
Function, random-level: Private ordinary functions
Function, reset-mcas: Private ordinary functions
Function, safe-update?: Private ordinary functions
Function, skip-list-comparison: Private ordinary functions
Function, skip-list-duplicates-allowed?: Private ordinary functions
Function, skip-list-head: Private ordinary functions
Function, skip-list-key-equal: Private ordinary functions
Function, skip-list-length: Public ordinary functions
Function, skip-list-node-fn: Private ordinary functions
Function, skip-list-value-equal: Private ordinary functions
Function, skip-list?: Public ordinary functions
Function, sl-test: Private ordinary functions
Function, update-index: Private ordinary functions
Function, update-new: Private ordinary functions
Function, update-old: Private ordinary functions
Function, update-vector: Private ordinary functions

G
Generic Function, (setf skip-list): Private generic functions
Generic Function, (setf skip-list-cursor-node): Private generic functions
Generic Function, delete-min: Public generic functions
Generic Function, less-than: Public generic functions
Generic Function, map-skip-list: Public generic functions
Generic Function, map-skip-list-values: Public generic functions
Generic Function, mcas-successful?: Private generic functions
Generic Function, skip-list: Private generic functions
Generic Function, skip-list-add: Public generic functions
Generic Function, skip-list-cursor: Private generic functions
Generic Function, skip-list-cursor-node: Private generic functions
Generic Function, skip-list-delete: Public generic functions
Generic Function, skip-list-empty?: Public generic functions
Generic Function, skip-list-fetch-all: Public generic functions
Generic Function, skip-list-keys-cursor: Public generic functions
Generic Function, skip-list-lookup: Public generic functions
Generic Function, skip-list-range-cursor: Public generic functions
Generic Function, skip-list-replace-kv: Public generic functions
Generic Function, skip-list-search: Private generic functions
Generic Function, skip-list-to-list: Public generic functions
Generic Function, skip-list-values-cursor: Public generic functions
Generic Function, skip-pq-add: Private generic functions
Generic Function, skip-pq-delete: Private generic functions
Generic Function, skip-pq-search: Private generic functions
Generic Function, sl-cursor-next: Public generic functions
Generic Function, slrc-end: Private generic functions
get-prop: Private ordinary functions
get-vector-addr: Private ordinary functions
gettimeofday: Private ordinary functions

L
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions
less-than: Public generic functions

M
Macro, cas: Private macros
Macro, skip-node-deleted?: Private macros
Macro, skip-node-forward: Private macros
Macro, skip-node-key: Private macros
Macro, skip-node-level: Private macros
Macro, skip-node-timestamp: Private macros
Macro, skip-node-value: Private macros
Macro, while: Private macros
Macro, with-mcas: Private macros
Macro, with-recursive-mcas: Private macros
make-ccas-descriptor: Private ordinary functions
make-head: Private ordinary functions
make-mcas-descriptor: Private ordinary functions
make-mt-random-state: Private ordinary functions
make-safe-update: Private ordinary functions
make-skip-list: Public ordinary functions
make-skip-node: Private ordinary functions
make-skip-pq: Public ordinary functions
make-skip-pq-node: Private ordinary functions
map-skip-list: Public generic functions
map-skip-list: Public generic functions
map-skip-list-values: Public generic functions
map-skip-list-values: Public generic functions
mcas: Private ordinary functions
mcas-count: Private ordinary functions
mcas-descriptor?: Private ordinary functions
mcas-equality: Private ordinary functions
mcas-help: Private ordinary functions
mcas-read: Private ordinary functions
mcas-retries: Private ordinary functions
mcas-set: Private ordinary functions
mcas-status: Private ordinary functions
mcas-success-actions: Private ordinary functions
mcas-successful?: Private generic functions
mcas-successful?: Private generic functions
mcas-successful?: Private generic functions
mcas-timestamp: Private ordinary functions
mcas-updates: Private ordinary functions
Method, (setf skip-list): Private generic functions
Method, (setf skip-list-cursor-node): Private generic functions
Method, delete-min: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, less-than: Public generic functions
Method, map-skip-list: Public generic functions
Method, map-skip-list-values: Public generic functions
Method, mcas-successful?: Private generic functions
Method, mcas-successful?: Private generic functions
Method, print-object: Public standalone methods
Method, skip-list: Private generic functions
Method, skip-list-add: Public generic functions
Method, skip-list-cursor: Private generic functions
Method, skip-list-cursor-node: Private generic functions
Method, skip-list-delete: Public generic functions
Method, skip-list-empty?: Public generic functions
Method, skip-list-fetch-all: Public generic functions
Method, skip-list-keys-cursor: Public generic functions
Method, skip-list-lookup: Public generic functions
Method, skip-list-range-cursor: Public generic functions
Method, skip-list-replace-kv: Public generic functions
Method, skip-list-search: Private generic functions
Method, skip-list-to-list: Public generic functions
Method, skip-list-values-cursor: Public generic functions
Method, skip-pq-add: Private generic functions
Method, skip-pq-delete: Private generic functions
Method, skip-pq-search: Private generic functions
Method, sl-cursor-next: Public generic functions
Method, sl-cursor-next: Public generic functions
Method, sl-cursor-next: Public generic functions
Method, sl-cursor-next: Public generic functions
Method, slrc-end: Private generic functions
Method, translate-from-foreign: Public standalone methods
Method, translate-to-foreign: Public standalone methods
mt-genrand: Private ordinary functions
mt-internal-make-random-state: Private ordinary functions
mt-make-random-state-integer: Private ordinary functions
mt-make-random-state-random: Private ordinary functions
mt-random: Private ordinary functions
mt-random-state-arr: Private ordinary functions
mt-random-state-mti: Private ordinary functions
mt-random-state-p: Private ordinary functions
mt-refill: Private ordinary functions
mt-tempering-shift-l: Private ordinary functions
mt-tempering-shift-s: Private ordinary functions
mt-tempering-shift-t: Private ordinary functions
mt-tempering-shift-u: Private ordinary functions

N
node-forward: Private ordinary functions

P
print-object: Public standalone methods
print-skip-list: Private ordinary functions

R
random-level: Private ordinary functions
reset-mcas: Private ordinary functions

S
safe-update?: Private ordinary functions
skip-list: Private generic functions
skip-list: Private generic functions
skip-list-add: Public generic functions
skip-list-add: Public generic functions
skip-list-comparison: Private ordinary functions
skip-list-cursor: Private generic functions
skip-list-cursor: Private generic functions
skip-list-cursor-node: Private generic functions
skip-list-cursor-node: Private generic functions
skip-list-delete: Public generic functions
skip-list-delete: Public generic functions
skip-list-duplicates-allowed?: Private ordinary functions
skip-list-empty?: Public generic functions
skip-list-empty?: Public generic functions
skip-list-fetch-all: Public generic functions
skip-list-fetch-all: Public generic functions
skip-list-head: Private ordinary functions
skip-list-key-equal: Private ordinary functions
skip-list-keys-cursor: Public generic functions
skip-list-keys-cursor: Public generic functions
skip-list-length: Public ordinary functions
skip-list-lookup: Public generic functions
skip-list-lookup: Public generic functions
skip-list-node-fn: Private ordinary functions
skip-list-range-cursor: Public generic functions
skip-list-range-cursor: Public generic functions
skip-list-replace-kv: Public generic functions
skip-list-replace-kv: Public generic functions
skip-list-search: Private generic functions
skip-list-search: Private generic functions
skip-list-to-list: Public generic functions
skip-list-to-list: Public generic functions
skip-list-value-equal: Private ordinary functions
skip-list-values-cursor: Public generic functions
skip-list-values-cursor: Public generic functions
skip-list?: Public ordinary functions
skip-node-deleted?: Private macros
skip-node-forward: Private macros
skip-node-key: Private macros
skip-node-level: Private macros
skip-node-timestamp: Private macros
skip-node-value: Private macros
skip-pq-add: Private generic functions
skip-pq-add: Private generic functions
skip-pq-delete: Private generic functions
skip-pq-delete: Private generic functions
skip-pq-search: Private generic functions
skip-pq-search: Private generic functions
sl-cursor-next: Public generic functions
sl-cursor-next: Public generic functions
sl-cursor-next: Public generic functions
sl-cursor-next: Public generic functions
sl-cursor-next: Public generic functions
sl-test: Private ordinary functions
slrc-end: Private generic functions
slrc-end: Private generic functions

T
translate-from-foreign: Public standalone methods
translate-to-foreign: Public standalone methods

U
update-index: Private ordinary functions
update-new: Private ordinary functions
update-old: Private ordinary functions
update-vector: Private ordinary functions

W
while: Private macros
with-mcas: Private macros
with-recursive-mcas: Private macros


A.3 Variables

Jump to:   *   +  
A   C   D   E   H   I   K   L   M   N   R   S   V  
Index Entry  Section

*
*mcas*: Private special variables
*mt-k-inverse-2^32f*: Private constants
*mt-k2^32*: Private constants
*mt-lower-mask*: Private constants
*mt-m*: Private constants
*mt-n*: Private constants
*mt-random-state*: Private special variables
*mt-upper-mask*: Private constants

+
+max-level+: Private constants
+mcas-failed+: Public constants
+mcas-make-durable+: Private constants
+mcas-succeeded+: Public constants
+mcas-undecided+: Public constants
+skip-node-deleted+: Private constants
+skip-node-forward+: Private constants
+skip-node-key+: Private constants
+skip-node-level+: Private constants
+skip-node-timestamp+: Private constants
+skip-node-value+: Private constants

A
arr: Private structures

C
comparison: Private structures
Constant, *mt-k-inverse-2^32f*: Private constants
Constant, *mt-k2^32*: Private constants
Constant, *mt-lower-mask*: Private constants
Constant, *mt-m*: Private constants
Constant, *mt-n*: Private constants
Constant, *mt-upper-mask*: Private constants
Constant, +max-level+: Private constants
Constant, +mcas-failed+: Public constants
Constant, +mcas-make-durable+: Private constants
Constant, +mcas-succeeded+: Public constants
Constant, +mcas-undecided+: Public constants
Constant, +skip-node-deleted+: Private constants
Constant, +skip-node-forward+: Private constants
Constant, +skip-node-key+: Private constants
Constant, +skip-node-level+: Private constants
Constant, +skip-node-timestamp+: Private constants
Constant, +skip-node-value+: Private constants

D
duplicates-allowed?: Private structures

E
end: Public classes

H
head: Private structures

I
instance: Private conditions
instance: Private conditions

K
key: Private conditions
key: Private conditions
key-equal: Private structures

L
length: Private structures

M
mti: Private structures

N
node: Private classes
node-fn: Private structures

R
reason: Private conditions
reason: Private conditions

S
skip-list: Private classes
Slot, arr: Private structures
Slot, comparison: Private structures
Slot, duplicates-allowed?: Private structures
Slot, end: Public classes
Slot, head: Private structures
Slot, instance: Private conditions
Slot, instance: Private conditions
Slot, key: Private conditions
Slot, key: Private conditions
Slot, key-equal: Private structures
Slot, length: Private structures
Slot, mti: Private structures
Slot, node: Private classes
Slot, node-fn: Private structures
Slot, reason: Private conditions
Slot, reason: Private conditions
Slot, skip-list: Private classes
Slot, value: Private conditions
Slot, value: Private conditions
Slot, value-equal: Private structures
Special Variable, *mcas*: Private special variables
Special Variable, *mt-random-state*: Private special variables

V
value: Private conditions
value: Private conditions
value-equal: Private structures


A.4 Data types

Jump to:   C   F   G   M   N   P   R   S   T   U  
Index Entry  Section

C
cl-skip-list: The cl-skip-list system
cl-skip-list: The cl-skip-list package
cl-skip-list-package.lisp: The cl-skip-list/cl-skip-list-package․lisp file
cl-skip-list-system: The cl-skip-list-system package
cl-skip-list.asd: The cl-skip-list/cl-skip-list․asd file
Class, null-pointer-type: Private classes
Class, skip-list-cursor: Private classes
Class, skip-list-key-cursor: Private classes
Class, skip-list-range-cursor: Public classes
Class, skip-list-value-cursor: Private classes
Class, syscall-result-type: Private classes
Class, timeval-tclass: Private classes
Condition, mcas-error: Private conditions
Condition, skip-list-duplicate-error: Private conditions
Condition, skip-list-kv-not-found-error: Private conditions
Condition, transaction-error: Private conditions
constants.lisp: The cl-skip-list/constants․lisp file

F
File, cl-skip-list-package.lisp: The cl-skip-list/cl-skip-list-package․lisp file
File, cl-skip-list.asd: The cl-skip-list/cl-skip-list․asd file
File, constants.lisp: The cl-skip-list/constants․lisp file
File, gettimeofday.lisp: The cl-skip-list/gettimeofday․lisp file
File, mcas.lisp: The cl-skip-list/mcas․lisp file
File, random.lisp: The cl-skip-list/random․lisp file
File, skip-list.lisp: The cl-skip-list/skip-list․lisp file
File, skip-pq.lisp: The cl-skip-list/skip-pq․lisp file
File, utilities.lisp: The cl-skip-list/utilities․lisp file

G
gettimeofday.lisp: The cl-skip-list/gettimeofday․lisp file

M
mcas-error: Private conditions
mcas.lisp: The cl-skip-list/mcas․lisp file
mt-random-state: Private structures

N
null-pointer-type: Private classes

P
Package, cl-skip-list: The cl-skip-list package
Package, cl-skip-list-system: The cl-skip-list-system package

R
random.lisp: The cl-skip-list/random․lisp file

S
skip-list: Private structures
skip-list-cursor: Private classes
skip-list-duplicate-error: Private conditions
skip-list-key-cursor: Private classes
skip-list-kv-not-found-error: Private conditions
skip-list-range-cursor: Public classes
skip-list-value-cursor: Private classes
skip-list.lisp: The cl-skip-list/skip-list․lisp file
skip-pq.lisp: The cl-skip-list/skip-pq․lisp file
Structure, mt-random-state: Private structures
Structure, skip-list: Private structures
syscall-result-type: Private classes
System, cl-skip-list: The cl-skip-list system

T
timeval-tclass: Private classes
transaction-error: Private conditions

U
utilities.lisp: The cl-skip-list/utilities․lisp file