Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
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.
• Introduction | What cl-skip-list is all about | |
• Systems | The systems documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
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
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The cl-skip-list system |
Kevin Raison
Kevin Raison <last name @ chatsubo dot net>
Concurrent lock-free skip list.
Concurrent lock-free skip list.
0.1
cffi
cl-skip-list.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
Next: The cl-skip-list/cl-skip-list-package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
cl-skip-list.asd
cl-skip-list (system)
Next: The cl-skip-list/random․lisp file, Previous: The cl-skip-list․asd file, Up: Lisp files [Contents][Index]
cl-skip-list (system)
cl-skip-list-package.lisp
Next: The cl-skip-list/utilities․lisp file, Previous: The cl-skip-list/cl-skip-list-package․lisp file, Up: Lisp files [Contents][Index]
cl-skip-list-package.lisp (file)
cl-skip-list (system)
random.lisp
Next: The cl-skip-list/gettimeofday․lisp file, Previous: The cl-skip-list/random․lisp file, Up: Lisp files [Contents][Index]
cl-skip-list-package.lisp (file)
cl-skip-list (system)
utilities.lisp
Next: The cl-skip-list/constants․lisp file, Previous: The cl-skip-list/utilities․lisp file, Up: Lisp files [Contents][Index]
cl-skip-list-package.lisp (file)
cl-skip-list (system)
gettimeofday.lisp
Next: The cl-skip-list/mcas․lisp file, Previous: The cl-skip-list/gettimeofday․lisp file, Up: Lisp files [Contents][Index]
cl-skip-list-package.lisp (file)
cl-skip-list (system)
constants.lisp
Next: The cl-skip-list/skip-list․lisp file, Previous: The cl-skip-list/constants․lisp file, Up: Lisp files [Contents][Index]
cl-skip-list (system)
mcas.lisp
Next: The cl-skip-list/skip-pq․lisp file, Previous: The cl-skip-list/mcas․lisp file, Up: Lisp files [Contents][Index]
cl-skip-list (system)
skip-list.lisp
Previous: The cl-skip-list/skip-list․lisp file, Up: Lisp files [Contents][Index]
skip-list.lisp (file)
cl-skip-list (system)
skip-pq.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The cl-skip-list-system package | ||
• The cl-skip-list package |
Next: The cl-skip-list package, Previous: Packages, Up: Packages [Contents][Index]
cl-skip-list.asd
Previous: The cl-skip-list-system package, Up: Packages [Contents][Index]
cl-skip-list-package.lisp (file)
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported constants | ||
• Exported functions | ||
• Exported generic functions | ||
• Exported classes |
Next: Exported functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
constants.lisp (file)
constants.lisp (file)
constants.lisp (file)
Next: Exported generic functions, Previous: Exported constants, Up: Exported definitions [Contents][Index]
skip-list.lisp (file)
skip-pq.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
Next: Exported classes, Previous: Exported functions, Up: Exported definitions [Contents][Index]
skip-pq.lisp (file)
Generic less-than operator. Allows comparison of apples and oranges.
utilities.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
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.
skip-list.lisp (file)
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.
skip-list.lisp (file)
skip-list.lisp (file)
Return all values for a key in a skip list where duplicates are allowed.
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
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.
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
skip-list.lisp (file)
skip-list-cursor (class)
:end
slrc-end (generic function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal constants | ||
• Internal special variables | ||
• Internal macros | ||
• Internal functions | ||
• Internal generic functions | ||
• Internal conditions | ||
• Internal structures | ||
• Internal classes |
Next: Internal special variables, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
1/(2^32), as a floating-point number
random.lisp (file)
random.lisp (file)
least significant r bits
random.lisp (file)
random.lisp (file)
random.lisp (file)
most significant w-r bits
random.lisp (file)
Maximum level of skip-list, should be enough for 2^32 elements.
skip-list.lisp (file)
constants.lisp (file)
skip-pq.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-pq.lisp (file)
skip-list.lisp (file)
Next: Internal macros, Previous: Internal constants, Up: Internal definitions [Contents][Index]
constants.lisp (file)
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)
random.lisp (file)
Next: Internal functions, Previous: Internal special variables, Up: Internal definitions [Contents][Index]
mcas.lisp (file)
skip-pq.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-pq.lisp (file)
skip-list.lisp (file)
utilities.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
Next: Internal generic functions, Previous: Internal macros, Up: Internal definitions [Contents][Index]
gettimeofday.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
SYS:SRC;CODE;SEQ.LISP (not found)
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
SYS:SRC;CODE;SEQ.LISP (not found)
random.lisp (file)
Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.
SYS:SRC;CODE;SEQ.LISP (not found)
skip-list.lisp (file)
utilities.lisp (file)
mcas.lisp (file)
gettimeofday.lisp (file)
mcas.lisp (file)
skip-list.lisp (file)
mcas.lisp (file)
Analogous to Common Lisp’s MAKE-RANDOM-STATE except that this function works on random states for JMT’s Mersenne Twister implementation.
random.lisp (file)
mcas.lisp (file)
skip-list.lisp (file)
skip-pq.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
This is the bulk of the transaction logic.
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
random.lisp (file)
random.lisp (file)
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.
random.lisp (file)
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.
random.lisp (file)
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!
random.lisp (file)
random.lisp (file)
random.lisp (file)
random.lisp (file)
In the C program mt19937int.c, there is a function called ’genrand’, & in that function there is a block of code to execute when the mt[] array is exhausted. This function is that block of code. I’ve removed it from my MT-GENRAND function for clarity.
random.lisp (file)
random.lisp (file)
random.lisp (file)
random.lisp (file)
random.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
Returns a random level for a new skip-list node, following Pugh’s pattern of L1: 50%, L2: 25%, L3: 12.5%, ...
skip-list.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
skip-list.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
mcas.lisp (file)
Next: Internal conditions, Previous: Internal functions, Up: Internal definitions [Contents][Index]
mcas.lisp (file)
automatically generated reader method
skip-list.lisp (file)
automatically generated writer method
skip-list.lisp (file)
skip-list.lisp (file)
automatically generated reader method
skip-list.lisp (file)
automatically generated writer method
skip-list.lisp (file)
skip-list.lisp (file)
skip-pq.lisp (file)
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.
skip-pq.lisp (file)
skip-pq.lisp (file)
automatically generated reader method
skip-list.lisp (file)
Next: Internal structures, Previous: Internal generic functions, Up: Internal definitions [Contents][Index]
mcas.lisp (file)
error (condition)
:instance
:reason
skip-list.lisp (file)
error (condition)
:key
:value
skip-list.lisp (file)
error (condition)
:key
:value
mcas.lisp (file)
error (condition)
:instance
:reason
Next: Internal classes, Previous: Internal conditions, Up: Internal definitions [Contents][Index]
random.lisp (file)
structure-object (structure)
mt-random-state-mti (function)
(setf mt-random-state-mti) (function)
mt-random-state-arr (function)
(setf mt-random-state-arr) (function)
skip-list.lisp (file)
structure-object (structure)
(cl-skip-list::make-head)
skip-list-head (function)
(setf skip-list-head) (function)
(function equal)
skip-list-key-equal (function)
(setf skip-list-key-equal) (function)
(function equal)
skip-list-value-equal (function)
(setf skip-list-value-equal) (function)
(function cl-skip-list:less-than)
skip-list-comparison (function)
(setf skip-list-comparison) (function)
skip-list-duplicates-allowed? (function)
(setf skip-list-duplicates-allowed?) (function)
(function cl-skip-list::make-skip-node)
skip-list-node-fn (function)
(setf skip-list-node-fn) (function)
(unsigned-byte 64)
0
skip-list-length (function)
(setf skip-list-length) (function)
Previous: Internal structures, Up: Internal definitions [Contents][Index]
gettimeofday.lisp (file)
enhanced-foreign-type (class)
translate-to-foreign (method)
Initarg | Value |
---|---|
:actual-type | (quote (:pointer)) |
skip-list.lisp (file)
standard-object (class)
:node
skip-list-cursor-node (generic function)
(setf skip-list-cursor-node) (generic function)
:skip-list
skip-list (generic function)
(setf skip-list) (generic function)
skip-list.lisp (file)
skip-list-cursor (class)
sl-cursor-next (method)
skip-list.lisp (file)
skip-list-cursor (class)
sl-cursor-next (method)
gettimeofday.lisp (file)
enhanced-foreign-type (class)
translate-from-foreign (method)
Initarg | Value |
---|---|
:actual-type | (quote (:int)) |
gettimeofday.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | C F L |
---|
Jump to: | C F L |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | %
(
C D F G L M N P R S U W |
---|
Jump to: | %
(
C D F G L M N P R S U W |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
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 |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | C M N P S T |
---|
Jump to: | C M N P S T |
---|