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 08 17:23:24 2024 GMT+0.
cl-skip-list/cl-skip-list.asd
cl-skip-list/cl-skip-list-package.lisp
cl-skip-list/random.lisp
cl-skip-list/utilities.lisp
cl-skip-list/gettimeofday.lisp
cl-skip-list/constants.lisp
cl-skip-list/mcas.lisp
cl-skip-list/skip-list.lisp
cl-skip-list/skip-pq.lisp
The main system appears first, followed by any subsystem dependency.
cl-skip-list
Concurrent 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.asd
cl-skip-list/cl-skip-list-package.lisp
cl-skip-list/random.lisp
cl-skip-list/utilities.lisp
cl-skip-list/gettimeofday.lisp
cl-skip-list/constants.lisp
cl-skip-list/mcas.lisp
cl-skip-list/skip-list.lisp
cl-skip-list/skip-pq.lisp
cl-skip-list/cl-skip-list.asd
cl-skip-list
(system).
cl-skip-list/cl-skip-list-package.lisp
cl-skip-list
(system).
cl-skip-list/random.lisp
cl-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.lisp
cl-skip-list-package.lisp
(file).
cl-skip-list
(system).
less-than
(generic function).
cl-skip-list/gettimeofday.lisp
cl-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.lisp
cl-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.lisp
utilities.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.lisp
mcas.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.lisp
skip-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-list
cffi
.
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 |
---|