This is the cl-skip-list Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 05:23:31 2024 GMT+0.
cl-skip-list/cl-skip-list.asdcl-skip-list/cl-skip-list-package.lispcl-skip-list/random.lispcl-skip-list/utilities.lispcl-skip-list/gettimeofday.lispcl-skip-list/constants.lispcl-skip-list/mcas.lispcl-skip-list/skip-list.lispcl-skip-list/skip-pq.lispThe main system appears first, followed by any subsystem dependency.
cl-skip-listConcurrent lock-free skip list.
Kevin Raison
Kevin Raison <last name @ chatsubo dot net>
Concurrent lock-free skip list.
0.1
cffi (system).
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).
Files are sorted by type and then listed depth-first from the systems components trees.
cl-skip-list/cl-skip-list.asdcl-skip-list/cl-skip-list-package.lispcl-skip-list/random.lispcl-skip-list/utilities.lispcl-skip-list/gettimeofday.lispcl-skip-list/constants.lispcl-skip-list/mcas.lispcl-skip-list/skip-list.lispcl-skip-list/skip-pq.lispcl-skip-list/cl-skip-list.asdcl-skip-list (system).
cl-skip-list/cl-skip-list-package.lispcl-skip-list (system).
cl-skip-list/random.lispcl-skip-list-package.lisp (file).
cl-skip-list (system).
*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 (reader).
(setf mt-random-state-arr) (writer).
mt-random-state-mti (reader).
(setf mt-random-state-mti) (writer).
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).
cl-skip-list/utilities.lispcl-skip-list-package.lisp (file).
cl-skip-list (system).
less-than (generic function).
cl-skip-list/gettimeofday.lispcl-skip-list-package.lisp (file).
cl-skip-list (system).
translate-from-foreign (method).
translate-to-foreign (method).
%gettimeofday (function).
gettimeofday (function).
null-pointer-type (class).
syscall-result-type (class).
timeval-tclass (class).
cl-skip-list/constants.lispcl-skip-list-package.lisp (file).
cl-skip-list (system).
+mcas-failed+ (constant).
+mcas-succeeded+ (constant).
+mcas-undecided+ (constant).
*mcas* (special variable).
+mcas-make-durable+ (constant).
cl-skip-list/mcas.lisputilities.lisp (file).
constants.lisp (file).
gettimeofday.lisp (file).
cl-skip-list (system).
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-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).
cl-skip-list/skip-list.lispmcas.lisp (file).
random.lisp (file).
cl-skip-list (system).
make-skip-list (function).
map-skip-list (method).
map-skip-list-values (method).
print-object (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 (reader).
(setf skip-list-length) (writer).
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).
+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 (reader method).
(setf skip-list) (writer method).
skip-list (structure).
skip-list-comparison (reader).
(setf skip-list-comparison) (writer).
skip-list-cursor (method).
skip-list-cursor (class).
skip-list-cursor-node (reader method).
(setf skip-list-cursor-node) (writer method).
skip-list-duplicate-error (condition).
skip-list-duplicates-allowed? (reader).
(setf skip-list-duplicates-allowed?) (writer).
skip-list-head (reader).
(setf skip-list-head) (writer).
skip-list-key-cursor (class).
skip-list-key-equal (reader).
(setf skip-list-key-equal) (writer).
skip-list-kv-not-found-error (condition).
skip-list-node-fn (reader).
(setf skip-list-node-fn) (writer).
skip-list-search (method).
skip-list-value-cursor (class).
skip-list-value-equal (reader).
(setf skip-list-value-equal) (writer).
skip-node-forward (macro).
skip-node-key (macro).
skip-node-level (macro).
skip-node-value (macro).
sl-test (function).
slrc-end (reader method).
cl-skip-list/skip-pq.lispskip-list.lisp (file).
cl-skip-list (system).
delete-min (method).
make-skip-pq (function).
+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).
Packages are listed by definition order.
cl-skip-listcffi.
common-lisp.
+mcas-failed+ (constant).
+mcas-succeeded+ (constant).
+mcas-undecided+ (constant).
delete-min (generic function).
less-than (generic function).
make-skip-list (function).
make-skip-pq (function).
map-skip-list (generic function).
map-skip-list-values (generic function).
skip-list-add (generic function).
skip-list-delete (generic function).
skip-list-empty? (generic function).
skip-list-fetch-all (generic function).
skip-list-keys-cursor (generic function).
skip-list-length (reader).
(setf skip-list-length) (writer).
skip-list-lookup (generic function).
skip-list-range-cursor (generic function).
skip-list-range-cursor (class).
skip-list-replace-kv (generic function).
skip-list-to-list (generic function).
skip-list-values-cursor (generic function).
skip-list? (function).
sl-cursor-next (generic function).
%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-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 (reader).
(setf mt-random-state-arr) (writer).
mt-random-state-mti (reader).
(setf mt-random-state-mti) (writer).
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 reader).
(setf skip-list) (generic writer).
skip-list (structure).
skip-list-comparison (reader).
(setf skip-list-comparison) (writer).
skip-list-cursor (generic function).
skip-list-cursor (class).
skip-list-cursor-node (generic reader).
(setf skip-list-cursor-node) (generic writer).
skip-list-duplicate-error (condition).
skip-list-duplicates-allowed? (reader).
(setf skip-list-duplicates-allowed?) (writer).
skip-list-head (reader).
(setf skip-list-head) (writer).
skip-list-key-cursor (class).
skip-list-key-equal (reader).
(setf skip-list-key-equal) (writer).
skip-list-kv-not-found-error (condition).
skip-list-node-fn (reader).
(setf skip-list-node-fn) (writer).
skip-list-search (generic function).
skip-list-value-cursor (class).
skip-list-value-equal (reader).
(setf skip-list-value-equal) (writer).
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-delete (generic function).
skip-pq-search (generic function).
sl-test (function).
slrc-end (generic reader).
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).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Generic less-than operator. Allows comparison of apples and oranges.
symbol) (y symbol)) ¶symbol) (y string)) ¶symbol) (y number)) ¶number) (y number)) ¶number) (y symbol)) ¶number) (y string)) ¶string) (y string)) ¶string) (y symbol)) ¶string) (y number)) ¶skip-list-range-cursor) &optional eoc) ¶skip-list-key-cursor) &optional eoc) ¶skip-list-value-cursor) &optional eoc) ¶skip-list-cursor) &optional eoc) ¶syscall-result-type)) ¶cffi.
null-pointer-type)) ¶cffi.
1/(2^32), as a floating-point number
least significant r bits
most significant w-r bits
Maximum level of skip-list, should be enough for 2^32 elements.
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)
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
copy-seq.
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
copy-seq.
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
copy-seq.
Analogous to Common Lisp’s MAKE-RANDOM-STATE except that this function works on random states for JMT’s Mersenne Twister implementation.
This is the bulk of the transaction logic.
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.
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.
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!
arr.
mti.
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.
Returns a random level for a new skip-list node, following Pugh’s pattern of L1: 50%, L2: 25%, L3: 12.5%, ...
head.
skip-list-cursor)) ¶automatically generated reader method
skip-list-cursor)) ¶automatically generated writer method
skip-list-cursor)) ¶automatically generated reader method
node.
skip-list-cursor)) ¶automatically generated writer method
node.
skip-list-range-cursor)) ¶automatically generated reader method
end.
structure-object.
delete-min.
map-skip-list.
map-skip-list-values.
print-object.
skip-list-add.
skip-list-cursor.
skip-list-delete.
skip-list-empty?.
skip-list-fetch-all.
skip-list-keys-cursor.
skip-list-lookup.
skip-list-range-cursor.
skip-list-replace-kv.
skip-list-search.
skip-list-to-list.
skip-list-values-cursor.
skip-pq-add.
skip-pq-delete.
skip-pq-search.
(cl-skip-list::make-head)
(function equal)
(function equal)
(function cl-skip-list:less-than)
(function cl-skip-list::make-skip-node)
common-lisp.
(unsigned-byte 64)
0
enhanced-foreign-type.
| Initarg | Value |
|---|---|
:actual-type | (quote (pointer)) |
enhanced-foreign-type.
| Initarg | Value |
|---|---|
:actual-type | (quote (int)) |
foreign-struct-type.
translatable-foreign-type.
| Jump to: | %
(
C D F G L M N P R S T U W |
|---|
| Jump to: | %
(
C D F G L M N P R S T U W |
|---|
| Jump to: | *
+
A C D E H I K L M N R S V |
|---|
| Jump to: | *
+
A C D E H I K L M N R S V |
|---|
| Jump to: | C F G M N P R S T U |
|---|
| Jump to: | C F G M N P R S T U |
|---|