Safe Haskell | None |
---|---|

Language | Haskell2010 |

A compact bytestring trie implemented above VCache.

- data Trie a
- trie_space :: Trie a -> VSpace
- empty :: VSpace -> Trie a
- singleton :: VCacheable a => VSpace -> ByteString -> a -> Trie a
- null :: Trie a -> Bool
- size :: Trie a -> Int
- lookup :: ByteString -> Trie a -> Maybe a
- lookup' :: ByteString -> Trie a -> Maybe a
- lookupc :: CacheMode -> ByteString -> Trie a -> Maybe a
- prefixKeys :: VCacheable a => ByteString -> Trie a -> Trie a
- lookupPrefix :: VCacheable a => ByteString -> Trie a -> Trie a
- deletePrefix :: VCacheable a => ByteString -> Trie a -> Trie a
- insert :: VCacheable a => ByteString -> a -> Trie a -> Trie a
- delete :: VCacheable a => ByteString -> Trie a -> Trie a
- adjust :: VCacheable a => (Maybe a -> Maybe a) -> ByteString -> Trie a -> Trie a
- insertList :: VCacheable a => [(ByteString, a)] -> Trie a -> Trie a
- deleteList :: VCacheable a => [ByteString] -> Trie a -> Trie a
- toList :: Trie a -> [(ByteString, a)]
- toListBy :: (ByteString -> a -> b) -> Trie a -> [b]
- elems :: Trie a -> [a]
- keys :: Trie a -> [ByteString]
- foldr :: (a -> b -> b) -> b -> Trie a -> b
- foldr' :: (a -> b -> b) -> b -> Trie a -> b
- foldrM :: Monad m => (a -> b -> m b) -> b -> Trie a -> m b
- foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> b
- foldrWithKey' :: (ByteString -> a -> b -> b) -> b -> Trie a -> b
- foldrWithKeyM :: Monad m => (ByteString -> a -> b -> m b) -> b -> Trie a -> m b
- foldl :: (b -> a -> b) -> b -> Trie a -> b
- foldl' :: (b -> a -> b) -> b -> Trie a -> b
- foldlM :: Monad m => (b -> a -> m b) -> b -> Trie a -> m b
- foldlWithKey :: (b -> ByteString -> a -> b) -> b -> Trie a -> b
- foldlWithKey' :: (b -> ByteString -> a -> b) -> b -> Trie a -> b
- foldlWithKeyM :: Monad m => (b -> ByteString -> a -> m b) -> b -> Trie a -> m b
- map :: VCacheable b => (a -> b) -> Trie a -> Trie b
- mapM :: (VCacheable b, Monad m) => (a -> m b) -> Trie a -> m (Trie b)
- mapWithKey :: VCacheable b => (ByteString -> a -> b) -> Trie a -> Trie b
- mapWithKeyM :: (Monad m, VCacheable b) => (ByteString -> a -> m b) -> Trie a -> m (Trie b)
- validate :: Trie a -> Bool
- unsafeTrieAddr :: Trie a -> Word64

# Documentation

A trie data structure with bytestring keys, above VCache.

A trie supports keys of arbitrary size, though very large keys may cause performance degradation. Values are directly serialized into nodes, so very large values should use indirection.

Eq (Trie a) | |

Show (Trie a) | |

VCacheable a => VCacheable (Trie a) | |

Typeable (* -> *) Trie |

trie_space :: Trie a -> VSpace Source

singleton :: VCacheable a => VSpace -> ByteString -> a -> Trie a Source

Construct Trie with one element.

lookup :: ByteString -> Trie a -> Maybe a Source

Lookup an object by key

lookup' :: ByteString -> Trie a -> Maybe a Source

Lookup an object by key without caching nodes

lookupc :: CacheMode -> ByteString -> Trie a -> Maybe a Source

Lookup object by key with a specific cache mode.

prefixKeys :: VCacheable a => ByteString -> Trie a -> Trie a Source

O(1). Add a common prefix to all keys currently in the Trie

lookupPrefix :: VCacheable a => ByteString -> Trie a -> Trie a Source

Obtain a trie rooted at a given prefix.

This operation may need to allocate a new node.

deletePrefix :: VCacheable a => ByteString -> Trie a -> Trie a Source

Delete all keys sharing a given prefix.

insert :: VCacheable a => ByteString -> a -> Trie a -> Trie a Source

Insert a single key,value pair into the trie, replacing any existing value at that location.

delete :: VCacheable a => ByteString -> Trie a -> Trie a Source

Remove a single key from the trie.

adjust :: VCacheable a => (Maybe a -> Maybe a) -> ByteString -> Trie a -> Trie a Source

Update an element in the Trie with a given function. Capable of inserts, modifies, and deletes.

insertList :: VCacheable a => [(ByteString, a)] -> Trie a -> Trie a Source

Insert a list of (key,value) pairs into the trie. At the moment this is just a linear insert, but it may later be replaced by an efficient batch-insert model. If a key appears more than once in this list, the last entry will win.

deleteList :: VCacheable a => [ByteString] -> Trie a -> Trie a Source

Remove a collection of keys from the trie. At the moment this is just a sequential deletion, but it may later be replaced by a more efficient batch-deletion model.

toList :: Trie a -> [(ByteString, a)] Source

O(n). Obtain a list of (key,val) pairs, sorted by key.

toListBy :: (ByteString -> a -> b) -> Trie a -> [b] Source

keys :: Trie a -> [ByteString] Source

O(n). Obtain a sorted list of of keys.

foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> b Source

foldrWithKey' :: (ByteString -> a -> b -> b) -> b -> Trie a -> b Source

foldrWithKeyM :: Monad m => (ByteString -> a -> b -> m b) -> b -> Trie a -> m b Source

foldlWithKey :: (b -> ByteString -> a -> b) -> b -> Trie a -> b Source

foldlWithKey' :: (b -> ByteString -> a -> b) -> b -> Trie a -> b Source

foldlWithKeyM :: Monad m => (b -> ByteString -> a -> m b) -> b -> Trie a -> m b Source

map :: VCacheable b => (a -> b) -> Trie a -> Trie b Source

mapWithKey :: VCacheable b => (ByteString -> a -> b) -> Trie a -> Trie b Source

mapWithKeyM :: (Monad m, VCacheable b) => (ByteString -> a -> m b) -> Trie a -> m (Trie b) Source

validate :: Trie a -> Bool Source

Validate the invariant structure of the Trie. Every node must branch or contain a value.

unsafeTrieAddr :: Trie a -> Word64 Source

Obtain unique address for Trie value. As with VRef addresses, this should be stable while the Trie is reachable, but may change if the value is GC'd and later reconstructed at a new address. Exposed for memoization and similar purposes.