The hashtrie Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The hashtrie Reference Manual

This is the hashtrie Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 04:58:07 2022 GMT+0.

Table of Contents


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.


Previous: , Up: Systems   [Contents][Index]

2.1 hashtrie

An implementation of the Hash Trie datastructure, based on Clojure’s

Author

Daniel Keogh

License

Eclipse 2.0

Version

1.0.0

Source

hashtrie.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 hashtrie/hashtrie.asd

Source

hashtrie.asd.

Parent Component

hashtrie (system).

ASDF Systems

hashtrie.


3.1.2 hashtrie/package.lisp

Source

hashtrie.asd.

Parent Component

hashtrie (system).

Packages

hashtrie.


3.1.3 hashtrie/utils.lisp

Dependency

package.lisp (file).

Source

hashtrie.asd.

Parent Component

hashtrie (system).

Internals

3.1.4 hashtrie/hashtrie.lisp

Dependency

utils.lisp (file).

Source

hashtrie.asd.

Parent Component

hashtrie (system).

Public Interface
Internals

Previous: , Up: Lisp   [Contents][Index]

3.1.5 hashtrie/api.lisp

Dependency

hashtrie.lisp (file).

Source

hashtrie.asd.

Parent Component

hashtrie (system).

Public Interface

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 hashtrie

A fast implementation of the Hash Trie data structure, based on Clojure.

Source

package.lisp.

Nickname

htr

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


Next: , Previous: , Up: Public Interface   [Contents][Index]

5.1.1 Special variables

Special Variable: *max-print-length*
Package

hashtrie.

Source

hashtrie.lisp.


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.


5.1.3 Ordinary functions

Function: hash-trie-p (object)
Package

hashtrie.

Source

hashtrie.lisp.

Function: make-hash-trie (&rest args)
Package

hashtrie.

Source

hashtrie.lisp.

Function: persistent-hash-map-p (object)
Package

hashtrie.

Source

hashtrie.lisp.

Function: transient-hash-map-p (object)
Package

hashtrie.

Source

hashtrie.lisp.

Function: tri-add (hash-trie key val)

Create a new map with the given key-value pair

Package

hashtrie.

Source

api.lisp.

Function: tri-has-key (hash-trie key)

Test if the key is in the hash trie

Package

hashtrie.

Source

api.lisp.

Function: tri-length (hash-trie)

The number of pairs in the hash trie

Package

hashtrie.

Source

api.lisp.

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.

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.

Function: tri-remove (hash-trie key)

Remove the pair from the hash trie

Package

hashtrie.

Source

api.lisp.

Function: tri-val (hash-trie key &optional not-found)

Get the value for a given key

Package

hashtrie.

Source

api.lisp.


5.1.4 Standalone methods

Method: print-object ((map persistent-hash-map) stream)
Source

hashtrie.lisp.


5.1.5 Structures

Structure: hash-trie
Package

hashtrie.

Source

hashtrie.lisp.

Direct superclasses

structure-object.

Direct subclasses
Structure: persistent-hash-map
Package

hashtrie.

Source

hashtrie.lisp.

Direct superclasses

hash-trie.

Direct methods
Direct slots
Slot: meta
Type

(or null hashtrie:hash-trie)

Readers

phm-meta.

Writers

(setf phm-meta).

Slot: count
Package

common-lisp.

Type

fixnum

Readers

phm-count.

Writers

This slot is read-only.

Slot: root
Type

(or null hashtrie::hash-map-node)

Readers

phm-root.

Writers

This slot is read-only.

Slot: has-null
Type

boolean

Readers

phm-has-null.

Writers

This slot is read-only.

Slot: null-value
Readers

phm-null-value.

Writers

This slot is read-only.

Structure: transient-hash-map
Package

hashtrie.

Source

hashtrie.lisp.

Direct superclasses

hash-trie.

Direct methods
Direct slots
Slot: edit
Readers

thm-edit.

Writers

This slot is read-only.

Slot: count
Package

common-lisp.

Type

fixnum

Readers

thm-count.

Writers

(setf thm-count).

Slot: root
Type

(or null hashtrie::hash-map-node)

Readers

thm-root.

Writers

(setf thm-root).

Slot: has-null
Type

boolean

Readers

thm-has-null.

Writers

(setf thm-has-null).

Slot: null-value
Readers

