The hashtrie Reference Manual

Table of Contents

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 3.0 "Montgomery Scott" on Sun May 15 04:56:15 2022 GMT+0.


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

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"

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

2 Systems

The main system appears first, followed by any subsystem dependency.


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

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

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

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 files   [Contents][Index]

3.1.1 hashtrie.asd

Location

hashtrie.asd

Systems

hashtrie (system)


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

3.1.2 hashtrie/package.lisp

Parent

hashtrie (system)

Location

package.lisp

Packages

hashtrie


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

3.1.3 hashtrie/utils.lisp

Dependency

package.lisp (file)

Parent

hashtrie (system)

Location

utils.lisp

Internal Definitions

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

3.1.4 hashtrie/hashtrie.lisp

Dependency

utils.lisp (file)

Parent

hashtrie (system)

Location

hashtrie.lisp

Exported Definitions
Internal Definitions

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

3.1.5 hashtrie/api.lisp

Dependency

hashtrie.lisp (file)

Parent

hashtrie (system)

Location

api.lisp

Exported Definitions

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

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 (file)

Nickname

htr

Use List

common-lisp

Exported Definitions
Internal Definitions

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

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Special variables

Special Variable: *max-print-length*
Package

hashtrie

Source

hashtrie.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Previous: , Up: Exported definitions   [Contents][Index]

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)


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

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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

Previous: , Up: Internal definitions   [Contents][Index]

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

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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   H   L  
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

Jump to:   F   H   L  

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): 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

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*: 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

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   H   P   S   T  
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

Jump to:   A   H   P   S   T