roaring-wasm

WebAssembly port of Roaring Bitmaps for NodeJS. It is interoperable with other implementations via the Roaring format.

Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster.

motivation

This project was born to use Roaring WASM in AWS Lambdas without the need to compile a node-gyp module. AWS Lambda supports node 8.10 and supports WASM.

installation

npm install --save roaring-wasm

Try it live - https://npm.runkit.com/roaring-wasm

Code sample:

// npm install --save roaring-wasm
// create this file as demo.js
// type node demo.js or nodejs demo.js depending on your system

var roaring = require("roaring-wasm");

var bitmap1 = new roaring.RoaringBitmap32()
bitmap1.addMany([1, 2, 3, 4, 5, 100, 1000])
console.log("bitmap1.toSet():",bitmap1.toSet())

var bitmap2 = new roaring.RoaringBitmap32()
bitmap2.addMany([3, 4, 1000])
console.log("bitmap2.toSet():",bitmap1.toSet())

var bitmap3 = new roaring.RoaringBitmap32()
console.log("bitmap1.cardinality():", bitmap1.cardinality())
console.log("bitmap2.contains(3):",bitmap2.contains(3))

bitmap3.add(111)
bitmap3.add(544)
bitmap3.orInPlace(bitmap1)
bitmap1.optimize()
console.log(bitmap3.toString())

console.log("bitmap3.toArray():",bitmap3.toArray())
console.log("bitmap3.maximum():",bitmap3.maximum())
console.log("bitmap3.rank(100):",bitmap3.rank(100))

bitmap1.dispose()
bitmap2.dispose()
bitmap3.dispose()

references

This package - https://www.npmjs.com/package/roaring-wasm

Source code and build tools for this package - https://github.com/SalvatorePreviti/roaring-wasm

Roaring Bitmaps - http://roaringbitmap.org/

Portable Roaring bitmaps in C - https://github.com/RoaringBitmap/CRoaring

emscripten - https://github.com/kripken/emscripten/wiki

AWS Lambda - https://docs.aws.amazon.com/lambda/latest/dg/nodejs-prog-model-handler.html

licenses

• This package is provided as open source software using Apache License.

• CRoaring is provided as open source software using Apache License.

API

Table of Contents

• RoaringBitmap32
  • xorCardinality
    • Parameters
  • deserialize
    • Parameters
  • deserialize
    • Parameters
  • serializeArrayToNewBuffer
    • Parameters
  • deserializeToArray
    • Parameters
  • deserializeToSet
    • Parameters
  • isDisposed
  • dispose
  • throwIfDisposed
  • cardinality
  • isEmpty
  • add
    • Parameters
  • addChecked
    • Parameters
  • addMany
    • Parameters
  • remove
    • Parameters
  • removeChecked
    • Parameters
  • maximum
  • minimum
  • contains
    • Parameters
  • isSubset
    • Parameters
  • isStrictSubset
    • Parameters
  • toRoaringUint32Array
  • toArray
  • toSet
  • toUint32Array
  • equals
    • Parameters
  • flipRange
    • Parameters
  • optimize
  • select
    • Parameters
  • andCardinality
    • Parameters
  • orCardinality
    • Parameters
  • andNotCardinality
    • Parameters
  • andInPlace
    • Parameters
  • orInPlace
    • Parameters
  • xorInPlace
    • Parameters
  • andNotInPlace
    • Parameters
  • rank
    • Parameters
  • intersects
    • Parameters
  • jaccardIndex
    • Parameters
  • getSerializationSizeInBytes
    • Parameters
  • serializeToRoaringUint8Array
    • Parameters
  • serializeToUint8Array
    • Parameters
  • serializeToNodeBuffer
    • Parameters
• RoaringUint32Array
  • TypedArray
  • TypedArray
  • BYTES_PER_ELEMENT
  • BYTES_PER_ELEMENT
  • buffer
  • isDisposed
  • byteLength
  • heap
  • dispose
  • throwIfDisposed
  • set
    • Parameters
  • asTypedArray
  • asNodeBuffer
  • toTypedArray
  • toNodeBuffer
  • toArray
  • toSet
  • toString
  • iterator
