[pure-lang-svn] SF.net SVN: pure-lang: [259] pure/trunk

[<ag...@us...>]

Revision: 259
          http://pure-lang.svn.sourceforge.net/pure-lang/?rev=259&view=rev
Author:   agraef
Date:     2008-06-18 09:38:20 -0700 (Wed, 18 Jun 2008)

Log Message:
-----------
Add hash function to compute 32 bit hash codes of Pure expressions.

Modified Paths:
--------------
    pure/trunk/lib/primitives.pure
    pure/trunk/runtime.cc
    pure/trunk/runtime.h

Modified: pure/trunk/lib/primitives.pure
===================================================================
--- pure/trunk/lib/primitives.pure	2008-06-18 15:44:34 UTC (rev 258)
+++ pure/trunk/lib/primitives.pure	2008-06-18 16:38:20 UTC (rev 259)
@@ -65,6 +65,10 @@
 
 extern expr* fun(expr*), expr* arg(expr*);
 
+/* Compute a 32 bit hash code of a Pure expression. */
+
+extern int hash(expr*);
+
 /* Conversions between the different numeric and pointer types. */
 
 extern expr* pure_intval(expr*), expr* pure_dblval(expr*),

Modified: pure/trunk/runtime.cc
===================================================================
--- pure/trunk/runtime.cc	2008-06-18 15:44:34 UTC (rev 258)
+++ pure/trunk/runtime.cc	2008-06-18 16:38:20 UTC (rev 259)
@@ -1474,7 +1474,83 @@
   return res;
 }
 
+static uint32_t mpz_hash(const mpz_t z)
+{
+  uint32_t h = 0;
+  int i, len = z->_mp_size;
+  if (len < 0) len = -len;
+  if (sizeof(mp_limb_t) == 8) {
+    for (i=0; i<len; i++) {
+      h ^= (uint32_t)(uint64_t)z->_mp_d[i];
+      h ^= (uint32_t)(((uint64_t)z->_mp_d[i])>>32);
+    }
+  } else {
+    for (i=0; i<len; i++)
+      h ^= z->_mp_d[i];
+  }
+  if (z->_mp_size < 0)
+    h = -h;
+  return h;
+}
+
+static uint32_t double_hash(double d)
+{
+  uint32_t h;
+  char *c;
+  size_t i;
+  c = (char*)&d;
+  for (h=0, i=0; i<sizeof(double); i++) {
+    h += c[i] * 971;
+  }
+  return h;
+}
+
+static uint32_t string_hash(char *s)
+{
+  uint32_t h = 0, g;
+  while (*s) {
+    h = (h<<4)+*(s++);
+    if ((g = (h & 0xf0000000)))	{
+      h = h^(g>>24);
+      h = h^g;
+    }
+  }
+  return h;
+}
+
 extern "C"
+uint32_t hash(const pure_expr *x)
+{
+  char test;
+  switch (x->tag) {
+  case EXPR::INT:
+    return (uint32_t)x->data.i;
+  case EXPR::BIGINT:
+    return mpz_hash(x->data.z);
+  case EXPR::DBL:
+    return double_hash(x->data.d);
+  case EXPR::STR:
+    return string_hash(x->data.s);
+  case EXPR::PTR:
+#if SIZEOF_VOID_P==8
+    return ((uint32_t)(uint64_t)x->data.p) ^ ((uint32_t)(((uint64_t)p)>>32));
+#else
+    return (uint32_t)x->data.p;
+#endif
+  case EXPR::APP: {
+    checkstk(test);
+    int h;
+    h = hash(x->data.x[0]);
+    h = (h<<1) | (h<0 ? 1 : 0);
+    h ^= hash(x->data.x[1]);
+    return (uint32_t)h;
+  }
+  default:
+    return (uint32_t)x->tag;
+  }
+}
+
+extern "C"
 bool same(const pure_expr *x, const pure_expr *y)
 {
   char test;

Modified: pure/trunk/runtime.h
===================================================================
--- pure/trunk/runtime.h	2008-06-18 15:44:34 UTC (rev 258)
+++ pure/trunk/runtime.h	2008-06-18 16:38:20 UTC (rev 259)
@@ -280,6 +280,11 @@
 pure_expr *str(const pure_expr *x);
 pure_expr *eval(const char *s);
 
+/* Compute a 32 bit hash code of a Pure expression. This makes it possible to
+   use arbitary Pure values as keys in a hash table. */
+
+uint32_t hash(const pure_expr *x);
+
 /* Check whether two objects are the "same" (syntactically). */
 
 bool same(const pure_expr *x, const pure_expr *y);


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.