thm-null-value.

Writers

(setf thm-null-value).

Slot: leaf-flag
Initform

(hashtrie::make-box)

Readers

thm-leaf-flag.

Writers

This slot is read-only.


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Constants

Constant: +bits+
Package

hashtrie.

Source

utils.lisp.

Constant: +mask+
Package

hashtrie.

Source

utils.lisp.

Constant: +size+
Package

hashtrie.

Source

utils.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.2 Special variables

Special Variable: *empty-hash-iterator*
Package

hashtrie.

Source

hashtrie.lisp.

Special Variable: *empty-hash-map*
Package

hashtrie.

Source

hashtrie.lisp.

Special Variable: *empty-hash-map-node*
Package

hashtrie.

Source

hashtrie.lisp.

Special Variable: *not-found*
Package

hashtrie.

Source

hashtrie.lisp.


5.2.3 Macros

Macro: box-val (b)
Package

hashtrie.

Source

utils.lisp.

Macro: logandcount (n1 n2)
Package

hashtrie.

Source

utils.lisp.

Macro: shift-right (i)
Package

hashtrie.

Source

utils.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.4 Ordinary functions

Function: array-copy (src src-pos dest dest-start length)
Package

hashtrie.

Source

utils.lisp.

Function: atomic-reference-p (object)
Package

hashtrie.

Source

utils.lisp.

Reader: atomic-reference-val (instance)
Writer: (setf atomic-reference-val) (instance)
Package

hashtrie.

Source

utils.lisp.

Target Slot

val.

Function: bitpos (hash shift)
Package

hashtrie.

Source

hashtrie.lisp.

Function: clone-and-set (array i new-val &optional j new-val2)
Package

hashtrie.

Source

hashtrie.lisp.

Function: copy-atomic-reference (instance)
Package

hashtrie.

Source

utils.lisp.