• RoaringUint8Array
  • TypedArray
  • TypedArray
  • BYTES_PER_ELEMENT
  • BYTES_PER_ELEMENT
  • buffer
  • isDisposed
  • byteLength
  • heap
  • dispose
  • throwIfDisposed
  • set
    • Parameters
  • asTypedArray
  • asNodeBuffer
  • toTypedArray
  • toNodeBuffer
  • toArray
  • toString
  • iterator

RoaringBitmap32

A Roaring Bitmap that supports 32 bit unsigned integers.

The roaring bitmap allocates in WASM memory, remember to dispose the RoaringBitmap32 when not needed anymore to release WASM memory.

xorCardinality

Computes the size of the symmetric difference (xor) between two bitmaps. Both bitmaps are unchanged.

Parameters

• other RoaringBitmap32

Returns number Cardinality of the symmetric difference (xor) of two bitmaps.

deserialize

Creates a new roaring bitmap deserializing it from a buffer

The roaring bitmap allocates in WASM memory, remember to dispose the RoaringBitmap32 when not needed anymore to release WASM memory.

Parameters

• buffer (RoaringUint8Array | Uint8Array | Iterable<number>) The buffer to deserialize
• portable boolean If true, deserialization is compatible with the Java and Go versions of the library. If false, deserialization is compatible with the C version of the library. Default is false. (optional, default false)
• frozen (optional, default false)

Returns RoaringBitmap32 The reulting bitmap. Remember to dispose the instance when finished using it.

deserialize

Reads a bitmap from a serialized version. Throws an error if deserialization failed.

Parameters

• buffer (RoaringUint8Array | Uint8Array | Iterable<number>)
• portable boolean If true, deserialization is compatible with the Java and Go versions of the library. If false, deserialization is compatible with the C version of the library. Default is false. (optional, default false)
• frozen (optional, default false)

Returns void

serializeArrayToNewBuffer

Utility function that serializes an array of uint32 to a new NodeJS buffer. The returned buffer is automatically garbage collected.

Parameters

• values (RoaringUint32Array | Iterable<number>)
• portable boolean If true, serialization is compatible with the Java and Go versions of the library. If false, serialization is compatible with the C version of the library. Default is false. (optional, default false)

Returns Buffer The NodeJS buffer containing the serialized data.

deserializeToArray

Utility function that deserializes a RoaringBitmap32 serialized in a buffer to an Array of values. The array can be very big, be careful when you use this function.

Parameters

• buffer (RoaringUint8Array | Uint8Array | Iterable<number>) The buffer to deserialize.
• portable boolean If true, deserialization is compatible with the Java and Go versions of the library. If false, deserialization is compatible with the C version of the library. Default is false. (optional, default false)

Returns Array<number> All the values in the bitmap.

deserializeToSet

Utility function that deserializes a RoaringBitmap32 serialized in a buffer to a Set of values. The array can be very big, be careful when you use this function.

Parameters

• buffer (RoaringUint8Array | Uint8Array | Iterable<number>) The buffer to deserialize.
• portable boolean If true, deserialization is compatible with the Java and Go versions of the library. If false, deserialization is compatible with the C version of the library. Default is false. (optional, default false)

Returns Array<number> All the values in the bitmap.

isDisposed

Returns true if this instance was disposed.

Type: boolean

dispose

Disposes this object freeing all WASM memory associated to it. Is safe to call this method more than once.

Returns boolean True if disposed during this call, false if not.

throwIfDisposed

Throws an exception if this object was disposed before.

Returns (void | never)

cardinality

Get the cardinality of the bitmap (number of elements).

Returns number Number of elements in this bitmap.

isEmpty

Returns true if the bitmap has no elements.

Returns boolean True if the bitmap is empty.

add

Adds a 32 bit unsigned integer value. Values are unique, this function does nothing if the value already exists.

Parameters

• value number 32 bit unsigned integer to add in the set.

addChecked

