1*8fbb14c0Sjoris /* $OpenBSD: hash_func.c,v 1.1 2008/06/21 15:39:15 joris Exp $ */
2*8fbb14c0Sjoris
3*8fbb14c0Sjoris /*-
4*8fbb14c0Sjoris * Copyright (c) 1990, 1993
5*8fbb14c0Sjoris * The Regents of the University of California. All rights reserved.
6*8fbb14c0Sjoris *
7*8fbb14c0Sjoris * This code is derived from software contributed to Berkeley by
8*8fbb14c0Sjoris * Margo Seltzer.
9*8fbb14c0Sjoris *
10*8fbb14c0Sjoris * Redistribution and use in source and binary forms, with or without
11*8fbb14c0Sjoris * modification, are permitted provided that the following conditions
12*8fbb14c0Sjoris * are met:
13*8fbb14c0Sjoris * 1. Redistributions of source code must retain the above copyright
14*8fbb14c0Sjoris * notice, this list of conditions and the following disclaimer.
15*8fbb14c0Sjoris * 2. Redistributions in binary form must reproduce the above copyright
16*8fbb14c0Sjoris * notice, this list of conditions and the following disclaimer in the
17*8fbb14c0Sjoris * documentation and/or other materials provided with the distribution.
18*8fbb14c0Sjoris * 3. Neither the name of the University nor the names of its contributors
19*8fbb14c0Sjoris * may be used to endorse or promote products derived from this software
20*8fbb14c0Sjoris * without specific prior written permission.
21*8fbb14c0Sjoris *
22*8fbb14c0Sjoris * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23*8fbb14c0Sjoris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24*8fbb14c0Sjoris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25*8fbb14c0Sjoris * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26*8fbb14c0Sjoris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27*8fbb14c0Sjoris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28*8fbb14c0Sjoris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29*8fbb14c0Sjoris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30*8fbb14c0Sjoris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31*8fbb14c0Sjoris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32*8fbb14c0Sjoris * SUCH DAMAGE.
33*8fbb14c0Sjoris */
34*8fbb14c0Sjoris
35*8fbb14c0Sjoris #include <sys/types.h>
36*8fbb14c0Sjoris #include <sys/queue.h>
37*8fbb14c0Sjoris
38*8fbb14c0Sjoris #include "hash.h"
39*8fbb14c0Sjoris
40*8fbb14c0Sjoris /* Chris Torek's hash function. */
41*8fbb14c0Sjoris u_int32_t
hash4(const char * key,size_t len)42*8fbb14c0Sjoris hash4(const char *key, size_t len)
43*8fbb14c0Sjoris {
44*8fbb14c0Sjoris u_int32_t h, loop;
45*8fbb14c0Sjoris const char *k;
46*8fbb14c0Sjoris
47*8fbb14c0Sjoris #define HASH4 h = (h << 5) + h + *k++;
48*8fbb14c0Sjoris
49*8fbb14c0Sjoris h = 0;
50*8fbb14c0Sjoris k = key;
51*8fbb14c0Sjoris if (len > 0) {
52*8fbb14c0Sjoris loop = (len + 8 - 1) >> 3;
53*8fbb14c0Sjoris
54*8fbb14c0Sjoris switch (len & (8 - 1)) {
55*8fbb14c0Sjoris case 0:
56*8fbb14c0Sjoris do { /* All fall throughs */
57*8fbb14c0Sjoris HASH4;
58*8fbb14c0Sjoris case 7:
59*8fbb14c0Sjoris HASH4;
60*8fbb14c0Sjoris case 6:
61*8fbb14c0Sjoris HASH4;
62*8fbb14c0Sjoris case 5:
63*8fbb14c0Sjoris HASH4;
64*8fbb14c0Sjoris case 4:
65*8fbb14c0Sjoris HASH4;
66*8fbb14c0Sjoris case 3:
67*8fbb14c0Sjoris HASH4;
68*8fbb14c0Sjoris case 2:
69*8fbb14c0Sjoris HASH4;
70*8fbb14c0Sjoris case 1:
71*8fbb14c0Sjoris HASH4;
72*8fbb14c0Sjoris } while (--loop);
73*8fbb14c0Sjoris }
74*8fbb14c0Sjoris
75*8fbb14c0Sjoris }
76*8fbb14c0Sjoris return (h);
77*8fbb14c0Sjoris }
78