## hashtable-rep.pkg
#
# This is the internal representation of hashtables, along with some
# utility functions. It is used in both the typeagnostic and generic
# hashtable implementations.
# Compiled by:
# src/lib/std/standard.libstipulate
package rwv = rw_vector; # rw_vector is from src/lib/std/src/rw-vector.pkgherein
package hashtable_representation
# ========================
#
: (weak) api {
Bucket (X, Y)
= NIL
| BUCKET (Unt, X, Y, Bucket( X, Y ))
;
Table (X, Y) = Rw_Vector( Bucket (X, Y) );
allot: Int -> Table( X, Y ); # Allocate a table of at least the given size.
grow_table: ((Table (X, Y), Int)) -> Table( X, Y ); # Grow a table to the specified size.
grow_table_if_needed: ((Ref( Table( X, Y ) ), Int)) -> Bool; # Conditionally grow a table; the second argument is the number of items currently in the table.
clear: Table( X, Y ) -> Void; # Remove all items.
vals_list: (Table( X, Y ), Ref( Int )) -> List(Y);
keyvals_list: (Table( X, Y ), Ref( Int )) -> List( (X, Y) );
keyed_apply: ((X, Y) -> Z) -> Table (X, Y) -> Void;
apply: (X -> Y) -> Table (Z, X) -> Void;
keyed_map: ((X, Y) -> Z) -> Table (X, Y) -> Table (X, Z);
map: (X -> Y) -> Table (Z, X) -> Table (Z, Y);
foldi: ((X, Y, Z) -> Z) -> Z -> Table (X, Y) -> Z;
fold: ((X, Y) -> Y) -> Y -> Table (Z, X) -> Y;
map_in_place: (Y -> Y) -> Table (X, Y) -> Void;
keyed_map_in_place: ((X, Y) -> Y) -> Table (X, Y) -> Void;
keyed_filter: ((X, Y) -> Bool) -> Table (X, Y) -> Int;
filter: (X -> Bool) -> Table (Y, X) -> Int;
copy: Table (X, Y) -> Table (X, Y);
bucket_sizes: Table (X, Y) -> List( Int );
}
{
Bucket (X, Y)
= NIL
| BUCKET ((Unt, X, Y, Bucket (X, Y )));
Table (X, Y) = Rw_Vector( Bucket (X, Y) );
fun index (i, size)
=
unt::to_int_x (unt::bitwise_and (i, unt::from_int size - 0u1));
# Find smallest power of 2 (>= 32) that is >= n
#
fun round_up n
=
f 32
where
fun f i = if (i >= n) i;
else f (i * 2);
fi;
end;
# Create a new table; the int is a size hint
# and the exception is to be raised by find.
#
fun allot size_hint
=
rwv::make_rw_vector (round_up size_hint, NIL);
# Grow a table to the specified size:
#
fun grow_table (table, new_size)
=
{ new_arr = rwv::make_rw_vector (new_size, NIL);
#
fun copy NIL => ();
#
copy (BUCKET (h, key, v, rest))
=>
{ index = index (h, new_size);
#
rwv::set (new_arr, index,
BUCKET (h, key, v, rwv::get (new_arr, index)));
copy rest;
};
end;
rwv::apply copy table;
new_arr;
};
# Conditionally grow a table;
# return TRUE if it grew.
#
fun grow_table_if_needed (table, n_items)
=
{ arr = *table;
size = rwv::length arr;
if (n_items >= size)
table := grow_table (arr, size+size);
TRUE;
else
FALSE;
fi;
};
# Remove all items
#
fun clear table
=
rwv::map_in_place (\\ _ = NIL) table;
# Return a list of the items in the table:
#
fun vals_list (table, n_items)
=
f ((rwv::length table) - 1, [], *n_items)
where
fun f (_, l, 0) => l;
f (-1, l, _) => l;
f (i, l, n)
=>
g (rwv::get (table, i), l, n)
where
fun g (NIL, l, n) => f (i - 1, l, n);
g (BUCKET(_, k, v, r), l, n) => g (r, v ! l, n - 1);
end;
end;
end;
end;
fun keyvals_list (table, n_items)
=
f ((rwv::length table) - 1, [], *n_items)
where
fun f (_, l, 0) => l;
f (-1, l, _) => l;
f (i, l, n)
=>
g (rwv::get (table, i), l, n)
where
fun g (BUCKET(_, k, v, r), l, n) => g (r, (k, v) ! l, n - 1);
g (NIL, l, n) => f (i - 1, l, n );
end;
end;
end;
end;
# Apply a function to the
# entries of the table:
#
fun keyed_apply f table
=
rwv::apply apply_f table
where
fun apply_f NIL => ();
apply_f (BUCKET(_, key, item, rest))
=>
{ f (key, item);
apply_f rest;
};
end;
end;
fun apply f table
=
rwv::apply apply_f table
where
fun apply_f NIL => ();
#
apply_f (BUCKET(_, key, item, rest))
=>
{ f item;
#
apply_f rest;
};
end;
end;
# Map a table to a new table that has the same keys:
#
fun keyed_map f table
=
new_table
where
fun map_f NIL => NIL;
map_f (BUCKET (hash, key, item, rest))
=>
BUCKET (hash, key, f (key, item), map_f rest);
end;
new_table
=
rwv::from_fn (
rwv::length table,
\\ i = map_f (rwv::get (table, i))
);
end;
# Map a table to a new table that has the same keys:
#
fun map f table
=
new_table
where
fun map_f NIL => NIL;
#
map_f (BUCKET (hash, key, item, rest))
=>
BUCKET (hash, key, f item, map_f rest);
end;
new_table
=
rwv::from_fn
(
rwv::length table,
\\ i = map_f (rwv::get (table, i))
);
end;
fun foldi f init table
=
{ fun fold_f (NIL, accum) => accum;
fold_f (BUCKET (hash, key, item, rest), accum)
=>
fold_f (rest, f (key, item, accum));
end;
rwv::fold_forward
fold_f
init
table;
};
fun fold f init table
=
rwv::fold_forward fold_f init table
where
fun fold_f (NIL, accum) => accum;
fold_f (BUCKET (hash, key, item, rest), accum)
=>
fold_f (rest, f (item, accum));
end;
end;
# Modify the hashtable items in place:
#
fun map_in_place f table
=
rwv::map_in_place modify_f table
where
fun modify_f NIL
=>
NIL;
modify_f (BUCKET (hash, key, item, rest))
=>
BUCKET (hash, key, f item, modify_f rest);
end;
end;
fun keyed_map_in_place f table
=
rwv::map_in_place modify_f table
where
fun modify_f NIL => NIL;
modify_f (BUCKET (hash, key, item, rest))
=>
BUCKET (hash, key, f (key, item), modify_f rest);
end;
end;
# Remove any hashtable items that do not satisfy the given
# predicate. Return the number of items left in the table.
#
fun keyed_filter predicate table
=
{ n_items = REF 0;
#
fun filter_p NIL
=>
NIL;
filter_p (BUCKET (hash, key, item, rest))
=>
if (predicate (key, item))
#
n_items := *n_items+1;
BUCKET (hash, key, item, filter_p rest);
else
filter_p rest;
fi;
end;
rwv::map_in_place filter_p table;
*n_items;
};
fun filter predicate table
=
{ n_items = REF 0;
#
fun filter_p NIL => NIL;
#
filter_p (BUCKET (hash, key, item, rest))
=>
if (predicate item)
#
n_items := *n_items+1;
BUCKET (hash, key, item, filter_p rest);
else
filter_p rest;
fi;
end;
rwv::map_in_place filter_p table;
*n_items;
};
# Create a copy of a hashtable:
#
fun copy table
=
rwv::from_fn
(
rwv::length table,
\\ i = rwv::get (table, i)
);
# Return a list of the sizes of the various buckets.
# This is to allow users to gauge
# the quality of their hashing function:
#
fun bucket_sizes table
=
rwv::fold_backward
(\\ (b, l) = len (b, 0) ! l)
[]
table
where
fun len (NIL, n) => n;
#
len (BUCKET(_, _, _, r), n)
=>
len (r, n+1);
end;
end;
}; # hashtable_representation
end;