Adds a 32 bit unsigned integer value checking if the bitmap changes. Use add() if you don't need to know if something changed. Values are unique, this function does nothing and returns false if the value already exists.

Parameters

• value number 32 bit unsigned integer to add in the set.

Returns boolean True if the bitmap changed, false if not.

addMany

Adds multiple values. Using this is faster than calling add() multiple times. Inserting ordered or partially ordered arrays is faster.

Parameters

• values (RoaringUint32Array | Iterable<number>) The values to add.

remove

Removes a value from the set. If the value does not exists, this function does nothing.

Parameters

• value number The value to remove.

removeChecked

Removes a value from the set checking if the bitmap changes. Use remove() if you don't need to know if something changed. If the value does not exists, this function does nothing and returns false.

Parameters

• value number 32 bit unsigned integer to remove from the set.

Returns boolean True if the bitmap changed, false if not.

maximum

Gets the maximum value stored in the bitmap. If the bitmap is empty, returns 0.

Returns number The maximum 32 bit unsigned integer or 0 if empty.

minimum

Gets the minimum value stored in the bitmap. If the bitmap is empty, returns 0xFFFFFFFF

Returns number The minimum 32 bit unsigned integer or 0xFFFFFFFF if empty.

contains

Checks whether the given value is contained in the set.

Parameters

• value number The value to look for.

Returns boolean True if value exists in the set, false if not.

isSubset

Returns true if the bitmap is subset of the other.

Parameters

• other RoaringBitmap32 the other bitmap

Returns boolean

isStrictSubset

Returns true if this bitmap is strict subset of the other.

Parameters

• other RoaringBitmap32 The other bitmap

Returns boolean True if this bitmap is a strict subset of other

toRoaringUint32Array

Converts the bitmap to an array. The array may be very big, use this function with caution. The returned RoaringUint32Array is allocated in WASM memory and not garbage collected, it need to be freed manually calling dispose().

Returns RoaringUint32Array The RoaringUint32Array. Remember to manually dispose to free the memory.

toArray

Converts the bitmap to a JS array. The resulting array may be very big, use this function with caution.

Returns Array<number> The array containing all values in the bitmap.

toSet

Converts the bitmap to a JS Set. The resulting set may be very big, use this function with caution.

Returns Set<number> The set containing all values in the bitmap.

toUint32Array

Converts the bitmap to a JS Uint32Array. The resulting array may be very big, use this function with caution.

Returns Uint32Array The array containing all values in the bitmap.

equals

Checks wether two roaring bitmap contains the same data.

Parameters

• other RoaringBitmap32

Returns boolean True if the bitmaps contains the same data, false if not.

flipRange

Negates in place the bitmap within a specified interval. Areas outside the range are passed through unchanged.

Parameters

• start number Range start.
• end number Range end.

optimize

Optimizes the bitmap releasing unused memory and compressing containers. Returns true if something changed.

Returns boolean True if something changed.

select

If the size of the roaring bitmap is strictly greater than rank, then this function returns the element of given rank. Otherwise, it returns NaN.

Parameters

• rank number Element rank

Returns number element or NaN

andCardinality

Computes the size of the intersection between two bitmaps. Both bitmaps are unchanged.

Parameters

• other RoaringBitmap32

Returns number Cardinality of the intersection between two bitmaps.

orCardinality

Computes the size of the union of two bitmaps. Both bitmaps are unchanged.

Parameters

• other RoaringBitmap32

Returns number Cardinality of the union of two bitmaps.

andNotCardinality

Computes the size of the difference (andnot) of two bitmaps. Both bitmaps are unchanged.

Parameters

• other RoaringBitmap32

Returns number Cardinality of the difference (andnot) of two bitmaps.

andInPlace

Intersects this bitmap with another. Removes the elements from this bitmap that don't exists in the other. Stores the result in this bitmap. The provided bitmap is not modified.

Parameters

• other RoaringBitmap32

orInPlace

Adds the element of the other bitmap into this bitmap. Stores the result in this bitmap. The provided bitmap is not modified.

Parameters

• other RoaringBitmap32

xorInPlace

