The hashtrie Reference Manual
Table of Contents
The hashtrie Reference Manual
This is the hashtrie Reference Manual, version 1.0.0,
generated automatically by Declt version 3.0 "Montgomery Scott"
on Sun May 15 04:56:15 2022 GMT+0.
1 Introduction
hashtrie
A fast Hash trie implementation based upon Clojure's.
A Hash Trie works like a Hash Set, except that it has been optimised for immutability and thread-safety.
By default, hash-trie's are persistent and immutable, but this implementation also supports transients for building sets significantly faster.
Usage
Constructor:
(htr:make-hash-trie nil "foo" 1 "bar")
;; {nil "foo", 1 "bar"}
Construct with transience:
(htr:with-transient (trans (htr:make-hash-trie))
(htr:tri-add trans 1 "bar")
(htr:tri-add trans nil "foo"))
;; {nil "foo", 1 "bar"}
Adding:
(htr:tri-add (htr:make-hash-trie 1 "foo") 1 "bar")
;; {1 "bar"}
Removing:
(htr:tri-remove (htr:make-hash-trie 1 1 2 2) 1)
;; {2 2}
Finding values:
(htr:tri-val (htr:make-hash-trie 1 "foo" 2 "bar") 1)
;; "foo"
Testing keys:
(htr:tri-has-key (htr:make-hash-trie 1 1 2 2) 1)
;; T
(htr:tri-has-key (htr:make-hash-trie 1 1 2 2) 100)
;; nil
Length/Count:
(htr:tri-length (htr:make-hash-trie 1 "foo" 2 "bar"))
;; 2
Mapping:
(htr:tri-map (htr:make-hash-trie 1 100 2 200 3 300)
(lambda (key val) (+ key val))
;; (101 202 303)
Reduce:
(htr:tri-reduce (htr:make-hash-trie 1 0 2 0 3 0)
(lambda (start key val) (+ start key val))
0)
;; 6
Thread Safety
In theory the persistent Hash Trie is completely thread safe. This has been tested casually, but never in a production system.
Other important info
This library currently uses sxhash
and equal
for comparison. Alternative hashing/comparison functions are not supported.
Supported Lisps
In theory should work on all Common Lisp implementations.
Has only been tested on SBCL, and CLisp.
Benchmarking
Running SBCL, for comparison between using hash-trie and SBCL's own implementation of hashset, you can see that building SBCL's hashset is a bit over 10x faster. This is to be expected because it isn't immutable.
hashtrie
CL-USER> (time (loop for i from 0 to 1000000
for map = (htr:make-hash-trie i i) then (htr:tri-add map i i)
finally (return map)))
;Evaluation took:
; 1.158 seconds of real time
; 1.163023 seconds of total run time (1.002477 user, 0.160546 system)
; [ Run times consist of 0.486 seconds GC time, and 0.678 seconds non-GC time. ]
; 100.43% CPU
; 2,306,805,783 processor cycles
; 1,279,064,720 bytes consed
(time (htr:with-transient (trans (htr:make-hash-trie))
(dotimes (i 1000000)
(htr:tri-add trans i i))))
;Evaluation took:
; 0.640 seconds of real time
; 0.640942 seconds of total run time (0.557056 user, 0.083886 system)
; [ Run times consist of 0.297 seconds GC time, and 0.344 seconds non-GC time. ]
; 100.16% CPU
; 1,275,757,029 processor cycles
; 190,686,512 bytes consed
hashset
(time (let ((m (make-hash-table :test 'equal)))
(dotimes (i 1000000)
(setf (gethash i m) i))))
; Evaluation took:
; 0.170 seconds of real time
; 0.171739 seconds of total run time (0.152880 user, 0.018859 system)
; [ Run times consist of 0.024 seconds GC time, and 0.148 seconds non-GC time. ]
; 101.18% CPU
; 339,892,350 processor cycles
; 132,035,232 bytes consed
Also comparing the performance to clojure. Building a hash trie in sbcl is still slightly slower than doing the same in clojure, but not by much.
;Clojure 1.10.2
(defn persistent-build-map [set n]
(if (> n 0)
(recur (assoc set n n) (dec n))
set))
(defn transient-build-map [n]
(loop [i 0 v (transient {})]
(if (< i n)
(recur (inc i) (assoc! v i i))
(persistent! v))))
(time (count (persistent-build-map {} 1000000)))
;"Elapsed time: 606.96371 msecs"
(time (count (transient-build-map 1000000)))
"Elapsed time: 502.676784 msecs"
2 Systems
The main system appears first, followed by any subsystem dependency.
2.1 hashtrie
- Author
Daniel Keogh
- License
Eclipse 2.0
- Description
An implementation of the Hash Trie datastructure, based on Clojure’s
- Version
1.0.0
- Source
hashtrie.asd (file)
- Components
-
3 Files
Files are sorted by type and then listed depth-first from the systems
components trees.
3.1 Lisp
3.1.1 hashtrie.asd
- Location
hashtrie.asd
- Systems
hashtrie (system)
3.1.2 hashtrie/package.lisp
- Parent
hashtrie (system)
- Location
package.lisp
- Packages
hashtrie
3.1.3 hashtrie/utils.lisp
- Dependency
package.lisp (file)
- Parent
hashtrie (system)
- Location
utils.lisp
- Internal Definitions
-
3.1.4 hashtrie/hashtrie.lisp
- Dependency
utils.lisp (file)
- Parent
hashtrie (system)
- Location
hashtrie.lisp
- Exported Definitions
-
- Internal Definitions
-
3.1.5 hashtrie/api.lisp
- Dependency
hashtrie.lisp (file)
- Parent
hashtrie (system)
- Location
api.lisp
- Exported Definitions
-
4 Packages
Packages are listed by definition order.
4.1 hashtrie
A fast implementation of the Hash Trie data structure, based on Clojure.
- Source
package.lisp (file)
- Nickname
htr
- Use List
common-lisp
- Exported Definitions
-
- Internal Definitions
-
5 Definitions
Definitions are sorted by export status, category, package, and then by
lexicographic order.
5.1 Exported definitions
5.1.1 Special variables
- Special Variable: *max-print-length*
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
5.1.2 Macros
- Macro: with-transient (NAME MAP) &body BODY
-
Within the body of this macro modify a temporary, transient copy of the hash trie. e.g. (with-transient (name (make-has-trie)) <body>). The transient copy will not be thread safe.
Returns a new persistent hash trie
- Package
hashtrie
- Source
api.lisp (file)
5.1.3 Functions
- Function: hash-trie-p OBJECT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: make-hash-trie &rest ARGS
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: persistent-hash-map-p OBJECT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: transient-hash-map-p OBJECT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: tri-add HASH-TRIE KEY VAL
-
Create a new map with the given key-value pair
- Package
hashtrie
- Source
api.lisp (file)
- Function: tri-has-key HASH-TRIE KEY
-
Test if the key is in the hash trie
- Package
hashtrie
- Source
api.lisp (file)
- Function: tri-length HASH-TRIE
-
The number of pairs in the hash trie
- Package
hashtrie
- Source
api.lisp (file)
- Function: tri-map HASH-TRIE FN
-
Apply a (lambda (x y)) to each key-value pair and collect the results into a list
- Package
hashtrie
- Source
api.lisp (file)
- Function: tri-reduce HASH-TRIE FN &optional START-VAL
-
Apply (lambda (start key val)) to aggregate all pairs of a persistent hash map
- Package
hashtrie
- Source
api.lisp (file)
- Function: tri-remove HASH-TRIE KEY
-
Remove the pair from the hash trie
- Package
hashtrie
- Source
api.lisp (file)
- Function: tri-val HASH-TRIE KEY &optional NOT-FOUND
-
Get the value for a given key
- Package
hashtrie
- Source
api.lisp (file)
5.1.4 Structures
- Structure: hash-trie ()
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct subclasses
-
- Structure: persistent-hash-map ()
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Direct superclasses
hash-trie (structure)
- Direct methods
-
- Direct slots
- Slot: meta
-
- Type
(or null hashtrie:hash-trie)
- Readers
phm-meta (function)
- Writers
(setf phm-meta) (function)
- Slot: count
-
- Type
fixnum
- Readers
phm-count (function)
- Writers
(setf phm-count) (function)
- Slot: root
-
- Type
(or null hashtrie::hash-map-node)
- Readers
phm-root (function)
- Writers
(setf phm-root) (function)
- Slot: has-null
-
- Type
boolean
- Readers
phm-has-null (function)
- Writers
(setf phm-has-null) (function)
- Slot: null-value
-
- Readers
phm-null-value (function)
- Writers
(setf phm-null-value) (function)
- Structure: transient-hash-map ()
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Direct superclasses
hash-trie (structure)
- Direct methods
-
- Direct slots
- Slot: edit
-
- Readers
thm-edit (function)
- Writers
(setf thm-edit) (function)
- Slot: count
-
- Type
fixnum
- Readers
thm-count (function)
- Writers
(setf thm-count) (function)
- Slot: root
-
- Type
(or null hashtrie::hash-map-node)
- Readers
thm-root (function)
- Writers
(setf thm-root) (function)
- Slot: has-null
-
- Type
boolean
- Readers
thm-has-null (function)
- Writers
(setf thm-has-null) (function)
- Slot: null-value
-
- Readers
thm-null-value (function)
- Writers
(setf thm-null-value) (function)
- Slot: leaf-flag
-
- Initform
(hashtrie::make-box)
- Readers
thm-leaf-flag (function)
- Writers
(setf thm-leaf-flag) (function)
5.2 Internal definitions
5.2.1 Constants
- Constant: +bits+
-
- Package
hashtrie
- Source
utils.lisp (file)
- Constant: +mask+
-
- Package
hashtrie
- Source
utils.lisp (file)
- Constant: +size+
-
- Package
hashtrie
- Source
utils.lisp (file)
5.2.2 Special variables
- Special Variable: *empty-hash-iterator*
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Special Variable: *empty-hash-map*
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Special Variable: *empty-hash-map-node*
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Special Variable: *not-found*
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
5.2.3 Macros
- Macro: box-val B
-
- Package
hashtrie
- Source
utils.lisp (file)
- Macro: logandcount N1 N2
-
- Package
hashtrie
- Source
utils.lisp (file)
- Macro: shift-right I
-
- Package
hashtrie
- Source
utils.lisp (file)
5.2.4 Functions
- Function: array-copy SRC SRC-POS DEST DEST-START LENGTH
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: atomic-reference-p OBJECT
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: atomic-reference-val INSTANCE
-
- Function: (setf atomic-reference-val) VALUE INSTANCE
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: bitpos HASH SHIFT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: clone-and-set ARRAY I NEW-VAL &optional J NEW-VAL2
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: copy-atomic-reference INSTANCE
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: copy-hash-map-array-node INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: copy-hash-map-bitmap-node INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: copy-hash-map-collision-node INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: copy-hash-map-node INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: copy-hash-trie INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: copy-persistent-hash-map INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: copy-simple-array ARR
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: copy-transient-hash-map INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: create-edit-node EDIT SHIFT KEY1 VAL1 KEY2HASH KEY2 VAL2
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: create-node SHIFT KEY1 VAL1 KEY2HASH KEY2 VAL2
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: equiv V1 V2
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: hash X
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: hash-map-array-node-p OBJECT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hash-map-bitmap-node-p OBJECT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hash-map-collision-node-p OBJECT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hash-map-node-p OBJECT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hman-array INSTANCE
-
- Function: (setf hman-array) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hman-count INSTANCE
-
- Function: (setf hman-count) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hman-edit INSTANCE
-
- Function: (setf hman-edit) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hman-edit-and-set NODE EDIT I N
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hman-ensure-editable NODE EDIT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hman-pack NODE EDIT IDX
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmcn-array INSTANCE
-
- Function: (setf hmcn-array) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmcn-count INSTANCE
-
- Function: (setf hmcn-count) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmcn-edit INSTANCE
-
- Function: (setf hmcn-edit) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmcn-edit-and-set NODE EDIT I A &optional J B
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmcn-ensure-editable NODE EDIT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmcn-find-index NODE KEY
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmcn-hash INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmn-array INSTANCE
-
- Function: (setf hmn-array) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmn-bitmap INSTANCE
-
- Function: (setf hmn-bitmap) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmn-edit INSTANCE
-
- Function: (setf hmn-edit) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmn-edit-and-remove-pair NODE EDIT BIT I
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmn-edit-and-set NODE EDIT I A &optional J B
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmn-ensure-editable NODE EDIT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: hmn-index NODE BIT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: make-atomic-reference &key (VAL VAL)
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: make-box ()
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: make-hash-map-array-node &key (EDIT EDIT) (COUNT COUNT) (ARRAY ARRAY)
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: make-hash-map-bitmap-node &key (EDIT EDIT) (BITMAP BITMAP) (ARRAY ARRAY)
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: make-hash-map-collision-node &key (EDIT EDIT) (HASH HASH) (COUNT COUNT) (ARRAY ARRAY)
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: make-hash-map-node &key
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: make-persistent-hash-map &key (META META) (COUNT COUNT) (ROOT ROOT) (HAS-NULL HAS-NULL) (NULL-VALUE NULL-VALUE)
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: make-transient-hash-map &key (EDIT EDIT) (COUNT COUNT) (ROOT ROOT) (HAS-NULL HAS-NULL) (NULL-VALUE NULL-VALUE) (LEAF-FLAG LEAF-FLAG)
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: map-map MAP FN
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: map-reduce MAP FN &optional START-VAL
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: mask HASH SHIFT
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: node-make-array-iterator ARRAY
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: phm-as-transient MAP
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: phm-count INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: phm-has-null INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: phm-meta INSTANCE
-
- Function: (setf phm-meta) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: phm-null-value INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: phm-root INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: remove-pair ARRAY I
-
- Package
hashtrie
- Source
utils.lisp (file)
- Function: thm-count INSTANCE
-
- Function: (setf thm-count) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-do-assoc MAP KEY VAL
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-do-persistent MAP
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-do-val-at MAP KEY NOT-FOUND
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-do-without MAP KEY
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-edit INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-ensure-editable MAP
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-has-null INSTANCE
-
- Function: (setf thm-has-null) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-leaf-flag INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-null-value INSTANCE
-
- Function: (setf thm-null-value) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-persistent MAP
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Function: thm-root INSTANCE
-
- Function: (setf thm-root) VALUE INSTANCE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
5.2.5 Generic functions
- Generic Function: map-assoc HASH-MAP KEY VAL
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: map-assoc (MAP transient-hash-map) KEY VALUE
-
- Method: map-assoc (M persistent-hash-map) KEY VAL
-
- Generic Function: map-count HASH-MAP
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: map-count (MAP transient-hash-map)
-
- Method: map-count (MAP persistent-hash-map)
-
- Generic Function: map-make-iterator HASH-MAP
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: map-make-iterator (MAP transient-hash-map)
-
- Method: map-make-iterator (MAP persistent-hash-map)
-
- Generic Function: map-val-at HASH-MAP KEY &optional NOT-FOUND
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: map-val-at (MAP transient-hash-map) KEY &optional NOT-FOUND
-
- Method: map-val-at (MAP persistent-hash-map) KEY &optional NOT-FOUND
-
- Generic Function: map-without HASH-MAP KEY
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: map-without (MAP transient-hash-map) KEY
-
- Method: map-without (MAP persistent-hash-map) KEY
-
- Generic Function: node-assoc NODE SHIFT HASH KEY VAL ADDEDLEAF
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: node-assoc (NODE hash-map-collision-node) SHIFT HASH KEY VAL ADDED-LEAF
-
- Method: node-assoc (NODE hash-map-bitmap-node) SHIFT HASH KEY VAL ADDED-LEAF
-
- Method: node-assoc (THIS hash-map-array-node) SHIFT HASH KEY VAL ADDED-LEAF
-
- Generic Function: node-assoc-edit NODE EDIT SHIFT HASH KEY VAL ADDEDLEAF
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: node-assoc-edit (NODE hash-map-collision-node) EDIT SHIFT HASH KEY VAL ADDED-LEAF
-
- Method: node-assoc-edit (NODE hash-map-bitmap-node) EDIT SHIFT HASH KEY VAL ADDED-LEAF
-
- Method: node-assoc-edit (THIS hash-map-array-node) EDIT SHIFT HASH KEY VAL ADDED-LEAF
-
- Generic Function: node-find NODE SHIFT HASH KEY NOT-FOUND
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: node-find (NODE hash-map-collision-node) SHIFT HASH KEY NOT-FOUND
-
- Method: node-find (NODE hash-map-bitmap-node) SHIFT HASH KEY NOT-FOUND
-
- Method: node-find (THIS hash-map-array-node) SHIFT HASH KEY NOT-FOUND
-
- Generic Function: node-make-iterator NODE
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: node-make-iterator (NODE hash-map-collision-node)
-
- Method: node-make-iterator (NODE hash-map-bitmap-node)
-
- Method: node-make-iterator (NODE hash-map-array-node)
-
- Generic Function: node-without NODE SHIFT HASH KEY
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: node-without (NODE hash-map-collision-node) SHIFT HASH KEY
-
- Method: node-without (NODE hash-map-bitmap-node) SHIFT HASH KEY
-
- Method: node-without (THIS hash-map-array-node) SHIFT HASH KEY
-
- Generic Function: node-without-edit NODE EDIT SHIFT HASH KEY REMOVED-LEAF
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Methods
- Method: node-without-edit (NODE hash-map-collision-node) EDIT SHIFT HASH KEY REMOVED-LEAF
-
- Method: node-without-edit (THIS hash-map-bitmap-node) EDIT SHIFT HASH KEY REMOVED-LEAF
-
- Method: node-without-edit (THIS hash-map-array-node) EDIT SHIFT HASH KEY REMOVED-LEAF
-
5.2.6 Structures
- Structure: atomic-reference ()
-
- Package
hashtrie
- Source
utils.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct slots
- Slot: val
-
- Readers
atomic-reference-val (function)
- Writers
(setf atomic-reference-val) (function)
- Structure: hash-map-array-node ()
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Direct superclasses
hash-map-node (structure)
- Direct methods
-
- Direct slots
- Slot: edit
-
- Readers
hman-edit (function)
- Writers
(setf hman-edit) (function)
- Slot: count
-
- Type
fixnum
- Readers
hman-count (function)
- Writers
(setf hman-count) (function)
- Slot: array
-
- Type
(simple-array t (*))
- Readers
hman-array (function)
- Writers
(setf hman-array) (function)
- Structure: hash-map-bitmap-node ()
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Direct superclasses
hash-map-node (structure)
- Direct methods
-
- Direct slots
- Slot: edit
-
- Readers
hmn-edit (function)
- Writers
(setf hmn-edit) (function)
- Slot: bitmap
-
- Type
fixnum
- Readers
hmn-bitmap (function)
- Writers
(setf hmn-bitmap) (function)
- Slot: array
-
- Type
(simple-array t (*))
- Readers
hmn-array (function)
- Writers
(setf hmn-array) (function)
- Structure: hash-map-collision-node ()
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Direct superclasses
hash-map-node (structure)
- Direct methods
-
- Direct slots
- Slot: edit
-
- Readers
hmcn-edit (function)
- Writers
(setf hmcn-edit) (function)
- Slot: hash
-
- Type
fixnum
- Readers
hmcn-hash (function)
- Writers
(setf hmcn-hash) (function)
- Slot: count
-
- Type
fixnum
- Readers
hmcn-count (function)
- Writers
(setf hmcn-count) (function)
- Slot: array
-
- Type
(simple-array t (*))
- Readers
hmcn-array (function)
- Writers
(setf hmcn-array) (function)
- Structure: hash-map-node ()
-
- Package
hashtrie
- Source
hashtrie.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct subclasses
-
Appendix A Indexes
A.1 Concepts
| Index Entry | | Section |
|
F | | |
| File, Lisp, hashtrie.asd: | | The hashtrie․asd file |
| File, Lisp, hashtrie/api.lisp: | | The hashtrie/api․lisp file |
| File, Lisp, hashtrie/hashtrie.lisp: | | The hashtrie/hashtrie․lisp file |
| File, Lisp, hashtrie/package.lisp: | | The hashtrie/package․lisp file |
| File, Lisp, hashtrie/utils.lisp: | | The hashtrie/utils․lisp file |
|
H | | |
| hashtrie.asd: | | The hashtrie․asd file |
| hashtrie/api.lisp: | | The hashtrie/api․lisp file |
| hashtrie/hashtrie.lisp: | | The hashtrie/hashtrie․lisp file |
| hashtrie/package.lisp: | | The hashtrie/package․lisp file |
| hashtrie/utils.lisp: | | The hashtrie/utils․lisp file |
|
L | | |
| Lisp File, hashtrie.asd: | | The hashtrie․asd file |
| Lisp File, hashtrie/api.lisp: | | The hashtrie/api․lisp file |
| Lisp File, hashtrie/hashtrie.lisp: | | The hashtrie/hashtrie․lisp file |
| Lisp File, hashtrie/package.lisp: | | The hashtrie/package․lisp file |
| Lisp File, hashtrie/utils.lisp: | | The hashtrie/utils․lisp file |
|
A.2 Functions
| Index Entry | | Section |
|
( | | |
| (setf atomic-reference-val) : | | Internal functions |
| (setf hman-array) : | | Internal functions |
| (setf hman-count) : | | Internal functions |
| (setf hman-edit) : | | Internal functions |
| (setf hmcn-array) : | | Internal functions |
| (setf hmcn-count) : | | Internal functions |
| (setf hmcn-edit) : | | Internal functions |
| (setf hmn-array) : | | Internal functions |
| (setf hmn-bitmap) : | | Internal functions |
| (setf hmn-edit) : | | Internal functions |
| (setf phm-meta) : | | Internal functions |
| (setf thm-count) : | | Internal functions |
| (setf thm-has-null) : | | Internal functions |
| (setf thm-null-value) : | | Internal functions |
| (setf thm-root) : | | Internal functions |
|
A | | |
| array-copy : | | Internal functions |
| atomic-reference-p : | | Internal functions |
| atomic-reference-val : | | Internal functions |
|
B | | |
| bitpos : | | Internal functions |
| box-val : | | Internal macros |
|
C | | |
| clone-and-set : | | Internal functions |
| copy-atomic-reference : | | Internal functions |
| copy-hash-map-array-node : | | Internal functions |
| copy-hash-map-bitmap-node : | | Internal functions |
| copy-hash-map-collision-node : | | Internal functions |
| copy-hash-map-node : | | Internal functions |
| copy-hash-trie : | | Internal functions |
| copy-persistent-hash-map : | | Internal functions |
| copy-simple-array : | | Internal functions |
| copy-transient-hash-map : | | Internal functions |
| create-edit-node : | | Internal functions |
| create-node : | | Internal functions |
|
E | | |
| equiv : | | Internal functions |
|
F | | |
| Function, (setf atomic-reference-val) : | | Internal functions |
| Function, (setf hman-array) : | | Internal functions |
| Function, (setf hman-count) : | | Internal functions |
| Function, (setf hman-edit) : | | Internal functions |
| Function, (setf hmcn-array) : | | Internal functions |
| Function, (setf hmcn-count) : | | Internal functions |
| Function, (setf hmcn-edit) : | | Internal functions |
| Function, (setf hmn-array) : | | Internal functions |
| Function, (setf hmn-bitmap) : | | Internal functions |
| Function, (setf hmn-edit) : | | Internal functions |
| Function, (setf phm-meta) : | | Internal functions |
| Function, (setf thm-count) : | | Internal functions |
| Function, (setf thm-has-null) : | | Internal functions |
| Function, (setf thm-null-value) : | | Internal functions |
| Function, (setf thm-root) : | | Internal functions |
| Function, array-copy : | | Internal functions |
| Function, atomic-reference-p : | | Internal functions |
| Function, atomic-reference-val : | | Internal functions |
| Function, bitpos : | | Internal functions |
| Function, clone-and-set : | | Internal functions |
| Function, copy-atomic-reference : | | Internal functions |
| Function, copy-hash-map-array-node : | | Internal functions |
| Function, copy-hash-map-bitmap-node : | | Internal functions |
| Function, copy-hash-map-collision-node : | | Internal functions |
| Function, copy-hash-map-node : | | Internal functions |
| Function, copy-hash-trie : | | Internal functions |
| Function, copy-persistent-hash-map : | | Internal functions |
| Function, copy-simple-array : | | Internal functions |
| Function, copy-transient-hash-map : | | Internal functions |
| Function, create-edit-node : | | Internal functions |
| Function, create-node : | | Internal functions |
| Function, equiv : | | Internal functions |
| Function, hash : | | Internal functions |
| Function, hash-map-array-node-p : | | Internal functions |
| Function, hash-map-bitmap-node-p : | | Internal functions |
| Function, hash-map-collision-node-p : | | Internal functions |
| Function, hash-map-node-p : | | Internal functions |
| Function, hash-trie-p : | | Exported functions |
| Function, hman-array : | | Internal functions |
| Function, hman-count : | | Internal functions |
| Function, hman-edit : | | Internal functions |
| Function, hman-edit-and-set : | | Internal functions |
| Function, hman-ensure-editable : | | Internal functions |
| Function, hman-pack : | | Internal functions |
| Function, hmcn-array : | | Internal functions |
| Function, hmcn-count : | | Internal functions |
| Function, hmcn-edit : | | Internal functions |
| Function, hmcn-edit-and-set : | | Internal functions |
| Function, hmcn-ensure-editable : | | Internal functions |
| Function, hmcn-find-index : | | Internal functions |
| Function, hmcn-hash : | | Internal functions |
| Function, hmn-array : | | Internal functions |
| Function, hmn-bitmap : | | Internal functions |
| Function, hmn-edit : | | Internal functions |
| Function, hmn-edit-and-remove-pair : | | Internal functions |
| Function, hmn-edit-and-set : | | Internal functions |
| Function, hmn-ensure-editable : | | Internal functions |
| Function, hmn-index : | | Internal functions |
| Function, make-atomic-reference : | | Internal functions |
| Function, make-box : | | Internal functions |
| Function, make-hash-map-array-node : | | Internal functions |
| Function, make-hash-map-bitmap-node : | | Internal functions |
| Function, make-hash-map-collision-node : | | Internal functions |
| Function, make-hash-map-node : | | Internal functions |
| Function, make-hash-trie : | | Exported functions |
| Function, make-persistent-hash-map : | | Internal functions |
| Function, make-transient-hash-map : | | Internal functions |
| Function, map-map : | | Internal functions |
| Function, map-reduce : | | Internal functions |
| Function, mask : | | Internal functions |
| Function, node-make-array-iterator : | | Internal functions |
| Function, persistent-hash-map-p : | | Exported functions |
| Function, phm-as-transient : | | Internal functions |
| Function, phm-count : | | Internal functions |
| Function, phm-has-null : | | Internal functions |
| Function, phm-meta : | | Internal functions |
| Function, phm-null-value : | | Internal functions |
| Function, phm-root : | | Internal functions |
| Function, remove-pair : | | Internal functions |
| Function, thm-count : | | Internal functions |
| Function, thm-do-assoc : | | Internal functions |
| Function, thm-do-persistent : | | Internal functions |
| Function, thm-do-val-at : | | Internal functions |
| Function, thm-do-without : | | Internal functions |
| Function, thm-edit : | | Internal functions |
| Function, thm-ensure-editable : | | Internal functions |
| Function, thm-has-null : | | Internal functions |
| Function, thm-leaf-flag : | | Internal functions |
| Function, thm-null-value : | | Internal functions |
| Function, thm-persistent : | | Internal functions |
| Function, thm-root : | | Internal functions |
| Function, transient-hash-map-p : | | Exported functions |
| Function, tri-add : | | Exported functions |
| Function, tri-has-key : | | Exported functions |
| Function, tri-length : | | Exported functions |
| Function, tri-map : | | Exported functions |
| Function, tri-reduce : | | Exported functions |
| Function, tri-remove : | | Exported functions |
| Function, tri-val : | | Exported functions |
|
G | | |
| Generic Function, map-assoc : | | Internal generic functions |
| Generic Function, map-count : | | Internal generic functions |
| Generic Function, map-make-iterator : | | Internal generic functions |
| Generic Function, map-val-at : | | Internal generic functions |
| Generic Function, map-without : | | Internal generic functions |
| Generic Function, node-assoc : | | Internal generic functions |
| Generic Function, node-assoc-edit : | | Internal generic functions |
| Generic Function, node-find : | | Internal generic functions |
| Generic Function, node-make-iterator : | | Internal generic functions |
| Generic Function, node-without : | | Internal generic functions |
| Generic Function, node-without-edit : | | Internal generic functions |
|
H | | |
| hash : | | Internal functions |
| hash-map-array-node-p : | | Internal functions |
| hash-map-bitmap-node-p : | | Internal functions |
| hash-map-collision-node-p : | | Internal functions |
| hash-map-node-p : | | Internal functions |
| hash-trie-p : | | Exported functions |
| hman-array : | | Internal functions |
| hman-count : | | Internal functions |
| hman-edit : | | Internal functions |
| hman-edit-and-set : | | Internal functions |
| hman-ensure-editable : | | Internal functions |
| hman-pack : | | Internal functions |
| hmcn-array : | | Internal functions |
| hmcn-count : | | Internal functions |
| hmcn-edit : | | Internal functions |
| hmcn-edit-and-set : | | Internal functions |
| hmcn-ensure-editable : | | Internal functions |
| hmcn-find-index : | | Internal functions |
| hmcn-hash : | | Internal functions |
| hmn-array : | | Internal functions |
| hmn-bitmap : | | Internal functions |
| hmn-edit : | | Internal functions |
| hmn-edit-and-remove-pair : | | Internal functions |
| hmn-edit-and-set : | | Internal functions |
| hmn-ensure-editable : | | Internal functions |
| hmn-index : | | Internal functions |
|
L | | |
| logandcount : | | Internal macros |
|
M | | |
| Macro, box-val : | | Internal macros |
| Macro, logandcount : | | Internal macros |
| Macro, shift-right : | | Internal macros |
| Macro, with-transient : | | Exported macros |
| make-atomic-reference : | | Internal functions |
| make-box : | | Internal functions |
| make-hash-map-array-node : | | Internal functions |
| make-hash-map-bitmap-node : | | Internal functions |
| make-hash-map-collision-node : | | Internal functions |
| make-hash-map-node : | | Internal functions |
| make-hash-trie : | | Exported functions |
| make-persistent-hash-map : | | Internal functions |
| make-transient-hash-map : | | Internal functions |
| map-assoc : | | Internal generic functions |
| map-assoc : | | Internal generic functions |
| map-assoc : | | Internal generic functions |
| map-count : | | Internal generic functions |
| map-count : | | Internal generic functions |
| map-count : | | Internal generic functions |
| map-make-iterator : | | Internal generic functions |
| map-make-iterator : | | Internal generic functions |
| map-make-iterator : | | Internal generic functions |
| map-map : | | Internal functions |
| map-reduce : | | Internal functions |
| map-val-at : | | Internal generic functions |
| map-val-at : | | Internal generic functions |
| map-val-at : | | Internal generic functions |
| map-without : | | Internal generic functions |
| map-without : | | Internal generic functions |
| map-without : | | Internal generic functions |
| mask : | | Internal functions |
| Method, map-assoc : | | Internal generic functions |
| Method, map-assoc : | | Internal generic functions |
| Method, map-count : | | Internal generic functions |
| Method, map-count : | | Internal generic functions |
| Method, map-make-iterator : | | Internal generic functions |
| Method, map-make-iterator : | | Internal generic functions |
| Method, map-val-at : | | Internal generic functions |
| Method, map-val-at : | | Internal generic functions |
| Method, map-without : | | Internal generic functions |
| Method, map-without : | | Internal generic functions |
| Method, node-assoc : | | Internal generic functions |
| Method, node-assoc : | | Internal generic functions |
| Method, node-assoc : | | Internal generic functions |
| Method, node-assoc-edit : | | Internal generic functions |
| Method, node-assoc-edit : | | Internal generic functions |
| Method, node-assoc-edit : | | Internal generic functions |
| Method, node-find : | | Internal generic functions |
| Method, node-find : | | Internal generic functions |
| Method, node-find : | | Internal generic functions |
| Method, node-make-iterator : | | Internal generic functions |
| Method, node-make-iterator : | | Internal generic functions |
| Method, node-make-iterator : | | Internal generic functions |
| Method, node-without : | | Internal generic functions |
| Method, node-without : | | Internal generic functions |
| Method, node-without : | | Internal generic functions |
| Method, node-without-edit : | | Internal generic functions |
| Method, node-without-edit : | | Internal generic functions |
| Method, node-without-edit : | | Internal generic functions |
|
N | | |
| node-assoc : | | Internal generic functions |
| node-assoc : | | Internal generic functions |
| node-assoc : | | Internal generic functions |
| node-assoc : | | Internal generic functions |
| node-assoc-edit : | | Internal generic functions |
| node-assoc-edit : | | Internal generic functions |
| node-assoc-edit : | | Internal generic functions |
| node-assoc-edit : | | Internal generic functions |
| node-find : | | Internal generic functions |
| node-find : | | Internal generic functions |
| node-find : | | Internal generic functions |
| node-find : | | Internal generic functions |
| node-make-array-iterator : | | Internal functions |
| node-make-iterator : | | Internal generic functions |
| node-make-iterator : | | Internal generic functions |
| node-make-iterator : | | Internal generic functions |
| node-make-iterator : | | Internal generic functions |
| node-without : | | Internal generic functions |
| node-without : | | Internal generic functions |
| node-without : | | Internal generic functions |
| node-without : | | Internal generic functions |
| node-without-edit : | | Internal generic functions |
| node-without-edit : | | Internal generic functions |
| node-without-edit : | | Internal generic functions |
| node-without-edit : | | Internal generic functions |
|
P | | |
| persistent-hash-map-p : | | Exported functions |
| phm-as-transient : | | Internal functions |
| phm-count : | | Internal functions |
| phm-has-null : | | Internal functions |
| phm-meta : | | Internal functions |
| phm-null-value : | | Internal functions |
| phm-root : | | Internal functions |
|
R | | |
| remove-pair : | | Internal functions |
|
S | | |
| shift-right : | | Internal macros |
|
T | | |
| thm-count : | | Internal functions |
| thm-do-assoc : | | Internal functions |
| thm-do-persistent : | | Internal functions |
| thm-do-val-at : | | Internal functions |
| thm-do-without : | | Internal functions |
| thm-edit : | | Internal functions |
| thm-ensure-editable : | | Internal functions |
| thm-has-null : | | Internal functions |
| thm-leaf-flag : | | Internal functions |
| thm-null-value : | | Internal functions |
| thm-persistent : | | Internal functions |
| thm-root : | | Internal functions |
| transient-hash-map-p : | | Exported functions |
| tri-add : | | Exported functions |
| tri-has-key : | | Exported functions |
| tri-length : | | Exported functions |
| tri-map : | | Exported functions |
| tri-reduce : | | Exported functions |
| tri-remove : | | Exported functions |
| tri-val : | | Exported functions |
|
W | | |
| with-transient : | | Exported macros |
|
A.3 Variables
| Index Entry | | Section |
|
* | | |
| *empty-hash-iterator* : | | Internal special variables |
| *empty-hash-map* : | | Internal special variables |
| *empty-hash-map-node* : | | Internal special variables |
| *max-print-length* : | | Exported special variables |
| *not-found* : | | Internal special variables |
|
+ | | |
| +bits+ : | | Internal constants |
| +mask+ : | | Internal constants |
| +size+ : | | Internal constants |
|
A | | |
| array : | | Internal structures |
| array : | | Internal structures |
| array : | | Internal structures |
|
B | | |
| bitmap : | | Internal structures |
|
C | | |
| Constant, +bits+ : | | Internal constants |
| Constant, +mask+ : | | Internal constants |
| Constant, +size+ : | | Internal constants |
| count : | | Exported structures |
| count : | | Exported structures |
| count : | | Internal structures |
| count : | | Internal structures |
|
E | | |
| edit : | | Exported structures |
| edit : | | Internal structures |
| edit : | | Internal structures |
| edit : | | Internal structures |
|
H | | |
| has-null : | | Exported structures |
| has-null : | | Exported structures |
| hash : | | Internal structures |
|
L | | |
| leaf-flag : | | Exported structures |
|
M | | |
| meta : | | Exported structures |
|
N | | |
| null-value : | | Exported structures |
| null-value : | | Exported structures |
|
R | | |
| root : | | Exported structures |
| root : | | Exported structures |
|
S | | |
| Slot, array : | | Internal structures |
| Slot, array : | | Internal structures |
| Slot, array : | | Internal structures |
| Slot, bitmap : | | Internal structures |
| Slot, count : | | Exported structures |
| Slot, count : | | Exported structures |
| Slot, count : | | Internal structures |
| Slot, count : | | Internal structures |
| Slot, edit : | | Exported structures |
| Slot, edit : | | Internal structures |
| Slot, edit : | | Internal structures |
| Slot, edit : | | Internal structures |
| Slot, has-null : | | Exported structures |
| Slot, has-null : | | Exported structures |
| Slot, hash : | | Internal structures |
| Slot, leaf-flag : | | Exported structures |
| Slot, meta : | | Exported structures |
| Slot, null-value : | | Exported structures |
| Slot, null-value : | | Exported structures |
| Slot, root : | | Exported structures |
| Slot, root : | | Exported structures |
| Slot, val : | | Internal structures |
| Special Variable, *empty-hash-iterator* : | | Internal special variables |
| Special Variable, *empty-hash-map* : | | Internal special variables |
| Special Variable, *empty-hash-map-node* : | | Internal special variables |
| Special Variable, *max-print-length* : | | Exported special variables |
| Special Variable, *not-found* : | | Internal special variables |
|
V | | |
| val : | | Internal structures |
|
A.4 Data types
| Index Entry | | Section |
|
A | | |
| atomic-reference : | | Internal structures |
|
H | | |
| hash-map-array-node : | | Internal structures |
| hash-map-bitmap-node : | | Internal structures |
| hash-map-collision-node : | | Internal structures |
| hash-map-node : | | Internal structures |
| hash-trie : | | Exported structures |
| hashtrie : | | The hashtrie system |
| hashtrie : | | The hashtrie package |
|
P | | |
| Package, hashtrie : | | The hashtrie package |
| persistent-hash-map : | | Exported structures |
|
S | | |
| Structure, atomic-reference : | | Internal structures |
| Structure, hash-map-array-node : | | Internal structures |
| Structure, hash-map-bitmap-node : | | Internal structures |
| Structure, hash-map-collision-node : | | Internal structures |
| Structure, hash-map-node : | | Internal structures |
| Structure, hash-trie : | | Exported structures |
| Structure, persistent-hash-map : | | Exported structures |
| Structure, transient-hash-map : | | Exported structures |
| System, hashtrie : | | The hashtrie system |
|
T | | |
| transient-hash-map : | | Exported structures |
|