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.2

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: 
1.2     ! moko       64: #include "pa_sdbm.h"
1.1       paf        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: }