contrib/apr-util/dbm/sdbm/sdbm_hash.c

   1 /* Licensed to the Apache Software Foundation (ASF) under one or more
   2  * contributor license agreements.  See the NOTICE file distributed with
   3  * this work for additional information regarding copyright ownership.
   4  * The ASF licenses this file to You under the Apache License, Version 2.0
   5  * (the "License"); you may not use this file except in compliance with
   6  * the License.  You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /*
  18  * sdbm - ndbm work-alike hashed database library
  19  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
  20  * author: oz@nexus.yorku.ca
  21  * status: ex-public domain. keep it that way.
  22  *
  23  * hashing routine
  24  */
  25
  26 #include "apr_sdbm.h"
  27 #include "sdbm_private.h"
  28
  29 /*
  30  * polynomial conversion ignoring overflows
  31  * [this seems to work remarkably well, in fact better
  32  * then the ndbm hash function. Replace at your own risk]
  33  * use: 65599   nice.
  34  *      65587   even better.
  35  */
  36 long sdbm_hash(const char *str, int len)
  37 {
  38         register unsigned long n = 0;
  39
  40 #define DUFF    /* go ahead and use the loop-unrolled version */
  41 #ifdef DUFF
  42
  43 #define HASHC   n = *str++ + 65599 * n
  44
  45         if (len > 0) {
  46                 register int loop = (len + 8 - 1) >> 3;
  47
  48                 switch(len & (8 - 1)) {
  49                 case 0: do {
  50                         HASHC;  case 7: HASHC;
  51                 case 6: HASHC;  case 5: HASHC;
  52                 case 4: HASHC;  case 3: HASHC;
  53                 case 2: HASHC;  case 1: HASHC;
  54                         } while (--loop);
  55                 }
  56
  57         }
  58 #else
  59         while (len--)
  60                 n = *str++ + 65599 * n;
  61 #endif
  62         return n;
  63 }