API for clojure.core.rrb-vector - core.rrb-vector 0.1.3-SNAPSHOT (in development)

by MichaƂ Marczyk

Full namespace name: clojure.core.rrb-vector

Overview

An implementation of the confluently persistent vector data
structure introduced in Bagwell, Rompf, "RRB-Trees: Efficient
Immutable Vectors", EPFL-REPORT-169879, September, 2011.

RRB-Trees build upon Clojure's PersistentVectors, adding logarithmic
time concatenation and slicing.

The main API entry points are clojure.core.rrb-vector/catvec,
performing vector concatenation, and clojure.core.rrb-vector/subvec,
which produces a new vector containing the appropriate subrange of
the input vector (in contrast to clojure.core/subvec, which returns
a view on the input vector).

core.rrb-vector's vectors can store objects or unboxed primitives.
The implementation allows for seamless interoperability with
clojure.lang.PersistentVector, clojure.core.Vec (more commonly known
as gvec) and clojure.lang.APersistentVector$SubVector instances:
clojure.core.rrb-vector/catvec and clojure.core.rrb-vector/subvec
convert their inputs to clojure.core.rrb-vector.rrbt.Vector
instances whenever necessary (this is a very fast constant time
operation for PersistentVector and gvec; for SubVector it is O(log
n), where n is the size of the underlying vector).

clojure.core.rrb-vector also exports its own versions of vector and
vector-of and vec which always produce
clojure.core.rrb-vector.rrbt.Vector instances. Note that vector-of
accepts :object as one of the possible type arguments, in addition
to keywords naming primitive types.

Public Variables and Functions



catvec

function
Usage: (catvec)
       (catvec v1)
       (catvec v1 v2)
       (catvec v1 v2 v3)
       (catvec v1 v2 v3 v4)
       (catvec v1 v2 v3 v4 & vn)
Concatenates the given vectors in logarithmic time.

    
    
    Source
  


subvec

function
Usage: (subvec v start)
       (subvec v start end)
Returns a new vector containing the elements of the given vector v
lying between the start (inclusive) and end (exclusive) indices in
logarithmic time. end defaults to end of vector. The resulting
vector shares structure with the original, but does not hold on to
any elements of the original vector lying outside the given index
range.

    
    
    Source
  


vec

function
Usage: (vec coll)
Returns a vector containing the contents of coll.

If coll is a vector, returns an RRB vector using the internal tree
of coll.

    
    
    Source
  


vector

function
Usage: (vector)
       (vector x1)
       (vector x1 x2)
       (vector x1 x2 x3)
       (vector x1 x2 x3 x4)
       (vector x1 x2 x3 x4 & xn)
Creates a new vector containing the args.

    
    
    Source
  


vector-of

function
Usage: (vector-of t)
       (vector-of t x1)
       (vector-of t x1 x2)
       (vector-of t x1 x2 x3)
       (vector-of t x1 x2 x3 x4)
       (vector-of t x1 x2 x3 x4 & xn)
Creates a new vector capable of storing homogenous items of type t,
which should be one of :object, :int, :long, :float, :double, :byte,
:short, :char, :boolean. Primitives are stored unboxed.

Optionally takes one or more elements to populate the vector.

    
    
    Source
  

clojure.core.rrb-vector.debug





Public Variables and Functions



check-catvec

function
Usage: (check-catvec extra-checks? & counts)
Perform a sequence of calls to catvec or checking-catvec on one or
more core.rrb-vector vectors.  Return true if Clojure's built-in
concat function give the same results, otherwise false.  Intended
for use in tests of this library.

    
    
    Source
  


check-subvec

function
Usage: (check-subvec extra-checks? init & starts-and-ends)
Perform a sequence of calls to subvec an a core.rrb-vector vector,
as well as a normal Clojure vector, returning true if they give the
same results, otherwise false.  Intended for use in tests of this
library.

    
    
    Source
  


checking-catvec

function
Usage: (checking-catvec & args)
checking-catvec is similar to checking-pop, with the
differences summarized below.  See checking-pop documentation for
details.

