Loading...
--- Libc/Libc-320/db/hash/hash_func.c
+++ /dev/null
@@ -1,237 +0,0 @@
-/*
- * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
- *
- * @APPLE_LICENSE_HEADER_START@
- *
- * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
- *
- * This file contains Original Code and/or Modifications of Original Code
- * as defined in and that are subject to the Apple Public Source License
- * Version 2.0 (the 'License'). You may not use this file except in
- * compliance with the License. Please obtain a copy of the License at
- * http://www.opensource.apple.com/apsl/ and read it before using this
- * file.
- *
- * The Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- * Please see the License for the specific language governing rights and
- * limitations under the License.
- *
- * @APPLE_LICENSE_HEADER_END@
- */
-/*-
- * 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.
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94";
-#endif /* LIBC_SCCS and not lint */
-#include <sys/cdefs.h>
-
-#include <sys/types.h>
-
-#include <db.h>
-#include "hash.h"
-#include "page.h"
-#include "extern.h"
-
-static u_int32_t hash1(const void *, size_t) ;
-static u_int32_t hash2(const void *, size_t) ;
-static u_int32_t hash3(const void *, size_t) ;
-static u_int32_t hash4(const void *, size_t);
-
-/* Global default hash function */
-u_int32_t (*__default_hash)(const void *, size_t) = hash4;
-
-/*
- * HASH FUNCTIONS
- *
- * Assume that we've already split the bucket to which this key hashes,
- * calculate that bucket, and check that in fact we did already split it.
- *
- * This came from ejb's hsearch.
- */
-
-#define PRIME1 37
-#define PRIME2 1048583
-
-static u_int32_t
-hash1(keyarg, len)
- const void *keyarg;
- size_t len;
-{
- const u_char *key;
- u_int32_t h;
-
- /* Convert string to integer */
- for (key = keyarg, h = 0; len--;)
- h = h * PRIME1 ^ (*key++ - ' ');
- h %= PRIME2;
- return (h);
-}
-
-/*
- * Phong's linear congruential hash
- */
-#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
-
-static u_int32_t
-hash2(keyarg, len)
- const void *keyarg;
- size_t len;
-{
- const u_char *e, *key;
- u_int32_t h;
- u_char c;
-
- key = keyarg;
- e = key + len;
- for (h = 0; key != e;) {
- c = *key++;
- if (!c && key > e)
- break;
- dcharhash(h, c);
- }
- return (h);
-}
-
-/*
- * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte
- * units. On the first time through the loop we get the "leftover bytes"
- * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle
- * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If
- * this routine is heavily used enough, it's worth the ugly coding.
- *
- * OZ's original sdbm hash
- */
-static u_int32_t
-hash3(keyarg, len)
- const void *keyarg;
- size_t len;
-{
- const u_char *key;
- size_t loop;
- u_int32_t h;
-
-#define HASHC h = *key++ + 65599 * h
-
- h = 0;
- key = keyarg;
- if (len > 0) {
- loop = (len + 8 - 1) >> 3;
-
- switch (len & (8 - 1)) {
- case 0:
- do {
- HASHC;
- /* FALLTHROUGH */
- case 7:
- HASHC;
- /* FALLTHROUGH */
- case 6:
- HASHC;
- /* FALLTHROUGH */
- case 5:
- HASHC;
- /* FALLTHROUGH */
- case 4:
- HASHC;
- /* FALLTHROUGH */
- case 3:
- HASHC;
- /* FALLTHROUGH */
- case 2:
- HASHC;
- /* FALLTHROUGH */
- case 1:
- HASHC;
- } while (--loop);
- }
- }
- return (h);
-}
-
-/* Hash function from Chris Torek. */
-static u_int32_t
-hash4(keyarg, len)
- const void *keyarg;
- size_t len;
-{
- const u_char *key;
- size_t loop;
- u_int32_t h;
-
-#define HASH4a h = (h << 5) - h + *key++;
-#define HASH4b h = (h << 5) + h + *key++;
-#define HASH4 HASH4b
-
- h = 0;
- key = keyarg;
- if (len > 0) {
- loop = (len + 8 - 1) >> 3;
-
- switch (len & (8 - 1)) {
- case 0:
- do {
- HASH4;
- /* FALLTHROUGH */
- case 7:
- HASH4;
- /* FALLTHROUGH */
- case 6:
- HASH4;
- /* FALLTHROUGH */
- case 5:
- HASH4;
- /* FALLTHROUGH */
- case 4:
- HASH4;
- /* FALLTHROUGH */
- case 3:
- HASH4;
- /* FALLTHROUGH */
- case 2:
- HASH4;
- /* FALLTHROUGH */
- case 1:
- HASH4;
- } while (--loop);
- }
- }
- return (h);
-}