| Overview |  |
Space-efficient dictionary implemented using a binary
This module implements a space-efficient dictionary with no overhead per entry. Read and write access is O(log n).
Keys and values are fixed size binaries stored ordered in a larger binary which acts as a sparse array. All operations are implemented using a binary search.
As large binaries can be shared among processes, there can be multiple concurrent readers of an instance of this structure.
serialize/1 and deserialize/1bindict() = #bindict{key_size = key_size(), value_size = value_size(), block_size = block_size(), b = binary()}
block_size() = pos_integer()
key() = binary()
key_size() = pos_integer()
value() = binary()
value_size() = pos_integer()
| append/3 | Append a key and value. |
| bulk_insert/2 | Insert a batch of key-value pairs into the dictionary. |
| cas/4 | Check-and-set operation. |
| compact/1 | Compacts the internal binary used for storage, by creating a new copy where all the data is aligned in memory. |
| delete/2 | |
| deserialize/1 | |
| expected_size/2 | Returns how many bytes would be used by the structure if it was storing NumKeys. |
| expected_size_mb/2 | |
| find/2 | Returns the value associated with the key or 'not_found' if there is no such key. |
| find_many/2 | |
| first/1 | Returns the first key-value pair or 'not_found' if the dict is empty. |
| foldl/3 | |
| from_orddict/2 | Populates the dictionary with data from the orddict, taking advantage of the fact that it is already ordered. |
| insert/3 | Inserts the key and value into the dictionary. |
| intersection/1 | Intersect two or more bindicts by key. |
| intersection/2 | SvS set intersection algorithm, as described in http://www.cs.toronto.edu/~tl/papers/fiats.pdf. |
| last/1 | Returns the last key-value pair or 'not_found' if the dict is empty. |
| merge/2 | |
| new/2 | Returns a new empty dictionary where where the keys and values will always be of the given size. |
| new/3 | Returns a new dictionary with the given data. |
| next/2 | Returns the next larger key and value associated with it or 'not_found' if no larger key exists. |
| next_nth/3 | Returns the nth next larger key and value associated with it or 'not_found' if it does not exist. |
| num_keys/1 | Returns the number of keys in the dictionary. |
| serialize/1 | Returns a binary representation of the dictionary which can be deserialized later to recreate the same structure. |
| size/1 | |
| to_orddict/1 | |
| update/4 | Update the value stored under the key by calling F on the old value to get a new value. |
Append a key and value. This is only useful if the key is known to be larger than any other key. Otherwise it will corrupt the bindict.
bulk_insert(Bindict, Orddict) -> any()
Insert a batch of key-value pairs into the dictionary. A new binary is only created once, making it much cheaper than individual calls to insert/2. The input list must be sorted.
Check-and-set operation. If 'not_found' is specified as the old value, the key should not exist in the array. Provided for use by bisect_server.
compact(B) -> any()
Compacts the internal binary used for storage, by creating a new copy where all the data is aligned in memory. Writes will cause fragmentation.
deserialize(Bin::binary()) -> bindict()
expected_size(B, NumKeys) -> any()
Returns how many bytes would be used by the structure if it was storing NumKeys.
expected_size_mb(B, NumKeys) -> any()
Returns the value associated with the key or 'not_found' if there is no such key.
Returns the first key-value pair or 'not_found' if the dict is empty
foldl(B::bindict(), F::function(), Acc::any()) -> any()
from_orddict(Bindict, Orddict) -> any()
Populates the dictionary with data from the orddict, taking advantage of the fact that it is already ordered. The given bindict must be empty, but contain size parameters.
Inserts the key and value into the dictionary. If the size of key and value is wrong, throws badarg. If the key is already in the array, the value is updated.
intersection(Bs) -> any()
Intersect two or more bindicts by key. The resulting bindict contains keys found in all input bindicts.
intersection(Bs, X2) -> any()
SvS set intersection algorithm, as described in http://www.cs.toronto.edu/~tl/papers/fiats.pdf
Returns the last key-value pair or 'not_found' if the dict is empty
merge(Small, Big) -> any()
new(KeySize::key_size(), ValueSize::value_size()) -> bindict()
Returns a new empty dictionary where where the keys and values will always be of the given size.
new(KeySize::key_size(), ValueSize::value_size(), Data::binary()) -> bindict()
Returns a new dictionary with the given data
Returns the next larger key and value associated with it or 'not_found' if no larger key exists.
Returns the nth next larger key and value associated with it or 'not_found' if it does not exist.
num_keys(B::bindict()) -> integer()
Returns the number of keys in the dictionary
serialize(Bindict::bindict()) -> binary()
Returns a binary representation of the dictionary which can be deserialized later to recreate the same structure.
size(Bindict) -> any()
to_orddict(Bindict) -> any()
update(B, K, Initial, F) -> any()
Update the value stored under the key by calling F on the old value to get a new value. If the key is not present, initial will be stored as the first value. Same as dict:update/4. Note: find and insert requires two binary searches in the binary, while update only needs one. It's as close to in-place update we can get in pure Erlang.
Generated by EDoc