Note that (get @d/debug-otps :catvec) is used to control tracing,
validating, and return value sanity checks for checking-catvec as a
whole.  This includes controlling those options for the function
checking-splice-rrbts, which is used to concatenate pairs of vectors
when you call checking-catvec with 3 or more vectors.  This takes a
bit longer to do the checking on every concatenation, but catches
problems closer to the time they are introduced.

    opts map: (get @d/debug-opts :catvec)
    function called if (:validating opts) is logical true:
        validating-catvec

    
    
    Source
  


checking-catvec-impl

function
Usage: (checking-catvec-impl)
       (checking-catvec-impl v1)
       (checking-catvec-impl v1 v2)
       (checking-catvec-impl v1 v2 v3)
       (checking-catvec-impl v1 v2 v3 v4)
       (checking-catvec-impl v1 v2 v3 v4 & vn)
checking-catvec-impl is identical to catvec, except that it calls
checking-splicev instead of splicev, for configurable additional
checking on each call to checking-splicev.

    
    
    Source
  


checking-pop

function
Usage: (checking-pop coll)
These two namespace aliases will be used later in this
documentation:

    (require '[clojure.core.rrb-vector.debug :as d])
    (require '[clojure.core.rrb-vector.debug-platform-dependent :as pd])

checking-pop passes its argument to clojure.core/pop, and if it
returns, it returns whatever clojure.core/pop does.  If checking-pop
detects any problems, it will record information about the problems
found in one or both of the global atoms 'd/failure-data' and
'd/warning-data', and optionally throw an exception.

If coll is not a vector type according to pd/is-vector?, then
checking-pop simply behaves exactly like clojure.core/pop, with no
additional checks performed.  All of checking-pop's extra checks are
specific to vectors.

If coll is a vector, then checking-pop looks up the key :pop in a
global atom 'd/debug-opts'.  The result of that lookup is a map we
will call 'opts' below.

    opts map: (get @d/debug-opts :pop)
    function called if (:validating opts) is logical true:
        validating-pop

If (:trace opts) is true, then a debug trace message is printed to
*out*.

If (:validate opts) is true, then validating-pop is called, using
clojure.core/pop to do the real work, but validating-pop will check
whether the return value looks correct relative to the input
parameter value, i.e. it is equal to a sequence of values containing
all but the last element of the input coll's sequence of values.
See validating-pop documentation for additional details.  This step
records details of problems found in the atoms d/failure-data.

(:return-value-checks opts) should be a sequence of functions that
each take the vector returned from calling clojure.core/pop, and
return data about any errors or warnings they find in the internals
of the vector data structure.  Errors or warnings are appended to
atoms d/failure-data and/or d/warning-data.

If either the validate or return value checks steps find an error,
they throw an exception if (:continue-on-error opts) is logical
false.

If the return value checks step finds no error, but does find a
warning, it throws an exception if (:continue-on-warning opts) is
logical false.

    
    
    Source
  


checking-pop!

function
Usage: (checking-pop! coll)
checking-pop! is similar to checking-pop, with the differences
summarized below.  See checking-pop documentation for details.

    opts map: (get @d/debug-opts :pop!)
    function called if (:validating opts) is logical true:
        validating-pop!

    
    
    Source
  


checking-slicev

function
Usage: (checking-slicev & args)
checking-slicev is similar to checking-pop, with the differences
summarized below.  See checking-pop documentation for details.

Unlike checking-pop, it seems unlikely that a user of
core.rrb-vector would want to call this function directly.  See
checking-subvec.  checking-slicev is part of the implementation of
checking-subvec.

    opts map: (get @d/debug-opts :subvec)  ;; _not_ :slicev
    function called if (:validating opts) is logical true:
        validating-slicev

    
    
    Source
  


checking-splice-rrbts

function
Usage: (checking-splice-rrbts & args)
checking-splice-rrbts is similar to checking-pop, with the
differences summarized below.  See checking-pop documentation for
details.

Unlike checking-pop, it seems unlikely that a user of
core.rrb-vector would want to call this function directly.  See
checking-catvec.  checking-splice-rrbts is part of the
implementation of checking-catvec.

    opts map: (get @d/debug-opts :catvec)  ;; _not_ :splice-rrbts
    function called if (:validating opts) is logical true:
        validating-splice-rrbts

    
    
    Source
  


checking-splice-rrbts-main

function
Usage: (checking-splice-rrbts-main & args)
checking-splice-rrbts-main is similar to checking-pop, with the
differences summarized below.  See checking-pop documentation for
details.

Unlike checking-pop, it seems unlikely that a user of
core.rrb-vector would want to call this function directly.  See
checking-catvec.  checking-splice-rrbts-main is part of the
implementation of checking-catvec.

    opts map: (get @d/debug-opts :catvec)  ;; _not_ :splice-rrbts-main
    function called if (:validating opts) is logical true:
        validating-splice-rrbts-main

    
    
    Source
  


checking-splicev

function
Usage: (checking-splicev v1 v2)
checking-splicev is identical to splicev, except that it calls
checking-splice-rrbts instead of splice-rrbts, for configurable
additional checking on each call to checking-splice-rrbts.

It is more likely that a core.rrb-vector library user will want to
call checking-catvec rather than this one.  checking-splicev is part
of the implementation of checking-catvec.

    
    
    Source
  


checking-subvec

function
Usage: (checking-subvec v start)
       (checking-subvec v start end)
checking-subvec is similar to checking-pop, with the differences
summarized below.  See checking-pop documentation for details.

    opts map: (get @d/debug-opts :subvec)
    function called if (:validating opts) is logical true:
        validating-slicev

    
    
    Source
  


checking-transient

function
Usage: (checking-transient coll)
checking-transient is similar to checking-pop, with the differences
summarized below.  See checking-pop documentation for details.

    opts map: (get @d/debug-opts :transient)
    function called if (:validating opts) is logical true:
        validating-transient

    
    
    Source
  


filter-indexes

function
Usage: (filter-indexes pred coll)
Return a sequence of all indexes of elements e of coll for
which (pred e) returns logical true.  0 is the index of the first
element.

    
    
    Source
  


first-diff

function
Usage: (first-diff xs ys)
Compare two sequences to see if they have = elements in the same
order, and both sequences have the same number of elements.  If all
of those conditions are true, and no exceptions occur while calling
seq, first, and next on the seqs of xs and ys, then return -1.

If two elements at the same index in each sequence are found not =
to each other, or the sequences differ in their number of elements,
return the index, 0 or larger, at which the first difference occurs.

If an exception occurs while calling seq, first, or next, throw an
exception that contains the index at which this exception occurred.

    
    
    Source
  


generative-check-catvec

function
Usage: (generative-check-catvec extra-checks? iterations max-vcnt min-cnt max-cnt)
Perform many calls to check-catvec with randomly generated inputs.
Intended for use in tests of this library.  Returns true if all
tests pass, otherwise throws an exception containing data about the
inputs that caused the failing test.

    
    
    Source
  


generative-check-subvec

function
Usage: (generative-check-subvec extra-checks? iterations max-init-cnt slices)
Perform many calls to check-subvec with randomly generated inputs.
Intended for use in tests of this library.  Returns true if all
tests pass, otherwise throws an exception containing data about the
inputs that caused the failing test.

    
    
    Source
  


objects-in-slot-32-of-obj-arrays

function
Usage: (objects-in-slot-32-of-obj-arrays v)
Function to look for errors of the form where a node's node.array
object, which is often an array of 32 or 33 java.lang.Object's, has
an element at index 32 that is not nil, and refers to an object that
is of any type _except_ an array of ints.  There appears to be some
situation in which this can occur, but it seems to almost certainly
be a bug if that happens, and we should be able to detect it
whenever it occurs.

    
    
    Source
  


sanity-check-vector-internals

function
Usage: (sanity-check-vector-internals err-desc-str ret args opts)
This function is called by all of the checking-* variants of
functions in the debug namespace.  It calls all of the functions
in (:return-value-checks opts) in the order given, passing each of
those functions a return value 'ret'.  Each function performs sanity
checks on the 'ret' data structure used to represent the vector.

Those functions should return a map with key :error having a logical
true value if any errors were found, or a key :warning having a
logical true value if any warnings were found, otherwise both of
those values must be logical false in the returned map (or no such
key is present in the returned map at all).

Three examples of such functions are included in core.rrb-vector's
debug namespace.

* edit-nodes-errors
* basic-node-errors
* ranges-errors

They each look for different problems in the vector data structure
internals.  They were developed as separate functions in case there
was ever a significant performance advantage to configuring only
some of them to be called, not all of them, for long tests.

If any errors are found, this function calls record-failure-data, to
record the details in a global atom.  It prints a message to *out*,
and if (:continue-on-error opts) is logical false, it throws a data
conveying exception using ex-info containing the same message, and
the same error details map passed to record-failure-data.

If no exception is thrown due to an error, then repeat the same
checks for a warning message, recording details via calling
record-warning-data, and throwing an exception
if (:continue-on-warning opts) is logical false.

    
    
    Source
  


set-debug-opts!

function
Usage: (set-debug-opts! opts)
set-debug-opts! modified the debug-opts atom of the core.rrb-vector
library, which configures what kinds of extra checks are performed
when calling the checking-* versions of functions defined in the
library's debug namespace.

Example call:

  (require '[clojure.core.rrb-vector.debug :as d])
  (d/set-debug-opts! d/full-debug-opts)

This call enables as thorough of extra verification checks as is
supported by existing code, when you call any of the checking-*
variants of the functions in this namespace, e.g. checking-catvec,
checking-subvec.

It will also slow down your code to do so.  checking-* functions
return the same values as their non checking-* original functions
they are based upon, so you can write application code that mixes
calls to both, calling the checking-* versions only occasionally, if
you have a long sequence of operations that you want to look for
bugs within core.rrb-vector's implementation of.

    
    
    Source
  


validating-catvec

function
Usage: (validating-catvec err-desc-str & vs)
validating-catvec behaves similarly to validating-pop, but note
that it does not allow you to pass in a function f on which to
concatenate its arguments.  It hardcodes d/checking-catvec-impl for
that purpose.  See validating-pop for more details.

    opts map: (get @d/debug-opts :catvec)

If no exception is thrown, the return value is (apply
checking-catvec-impl vs).

    
    
    Source
  


validating-pop

function
Usage: (validating-pop f err-desc-str coll)
validating-pop is not really designed to be called from user
programs.  checking-pop can do everything that validating-pop can,
and more.  See its documentation.

A typical way of calling validating-pop is:

    (require '[clojure.core.rrb-vector.debug :as d])
    (d/validating-pop clojure.core/pop "pop" coll)

Most of the validating-* functions behave similarly.  This one
contains the most complete documentation, and the others refer to
this one.  They all differ in the function that they are intended to
validate, and a few other details, which will be collected in one
place here for function validating-pop so one can quickly see the
differences between validating-pop and the other validating-*
functions.

    good example f: clojure.core/pop
    opts map: (get @d/debug-opts :pop)

The first argument can be any function f.  f is expected to take
arguments and return a value equal to what clojure.core/pop would,
given the argument coll.

validating-pop will first make a copy of the seq of items in coll,
as a safety precaution, because some kinds of incorrect
implementations of pop could mutate their input argument.  That
would be a bug, of course, but aiding a developer in detecting bugs
is the reason validating-pop exists.  It uses the function
copying-seq to do this, which takes at least linear time in the size
of coll.

It will then calculate a sequence that is = to the expected return
value, e.g. for pop, all items in coll except the last one.

Then validating-pop will call (f coll), then call copying-seq on the
return value.

If the expected and returned sequences are not =, then a map
containing details about the arguments and actual return value is
created and passed to d/record-failure-data, which appends the map
to the end of a vector that is the value of an atom named
d/failure-data.  An exception is thrown if (:continue-on-error opts)
is logical false, with ex-data equal to this same map of error data.

If the expected and actual sequences are the same, no state is
modified and no exception is thrown.

If validating-pop does not throw an exception, the return value is
(f coll).

    
    
    Source
  


validating-pop!

function
Usage: (validating-pop! f err-desc-str coll)
validating-pop! behaves the same as validating-pop, with the
differences described here.  See validating-pop for details.

    good example f: clojure.core/pop!
    opts map: (get @d/debug-opts :pop!)

If no exception is thrown, the return value is (f coll).

    
    
    Source
  


validating-slicev

function
Usage: (validating-slicev err-desc-str coll start)
       (validating-slicev err-desc-str coll start end)
validating-slicev behaves similarly to validating-pop, but note
that it does not allow you to pass in a function f to call.  It
hardcodes slicev for that purpose.  See validating-pop for more
details.

    opts map: (get @d/debug-opts :subvec)  ;; _not_ :slicev

    
    
    Source
  


validating-splice-rrbts-main

function
Usage: (validating-splice-rrbts-main err-desc-str nm am v1 v2)
validating-splice-rrbts-main behaves the same as validating-pop, with
the differences described here.  See validating-pop for details.

    good example f: clojure.core.rrb-vector.rrbt/splice-rrbts-main
    opts map: (get @d/debug-opts :catvec)  ;; _not_ :splice-rrbts-main

Given that splice-rrbts-main is an internal implementation detail of
the core.rrb-vector library, it is expected that it is more likely
you would call validating-catvec instead of this function.

If no exception is thrown, the return value is (f v1 v2).

    
    
    Source
  


validating-transient

function
Usage: (validating-transient f err-desc-str coll)
validating-transient behaves the same as validating-pop, with the
differences described here.  See validating-pop for details.

    good example f: clojure.core/transient
    opts map: (get @d/debug-opts :transient)

If no exception is thrown, the return value is (f coll).

    
    
    Source
  

clojure.core.rrb-vector.rrbt





Types



Transient

type

    Fields: [nm am objects? cnt shift root tail tidx]
Protocols: clojure.core.rrb-vector.protocols/PTransientDebugAccess
Interfaces: clojure.core.rrb_vector.rrbt.IVecImpl, clojure.lang.Counted, clojure.lang.IFn, clojure.lang.ILookup, clojure.lang.ITransientAssociative, clojure.lang.ITransientCollection, clojure.lang.ITransientVector, clojure.lang.Indexed


VecSeq

type

    Fields: [am vec anode i offset _meta _hash _hasheq]
Protocols: clojure.core.protocols/InternalReduce
Interfaces: clojure.lang.Counted, clojure.lang.IChunkedSeq, clojure.lang.IHashEq, clojure.lang.IMeta, clojure.lang.IObj, clojure.lang.ISeq, clojure.lang.Seqable, java.io.Serializable, java.lang.Iterable, java.util.Collection, java.util.List


Vector

type

    Fields: [nm am cnt shift root tail _meta _hash _hasheq]
Protocols: clojure.core.protocols/IKVReduce, clojure.core.reducers/CollFold, clojure.core.rrb-vector.protocols/PSliceableVector, clojure.core.rrb-vector.protocols/PSpliceableVector, AsRRBT
Interfaces: clojure.core.rrb_vector.rrbt.IVecImpl, clojure.lang.Associative, clojure.lang.Counted, clojure.lang.IEditableCollection, clojure.lang.IFn, clojure.lang.IHashEq, clojure.lang.ILookup, clojure.lang.IMeta, clojure.lang.IObj, clojure.lang.IPersistentCollection, clojure.lang.IPersistentStack, clojure.lang.IPersistentVector, clojure.lang.Indexed, clojure.lang.Reversible, clojure.lang.Seqable, clojure.lang.Sequential, java.io.Serializable, java.lang.Comparable, java.lang.Iterable, java.util.Collection, java.util.List, java.util.RandomAccess

Public Variables and Functions



->Transient

function
Usage: (->Transient nm am objects? cnt shift root tail tidx)
Positional factory function for class clojure.core.rrb_vector.rrbt.Transient.

    
    
    Source
  


->VecSeq

function
Usage: (->VecSeq am vec anode i offset _meta _hash _hasheq)
Positional factory function for class clojure.core.rrb_vector.rrbt.VecSeq.

    
    
    Source
  


->Vector

function
Usage: (->Vector nm am cnt shift root tail _meta _hash _hasheq)
Positional factory function for class clojure.core.rrb_vector.rrbt.Vector.

    
    
    Source
  
Logo & site design by Tom Hickey.
Clojure auto-documentation system by Tom Faulhaber.