Return to sdbm_hash.c CVS log

Up to [parser3project] / parser3 / src / lib / sdbm

Annotation of parser3/src/lib/sdbm/sdbm_hash.c, revision 1.1

1.1     ! paf         1: /* ====================================================================
        !             2:  * The Apache Software License, Version 1.1
        !             3:  *
        !             4:  * Copyright (c) 2000-2002 The Apache Software Foundation.  All rights
        !             5:  * reserved.
        !             6:  *
        !             7:  * Redistribution and use in source and binary forms, with or without
        !             8:  * modification, are permitted provided that the following conditions
        !             9:  * are met:
        !            10:  *
        !            11:  * 1. Redistributions of source code must retain the above copyright
        !            12:  *    notice, this list of conditions and the following disclaimer.
        !            13:  *
        !            14:  * 2. Redistributions in binary form must reproduce the above copyright
        !            15:  *    notice, this list of conditions and the following disclaimer in
        !            16:  *    the documentation and/or other materials provided with the
        !            17:  *    distribution.
        !            18:  *
        !            19:  * 3. The end-user documentation included with the redistribution,
        !            20:  *    if any, must include the following acknowledgment:
        !            21:  *       "This product includes software developed by the
        !            22:  *        Apache Software Foundation (http://www.apache.org/)."
        !            23:  *    Alternately, this acknowledgment may appear in the software itself,
        !            24:  *    if and wherever such third-party acknowledgments normally appear.
        !            25:  *
        !            26:  * 4. The names "Apache" and "Apache Software Foundation" must
        !            27:  *    not be used to endorse or promote products derived from this
        !            28:  *    software without prior written permission. For written
        !            29:  *    permission, please contact apache@apache.org.
        !            30:  *
        !            31:  * 5. Products derived from this software may not be called "Apache",
        !            32:  *    nor may "Apache" appear in their name, without prior written
        !            33:  *    permission of the Apache Software Foundation.
        !            34:  *
        !            35:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
        !            36:  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
        !            37:  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
        !            38:  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
        !            39:  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
        !            40:  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
        !            41:  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
        !            42:  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
        !            43:  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
        !            44:  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
        !            45:  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
        !            46:  * SUCH DAMAGE.
        !            47:  * ====================================================================
        !            48:  *
        !            49:  * This software consists of voluntary contributions made by many
        !            50:  * individuals on behalf of the Apache Software Foundation.  For more
        !            51:  * information on the Apache Software Foundation, please see
        !            52:  * <http://www.apache.org/>.
        !            53:  */
        !            54: 
        !            55: /*
        !            56:  * sdbm - ndbm work-alike hashed database library
        !            57:  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
        !            58:  * author: oz@nexus.yorku.ca
        !            59:  * status: ex-public domain. keep it that way.
        !            60:  *
        !            61:  * hashing routine
        !            62:  */
        !            63: 
        !            64: #include "apr_sdbm.h"
        !            65: #include "sdbm_private.h"
        !            66: 
        !            67: /*
        !            68:  * polynomial conversion ignoring overflows
        !            69:  * [this seems to work remarkably well, in fact better
        !            70:  * then the ndbm hash function. Replace at your own risk]
        !            71:  * use: 65599  nice.
        !            72:  *      65587   even better. 
        !            73:  */
        !            74: long sdbm_hash(const char *str, int len)
        !            75: {
        !            76:        register unsigned long n = 0;
        !            77: 
        !            78: #define DUFF   /* go ahead and use the loop-unrolled version */
        !            79: #ifdef DUFF
        !            80: 
        !            81: #define HASHC  n = *str++ + 65599 * n
        !            82: 
        !            83:        if (len > 0) {
        !            84:                register int loop = (len + 8 - 1) >> 3;
        !            85: 
        !            86:                switch(len & (8 - 1)) {
        !            87:                case 0: do {
        !            88:                        HASHC;  case 7: HASHC;
        !            89:                case 6: HASHC;  case 5: HASHC;
        !            90:                case 4: HASHC;  case 3: HASHC;
        !            91:                case 2: HASHC;  case 1: HASHC;
        !            92:                        } while (--loop);
        !            93:                }
        !            94: 
        !            95:        }
        !            96: #else
        !            97:        while (len--)
        !            98:                n = *str++ + 65599 * n;
        !            99: #endif
        !           100:        return n;
        !           101: }