ref: d0ffb958c7247028223c7e53253249d52a47a324
dir: /doc/api/libstd/datastruct.txt/
{
title: Data Structures
description: libstd: Data Structures
}
Data Structures
----------------
pkg std =
type htab(@k, @v) = struct
;;
type bitset = struct
;;
/* hash tables */
generic mkht : (h : (k : @k -> uint32), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)
generic htfree : (ht : htab(@k, @v)# -> void)
generic htput : (ht : htab(@k, @v)#, k : @k, v : @v -> void)
generic htdel : (ht : htab(@k, @v)#, k : @k -> void)
generic htget : (ht : htab(@k, @v)#, k : @k -> option(@v))
generic htgetv : (ht : htab(@k, @v)#, k : @k, fallback : @v-> @v)
generic hthas : (ht : htab(@k, @v)#, k : @k -> bool)
generic htkeys : (ht : htab(@k, @v)# -> @k[:])
/* bit sets */
const mkbs : (-> bitset#)
const bsdup : (bs : bitset# -> bitset#)
const bsfree : (bs : bitset# -> void)
const bsmax : (a : bitset# -> size)
generic bsput : (bs : bitset#, v : @a::(integral,numeric) -> bool)
generic bsdel : (bs : bitset#, v : @a::(integral,numeric) -> bool)
generic bshas : (bs : bitset#, v : @a::(integral,numeric) -> bool)
const bsdiff : (a : bitset#, b : bitset# -> void)
const bsintersect : (a : bitset#, b : bitset# -> void)
const bsunion : (a : bitset#, b : bitset# -> void)
const bseq : (a : bitset#, b : bitset# -> bool)
const bsissubset : (a : bitset#, b : bitset# -> bool)
const bsclear : (bs : bitset# -> bitset#)
/* prepackaged hashing and equality tests */
const strhash : (s : byte[:] -> uint32)
const streq : (a : byte[:], b : byte[:] -> bool)
generic ptrhash : (p : @a# -> uint32)
generic ptreq : (a : @a#, b : @a# -> bool)
generic inthash : (v : @a::(integral,numeric) -> uint32)
generic inteq : (a : @a::(integral,numeric), b : @a::(integral,numeric) -> bool)
generic slhash : (sl : @a[:] -> uint32)
;;
Hash Tables
-----------
The need for key value lookup shows up everywhere, so libstd contains an
implementation of hash tables.
type htab(@k, @v) = struct
;;
The hash table is a generic type which contains any key and any value. The
key used is `@k`, and the value is `@v`.
generic mkht : (h : (k : @k -> uint32), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)
Mkht creates a hash table on the heap. It accepts two functions, for hashing
and equality comparison. The hash table should be freed with `htfree`.
generic htfree : (ht : htab(@k, @v)# -> void)
Htfree frees a hash table and associated storage. The keys and values remain
untouched.
generic htput : (ht : htab(@k, @v)#, k : @k, v : @v -> void)
Inserts a key value pair into the hash table `ht`. If there is already a value
with the key `k`, then the key value pair will be replaced.
generic htdel : (ht : htab(@k, @v)#, k : @k -> void)
Removes a key value pair from the hash table `ht`.
generic htget : (ht : htab(@k, @v)#, k : @k -> option(@v))
Looks up a value from a hash table, returning `\`Some v` if the key is
present, or `\`None` if the value is not present.
generic htgetv : (ht : htab(@k, @v)#, k : @k, fallback : @v-> @v)
Looks up a value from a hash table, returning the value if the key is
present, or `fallback` if it is not present.
generic hthas : (ht : htab(@k, @v)#, k : @k -> bool)
Looks up a value from a hash table, returning `true` if the key is
present, or `falase` if the value is not present.
generic htkeys : (ht : htab(@k, @v)# -> @k[:])
Returns a list of all the keys present in the hash table. This list is
heap allocated, and must be freed with `slfree`.
Bit Sets
--------
The need for sets lookup shows up in many places, so libstd contains an
implementation of bit sets. Any numeric value can be put into the set,
and with the current API they may be freely intermixed [BUG?]
type bitset = struct
;;
The bitset holds a set of integers. It works well for relatively dense, small
integers, as storage used is `O(max_value)`.
const mkbs : (-> bitset#)
Creates an empty bit set. The returned bit set should be freed with `bsfree`.
const bsdup : (bs : bitset# -> bitset#)
Duplicates an existing bit set. The returned bit set should be freed with
`bsfree`.
const bsfree : (bs : bitset# -> void)
Frees all resources associated with the bitset `bs`.
const bsmax : (a : bitset# -> size)
Returns the maximum value that the bitset contains. This is an approximation
of the capacity of the bitset, not a hard limit on the number of elements.
const bscount : (a : bitset# -> size)
Returns the total number of elements that the bitset contains. This is an
O(n) operation that involves iterating all of the bits.
generic bsput : (bs : bitset#, v : @a::(integral,numeric) -> bool)
Inserts the integer value `v` into the bit set `bs`. Returns `true` if this
operation changed the set, or `false` otherwise.
generic bsdel : (bs : bitset#, v : @a::(integral,numeric) -> bool)
Removes the integer value `v` from the bit set `bs`. Returns `true` if this
operation changed the set, or `false` otherwise.
generic bshas : (bs : bitset#, v : @a::(integral,numeric) -> bool)
Returns whether the bit set `bs` contains the value `v`.
const bsdiff : (a : bitset#, b : bitset# -> void)
Takes the set difference between `a` and `b`, storing the result back into
`a`.
const bsintersect : (a : bitset#, b : bitset# -> void)
Takes the set intersection between `a` and `b`, storing the result back into
`a`.
const bsunion : (a : bitset#, b : bitset# -> void)
Takes the set union between `a` and `b`, storing the result back into `a`.
const bseq : (a : bitset#, b : bitset# -> bool)
Tests whether the bitsets `a` and `b` contain the same elements, returning
`true` if they are equivalent and `false` otherwise.
const bsissubset : (a : bitset#, b : bitset# -> bool)
Tests whether every element of `b` is also within `a`, returning `true` if
`true` if `b` is a subset of `a`, and `false` otherwise.
const bsclear : (bs : bitset# -> bitset#)
Zeros every value within the bitset `bs`. This is equivalent to iterating
through it and deleting every element.