Computes the difference between two bitmaps. Stores the result in this bitmap. The provided bitmap is not modified.

Parameters

• other RoaringBitmap32

andNotInPlace

Compute the difference between this and the provided bitmap, writing the result in the current bitmap. The provided bitmap is not modified.

Parameters

• other RoaringBitmap32

rank

Returns the number of integers that are smaller or equal to the given value.

Parameters

• value number The value to rank

Returns number The number of values smaller than the given value

intersects

Check whether the two bitmaps intersect (have at least one element in common).

Parameters

• other RoaringBitmap32 The other bitmap.

Returns boolean True if the two bitmaps intersects, false if not.

jaccardIndex

Computes the Jaccard index between two bitmaps. (Also known as the Tanimoto distance, or the Jaccard similarity coefficient) See https://en.wikipedia.org/wiki/Jaccard_index

The Jaccard index is undefined if both bitmaps are empty.

Parameters

• other

Returns number The Jaccard index

getSerializationSizeInBytes

How many bytes are required to serialize this bitmap.

Parameters

• portable boolean If true, deserialization is compatible with the Java and Go versions of the library. If false, deserialization is compatible with the C version of the library. Default is false. (optional, default false)

serializeToRoaringUint8Array

Serializes a bitmap to a byte buffer allocated in WASM memory.

The returned RoaringUint8Array is allocated in WASM memory and not garbage collected, it need to be freed manually calling dispose().

Parameters

• portable boolean If true, serialization is compatible with the Java and Go versions of the library. If false, serialization is compatible with the C version of the library. Default is false. (optional, default false)

Returns RoaringUint8Array The RoaringUint8Array. Remember to manually dispose to free the memory.

serializeToUint8Array

Serializes a bitmap to a typed Uint8Array. The returned array is automatically garbage collected and there is no need to be disposed manually.

Parameters

• portable boolean If true, serialization is compatible with the Java and Go versions of the library. If false, serialization is compatible with the C version of the library. Default is false. (optional, default false)

Returns Uint8Array The Uint8Array that contains the serialized bitmap

serializeToNodeBuffer

Serializes a bitmap to a NodeJS buffer. The returned buffer is automatically garbage collected and there is no need to be disposed manually.

Parameters

• portable boolean If true, serialization is compatible with the Java and Go versions of the library. If false, serialization is compatible with the C version of the library. Default is false. (optional, default false)

Returns Buffer The NodeJS Buffer that contains the serialized bitmap

RoaringUint32Array

Array of unsigned 32 bit integers allocted directly in roaring library WASM memory. Note: Memory is not garbage collected, you are responsible to free the allocated memory calling "dispose" method.

TypedArray

The type of typed array used by this class. For RoaringUint32Array is Uint32Array.

TypedArray

The type of typed array used by this class. For RoaringUint32Array is Uint32Array.

BYTES_PER_ELEMENT

The size in bytes of each element in the array. For RoaringUint32Array is always 4

Type: number

BYTES_PER_ELEMENT

The size in bytes of each element in the array. For RoaringUint32Array is always 4

Type: number

buffer

The ArrayBuffer instance referenced by the array. Note that the buffer may become invalid if the WASM allocated memory grows. When the WASM grows the preallocated memory this property will return the new allocated buffer. Use the returned buffer for short periods of time.

Type: ArrayBuffer

isDisposed

Returns true if this object was deallocated.

Type: boolean

byteLength

The length in bytes of the array. For RoaringUint32Array it is equal to this.length * 4

Type: number

heap

The full WASM heap in hich this array is allocated. Note that the buffer may become invalid if the WASM allocated memory grows. When the WASM grows the preallocated memory this property will return the new allocated buffer. Use the returned array for short periods of time.

Type: TypedArray

dispose

Frees the allocated memory. Is safe to call this method more than once.

Returns boolean True if memory gets freed during this call, false if not.

throwIfDisposed

Throws an error if the memory was freed.

Returns (void | never)

set

Writes the given array at the specified position

Parameters

• array A typed or untyped array of values to set.
• offset The index in the current array at which the values are to be written.

asTypedArray

