## hashtable-rep.pkg
## COPYRIGHT (c) 1996 AT&T Research.
## AUTHOR: John Reppy
## AT&T Bell Laboratories
## Murray Hill, NJ 07974
## jhr@research.att.com
# Compiled by:
# src/lib/std/standard.lib# This is the internal representation of hashtables, along with some
# utility functions. It is used in both the typeagnostic and generic
# hashtable implementations.
package hashtable_representation: (weak) api {
Bucket (X, Y)
= NIL
| BUCKET ((Unt, X, Y, Bucket( X, Y )));
Table (X, Y) = Rw_Vector( Bucket (X, Y) );
alloc: 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;
modify: (Y -> Y) -> Table (X, Y) -> Void;
modifyi: (((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 alloc size_hint
=
rw_vector::make_rw_vector (round_up size_hint, NIL);
# Grow a table to the specified size:
#
fun grow_table (table, new_size) = {
new_arr = rw_vector::make_rw_vector (new_size, NIL);
fun copy NIL => ();
copy (BUCKET (h, key, v, rest)) => {
index = index (h, new_size);
rw_vector::set (new_arr, index,
BUCKET (h, key, v, rw_vector::get (new_arr, index)));
copy rest;
};
end;
rw_vector::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 = rw_vector::length arr;
if (n_items >= size)
table := grow_table (arr, size+size);
TRUE;
else
FALSE;
fi;
};
# Remove all items
fun clear table = rw_vector::modify (fn _ => NIL; end ) table;
# Return a list of the items in the table:
#
fun vals_list (table, n_items)
=
f ((rw_vector::length table) - 1, [], *n_items)
where
fun f (_, l, 0) => l;
f (-1, l, _) => l;
f (i, l, n)
=>
g (rw_vector::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 ((rw_vector::length table) - 1, [], *n_items)
where
fun f (_, l, 0) => l;
f (-1, l, _) => l;
f (i, l, n)
=>
g (rw_vector::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
=
rw_vector::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
=
{ fun apply_f NIL => ();
apply_f (BUCKET(_, key, item, rest))
=>
{ f item;
apply_f rest;
};
end;
rw_vector::apply apply_f table;
};
# 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
=
rw_vector::tabulate (
rw_vector::length table,
fn i = map_f (rw_vector::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 = rw_vector::tabulate (
rw_vector::length table,
fn i = map_f (rw_vector::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;
rw_vector::fold_left
fold_f
init
table;
};
fun fold f init table
=
rw_vector::fold_left 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 modify f table
=
{ fun modify_f NIL
=>
NIL;
modify_f (BUCKET (hash, key, item, rest))
=>
BUCKET (hash, key, f item, modify_f rest);
end;
rw_vector::modify modify_f table;
};
fun modifyi f table
=
{
fun modify_f NIL => NIL;
modify_f (BUCKET (hash, key, item, rest))
=>
BUCKET (hash, key, f (key, item), modify_f rest);
end;
rw_vector::modify modify_f table;
};
# Remove any hashtable items that do not satisfy the given
# predicate. Return the number of items left in the table.
fun keyed_filter prior table
=
{ n_items = REF 0;
fun filter_p NIL
=>
NIL;
filter_p (BUCKET (hash, key, item, rest))
=>
if (prior (key, item))
n_items := *n_items+1;
BUCKET (hash, key, item, filter_p rest);
else
filter_p rest;
fi;
end;
rw_vector::modify filter_p table;
*n_items;
};
fun filter prior table
=
{ n_items = REF 0;
fun filter_p NIL => NIL;
filter_p (BUCKET (hash, key, item, rest))
=>
if (prior item)
n_items := *n_items+1;
BUCKET (hash, key, item, filter_p rest);
else
filter_p rest;
fi;
end;
rw_vector::modify filter_p table;
*n_items;
}; # filter
# Create a copy of a hashtable:
fun copy table
=
rw_vector::tabulate (
rw_vector::length table,
fn i = rw_vector::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
=
{ fun len (NIL, n) => n;
len (BUCKET(_, _, _, r), n)
=>
len (r, n+1);
end;
rw_vector::fold_right
(fn (b, l) = len (b, 0) ! l)
[]
table;
};
}; # hashtable_representation