// 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(0).push_back(hash(0, input));
  break;
}

//: in all the code below, the intermediate results of hashing are threaded through 'h'

:(code)
size_t hash(size_t h, reagent/*copy*/ r) {
  canonize(r);
  if (is_mu_string(r))  // optimization
    return hash_mu_string(h, r);
  else if (is_mu_address(r))
    return hash_mu_address(h, r);
  else if (is_mu_scalar(r))
    return hash_mu_scalar(h, r);
  pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
/* © 2006-2007 Anselm R. Garbe <garbeam at gmail dot com>
 * © 2006-2007 Sander van Dijk <a dot h dot vandijk at gmail dot com>
 * See LICENSE file for license details. */

/* appearance */
#define BORDERPX		1
#define FONT			"-*-fixed-medium-r-normal-*-13-*-*-*-*-*-*-*"
#define NORMBORDERCOLOR		"#dddddd"
#define NORMBGCOLOR		"#eeeeee"
#define NORMFGCOLOR		"#222222"
#define SELBORDERCOLOR		"#ff0000"
#define SELBGCOLOR		"#006699"
#define SELFGCOLOR		"#ffffff"
#define TOPBAR			True		/* False */

/* tagging */
#define TAGS \
const char *tags[] = { "1", "2", "3", "4", "5", "6", "7", "8", "9", NULL };
/* Query class:instance:title for regex matching info with following command:
 * xprop | awk -F '"' '/^WM_CLASS/ { printf("%s:%s:",$4,$2) }; /^WM_NAME/ { printf("%s\n",$2) }' */
#define RULES \
static Rule rule[] = { \
	/* class:instance:title regex	tags regex	isfloating */ \
	{ "Gimp",			NULL,		True }, \
	{ "MPlayer",			NULL,		True }, \
	{ "Acroread",			NULL,		True }, \
};

/* layout(s) */
#define LAYOUTS \
static Layout layout[] = { \
	/* symbol		function */ \
	{ "[]=",		tile }, /* first entry is default */ \
	{ "><>",		floating }, \
};
#define MASTERWIDTH		600		/* master width per thousand */
#define NMASTER			1		/* clients in master area */
#define SNAP			32		/* snap pixel */

/* key definitions */
#define MODKEY			Mod1Mask
#define KEYS \
static Key key[] = { \
	/* modifier			key		function	argument */ \
	{ MODKEY|ShiftMask,		XK_Return,	spawn,		"exec xterm" }, \
	{ MODKEY,			XK_p,		spawn, 		"exe=`dmenu_path | dmenu` && exec $exe" }, \
	{ MODKEY,			XK_space,	setlayout,	NULL }, \
	{ MODKEY,			XK_h,		incmasterw,	"-32" }, \
	{ MODKEY,			XK_l,		incmasterw,	"32" }, \
	{ MODKEY|ShiftMask,		XK_j,		incnmaster,	"1" }, \
	{ MODKEY|ShiftMask,		XK_k,		incnmaster,	"-1" }, \
	{ MODKEY,			XK_j,		focusclient,	"1" }, \
	{ MODKEY,			XK_k,		focusclient,	"-1" }, \
	{ MODKEY,			XK_m,		togglemax,	NULL }, \
	{ MODKEY,			XK_Return,	zoom,		NULL }, \
	{ MODKEY|ShiftMask,		XK_space,	togglefloating,	NULL }, \
	{ MODKEY|ShiftMask,		XK_c,		killclient,	NULL }, \
	{ MODKEY,			XK_0,		view,		NULL }, \
	{ MODKEY,			XK_1,		view,		"0" }, \
	{ MODKEY,			XK_2,		view,		"1" }, \
	{ MODKEY,			XK_3,		view,		"2" }, \
	{ MODKEY,			XK_4,		view,		"3" }, \
	{ MODKEY,			XK_5,		view,		"4" }, \
	{ MODKEY,			XK_6,		view,		"5" }, \
	{ MODKEY,			XK_7,		view,		"6" }, \
	{ MODKEY,			XK_8,		view,		"7" }, \
	{ MODKEY,			XK_9,		view,		"8" }, \
	{ MODKEY|ControlMask,		XK_1,		toggleview,	"0" }, \
	{ MODKEY|ControlMask,		XK_2,		toggleview,	"1" }, \
	{ MODKEY|ControlMask,		XK_3,		toggleview,	"2" }, \
	{ MODKEY|ControlMask,		XK_4,		toggleview,	"3" }, \
	{ MODKEY|ControlMask,		XK_5,		toggleview,	"4" }, \
	{ MODKEY|ControlMask,		XK_6,		toggleview,	"5" }, \
	{ MODKEY|ControlMask,		XK_7,		toggleview,	"6" }, \
	{ MODKEY|ControlMask,		XK_8,		toggleview,	"7" }, \
	{ MODKEY|ControlMask,		XK_9,		toggleview,	"8" }, \
	{ MODKEY|ShiftMask,		XK_0,		tag,		NULL }, \
	{ MODKEY|ShiftMask,		XK_1,		tag,		"0" }, \
	{ MODKEY|ShiftMask,		XK_2,		tag,		"1" }, \
	{ MODKEY|ShiftMask,		XK_3,		tag,		"2" }, \
	{ MODKEY|ShiftMask,		XK_4,		tag,		"3" }, \
	{ MODKEY|ShiftMask,		XK_5,		tag,		"4" }, \
	{ MODKEY|ShiftMask,		XK_6,		tag,		"5" }, \
	{ MODKEY|ShiftMask,		XK_7,		tag,		"6" }, \
	{ MODKEY|ShiftMask,		XK_8,		tag,		"7" }, \
	{ MODKEY|ShiftMask,		XK_9,		tag,		"8" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_1,		toggletag,	"0" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_2,		toggletag,	"1" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_3,		toggletag,	"2" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_4,		toggletag,	"3" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_5,		toggletag,	"4" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_6,		toggletag,	"5" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_7,		toggletag,	"6" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_8,		toggletag,	"7" }, \
	{ MODKEY|ControlMask|ShiftMask,	XK_9,		toggletag,	"8" }, \
	{ MODKEY|ShiftMask,		XK_q,		quit,		NULL }, \
};
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2025-08-04 23:11:35 +0000
lass="Delimiter">; h += (h<<10); h ^= (h>>6); h += (h<<3); h ^= (h>>11); h += (h<<15); return h; } :(scenario hash_container_checks_all_elements) container foo [ x:number y:character ] def main [ 1:foo <- merge 34, 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 ] # hash on containers includes all elements +mem: storing 0 in location 7 :(scenario hash_exclusive_container_checks_all_elements) 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:foo <- merge 0/x, 34, 36 8:number <- hash 5:foo return-unless 8:number 9:boolean <- equal 4:number, 8:number ] # hash on containers includes all elements +mem: storing 0 in location 9 :(scenario hash_can_ignore_container_elements) container foo [ x:number y:character/ignore-for-hash ] def main [ 1:foo <- merge 34, 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; }