## typelocked-hashtable-g.pkg
## AUTHOR: John Reppy
## AT&T Bell Laboratories
## Murray Hill, NJ 07974
## jhr@research.att.com
# Compiled by:
# src/lib/std/standard.lib# A hashtable generic. It takes a key type with two operations: same_key and
# hash_value as arguments (see hash-key.api).
generic package typelocked_hashtable_g (
# ========================
#
key: Hash_Key # Hash_Key is from src/lib/src/hash-key.api)
: (weak) Typelocked_Hashtable # Typelocked_Hashtable is from src/lib/src/typelocked-hashtable.api{
package key = key;
include key;
package htrep= hashtable_representation; # hashtable_representation is from src/lib/src/hashtable-rep.pkg Hashtable X = HT {
not_found_exception: Exception,
table: Ref( htrep::Table( Hash_Key, X ) ),
n_items: Ref( Int )
};
fun index (i, size)
=
unt::to_int_x (unt::bitwise_and (i, unt::from_int size - 0u1));
# Create a new hashtable; the
# int is a size hint and the
# exception is to be raised by find.
#
fun make_hashtable { size_hint, not_found_exception }
=
HT {
not_found_exception,
table => REF (htrep::alloc size_hint),
n_items => REF 0
};
# Remove all elements from the table
#
fun clear (HT { table, n_items, ... } )
=
{ htrep::clear( *table );
n_items := 0;
};
# Insert an item.
# If the key already has an item associated with it,
# then the old item is discarded.
#
fun set (my_table as HT { table, n_items, ... } ) (key, item)
=
{ arr = *table;
size = rw_vector::length arr;
hash = hash_value key;
index = index (hash, size);
fun get htrep::NIL
=>
{ rw_vector::set (arr, index, htrep::BUCKET (hash, key, item, rw_vector::get (arr, index)));
n_items := *n_items + 1;
htrep::grow_table_if_needed (table, *n_items);
htrep::NIL;
};
get (htrep::BUCKET (h, k, v, r))
=>
if (hash == h and same_key (key, k))
htrep::BUCKET (hash, key, item, r);
else
case (get r)
htrep::NIL => htrep::NIL;
rest => htrep::BUCKET (h, k, v, rest);
esac;
fi;
end;
case (get (rw_vector::get (arr, index)))
htrep::NIL => ();
b => rw_vector::set (arr, index, b);
esac;
};
# Return TRUE iff the key is
# in the domain of the table:
#
fun contains_key (HT { table, ... } ) key
=
{ arr = *table;
hash = hash_value key;
index = index (hash, rw_vector::length arr);
fun get htrep::NIL => FALSE;
get (htrep::BUCKET (h, k, v, r))
=>
((hash == h) and same_key (key, k)) or get r; end;
get (rw_vector::get (arr, index));
};
# Find an item, the table's exception
# is raised if the item doesn't exist:
#
fun get (HT { table, not_found_exception, ... } ) key
=
get' (rw_vector::get (arr, index))
where
arr = *table;
hash = hash_value key;
index = index (hash, rw_vector::length arr);
fun get' htrep::NIL
=>
raise exception not_found_exception;
get' (htrep::BUCKET (h, k, v, r))
=>
if (hash == h and same_key (key, k)) v;
else get' r;
fi;
end;
end;
# Look up an item, return NULL
# if the item doesn't exist:
#
fun find (HT { table, ... } ) key
=
get' (rw_vector::get (arr, index))
where
arr = *table;
size = rw_vector::length arr;
hash = hash_value key;
index = index (hash, size);
fun get' htrep::NIL
=>
NULL;
get' (htrep::BUCKET (h, k, v, r))
=>
if (hash == h and same_key (key, k)) THE v;
else get' r;
fi;
end;
end;
# Remove an item.
# The table's exception is raised
# if the item doesn't exist.
#
fun remove (HT { not_found_exception, table, n_items } ) key
=
{ arr = *table;
size = rw_vector::length arr;
hash = hash_value key;
index = index (hash, size);
fun get' htrep::NIL
=>
raise exception not_found_exception;
get' (htrep::BUCKET (h, k, v, r))
=>
if (hash == h and same_key (key, k))
(v, r);
else
my (item, r') = get' r;
(item, htrep::BUCKET (h, k, v, r'));
fi;
end;
my (item, bucket)
=
get' (rw_vector::get (arr, index));
rw_vector::set (arr, index, bucket);
n_items := *n_items - 1;
item;
};
# Return the number of items in the table
#
fun vals_count (HT { n_items, ... } )
=
*n_items;
# Return a list of the items in the table:
#
fun vals_list (HT { table => REF arr, n_items, ... } )
=
htrep::vals_list (arr, n_items);
fun keyvals_list (HT { table => REF arr, n_items, ... } )
=
htrep::keyvals_list (arr, n_items);
# Apply a function to the entries of the table
fun keyed_apply f (HT { table, ... } ) = htrep::keyed_apply f *table;
fun apply f (HT { table, ... } ) = htrep::apply f *table;
# Map a table to a new table that
# has the same keys and exception:
fun keyed_map f (HT { table, n_items, not_found_exception } )
=
HT {
table => REF (htrep::keyed_map f *table),
n_items => REF *n_items,
not_found_exception
};
fun map f (HT { table, n_items, not_found_exception } )
=
HT {
table => REF (htrep::map f *table),
n_items => REF *n_items,
not_found_exception
};
# Fold a function over the entries of the table
fun foldi f init (HT { table, ... } ) = htrep::foldi f init *table;
fun fold f init (HT { table, ... } ) = htrep::fold f init *table;
# Modify the hashtable items in place
fun modifyi f (HT { table, ... } ) = htrep::modifyi f *table;
fun modify f (HT { table, ... } ) = htrep::modify f *table;
# Remove any hashtable items that
# do not satisfy the given predicate.
fun keyed_filter prior (HT { table, n_items, ... } )
=
n_items := htrep::keyed_filter prior *table;
fun filter prior (HT { table, n_items, ... } )
=
n_items := htrep::filter prior *table;
# Create a copy of a hashtable
fun copy (HT { table, n_items, not_found_exception } )
=
HT {
table => REF (htrep::copy *table),
n_items => REF *n_items,
not_found_exception
};
# 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 (HT { table, ... } )
=
htrep::bucket_sizes *table;
};
## COPYRIGHT (c) 1992 by AT&T Bell Laboratories.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2012,
## released under Gnu Public Licence version 3.