Myrddin: Data Structures

Summary: 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 -> bool) :: integral,numeric @a
        generic bsdel   : (bs : bitset#, v : @a -> bool) :: integral,numeric @a
        generic bshas   : (bs : bitset#, v : @a -> bool) :: integral,numeric @a
        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 bshash    : (a : bitset# -> uint64)
        const bsissubset    : (a : bitset#, b : bitset# -> bool)
        const bsclear   : (bs : bitset# -> bitset#)
    const bscount   : (a : bitset# -> size)

        /* 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   -> uint32) :: integral,numeric @a
        generic inteq   : (a : @a::(integral,numeric), b : @a -> bool) :: integral,numeric @a
        generic slhash  : (sl : @a[:] -> uint32)

    type bsiter
    impl iterable bsiter -> size
    const bybsvalue : (bs : bitset# -> bsiter)
;;

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 false 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 -> bool) :: integral,numeric @a

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 -> bool) :: integral,numeric @a

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 -> bool) :: integral,numeric @a

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 bshash    : (a : bitset# -> uint64)

Returns a hash of bitset a. The hash is identical for two bitsets that compare equal with std.bseq. This hash function is suitable for use with libstd hash tables.

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.

const bybsiter  : (bs : bitset -> bsiter)

Returns a bitset iterator that can be used in for loops.