Function: copy-hash-map-array-node (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Function: copy-hash-map-bitmap-node (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Function: copy-hash-map-collision-node (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Function: copy-hash-map-node (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Function: copy-hash-trie (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Function: copy-persistent-hash-map (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Function: copy-simple-array (arr)
Package

hashtrie.

Source

utils.lisp.

Function: copy-transient-hash-map (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Function: create-edit-node (edit shift key1 val1 key2hash key2 val2)
Package

hashtrie.

Source

hashtrie.lisp.

Function: create-node (shift key1 val1 key2hash key2 val2)
Package

hashtrie.

Source

hashtrie.lisp.

Function: equiv (v1 v2)
Package

hashtrie.

Source

utils.lisp.

Function: hash (x)
Package

hashtrie.

Source

utils.lisp.

Function: hash-map-array-node-p (object)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hash-map-bitmap-node-p (object)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hash-map-collision-node-p (object)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hash-map-node-p (object)
Package

hashtrie.

Source

hashtrie.lisp.

Reader: hman-array (instance)
Writer: (setf hman-array) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

array.

Reader: hman-count (instance)
Writer: (setf hman-count) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

count.

Reader: hman-edit (instance)
Writer: (setf hman-edit) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

edit.

Function: hman-edit-and-set (node edit i n)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hman-ensure-editable (node edit)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hman-pack (node edit idx)
Package

hashtrie.

Source

hashtrie.lisp.

Reader: hmcn-array (instance)
Writer: (setf hmcn-array) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

array.

Reader: hmcn-count (instance)
Writer: (setf hmcn-count) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

count.

Reader: hmcn-edit (instance)
Writer: (setf hmcn-edit) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

edit.

Function: hmcn-edit-and-set (node edit i a &optional j b)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hmcn-ensure-editable (node edit)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hmcn-find-index (node key)
Package

hashtrie.

Source

hashtrie.lisp.

Reader: hmcn-hash (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

hash.

Reader: hmn-array (instance)
Writer: (setf hmn-array) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

array.

Reader: hmn-bitmap (instance)
Writer: (setf hmn-bitmap) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

bitmap.

Reader: hmn-edit (instance)
Writer: (setf hmn-edit) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

edit.

Function: hmn-edit-and-remove-pair (node edit bit i)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hmn-edit-and-set (node edit i a &optional j b)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hmn-ensure-editable (node edit)
Package

hashtrie.

Source

hashtrie.lisp.

Function: hmn-index (node bit)
Package

hashtrie.

Source

hashtrie.lisp.

Function: make-atomic-reference (&key val)
Package

hashtrie.

Source

utils.lisp.

Function: make-box ()
Package

hashtrie.

Source

utils.lisp.

Function: make-hash-map-array-node (&key edit count array)
Package

hashtrie.

Source

hashtrie.lisp.

Function: make-hash-map-bitmap-node (&key edit bitmap array)
Package

hashtrie.

Source

hashtrie.lisp.

Function: make-hash-map-collision-node (&key edit hash count array)
Package

hashtrie.

Source

hashtrie.lisp.

Function: make-hash-map-node (&key)
Package

hashtrie.

Source

hashtrie.lisp.

Function: make-persistent-hash-map (&key meta count root has-null null-value)
Package

hashtrie.

Source

hashtrie.lisp.

Function: make-transient-hash-map (&key edit count root has-null null-value leaf-flag)
Package

hashtrie.

Source

hashtrie.lisp.

Function: map-map (map fn)
Package

hashtrie.

Source

hashtrie.lisp.

Function: map-reduce (map fn &optional start-val)
Package

hashtrie.

Source

hashtrie.lisp.

Function: mask (hash shift)
Package

hashtrie.

Source

hashtrie.lisp.

Function: node-make-array-iterator (array)
Package

hashtrie.

Source

hashtrie.lisp.

Function: phm-as-transient (map)
Package

hashtrie.

Source

hashtrie.lisp.

Reader: phm-count (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

count.

Reader: phm-has-null (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

has-null.

Reader: phm-meta (instance)
Writer: (setf phm-meta) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

meta.

Reader: phm-null-value (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

null-value.

Reader: phm-root (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

root.

Function: remove-pair (array i)
Package

hashtrie.

Source

utils.lisp.

Reader: thm-count (instance)
Writer: (setf thm-count) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

count.

Function: thm-do-assoc (map key val)
Package

hashtrie.

Source

hashtrie.lisp.

Function: thm-do-persistent (map)
Package

hashtrie.

Source

hashtrie.lisp.

Function: thm-do-val-at (map key not-found)
Package

hashtrie.

Source

hashtrie.lisp.

Function: thm-do-without (map key)
Package

hashtrie.

Source

hashtrie.lisp.

Reader: thm-edit (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

edit.

Function: thm-ensure-editable (map)
Package

hashtrie.

Source

hashtrie.lisp.

Reader: thm-has-null (instance)
Writer: (setf thm-has-null) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

has-null.

Reader: thm-leaf-flag (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

leaf-flag.

Reader: thm-null-value (instance)
Writer: (setf thm-null-value) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

null-value.

Function: thm-persistent (map)
Package

hashtrie.

Source

hashtrie.lisp.

Reader: thm-root (instance)
Writer: (setf thm-root) (instance)
Package

hashtrie.

Source

hashtrie.lisp.

Target Slot

root.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.5 Generic functions

Generic Function: map-assoc (hash-map key val)
Package

hashtrie.

Source

hashtrie.lisp.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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)

Previous: , Up: Internals   [Contents][Index]

5.2.6 Structures

Structure: atomic-reference
Package

hashtrie.

Source

utils.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: val
Readers

atomic-reference-val.

Writers

(setf atomic-reference-val).

Structure: hash-map-array-node
Package

hashtrie.

Source

hashtrie.lisp.

Direct superclasses

hash-map-node.

Direct methods
Direct slots
Slot: edit
Readers

hman-edit.

Writers

(setf hman-edit).

Slot: count
Package

common-lisp.

Type

fixnum

Readers

hman-count.

Writers

(setf hman-count).

Slot: array
Package

common-lisp.

Type

(simple-array t (*))

Readers

hman-array.

Writers

(setf hman-array).

Structure: hash-map-bitmap-node
Package

hashtrie.

Source

hashtrie.lisp.

Direct superclasses

hash-map-node.

Direct methods
Direct slots
Slot: edit
Readers

hmn-edit.

Writers

(setf hmn-edit).

Slot: bitmap
Type

fixnum

Readers

hmn-bitmap.

Writers

(setf hmn-bitmap).

Slot: array
Package

common-lisp.

Type

(simple-array t (*))

Readers

hmn-array.

Writers

(setf hmn-array).

Structure: hash-map-collision-node
Package

hashtrie.

Source

hashtrie.lisp.

Direct superclasses

hash-map-node.

Direct methods
Direct slots
Slot: edit
Readers

hmcn-edit.

Writers

(setf hmcn-edit).

Slot: hash
Type

fixnum

Readers

hmcn-hash.

Writers

This slot is read-only.

Slot: count
Package

common-lisp.

Type

fixnum

Readers

hmcn-count.

Writers

(setf hmcn-count).

Slot: array
Package

common-lisp.

Type

(simple-array t (*))

Readers

hmcn-array.

Writers

(setf hmcn-array).

Structure: hash-map-node
Package

hashtrie.

Source

hashtrie.lisp.

Direct superclasses

structure-object.

Direct subclasses

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
A   B   C   E   F   G   H   L   M   N   P   R   S   T   W  
Index Entry  Section

(
(setf atomic-reference-val): Private ordinary functions
(setf hman-array): Private ordinary functions
(setf hman-count): Private ordinary functions
(setf hman-edit): Private ordinary functions
(setf hmcn-array): Private ordinary functions
(setf hmcn-count): Private ordinary functions
(setf hmcn-edit): Private ordinary functions
(setf hmn-array): Private ordinary functions
(setf hmn-bitmap): Private ordinary functions
(setf hmn-edit): Private ordinary functions
(setf phm-meta): Private ordinary functions
(setf thm-count): Private ordinary functions
(setf thm-has-null): Private ordinary functions
(setf thm-null-value): Private ordinary functions
(setf thm-root): Private ordinary functions

A
array-copy: Private ordinary functions
atomic-reference-p: Private ordinary functions
atomic-reference-val: Private ordinary functions

B
bitpos: Private ordinary functions
box-val: Private macros

C
clone-and-set: Private ordinary functions
copy-atomic-reference: Private ordinary functions
copy-hash-map-array-node: Private ordinary functions
copy-hash-map-bitmap-node: Private ordinary functions
copy-hash-map-collision-node: Private ordinary functions
copy-hash-map-node: Private ordinary functions
copy-hash-trie: Private ordinary functions
copy-persistent-hash-map: Private ordinary functions
copy-simple-array: Private ordinary functions
copy-transient-hash-map: Private ordinary functions
create-edit-node: Private ordinary functions
create-node: Private ordinary functions

E
equiv: Private ordinary functions

F
Function, (setf atomic-reference-val): Private ordinary functions
Function, (setf hman-array): Private ordinary functions
Function, (setf hman-count): Private ordinary functions
Function, (setf hman-edit): Private ordinary functions
Function, (setf hmcn-array): Private ordinary functions
Function, (setf hmcn-count): Private ordinary functions
Function, (setf hmcn-edit): Private ordinary functions
Function, (setf hmn-array): Private ordinary functions
Function, (setf hmn-bitmap): Private ordinary functions
Function, (setf hmn-edit): Private ordinary functions
Function, (setf phm-meta): Private ordinary functions
Function, (setf thm-count): Private ordinary functions
Function, (setf thm-has-null): Private ordinary functions
Function, (setf thm-null-value): Private ordinary functions
Function, (setf thm-root): Private ordinary functions
Function, array-copy: Private ordinary functions
Function, atomic-reference-p: Private ordinary functions
Function, atomic-reference-val: Private ordinary functions
Function, bitpos: Private ordinary functions
Function, clone-and-set: Private ordinary functions
Function, copy-atomic-reference: Private ordinary functions
Function, copy-hash-map-array-node: Private ordinary functions
Function, copy-hash-map-bitmap-node: Private ordinary functions
Function, copy-hash-map-collision-node: Private ordinary functions
Function, copy-hash-map-node: Private ordinary functions
Function, copy-hash-trie: Private ordinary functions
Function, copy-persistent-hash-map: Private ordinary functions
Function, copy-simple-array: Private ordinary functions
Function, copy-transient-hash-map: Private ordinary functions
Function, create-edit-node: Private ordinary functions
Function, create-node: Private ordinary functions
Function, equiv: Private ordinary functions
Function, hash: Private ordinary functions
Function, hash-map-array-node-p: Private ordinary functions
Function, hash-map-bitmap-node-p: Private ordinary functions
Function, hash-map-collision-node-p: Private ordinary functions
Function, hash-map-node-p: Private ordinary functions
Function, hash-trie-p: Public ordinary functions
Function, hman-array: Private ordinary functions
Function, hman-count: Private ordinary functions
Function, hman-edit: Private ordinary functions
Function, hman-edit-and-set: Private ordinary functions
Function, hman-ensure-editable: Private ordinary functions
Function, hman-pack: Private ordinary functions
Function, hmcn-array: Private ordinary functions
Function, hmcn-count: Private ordinary functions
Function, hmcn-edit: Private ordinary functions
Function, hmcn-edit-and-set: Private ordinary functions
Function, hmcn-ensure-editable: Private ordinary functions
Function, hmcn-find-index: Private ordinary functions
Function, hmcn-hash: Private ordinary functions
Function, hmn-array: Private ordinary functions
Function, hmn-bitmap: Private ordinary functions
Function, hmn-edit: Private ordinary functions
Function, hmn-edit-and-remove-pair: Private ordinary functions
Function, hmn-edit-and-set: Private ordinary functions
Function, hmn-ensure-editable: Private ordinary functions
Function, hmn-index: Private ordinary functions
Function, make-atomic-reference: Private ordinary functions
Function, make-box: Private ordinary functions
Function, make-hash-map-array-node: Private ordinary functions
Function, make-hash-map-bitmap-node: Private ordinary functions
Function, make-hash-map-collision-node: Private ordinary functions
Function, make-hash-map-node: Private ordinary functions
Function, make-hash-trie: Public ordinary functions
Function, make-persistent-hash-map: Private ordinary functions
Function, make-transient-hash-map: Private ordinary functions
Function, map-map: Private ordinary functions
Function, map-reduce: Private ordinary functions
Function, mask: Private ordinary functions
Function, node-make-array-iterator: Private ordinary functions
Function, persistent-hash-map-p: Public ordinary functions
Function, phm-as-transient: Private ordinary functions
Function, phm-count: Private ordinary functions
Function, phm-has-null: Private ordinary functions
Function, phm-meta: Private ordinary functions
Function, phm-null-value: Private ordinary functions
Function, phm-root: Private ordinary functions
Function, remove-pair: Private ordinary functions
Function, thm-count: Private ordinary functions
Function, thm-do-assoc: Private ordinary functions
Function, thm-do-persistent: Private ordinary functions
Function, thm-do-val-at: Private ordinary functions
Function, thm-do-without: Private ordinary functions
Function, thm-edit: Private ordinary functions
Function, thm-ensure-editable: Private ordinary functions
Function, thm-has-null: Private ordinary functions
Function, thm-leaf-flag: Private ordinary functions
Function, thm-null-value: Private ordinary functions
Function, thm-persistent: Private ordinary functions
Function, thm-root: Private ordinary functions
Function, transient-hash-map-p: Public ordinary functions
Function, tri-add: Public ordinary functions
Function, tri-has-key: Public ordinary functions
Function, tri-length: Public ordinary functions
Function, tri-map: Public ordinary functions
Function, tri-reduce: Public ordinary functions
Function, tri-remove: Public ordinary functions
Function, tri-val: Public ordinary functions

G
Generic Function, map-assoc: Private generic functions
Generic Function, map-count: Private generic functions
Generic Function, map-make-iterator: Private generic functions
Generic Function, map-val-at: Private generic functions
Generic Function, map-without: Private generic functions
Generic Function, node-assoc: Private generic functions
Generic Function, node-assoc-edit: Private generic functions
Generic Function, node-find: Private generic functions
Generic Function, node-make-iterator: Private generic functions
Generic Function, node-without: Private generic functions
Generic Function, node-without-edit: Private generic functions

H
hash: Private ordinary functions
hash-map-array-node-p: Private ordinary functions
hash-map-bitmap-node-p: Private ordinary functions
hash-map-collision-node-p: Private ordinary functions
hash-map-node-p: Private ordinary functions
hash-trie-p: Public ordinary functions
hman-array: Private ordinary functions
hman-count: Private ordinary functions
hman-edit: Private ordinary functions
hman-edit-and-set: Private ordinary functions
hman-ensure-editable: Private ordinary functions
hman-pack: Private ordinary functions
hmcn-array: Private ordinary functions
hmcn-count: Private ordinary functions
hmcn-edit: Private ordinary functions
hmcn-edit-and-set: Private ordinary functions
hmcn-ensure-editable: Private ordinary functions
hmcn-find-index: Private ordinary functions
hmcn-hash: Private ordinary functions
hmn-array: Private ordinary functions
hmn-bitmap: Private ordinary functions
hmn-edit: Private ordinary functions
hmn-edit-and-remove-pair: Private ordinary functions
hmn-edit-and-set: Private ordinary functions
hmn-ensure-editable: Private ordinary functions
hmn-index: Private ordinary functions

L
logandcount: Private macros

M
Macro, box-val: Private macros
Macro, logandcount: Private macros
Macro, shift-right: Private macros
Macro, with-transient: Public macros
make-atomic-reference: Private ordinary functions
make-box: Private ordinary functions
make-hash-map-array-node: Private ordinary functions
make-hash-map-bitmap-node: Private ordinary functions
make-hash-map-collision-node: Private ordinary functions
make-hash-map-node: Private ordinary functions
make-hash-trie: Public ordinary functions
make-persistent-hash-map: Private ordinary functions
make-transient-hash-map: Private ordinary functions
map-assoc: Private generic functions
map-assoc: Private generic functions
map-assoc: Private generic functions
map-count: Private generic functions
map-count: Private generic functions
map-count: Private generic functions
map-make-iterator: Private generic functions
map-make-iterator: Private generic functions
map-make-iterator: Private generic functions
map-map: Private ordinary functions
map-reduce: Private ordinary functions
map-val-at: Private generic functions
map-val-at: Private generic functions
map-val-at: Private generic functions
map-without: Private generic functions
map-without: Private generic functions
map-without: Private generic functions
mask: Private ordinary functions
Method, map-assoc: Private generic functions
Method, map-assoc: Private generic functions
Method, map-count: Private generic functions
Method, map-count: Private generic functions
Method, map-make-iterator: Private generic functions
Method, map-make-iterator: Private generic functions
Method, map-val-at: Private generic functions
Method, map-val-at: Private generic functions
Method, map-without: Private generic functions
Method, map-without: Private generic functions
Method, node-assoc: Private generic functions
Method, node-assoc: Private generic functions
Method, node-assoc: Private generic functions
Method, node-assoc-edit: Private generic functions
Method, node-assoc-edit: Private generic functions
Method, node-assoc-edit: Private generic functions
Method, node-find: Private generic functions
Method, node-find: Private generic functions
Method, node-find: Private generic functions
Method, node-make-iterator: Private generic functions
Method, node-make-iterator: Private generic functions
Method, node-make-iterator: Private generic functions
Method, node-without: Private generic functions
Method, node-without: Private generic functions
Method, node-without: Private generic functions
Method, node-without-edit: Private generic functions
Method, node-without-edit: Private generic functions
Method, node-without-edit: Private generic functions
Method, print-object: Public standalone methods

N
node-assoc: Private generic functions
node-assoc: Private generic functions
node-assoc: Private generic functions
node-assoc: Private generic functions
node-assoc-edit: Private generic functions
node-assoc-edit: Private generic functions
node-assoc-edit: Private generic functions
node-assoc-edit: Private generic functions
node-find: Private generic functions
node-find: Private generic functions
node-find: Private generic functions
node-find: Private generic functions
node-make-array-iterator: Private ordinary functions
node-make-iterator: Private generic functions
node-make-iterator: Private generic functions
node-make-iterator: Private generic functions
node-make-iterator: Private generic functions
node-without: Private generic functions
node-without: Private generic functions
node-without: Private generic functions
node-without: Private generic functions
node-without-edit: Private generic functions
node-without-edit: Private generic functions
node-without-edit: Private generic functions
node-without-edit: Private generic functions

P
persistent-hash-map-p: Public ordinary functions
phm-as-transient: Private ordinary functions
phm-count: Private ordinary functions
phm-has-null: Private ordinary functions
phm-meta: Private ordinary functions
phm-null-value: Private ordinary functions
phm-root: Private ordinary functions
print-object: Public standalone methods

R
remove-pair: Private ordinary functions

S
shift-right: Private macros

T
thm-count: Private ordinary functions
thm-do-assoc: Private ordinary functions
thm-do-persistent: Private ordinary functions
thm-do-val-at: Private ordinary functions
thm-do-without: Private ordinary functions
thm-edit: Private ordinary functions
thm-ensure-editable: Private ordinary functions
thm-has-null: Private ordinary functions
thm-leaf-flag: Private ordinary functions
thm-null-value: Private ordinary functions
thm-persistent: Private ordinary functions
thm-root: Private ordinary functions
transient-hash-map-p: Public ordinary functions
tri-add: Public ordinary functions
tri-has-key: Public ordinary functions
tri-length: Public ordinary functions
tri-map: Public ordinary functions
tri-reduce: Public ordinary functions
tri-remove: Public ordinary functions
tri-val: Public ordinary functions

W
with-transient: Public macros

Jump to:   (  
A   B   C   E   F   G   H   L   M   N   P   R   S   T   W  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *   +  
A   B   C   E   H   L   M   N   R   S   V  
Index Entry  Section

*
*empty-hash-iterator*: Private special variables
*empty-hash-map*: Private special variables
*empty-hash-map-node*: Private special variables
*max-print-length*: Public special variables
*not-found*: Private special variables

+
+bits+: Private constants
+mask+: Private constants
+size+: Private constants

A
array: Private structures
array: Private structures
array: Private structures

B
bitmap: Private structures

C
Constant, +bits+: Private constants
Constant, +mask+: Private constants
Constant, +size+: Private constants
count: Public structures
count: Public structures
count: Private structures
count: Private structures

E
edit: Public structures
edit: Private structures
edit: Private structures
edit: Private structures

H
has-null: Public structures
has-null: Public structures
hash: Private structures

L
leaf-flag: Public structures

M
meta: Public structures

N
null-value: Public structures
null-value: Public structures

R
root: Public structures
root: Public structures

S
Slot, array: Private structures
Slot, array: Private structures
Slot, array: Private structures
Slot, bitmap: Private structures
Slot, count: Public structures
Slot, count: Public structures
Slot, count: Private structures
Slot, count: Private structures
Slot, edit: Public structures
Slot, edit: Private structures
Slot, edit: Private structures
Slot, edit: Private structures
Slot, has-null: Public structures
Slot, has-null: Public structures
Slot, hash: Private structures
Slot, leaf-flag: Public structures
Slot, meta: Public structures
Slot, null-value: Public structures
Slot, null-value: Public structures
Slot, root: Public structures
Slot, root: Public structures
Slot, val: Private structures
Special Variable, *empty-hash-iterator*: Private special variables
Special Variable, *empty-hash-map*: Private special variables
Special Variable, *empty-hash-map-node*: Private special variables
Special Variable, *max-print-length*: Public special variables
Special Variable, *not-found*: Private special variables

V
val: Private structures

Jump to:   *   +  
A   B   C   E   H   L   M   N   R   S   V  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   A   F   H   P   S   T   U  
Index Entry  Section

A
api.lisp: The hashtrie/api․lisp file
atomic-reference: Private structures

F
File, api.lisp: The hashtrie/api․lisp file
File, hashtrie.asd: The hashtrie/hashtrie․asd file
File, hashtrie.lisp: The hashtrie/hashtrie․lisp file
File, package.lisp: The hashtrie/package․lisp file
File, utils.lisp: The hashtrie/utils․lisp file

H
hash-map-array-node: Private structures
hash-map-bitmap-node: Private structures
hash-map-collision-node: Private structures
hash-map-node: Private structures
hash-trie: Public structures
hashtrie: The hashtrie system
hashtrie: The hashtrie package
hashtrie.asd: The hashtrie/hashtrie․asd file
hashtrie.lisp: The hashtrie/hashtrie․lisp file

P
Package, hashtrie: The hashtrie package
package.lisp: The hashtrie/package․lisp file
persistent-hash-map: Public structures

S
Structure, atomic-reference: Private structures
Structure, hash-map-array-node: Private structures
Structure, hash-map-bitmap-node: Private structures
Structure, hash-map-collision-node: Private structures
Structure, hash-map-node: Private structures
Structure, hash-trie: Public structures
Structure, persistent-hash-map: Public structures
Structure, transient-hash-map: Public structures
System, hashtrie: The hashtrie system

T
transient-hash-map: Public structures

U
utils.lisp: The hashtrie/utils․lisp file

Jump to:   A   F   H   P   S   T   U