diff options
author | Ulrich Drepper <drepper@redhat.com> | 2000-01-02 06:01:06 +0000 |
---|---|---|
committer | Ulrich Drepper <drepper@redhat.com> | 2000-01-02 06:01:06 +0000 |
commit | 8d6f1731fcd082e4f744ba9cb4bde4be7c08f1b3 (patch) | |
tree | 099a250d7366aef2ab028fdb24f0d692cd784b4a /db2/hash/hash_func.c | |
parent | 9a6450d578556c11e7c173d2f28362345b8f1258 (diff) | |
download | glibc-8d6f1731fcd082e4f744ba9cb4bde4be7c08f1b3.tar.gz glibc-8d6f1731fcd082e4f744ba9cb4bde4be7c08f1b3.tar.xz glibc-8d6f1731fcd082e4f744ba9cb4bde4be7c08f1b3.zip |
Update.
* Makeconfig (all-subdirs): Remove db and db2. * db/*: Removed. * db2/*: Removed.
Diffstat (limited to 'db2/hash/hash_func.c')
-rw-r--r-- | db2/hash/hash_func.c | 219 |
1 files changed, 0 insertions, 219 deletions
diff --git a/db2/hash/hash_func.c b/db2/hash/hash_func.c deleted file mode 100644 index 9131098e5e..0000000000 --- a/db2/hash/hash_func.c +++ /dev/null @@ -1,219 +0,0 @@ -/*- - * See the file LICENSE for redistribution information. - * - * Copyright (c) 1996, 1997, 1998 - * Sleepycat Software. All rights reserved. - */ -/* - * Copyright (c) 1990, 1993 - * Margo Seltzer. All rights reserved. - */ -/* - * Copyright (c) 1990, 1993 - * The Regents of the University of California. All rights reserved. - * - * This code is derived from software contributed to Berkeley by - * Margo Seltzer. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -#include "config.h" - -#ifndef lint -static const char sccsid[] = "@(#)hash_func.c 10.8 (Sleepycat) 4/10/98"; -#endif /* not lint */ - -#ifndef NO_SYSTEM_INCLUDES -#include <sys/types.h> -#endif - -#include "db_int.h" -#include "db_page.h" -#include "hash.h" - -/* - * __ham_func2 -- - * Phong Vo's linear congruential hash. - * - * PUBLIC: u_int32_t __ham_func2 __P((const void *, u_int32_t)); - */ -#define DCHARHASH(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) - -u_int32_t -__ham_func2(key, len) - const void *key; - u_int32_t len; -{ - const u_int8_t *e, *k; - u_int32_t h; - u_int8_t c; - - k = key; - e = k + len; - for (h = 0; k != e;) { - c = *k++; - if (!c && k > e) - break; - DCHARHASH(h, c); - } - return (h); -} - -/* - * __ham_func3 -- - * Ozan Yigit's original sdbm hash. - * - * Ugly, but fast. Break the string up into 8 byte units. On the first time - * through the loop get the "leftover bytes" (strlen % 8). On every other - * iteration, perform 8 HASHC's so we handle all 8 bytes. Essentially, this - * saves us 7 cmp & branch instructions. - * - * PUBLIC: u_int32_t __ham_func3 __P((const void *, u_int32_t)); - */ -u_int32_t -__ham_func3(key, len) - const void *key; - u_int32_t len; -{ - const u_int8_t *k; - u_int32_t n, loop; - - if (len == 0) - return (0); - -#define HASHC n = *k++ + 65599 * n - n = 0; - k = key; - - loop = (len + 8 - 1) >> 3; - switch (len & (8 - 1)) { - case 0: - do { - HASHC; - case 7: - HASHC; - case 6: - HASHC; - case 5: - HASHC; - case 4: - HASHC; - case 3: - HASHC; - case 2: - HASHC; - case 1: - HASHC; - } while (--loop); - } - return (n); -} - -/* - * __ham_func4 -- - * Chris Torek's hash function. Although this function performs only - * slightly worse than __ham_func5 on strings, it performs horribly on - * numbers. - * - * PUBLIC: u_int32_t __ham_func4 __P((const void *, u_int32_t)); - */ -u_int32_t -__ham_func4(key, len) - const void *key; - u_int32_t len; -{ - const u_int8_t *k; - u_int32_t h, loop; - - if (len == 0) - return (0); - -#define HASH4a h = (h << 5) - h + *k++; -#define HASH4b h = (h << 5) + h + *k++; -#define HASH4 HASH4b - h = 0; - k = key; - - loop = (len + 8 - 1) >> 3; - switch (len & (8 - 1)) { - case 0: - do { - HASH4; - case 7: - HASH4; - case 6: - HASH4; - case 5: - HASH4; - case 4: - HASH4; - case 3: - HASH4; - case 2: - HASH4; - case 1: - HASH4; - } while (--loop); - } - return (h); -} - -/* - * 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. - * - * PUBLIC: u_int32_t __ham_func5 __P((const void *, u_int32_t)); - */ -u_int32_t -__ham_func5(key, len) - const void *key; - u_int32_t len; -{ - const u_int8_t *k, *e; - u_int32_t h; - - k = key; - e = k + len; - for (h = 0; k < e; ++k) { - h *= 16777619; - h ^= *k; - } - return (h); -} |