cvsuser 03/11/11 07:17:20
Modified: include/parrot hash.h misc.h
src hash.c utils.c
Log:
some rand48 functions; randomize hash sorting
Revision Changes Path
1.19 +8 -6 parrot/include/parrot/hash.h
Index: hash.h
===================================================================
RCS file: /cvs/public/parrot/include/parrot/hash.h,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -w -r1.18 -r1.19
--- hash.h 7 Nov 2003 16:17:33 -0000 1.18
+++ hash.h 11 Nov 2003 15:17:16 -0000 1.19
@@ -1,7 +1,7 @@
/* hash.h
* Copyright: 2001-2003 The Perl Foundation. All Rights Reserved.
* CVS Info
- * $Id: hash.h,v 1.18 2003/11/07 16:17:33 boemmels Exp $
+ * $Id: hash.h,v 1.19 2003/11/11 15:17:16 leo Exp $
* Overview:
* Hashtable implementation
* Data Structure and Algorithms:
@@ -48,7 +48,7 @@
typedef int (*hash_comp_fn)(Parrot_Interp, void*, void*);
typedef void (*hash_mark_key_fn)(Parrot_Interp, PObj *);
-typedef size_t (*hash_hash_key_fn)(Parrot_Interp, void*);
+typedef size_t (*hash_hash_key_fn)(Parrot_Interp, struct _hash*, void*);
struct _hash {
Buffer buffer; /* This struct is a Buffer subclass! */
@@ -59,13 +59,15 @@
PARROT_DATA_TYPES entry_type; /* type of value */
size_t value_size; /* currently unused, if set this size
at value is copied as a hash_entry */
- hash_comp_fn compare;
- hash_hash_key_fn hash_val;
- hash_mark_key_fn mark_key;
+ size_t seed; /* randomizes the hash_key generation
+ updated for each new hash */
+ hash_comp_fn compare; /* compare two keys, 0 = equal */
+ hash_hash_key_fn hash_val; /* generate a hash value for key */
+ hash_mark_key_fn mark_key; /* mark a key being alive */
};
Hash * new_hash(Interp * interpreter);
-Hash * new_hash_x(Interp * interpreter,
+Hash * new_hash_x(Interp *, PARROT_DATA_TYPES, size_t val_size,
hash_comp_fn, hash_hash_key_fn, hash_mark_key_fn);
Hash * new_cstring_hash(Interp *interpreter);
Hash * hash_clone(Interp * interpreter, Hash * src);
1.14 +7 -1 parrot/include/parrot/misc.h
Index: misc.h
===================================================================
RCS file: /cvs/public/parrot/include/parrot/misc.h,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -w -r1.13 -r1.14
--- misc.h 9 Sep 2003 10:25:41 -0000 1.13
+++ misc.h 11 Nov 2003 15:17:16 -0000 1.14
@@ -1,7 +1,7 @@
/* misc.h
* Copyright: 2001-2003 The Perl Foundation. All Rights Reserved.
* CVS Info
- * $Id: misc.h,v 1.13 2003/09/09 10:25:41 leo Exp $
+ * $Id: misc.h,v 1.14 2003/11/11 15:17:16 leo Exp $
* Overview:
* Miscellaneous functions, mainly the Parrot_sprintf family
* Data Structure and Algorithms:
@@ -29,6 +29,12 @@
INTVAL intval_mod(INTVAL i2, INTVAL i3);
FLOATVAL floatval_mod(FLOATVAL n2, FLOATVAL n3);
+
+FLOATVAL Parrot_float_rand(INTVAL how_random);
+INTVAL Parrot_uint_rand(INTVAL how_random);
+INTVAL Parrot_int_rand(INTVAL how_random);
+INTVAL Parrot_range_rand(INTVAL from, INTVAL to, INTVAL how_random);
+void Parrot_srand(INTVAL seed);
/*
* misc.c
1.52 +31 -25 parrot/src/hash.c
Index: hash.c
===================================================================
RCS file: /cvs/public/parrot/src/hash.c,v
retrieving revision 1.51
retrieving revision 1.52
diff -u -w -r1.51 -r1.52
--- hash.c 7 Nov 2003 16:17:35 -0000 1.51
+++ hash.c 11 Nov 2003 15:17:20 -0000 1.52
@@ -1,7 +1,7 @@
/* hash.c
* Copyright: 2001-2003 The Perl Foundation. All Rights Reserved.
* CVS Info
- * $Id: hash.c,v 1.51 2003/11/07 16:17:35 boemmels Exp $
+ * $Id: hash.c,v 1.52 2003/11/11 15:17:20 leo Exp $
* Overview:
* Data Structure and Algorithms:
* A hashtable contains an array of bucket indexes. Buckets
@@ -22,12 +22,14 @@
* hash keys are now (void *)
* add new_cstring_hash() function
*
- * 2003.11.04 leo bucket->value is now a plain pointer, no nore
+ * 2003.11.04 leo bucket->value is now a plain pointer, no more
* an HASH_ENTRY
* With little changes, we can again store
* arbitrary items if needed, s. TODO in code
* 2003.11.06 boemmels renamed HASH and HASHBUCKET
* to Hash and HashBucket
+ * 2003.11.11 leo randomize key_hash seed
+ * extend new_hash_x() init call by value_type and _size.
*
* Notes:
* Future optimizations:
@@ -82,21 +84,20 @@
=cut */
static size_t
-key_hash_STRING(Interp *interpreter, void *value)
+key_hash_STRING(Interp *interpreter, Hash *hash, void *value)
{
char *buffptr = ((STRING* )value)->strstart;
- INTVAL len = ((STRING* )value)->bufused;
- /* TODO randomize this for each new_hash */
- register size_t hash = 5381;
+ UINTVAL len = ((STRING* )value)->bufused;
+ register size_t h = hash->seed;
UNUSED(interpreter);
while (len--) {
- hash += hash << 5;
- hash += *buffptr++;
+ h += h << 5;
+ h += *buffptr++;
}
- return hash;
+ return h;
}
static int
@@ -106,16 +107,15 @@
}
static size_t
-key_hash_cstring(Interp *interpreter, void *value)
+key_hash_cstring(Interp *interpreter, Hash* hash, void *value)
{
- /* TODO randomize this for each new_hash */
- register size_t hash = 5381;
+ register size_t h = hash->seed;
unsigned char * p = (unsigned char *) value;
while (*p) {
- hash += hash << 5;
- hash += *p++;
+ h += h << 5;
+ h += *p++;
}
- return hash;
+ return h;
}
static int
@@ -254,7 +254,8 @@
BucketIndex bucketIdx = *bucketIdxP;
bucket = getBucket(hash, bucketIdx);
new_loc =
- (hash->hash_val)(interpreter, bucket->key) & new_max_chain;
+ (hash->hash_val)(interpreter, hash, bucket->key) &
+ new_max_chain;
if (new_loc != hi) {
/* Remove from table */
*bucketIdxP = bucket->next;
@@ -329,6 +330,8 @@
new_hash(Interp *interpreter)
{
return new_hash_x(interpreter,
+ enum_type_PMC,
+ 0,
STRING_compare, /* STRING compare */
key_hash_STRING, /* hash */
pobject_lives); /* mark */
@@ -338,13 +341,15 @@
new_cstring_hash(Interp *interpreter)
{
return new_hash_x(interpreter,
+ enum_type_PMC,
+ 0,
cstring_compare, /* cstring compare */
key_hash_cstring, /* hash */
(hash_mark_key_fn)0);/* no mark */
}
Hash *
-new_hash_x(Interp *interpreter,
+new_hash_x(Interp *interpreter, PARROT_DATA_TYPES val_type, size_t val_size,
hash_comp_fn compare, hash_hash_key_fn keyhash,
hash_mark_key_fn mark)
{
@@ -352,9 +357,9 @@
hash->compare = compare;
hash->hash_val = keyhash;
hash->mark_key = mark;
- /* TODO make next 2 params configurable */
- hash->entry_type = enum_type_PMC;
- hash->value_size = 0; /* extra size */
+ hash->entry_type = val_type;
+ hash->value_size = val_size; /* extra size */
+ hash->seed = (size_t) Parrot_uint_rand(0);
/* PObj_report_SET(&hash->buffer); */
@@ -433,7 +438,7 @@
HashBucket *
hash_get_bucket(Interp *interpreter, Hash *hash, void *key)
{
- UINTVAL hashval = (hash->hash_val)(interpreter, key);
+ UINTVAL hashval = (hash->hash_val)(interpreter, hash, key);
HashIndex *table = (HashIndex *)hash->buffer.bufstart;
BucketIndex chain = table[hashval & hash->max_chain];
return find_bucket(interpreter, hash, chain, key);
@@ -465,7 +470,7 @@
/* dump_hash(interpreter, hash); */
- hashval = (hash->hash_val)(interpreter, key);
+ hashval = (hash->hash_val)(interpreter, hash, key);
table = (BucketIndex *)hash->buffer.bufstart;
assert(table);
chain = table[hashval & hash->max_chain];
@@ -498,7 +503,7 @@
HashBucket *bucket;
HashBucket *prev = NULL;
- hashval = (hash->hash_val)(interpreter, key);
+ hashval = (hash->hash_val)(interpreter, hash, key);
slot = hashval & hash->max_chain;
/*
@@ -535,7 +540,8 @@
HashIndex i;
Hash *dest;
- dest = new_hash_x(interp, hash->compare, hash->hash_val, hash->mark_key);
+ dest = new_hash_x(interp, hash->entry_type, hash->value_size,
+ hash->compare, hash->hash_val, hash->mark_key);
for (i = 0; i <= hash->max_chain; i++) {
BucketIndex bi = lookupBucketIndex(hash, i);
while (bi != NULLBucketIndex) {
@@ -545,7 +551,7 @@
switch (hash->entry_type) {
case enum_hash_undef:
case enum_hash_int:
- case enum_hash_num:
+ case enum_hash_num: /* TODO use value_size */
valtmp = b->value;
break;
1.3 +148 -1 parrot/src/utils.c
Index: utils.c
===================================================================
RCS file: /cvs/public/parrot/src/utils.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -w -r1.2 -r1.3
--- utils.c 23 Oct 2003 17:48:59 -0000 1.2
+++ utils.c 11 Nov 2003 15:17:20 -0000 1.3
@@ -1,7 +1,7 @@
/* utils.c
* Copyright: 2001-2003 The Perl Foundation. All Rights Reserved.
* CVS Info
- * $Id: utils.c,v 1.2 2003/10/23 17:48:59 robert Exp $
+ * $Id: utils.c,v 1.3 2003/11/11 15:17:20 leo Exp $
* Overview:
* Some utility functions
* Data Structure and Algorithms:
@@ -64,6 +64,153 @@
? (n2 - n3 * floor(n2 / n3))
: n2;
#endif
+}
+
+/*
+ * currently undefined
+ */
+#ifndef PARROT_HAS_DRAND48
+
+typedef unsigned short _rand_buf[3];
+/*
+ * s. man drand48, SuS V2
+ *
+ * X(n+1) = ( aX(n) + c ) mod 2^48
+ *
+ */
+#define A_lo 0xE66D
+#define A_mid 0xDEEC
+#define A_hi 0x5
+#define C 0xB
+#define SEED_LO 0x330E
+
+static _rand_buf a = { A_lo, A_mid, A_hi };
+static _rand_buf last_rand;
+static unsigned short c = C;
+
+static void
+next_rand(_rand_buf X)
+{
+ unsigned short lo, mid, hi;
+ unsigned int t;
+
+ /* 48 bit mul, one short at a time */
+ t = X[0] * a[0] + c;
+ lo = t & 0xffff;
+ mid = (t >> 16) & 0xffff;
+
+ t = X[1] * a[0] + X[0] * a[1] + mid;
+ mid = t & 0xffff;
+ hi = (t >> 16) & 0xffff;
+
+ t = X[2] * a[0] + X[1] * a[1] + X[0] * a[2] + hi;
+
+ X[0] = lo;
+ X[1] = mid;
+ X[2] = t & 0xffff;
+}
+
+static FLOATVAL
+_erand48(_rand_buf buf)
+{
+ FLOATVAL r;
+ next_rand(buf);
+ r = (( buf[0] / 65536.0 + buf[1] ) / 65536.0 + buf[2]) / 65536.0;
+ return r;
+}
+
+static FLOATVAL
+_drand48(void)
+{
+ return _erand48(last_rand);
+}
+
+static long
+_jrand48(_rand_buf buf)
+{
+ long ret;
+ next_rand(buf);
+ ret = buf[2] << 16 | buf[1];
+ return ret;
+}
+
+static long
+_nrand48(_rand_buf buf)
+{
+ return _jrand48(buf) & 0x7fffffff;
+}
+
+static long
+_lrand48(void)
+{
+ return _nrand48(last_rand);
+}
+
+static long
+_mrand48(void)
+{
+ return _jrand48(last_rand);
+}
+
+static void
+_srand48(long seed)
+{
+ last_rand[0] = SEED_LO;
+ last_rand[1] = seed & 0xffff;
+ last_rand[2] = (seed >> 16) & 0xffff;
+ /*
+ * reinit a, c if changed by lcong48()
+ */
+}
+
+#undef A_lo
+#undef A_mid
+#undef A_hi
+#undef C
+
+#else
+
+# define _drand48 drand48
+# define _erand48(b) erand48(b)
+
+# define _lrand48 lrand48
+# define _nrand48(b) nrand48(b)
+
+# define _mrand48 mrand48
+# define _jrand48(b) jrand48(b)
+
+# define _srand48 srand48
+
+#endif
+
+FLOATVAL
+Parrot_float_rand(INTVAL how_random)
+{
+ return _drand48(); /* [0.0..1.0] */
+}
+
+INTVAL
+Parrot_uint_rand(INTVAL how_random)
+{
+ return _lrand48(); /* [0..2^31] */
+}
+
+INTVAL
+Parrot_int_rand(INTVAL how_random)
+{
+ return _mrand48(); /* [-2^31..2^31] */
+}
+
+INTVAL
+Parrot_range_rand(INTVAL from, INTVAL to, INTVAL how_random)
+{
+ return from + ((double)(to - from)) * Parrot_float_rand(how_random);
+}
+
+void
+Parrot_srand(INTVAL seed)
+{
+ _srand48(seed);
}
/*
