►The Racket Reference
▼4 Datatypes
On this page:
stencil-vector?
stencil-vector-mask-width
stencil-vector
stencil-vector-mask
stencil-vector-length
stencil-vector-ref
stencil-vector-set!
stencil-vector-update
  top  contents  ← prev  up  next → 

4.13 Stencil Vectors

A stencil vector is like a vector, but it has an associated mask fixnum where the number of bits set in the mask determines the length of the vector. A stencil vector is useful for implementing some data structures [Torosyan21], such as a hash array mapped trie (HAMT).

Conceptually, a stencil vector’s mask indicates which virtual elements of a full-sized stencil vector are present, but mask bits have no effect on access or mutation via stencil-vector-ref and stencil-vector-set!. For example, such a stencil vector has a mask 25, which could also be written #b11001; reading from low bit to high, that mask represents values present at the first, fourth, and fifth virtual slots. If that stencil vector’s elements are 'a, 'b, and 'c, then 'a is at virtual slot 0 and accessed with index 0, 'b is at virtual slot 3 and accessed with index 1, and 'c is at virtual slot 4 and accessed with index 2.

The relative order of bits in a mask is relevant for a functional-update operation with stencil-vector-update. Elements to remove are specified with a removal mask, and elements to add are ordered relative to remaining elements through an addition mask. For example, starting with the stencil vector whose mask is #b11001 with elements 'a, 'b, and 'c, adding new elements 'd and 'e using the addition mask #b100100 produces a stencil vector whose mask is #b111101 and whose elements in order are 'a, 'b, 'd, 'c, and 'e.

The maximum size of a stencil vector is 58 elements on a 64-bit platform and 26 elements on a 32-bit platform. This limited size enables a compact internal representation and ensures that update operations are relatively simple. Stencil vectors are mutable, although they are intended primarily for use without mutation to implement a persistent data structure.

Two stencil vectors are equal? if they have the same mask, and if the values in corresponding slots of the stencil vectors are equal?.

A printed vector starts with #<stencil ...>, and this printed form cannot be parsed by read. The s-exp->fasl and serialize functions do not support stencil vectors, in part because a stencil vector on a 64-bit platform might not be representable on a 32-bit platform. The intent is that stencil vectors are used as an in-memory representation for a datatype implementation.

Added in version 8.5.0.7 of package base.

procedure

(stencil-vector? v) → boolean?

  v : any/c
Returns #t if v is a stencil vector, #f otherwise.

Examples:
> (stencil-vector #b10010 'a 'b)

#<stencil 18: a b>

> (stencil-vector #b111 'a 'b 'c)

#<stencil 7: a b c>

Added in version 8.5.0.7 of package base.

procedure

(stencil-vector-mask-width) → exact-nonnegative-integer?

Returns the maximum number of elements allowed in a stencil vector on the current platform. The result is 58 on a 64-bit platform or 26 on a 32-bit platform.

procedure

(stencil-vector mask v ...) → stencil-vector?

  mask : (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
  v : any/c
Returns a stencil vector combining mask with elements v. The number of supplied vs must match the number of bits set in mask’s two’s complement representation.

Added in version 8.5.0.7 of package base.

procedure

(stencil-vector-mask vec)

 → (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
  vec : stencil-vector?
Returns the mask of vec. Note that the mask of a stencil vector is determined at creation time and cannot be changed later.

Example:
> (stencil-vector-mask (stencil-vector #b10010 'a 'b))

18

Added in version 8.5.0.7 of package base.

procedure

(stencil-vector-length vec)

 → (integer-in 0 (sub1 (stencil-vector-mask-width)))
  vec : stencil-vector?
Returns the length of vec (i.e., the number of slots in the vector). The result is the same as (fxpopcount (stencil-vector-mask vec)).

Example:
> (stencil-vector-length (stencil-vector #b10010 'a 'b))

2

Added in version 8.5.0.7 of package base.

procedure

(stencil-vector-ref vec pos) → any/c

  vec : stencil-vector?
  pos : exact-nonnegative-integer?
Returns the element in slot pos of vec. The first slot is position 0, and the last slot is one less than (stencil-vector-length vec).

Examples:
> (stencil-vector-ref (stencil-vector #b10010 'a 'b) 1)

'b

> (stencil-vector-ref (stencil-vector #b111 'a 'b 'c) 1)

'b

Added in version 8.5.0.7 of package base.

procedure

(stencil-vector-set! vec pos v) → avoid?

  vec : stencil-vector?
  pos : exact-nonnegative-integer?
  v : any/c
Updates the slot pos of vec to contain v.

Examples:
> (define st-vec (stencil-vector #b101 'a 'b))
> st-vec

#<stencil 5: a b>

> (stencil-vector-set! st-vec 1 'c)
> st-vec

#<stencil 5: a c>

Added in version 8.5.0.7 of package base.

procedure

(stencil-vector-update vec    
  remove-mask    
  add-mask    
  v ...) → stencil-vector?
  vec : stencil-vector?
  remove-mask : (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
  add-mask : (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
  v : any/c
Returns a stencil vector that is like vec, but with elements corresponding to remove-mask removed, and with the given vs added at positions relative to existing (unremoved) elements determined by add-mask.

Examples:
> (define st-vec (stencil-vector #b101 'a 'b))
> (stencil-vector-update st-vec #b0 #b10 'c)

#<stencil 7: a c b>

> (stencil-vector-update st-vec #b0 #b1000 'c)

#<stencil 13: a b c>

> st-vec ; unchanged by updates

#<stencil 5: a b>

> (stencil-vector-update st-vec #b1 #b1 'c)

#<stencil 5: c b>

> (stencil-vector-update st-vec #b100 #b100 'c)

#<stencil 5: a c>

> (stencil-vector-update st-vec #b100 #b0)

#<stencil 1: a>

Added in version 8.5.0.7 of package base.

  top  contents  ← prev  up  next →