summaryrefslogtreecommitdiff
path: root/heap/hp_hash.c
diff options
context:
space:
mode:
authorunknown <monty@donna.mysql.com>2000-12-29 16:06:10 +0200
committerunknown <monty@donna.mysql.com>2000-12-29 16:06:10 +0200
commitcbafd764fb3248c55707d18e5e7a06385157a426 (patch)
tree53ef6da34dcfaf79e0e133177cccfb9bb63a9637 /heap/hp_hash.c
parent8debf25e98d79ed9143838aeba033c6337e6f267 (diff)
downloadmariadb-git-cbafd764fb3248c55707d18e5e7a06385157a426.tar.gz
Fixed --no-defaults in mysqltest
BUILD/compile-pentium-debug: Use /usr/local/BerkeleyDB-dbug/ if available BUILD/compile-pentium: Use /usr/local/BerkeleyDB-opt/ if available Docs/internals.texi: Added 'unedited' documentation for mysys functions Docs/manual.texi: Cleanups client/mysql.cc: Added client language to status client/mysqltest.c: Fixed bug with --no-defaults heap/_check.c: Added option to print status. heap/hp_close.c: Update to use new status interface heap/hp_hash.c: Clean up hash function and add new experimental hash heap/hp_test1.c: Update to use new status interface heap/hp_test2.c: Update to use new status interface include/heap.h: Update to use new status interface mysql-test/r/key_diff.result: Cleanup tests that may give rows in random order mysql-test/r/type_blob.result: Removed \r from output as this confused bk mysql-test/t/key_diff.test: Cleanup tests that may give rows in random order BitKeeper/etc/ignore: Added Docs/my_sys.doc to the ignore list mysql-test/t/type_blob.test: Removed \r from output as this confused bk mysys/hash.c: Add new experimental hash function scripts/safe_mysqld.sh: Added --mysqld option sql/ha_innobase.cc: Fixed store_locking sql/mysqld.cc: Cleaned up warning messages
Diffstat (limited to 'heap/hp_hash.c')
-rw-r--r--heap/hp_hash.c93
1 files changed, 87 insertions, 6 deletions
diff --git a/heap/hp_hash.c b/heap/hp_hash.c
index 28647ab7c94..eb35b947871 100644
--- a/heap/hp_hash.c
+++ b/heap/hp_hash.c
@@ -145,6 +145,7 @@ void _hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
return;
}
+#ifndef NEW_HASH_FUNCTION
/* Calc hashvalue for a key */
@@ -152,13 +153,14 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
{
register ulong nr=1, nr2=4;
HP_KEYSEG *seg,*endseg;
- uchar *pos;
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
{
+ uchar *pos=(uchar*) key;
+ key+=seg->length;
if (seg->type == HA_KEYTYPE_TEXT)
{
- for (pos=(uchar*) key,key+=seg->length ; pos < (uchar*) key ; pos++)
+ for (; pos < (uchar*) key ; pos++)
{
nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) my_sort_order[(uint) *pos]))+ (nr << 8);
nr2+=3;
@@ -166,7 +168,7 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
}
else
{
- for (pos=(uchar*) key,key+=seg->length ; pos < (uchar*) key ; pos++)
+ for (; pos < (uchar*) key ; pos++)
{
nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
nr2+=3;
@@ -182,13 +184,13 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
{
register ulong nr=1, nr2=4;
HP_KEYSEG *seg,*endseg;
- uchar *pos,*end;
for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
{
+ uchar *pos=(uchar*) rec+seg->start,*end=pos+seg->length;
if (seg->type == HA_KEYTYPE_TEXT)
{
- for (pos=(uchar*) rec+seg->start,end=pos+seg->length ; pos < end ; pos++)
+ for (; pos < end ; pos++)
{
nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) my_sort_order[(uint) *pos]))+ (nr << 8);
nr2+=3;
@@ -196,7 +198,7 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
}
else
{
- for (pos=(uchar*) rec+seg->start,end=pos+seg->length ; pos < end ; pos++)
+ for (; pos < end ; pos++)
{
nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
nr2+=3;
@@ -206,6 +208,85 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
return((ulong) nr);
}
+#else
+
+/*
+ * Fowler/Noll/Vo hash
+ *
+ * The basis of the hash algorithm was taken from an idea sent by email to the
+ * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
+ * Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)
+ * later improved on their algorithm.
+ *
+ * The magic is in the interesting relationship between the special prime
+ * 16777619 (2^24 + 403) and 2^32 and 2^8.
+ *
+ * This hash produces the fewest collisions of any function that we've seen so
+ * far, and works well on both numbers and strings.
+ */
+
+ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
+{
+ register ulong nr=0;
+ HP_KEYSEG *seg,*endseg;
+
+ for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+ {
+ uchar *pos=(uchar*) key;
+ key+=seg->length;
+ if (seg->type == HA_KEYTYPE_TEXT)
+ {
+ for (; pos < (uchar*) key ; pos++)
+ {
+ nr *=16777619;
+ nr ^=((uint) my_sort_order[(uint) *pos]);
+ }
+ }
+ else
+ {
+ for ( ; pos < (uchar*) key ; pos++)
+ {
+ nr *=16777619;
+ nr ^=(uint) *pos;
+ }
+ }
+ }
+ return((ulong) nr);
+}
+
+ /* Calc hashvalue for a key in a record */
+
+ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
+{
+ register ulong nr=0;
+ HP_KEYSEG *seg,*endseg;
+
+ for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+ {
+ uchar *pos=(uchar*) rec+seg->start,*end=pos+seg->length;
+ if (seg->type == HA_KEYTYPE_TEXT)
+ {
+ for ( ; pos < end ; pos++)
+ {
+ nr *=16777619;
+ nr ^=(uint) my_sort_order[(uint) *pos];
+ }
+ }
+ else
+ {
+ for ( ; pos < end ; pos++)
+ {
+ nr *=16777619;
+ nr ^=(uint) *pos;
+ }
+ }
+ }
+ return((ulong) nr);
+}
+
+#endif
+
+
/* Compare keys for two records. Returns 0 if they are identical */
int _hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)