Gets a new JS typed array instance that shares the memory used by this buffer. Note that the buffer may point to an outdated WASM memory if the WASM allocated memory grows while using the returned buffer. Use the returned array for short periods of time.

Returns Uint32Array A new typed array that shares the memory with this array.

asNodeBuffer

Gets a new NodeJS Buffer instance that shares the memory used by this buffer. Note that the buffer may point to an outdated WASM memory if the WASM allocated memory grows while using the returned buffer. Use the returned array for short periods of time.

Returns Buffer A new instance of NodeJS Buffer

toTypedArray

Copies the content of this buffer to a typed array. The returned array is garbage collected and don't need to be disposed manually.

Returns TypedArray A new typed array that contains a copy of this buffer

toNodeBuffer

Copies the content of this buffer to a NodeJS Buffer. The returned buffer is garbage collected and don't need to be disposed manually.

Returns Buffer A new instance of NodeJS Buffer that contains a copy of this buffer

toArray

Copies the content of this typed array into a new JS array of numbers and returns it.

Returns Array<number> A new array.

toSet

Copies the content of this typed array into a new JS Set and returns it.

Returns Array<number> A new array.

toString

Returns a string representation of an array.

iterator

Iterator that iterates through all values in the array.

Returns IterableIterator<number>

RoaringUint8Array

Array of bytes allocted directly in roaring library WASM memory. Note: Memory is not garbage collected, you are responsible to free the allocated memory calling "dispose" method.

TypedArray

The type of typed array used by this class. For RoaringUint8Array is Uint8Array.

TypedArray

The type of typed array used by this class. For RoaringUint8Array is Uint8Array.

BYTES_PER_ELEMENT

The size in bytes of each element in the array. For RoaringUint8Array is always 1

Type: number

BYTES_PER_ELEMENT

The size in bytes of each element in the array. For RoaringUint8Array is always 1

Type: number

buffer

The ArrayBuffer instance referenced by the array. Note that the buffer may become invalid if the WASM allocated memory grows. When the WASM grows the preallocated memory this property will return the new allocated buffer. Use the returned buffer for short periods of time.

Type: ArrayBuffer

isDisposed

Returns true if this object was deallocated.

Type: boolean

byteLength

The length in bytes of the array. For RoaringUint8Array it is equal to this.length

Type: number

heap

The full WASM heap in hich this array is allocated. Note that the buffer may become invalid if the WASM allocated memory grows. When the WASM grows the preallocated memory this property will return the new allocated buffer. Use the returned array for short periods of time.

Type: TypedArray

dispose

Frees the allocated memory. Is safe to call this method more than once.

Returns boolean True if memory gets freed during this call, false if not.

throwIfDisposed

Throws an error if the memory was freed.

Returns (void | never)

set

Writes the given array at the specified position

Parameters

• array A typed or untyped array of values to set.
• offset The index in the current array at which the values are to be written.

asTypedArray

Gets a new JS typed array instance that shares the memory used by this buffer. Note that the buffer may point to an outdated WASM memory if the WASM allocated memory grows while using the returned buffer. Use the returned array for short periods of time.

Returns Uint8Array A new typed array that shares the memory with this array.

asNodeBuffer

Gets a new NodeJS Buffer instance that shares the memory used by this buffer. Note that the buffer may point to an outdated WASM memory if the WASM allocated memory grows while using the returned buffer. Use the returned array for short periods of time.

Returns Buffer A new instance of NodeJS Buffer

toTypedArray

Copies the content of this buffer to a typed array. The returned array is garbage collected and don't need to be disposed manually.

Returns TypedArray A new typed array that contains a copy of this buffer

toNodeBuffer

Copies the content of this buffer to a NodeJS Buffer. The returned buffer is garbage collected and don't need to be disposed manually.

Returns Buffer A new instance of NodeJS Buffer that contains a copy of this buffer

toArray

Copies the content of this typed array into a standard JS array of numbers and returns it.

Returns Array<number> A new array.

toString

Returns a string representation of an array.

iterator

Iterator that iterates through all values in the array.

Returns IterableIterator<number>