Mu - 069hash.cc

// A universal hash function that can handle objects of any type.
//
// The way it's currently implemented, two objects will have the same hash if
// all their non-address fields (all the way down) expand to the same sequence
// of scalar values. In particular, a container with all zero addresses hashes
// to 0. Hopefully this won't be an issue because we are usually hashing
// objects of a single type in any given hash table.
//
// Based on http://burtleburtle.net/bob/hash/hashfaq.html

:(before "End Primitive Recipe Declarations")
HASH,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "hash", HASH);
:(before "End Primitive Recipe Checks")
case HASH: {
  if (SIZE(inst.ingredients) != 1) {
    raise << maybe(get(Recipe, r).name) << "'hash' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case HASH: {
  const reagent& input = current_instruction().ingredients.at(0);
  products.resize(1);
  products.at<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><title>Python: package ranger.gui</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head><body bgcolor="#f0f0f8">

<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
<tr bgcolor="#7799ee">
<td valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial">&nbsp;<br><big><big><strong><a href="ranger.html"><font color="#ffffff">ranger</font></a>.gui</strong></big></big></font></td
><td align=right valign=bottom
><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:/home/hut/code/ranger/ranger/gui/__init__.py">/home/hut/code/ranger/ranger/gui/__init__.py</a></font></td></tr></table>
    <p></p>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#aa55cc">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Package Contents</strong></big></font></td></tr>
    
<tr><td bgcolor="#aa55cc"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><table width="100%" summary="list"><tr><td width="25%" valign=top><a href="ranger.gui.bar.html">bar</a><br>
<a href="ranger.gui.color.html">color</a><br>
<a href="ranger.gui.colorscheme.html">colorscheme</a><br>
</td><td width="25%" valign=top><a href="ranger.gui.context.html">context</a><br>
<a href="ranger.gui.curses_shortcuts.html">curses_shortcuts</a><br>
<a href="ranger.gui.defaultui.html">defaultui</a><br>
</td><td width="25%" valign=top><a href="ranger.gui.displayable.html">displayable</a><br>
<a href="ranger.gui.mouse_event.html">mouse_event</a><br>
<a href="ranger.gui.ui.html">ui</a><br>
</td><td width="25%" valign=top><a href="ranger.gui.widgets.html"><strong>widgets</strong>&nbsp;(package)</a><br>
</td></tr></table></td></tr></table>
</body></html>

4, 97/a 3:number <- hash 1:foo return-unless 3:number 4:foo <- merge 34, 98/a 6:number <- hash 4:foo return-unless 6:number 7:boolean <- equal 3:number, 6:number ] # hashes match even though y is different +mem: storing 1 in location 7 //: These properties aren't necessary for hash, they just test that the //: current implementation works like we think it does. :(scenario hash_of_zero_address) def main [ 1:address:number <- copy 0 2:number <- hash 1:address:number ] +mem: storing 0 in location 2 //: This is probably too aggressive, but we need some way to avoid depending //: on the precise bit pattern of a floating-point number. :(scenario hash_of_numbers_ignores_fractional_part) def main [ 1:number <- hash 1.5 2:number <- hash 1 3:boolean <- equal 1:number, 2:number ] +mem: storing 1 in location 3 :(scenario hash_of_array_same_as_string) def main [ 10:number <- copy 3 11:number <- copy 97 12:number <- copy 98 13:number <- copy 99 2:number <- hash 10:array:number/unsafe return-unless 2:number 3:address:array:character <- new [abc] 4:number <- hash 3:address:array:character return-unless 4:number 5:boolean <- equal 2:number, 4:number ] +mem: storing 1 in location 5 :(scenario hash_ignores_address_value) def main [ 1:address:number <- new number:type *1:address:number <- copy 34 2:number <- hash 1:address:number 3:address:number <- new number:type *3:address:number <- copy 34 4:number <- hash 3:address:number 5:boolean <- equal 2:number, 4:number ] # different addresses hash to the same result as long as the values the point to do so +mem: storing 1 in location 5 :(scenario hash_ignores_address_refcount) def main [ 1:address:number <- new number:type *1:address:number <- copy 34 2:number <- hash 1:address:number return-unless 2:number # increment refcount 3:address:number <- copy 1:address:number 4:number <- hash 3:address:number return-unless 4:number 5:boolean <- equal 2:number, 4:number ] # hash doesn't change when refcount changes +mem: storing 1 in location 5 :(scenario hash_container_depends_only_on_elements) container foo [ x:number y:character ] container bar [ x:number y:character ] def main [ 1:foo <- merge 34, 97/a 3:number <- hash 1:foo return-unless 3:number 4:bar <- merge 34, 97/a 6:number <- hash 4:bar return-unless 6:number 7:boolean <- equal 3:number, 6:number ] # containers with identical elements return identical hashes +mem: storing 1 in location 7 :(scenario hash_container_depends_only_on_elements_2) container foo [ x:number y:character z:address:number ] def main [ 1:address:number <- new number:type *1:address:number <- copy 34 2:foo <- merge 34, 97/a, 1:address:number 5:number <- hash 2:foo return-unless 5:number 6:address:number <- new number:type *6:address:number <- copy 34 7:foo <- merge 34, 97/a, 6:address:number 10:number <- hash 7:foo return-unless 10:number 11:boolean <- equal 5:number, 10:number ] # containers with identical 'leaf' elements return identical hashes +mem: storing 1 in location 11 :(scenario hash_container_depends_only_on_elements_3) container foo [ x:number y:character z:bar ] container bar [ x:number y:number ] def main [ 1:foo <- merge 34, 97/a, 47, 48 6:number <- hash 1:foo return-unless 6:number 7:foo <- merge 34, 97/a, 47, 48 12:number <- hash 7:foo return-unless 12:number 13:boolean <- equal 6:number, 12:number ] # containers with identical 'leaf' elements return identical hashes +mem: storing 1 in location 13 :(scenario hash_exclusive_container_ignores_tag) exclusive-container foo [ x:bar y:number ] container bar [ a:number b:number ] def main [ 1:foo <- merge 0/x, 34, 35 4:number <- hash 1:foo return-unless 4:number 5:bar <- merge 34, 35 7:number <- hash 5:bar return-unless 7:number 8:boolean <- equal 4:number, 7:number ] # hash on containers includes all elements +mem: storing 1 in location 8 //: An older version that supported only strings. //: Hash functions are subtle and easy to get wrong, so we keep the old //: version around and check that the new one is consistent with it. :(scenario hash_matches_old_version) def main [ 1:address:array:character <- new [abc] 2:number <- hash 1:address:array:character 3:number <- hash_old 1:address:array:character 4:boolean <- equal 2:number, 3:number ] +mem: storing 1 in location 4 :(before "End Primitive Recipe Declarations") HASH_OLD, :(before "End Primitive Recipe Numbers") put(Recipe_ordinal, "hash_old", HASH_OLD); :(before "End Primitive Recipe Checks") case HASH_OLD: { if (SIZE(inst.ingredients) != 1) { raise << maybe(get(Recipe, r).name) << "'hash_old' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end(); break; } if (!is_mu_string(inst.ingredients.at(0))) { raise << maybe(get(Recipe, r).name) << "'hash_old' currently only supports strings (address:array:character), but got '" << inst.ingredients.at(0).original_string << "'\n" << end(); break; } break; } :(before "End Primitive Recipe Implementations") case HASH_OLD: { string input = read_mu_string(ingredients.at(0).at(0)); size_t h = 0 ; for (int i = 0; i < SIZE(input); ++i) { h += static_cast<size_t>(input.at(i)); h += (h<<10); h ^= (h>>6); h += (h<<3); h ^= (h>>11); h += (h<<15); } products.resize(1); products.at(0).push_back(h); break; }