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

• package.lisp (file)
• utils.lisp (file)
• hashtrie.lisp (file)
• api.lisp (file)

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

• +bits+ (constant)
• +mask+ (constant)
• +size+ (constant)
• array-copy (function)
• atomic-reference (structure)
• atomic-reference-p (function)
• atomic-reference-val (function)
• (setf atomic-reference-val) (function)
• box-val (macro)
• copy-atomic-reference (function)
• copy-simple-array (function)
• equiv (function)
• hash (function)
• logandcount (macro)
• make-atomic-reference (function)
• make-box (function)
• remove-pair (function)
• shift-right (macro)

3.1.4 hashtrie/hashtrie.lisp

Dependency

utils.lisp (file)

Parent

hashtrie (system)

Location

hashtrie.lisp

Exported Definitions

• *max-print-length* (special variable)
• hash-trie (structure)
• hash-trie-p (function)
• make-hash-trie (function)
• persistent-hash-map (structure)
• persistent-hash-map-p (function)
• transient-hash-map (structure)
• transient-hash-map-p (function)

Internal Definitions

• *empty-hash-iterator* (special variable)
• *empty-hash-map* (special variable)
• *empty-hash-map-node* (special variable)
• *not-found* (special variable)
• bitpos (function)
• clone-and-set (function)
• copy-hash-map-array-node (function)
• copy-hash-map-bitmap-node (function)
• copy-hash-map-collision-node (function)
• copy-hash-map-node (function)
• copy-hash-trie (function)
• copy-persistent-hash-map (function)
• copy-transient-hash-map (function)
• create-edit-node (function)
• create-node (function)
• hash-map-array-node (structure)
• hash-map-array-node-p (function)
• hash-map-bitmap-node (structure)
• hash-map-bitmap-node-p (function)
• hash-map-collision-node (structure)
• hash-map-collision-node-p (function)
• hash-map-node (structure)
• hash-map-node-p (function)
• hman-array (function)
• (setf hman-array) (function)
• hman-count (function)
• (setf hman-count) (function)
• hman-edit (function)
• (setf hman-edit) (function)
• hman-edit-and-set (function)
• hman-ensure-editable (function)
• hman-pack (function)
• hmcn-array (function)
• (setf hmcn-array) (function)
• hmcn-count (function)
• (setf hmcn-count) (function)
• hmcn-edit (function)
• (setf hmcn-edit) (function)
• hmcn-edit-and-set (function)
• hmcn-ensure-editable (function)
• hmcn-find-index (function)
• hmcn-hash (function)
• hmn-array (function)
• (setf hmn-array) (function)
• hmn-bitmap (function)
• (setf hmn-bitmap) (function)
• hmn-edit (function)
• (setf hmn-edit) (function)
• hmn-edit-and-remove-pair (function)
• hmn-edit-and-set (function)
• hmn-ensure-editable (function)
• hmn-index (function)
• make-hash-map-array-node (function)
• make-hash-map-bitmap-node (function)
• make-hash-map-collision-node (function)
• make-hash-map-node (function)
• make-persistent-hash-map (function)
• make-transient-hash-map (function)
• map-assoc (generic function)
• map-assoc (method)
• map-assoc (method)
• map-count (generic function)
• map-count (method)
• map-count (method)
• map-make-iterator (generic function)
• map-make-iterator (method)
• map-make-iterator (method)
• map-map (function)
• map-reduce (function)
• map-val-at (generic function)
• map-val-at (method)
• map-val-at (method)
• map-without (generic function)
• map-without (method)
• map-without (method)
• mask (function)
• node-assoc (generic function)
• node-assoc (method)
• node-assoc (method)
• node-assoc (method)
• node-assoc-edit (generic function)
• node-assoc-edit (method)
• node-assoc-edit (method)
• node-assoc-edit (method)
• node-find (generic function)
• node-find (method)
• node-find (method)
• node-find (method)
• node-make-array-iterator (function)
• node-make-iterator (generic function)
• node-make-iterator (method)
• node-make-iterator (method)
• node-make-iterator (method)
• node-without (generic function)
• node-without (method)
• node-without (method)
• node-without (method)
• node-without-edit (generic function)
• node-without-edit (method)
• node-without-edit (method)
• node-without-edit (method)
• phm-as-transient (function)
• phm-count (function)
• phm-has-null (function)
• phm-meta (function)
• (setf phm-meta) (function)
• phm-null-value (function)
• phm-root (function)
• thm-count (function)
• (setf thm-count) (function)
• thm-do-assoc (function)
• thm-do-persistent (function)
• thm-do-val-at (function)
• thm-do-without (function)
• thm-edit (function)
• thm-ensure-editable (function)
• thm-has-null (function)
• (setf thm-has-null) (function)
• thm-leaf-flag (function)
• thm-null-value (function)
• (setf thm-null-value) (function)
• thm-persistent (function)
• thm-root (function)
• (setf thm-root) (function)

3.1.5 hashtrie/api.lisp

Dependency

hashtrie.lisp (file)

Parent

hashtrie (system)

Location

api.lisp

Exported Definitions

• tri-add (function)
• tri-has-key (function)
• tri-length (function)
• tri-map (function)
• tri-reduce (function)
• tri-remove (function)
• tri-val (function)
• with-transient (macro)

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

• *max-print-length* (special variable)
• hash-trie (structure)
• hash-trie-p (function)
• make-hash-trie (function)
• persistent-hash-map (structure)
• persistent-hash-map-p (function)
• transient-hash-map (structure)
• transient-hash-map-p (function)
• tri-add (function)
• tri-has-key (function)
• tri-length (function)
• tri-map (function)
• tri-reduce (function)
• tri-remove (function)
• tri-val (function)
• with-transient (macro)

