## quickstring--premicrothread.pkg
# Compiled by:
# src/lib/std/standard.lib# See also:
# src/lib/src/quickstring-hashtable.pkg# src/lib/src/quickstring-set.pkg# src/lib/src/quickstring-map.pkg# src/lib/src/quickstring-red-black-set.pkg# src/lib/src/quickstring-red-black-map.pkg# src/lib/src/quickstring-binary-map.pkg# src/lib/src/quickstring-binary-set.pkg# src/lib/src/quickstring.pkg # (Quickstrings and Uniquestrings are so similar they should probably be merged. XXX BUGGO FIXME.)
# TODO: add a gensym operation?
### "The universe is made
### of stories, not of atoms."
###
### -- Muriel Rukiysen
package quickstring__premicrothread
: Quickstring # Quickstring is from src/lib/src/quickstring.api{
# Quickstrings are hashed strings that support fast equality testing.
Quickstring
=
QUICKSTRING {
hash: Unt,
id: String
};
# Return the string representation of the quickstring
fun to_string (QUICKSTRING a )
=
a.id;
# Return a hash key for the quickstring
#
fun hash (QUICKSTRING a )
=
a.hash;
# Return TRUE if the quickstrings are the same:
#
fun same ( QUICKSTRING a,
QUICKSTRING b
)
=
(a.hash == b.hash) and # Fast integer compare.
(a.id == b.id ); # Slow string compare.
# Compare two names for their relative order.
# NB: This is not lexical order!
#
fun compare (QUICKSTRING a,
QUICKSTRING b )
=
if (a.hash == b.hash) string::compare (a.id, b.id);
elif (a.hash < b.hash) LESS;
else GREATER;
fi;
# Compare two quickstrings for their lexical order
#
fun lex_compare (QUICKSTRING a,
QUICKSTRING b )
=
string::compare (a.id, b.id);
# The unique name hashtable:
#
table_size = 64;
my_table = REF (rw_vector::make_rw_vector (table_size, [] : List( Quickstring )));
vals_count = REF 0;
# XXX BUGGO FIXME is there any reason to re-invent the hashtable here
# rather than using existing implementations elsewhere?
infix my % ;
fun h % m
=
unt::to_int_x (unt::bitwise_and (h, m));
# Map a string or substring s to the corresponding unique quickstring.
#
fun quickstring0 (to_string, hash_string, same_string) s
=
get (rw_vector::get (table, indx))
where
h = hash_string s;
table = *my_table;
size = rw_vector::length table;
indx = h % (unt::from_int size - 0u1);
fun get ((a as QUICKSTRING { hash, id }) ! rest)
=>
(hash == h and same_string (s, id))
##
?? a
:: get rest;
get []
=>
{ fun new (table, indx)
=
quickstring
where
quickstring = QUICKSTRING { hash => h, id => to_string s };
rw_vector::set (table, indx, quickstring ! rw_vector::get (table, indx));
end;
if (*vals_count < size)
#
new (table, indx);
else
new_size = size + size;
new_mask = unt::from_int new_size - 0u1;
new_table = rw_vector::make_rw_vector (new_size, []);
fun ins (item as QUICKSTRING { hash, ... } )
=
{ indx = hash % new_mask;
rw_vector::set (new_table, indx, item ! rw_vector::get (new_table, indx));
};
rw_vector::apply (apply ins) table;
my_table := new_table;
new (new_table, h % new_mask);
fi;
};
end;
end;
from_string # quickstring0 for the string case:
=
quickstring0
( \\ s = s,
hash_string::hash_string,
(==)
);
from_substring # quickstring0 for the substring case
=
quickstring0
( substring::to_string,
hash_string::hash_substring,
\\ (ss, s) = (substring::compare (ss, substring::from_string s) == EQUAL)
);
}; # package quickstring__premicrothread
## AUTHOR: John Reppy
## AT&T Bell Laboratories
## Murray Hill, NJ 07974
## jhr@research.att.com
## COPYRIGHT (c) 1996 by AT&T Research
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.