4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * IPRT - Internal header containing inline string hashing functions.
c58f1213e628a545081c70e26c6b67a841cff880vboxsync * Copyright (C) 2006-2012 Oracle Corporation
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * available from http://www.virtualbox.org. This file is free software;
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * you can redistribute it and/or modify it under the terms of the GNU
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * General Public License (GPL) as published by the Free Software
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * The contents of this file may alternatively be used under the terms
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * of the Common Development and Distribution License Version 1.0
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * VirtualBox OSE distribution, in which case the provisions of the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * CDDL are applicable instead of those of the GPL.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * You may elect to license modified versions of this file under the
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * terms and conditions of either the GPL or the CDDL or both.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync This algorithm was created for sdbm (a public-domain reimplementation of
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync ndbm) database library. it was found to do well in scrambling bits,
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync causing better distribution of the keys and fewer splits. it also happens
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync to be a good general hashing function with good distribution. the actual
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync is the faster version used in gawk. [there is even a faster, duff-device
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync version] the magic constant 65599 was picked out of thin air while
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync experimenting with different constants, and turns out to be a prime.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync this is one of the algorithms used in berkeley db (see sleepycat) and
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync elsewhere. */
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Hash string, return hash + length.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsyncDECLINLINE(uint32_t) sdbm(const char *str, size_t *pcch)
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync while ((c = *pu8++))
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Hash up to N bytes, return hash + hashed length.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsyncDECLINLINE(uint32_t) sdbmN(const char *str, size_t cchMax, size_t *pcch)
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync * Incremental hashing.
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsyncDECLINLINE(uint32_t) sdbmInc(const char *str, uint32_t hash)
4f4877d6f6ea6dbe54cba4595450e5c837d5d419vboxsync while ((c = *pu8++))
8eef848e08a61236c40d1d8b48c4df49b157aac1vboxsync * Incremental hashing with length limitation.