Internal Definitions

• *empty-hash-iterator* (special variable)
• *empty-hash-map* (special variable)
• *empty-hash-map-node* (special variable)
• *not-found* (special variable)
• +bits+ (constant)
• +mask+ (constant)
• +size+ (constant)
• array-copy (function)
• atomic-reference (structure)
• atomic-reference-p (function)
• atomic-reference-val (function)
• (setf atomic-reference-val) (function)
• bitpos (function)
• box-val (macro)
• clone-and-set (function)
• copy-atomic-reference (function)
• copy-hash-map-array-node (function)
• copy-hash-map-bitmap-node (function)
• copy-hash-map-collision-node (function)
• copy-hash-map-node (function)
• copy-hash-trie (function)
• copy-persistent-hash-map (function)
• copy-simple-array (function)
• copy-transient-hash-map (function)
• create-edit-node (function)
• create-node (function)
• equiv (function)
• hash (function)
• hash-map-array-node (structure)
• hash-map-array-node-p (function)
• hash-map-bitmap-node (structure)
• hash-map-bitmap-node-p (function)
• hash-map-collision-node (structure)
• hash-map-collision-node-p (function)
• hash-map-node (structure)
• hash-map-node-p (function)
• hman-array (function)
• (setf hman-array) (function)
• hman-count (function)
• (setf hman-count) (function)
• hman-edit (function)
• (setf hman-edit) (function)
• hman-edit-and-set (function)
• hman-ensure-editable (function)
• hman-pack (function)
• hmcn-array (function)
• (setf hmcn-array) (function)
• hmcn-count (function)
• (setf hmcn-count) (function)
• hmcn-edit (function)
• (setf hmcn-edit) (function)
• hmcn-edit-and-set (function)
• hmcn-ensure-editable (function)
• hmcn-find-index (function)
• hmcn-hash (function)
• hmn-array (function)
• (setf hmn-array) (function)
• hmn-bitmap (function)
• (setf hmn-bitmap) (function)
• hmn-edit (function)
• (setf hmn-edit) (function)
• hmn-edit-and-remove-pair (function)
• hmn-edit-and-set (function)
• hmn-ensure-editable (function)
• hmn-index (function)
• logandcount (macro)
• make-atomic-reference (function)
• make-box (function)
• make-hash-map-array-node (function)
• make-hash-map-bitmap-node (function)
• make-hash-map-collision-node (function)
• make-hash-map-node (function)
• make-persistent-hash-map (function)
• make-transient-hash-map (function)
• map-assoc (generic function)
• map-assoc (method)
• map-assoc (method)
• map-count (generic function)
• map-count (method)
• map-count (method)
• map-make-iterator (generic function)
• map-make-iterator (method)
• map-make-iterator (method)
• map-map (function)
• map-reduce (function)
• map-val-at (generic function)
• map-val-at (method)
• map-val-at (method)
• map-without (generic function)
• map-without (method)
• map-without (method)
• mask (function)
• node-assoc (generic function)
• node-assoc (method)
• node-assoc (method)
• node-assoc (method)
• node-assoc-edit (generic function)
• node-assoc-edit (method)
• node-assoc-edit (method)
• node-assoc-edit (method)
• node-find (generic function)
• node-find (method)
• node-find (method)
• node-find (method)
• node-make-array-iterator (function)
• node-make-iterator (generic function)
• node-make-iterator (method)
• node-make-iterator (method)
• node-make-iterator (method)
• node-without (generic function)
• node-without (method)
• node-without (method)
• node-without (method)
• node-without-edit (generic function)
• node-without-edit (method)
• node-without-edit (method)
• node-without-edit (method)
• phm-as-transient (function)
• phm-count (function)
• phm-has-null (function)
• phm-meta (function)
• (setf phm-meta) (function)
• phm-null-value (function)
• phm-root (function)
• remove-pair (function)
• shift-right (macro)
• thm-count (function)
• (setf thm-count) (function)
• thm-do-assoc (function)
• thm-do-persistent (function)
• thm-do-val-at (function)
• thm-do-without (function)
• thm-edit (function)
• thm-ensure-editable (function)
• thm-has-null (function)
• (setf thm-has-null) (function)
• thm-leaf-flag (function)
• thm-null-value (function)
• (setf thm-null-value) (function)
• thm-persistent (function)
• thm-root (function)
• (setf thm-root) (function)

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

• persistent-hash-map (structure)
• transient-hash-map (structure)

Structure: persistent-hash-map ()

Package

hashtrie

Source

hashtrie.lisp (file)

Direct superclasses

hash-trie (structure)

Direct methods

• print-object (method)
• map-count (method)
• map-without (method)
• map-make-iterator (method)
• map-val-at (method)
• map-assoc (method)

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

• map-count (method)
• map-make-iterator (method)
• map-val-at (method)
• map-without (method)
• map-assoc (method)

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

• node-make-iterator (method)
• node-find (method)
• node-without (method)
• node-without-edit (method)
• node-assoc-edit (method)
• node-assoc (method)

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

• node-make-iterator (method)
• node-without (method)
• node-without-edit (method)
• node-find (method)
• node-assoc (method)
• node-assoc-edit (method)

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

• node-make-iterator (method)
• node-find (method)
• node-without-edit (method)
• node-assoc-edit (method)
• node-without (method)
• node-assoc (method)

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

• hash-map-array-node (structure)
• hash-map-bitmap-node (structure)
• hash-map-collision-node (structure)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables