1 /*-
2 * Copyright (c) 2001 Tobias Weingartner
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 * $OpenBSD: hash.h,v 1.4 2004/05/25 18:37:23 jmc Exp $
26 * $FreeBSD: src/sys/sys/hash.h,v 1.3 2007/04/09 22:55:14 thompsa Exp $
27 * $Id: hash.h 268 2011-07-10 16:36:17Z ivoras $
28 */
29
30 #ifndef _SYS_HASH_H_
31 #define _SYS_HASH_H_
32
33 #ifndef uint32_t
34 #define uint32_t unsigned int
35 #endif
36
37 /* Convenience */
38 #ifndef HASHINIT
39 #define HASHINIT 5381
40 #define HASHSTEP(x,c) (((x << 5) + x) + (c))
41 #endif
42
43 /*
44 * Return a 32-bit hash of the given buffer. The "hash"
45 * argument should be HASHINIT, or the previous hash value to extend
46 * the previous hash.
47 */
48 static inline uint32_t
hash32_raw_buf(const void * buf,size_t len,uint32_t hash)49 hash32_raw_buf(const void *buf, size_t len, uint32_t hash)
50 {
51 const unsigned char *p = (const unsigned char *) buf;
52
53 while (len--)
54 hash = HASHSTEP(hash, *p++);
55
56 return hash;
57 }
58
59
60 static inline uint32_t
hash32_buf(const void * buf,size_t len)61 hash32_buf(const void *buf, size_t len)
62 {
63 const unsigned char *p = (const unsigned char*) buf;
64 uint32_t hash = HASHINIT;
65
66 while (len--)
67 hash = HASHSTEP(hash, *p++);
68
69 return hash;
70 }
71
72
73 /*
74 * Return a 32-bit hash of the given string.
75 */
76 static inline uint32_t
hash32_str(const void * buf,uint32_t hash)77 hash32_str(const void *buf, uint32_t hash)
78 {
79 const unsigned char *p = (const unsigned char*) buf;
80
81 while (*p)
82 hash = HASHSTEP(hash, *p++);
83
84 return hash;
85 }
86
87 /*
88 * Return a 32-bit hash of the given string, limited by N.
89 */
90 static inline uint32_t
hash32_strn(const void * buf,size_t len,uint32_t hash)91 hash32_strn(const void *buf, size_t len, uint32_t hash)
92 {
93 const unsigned char *p = (const unsigned char *) buf;
94
95 while (*p && len--)
96 hash = HASHSTEP(hash, *p++);
97
98 return hash;
99 }
100
101 /*
102 * Return a 32-bit hash of the given string terminated by C,
103 * (as well as 0). This is mainly here as a helper for the
104 * namei() hashing of path name parts.
105 */
106 static inline uint32_t
hash32_stre(const void * buf,int end,const unsigned char ** ep,uint32_t hash)107 hash32_stre(const void *buf, int end, const unsigned char **ep, uint32_t hash)
108 {
109 const unsigned char *p = (const unsigned char*) buf;
110
111 while (*p && (*p != end))
112 hash = HASHSTEP(hash, *p++);
113
114 if (ep)
115 *ep = p;
116
117 return hash;
118 }
119
120 /*
121 * Return a 32-bit hash of the given string, limited by N,
122 * and terminated by C (as well as 0). This is mainly here
123 * as a helper for the namei() hashing of path name parts.
124 */
125 static inline uint32_t
hash32_strne(const void * buf,size_t len,int end,const unsigned char ** ep,uint32_t hash)126 hash32_strne(const void *buf, size_t len, int end, const unsigned char **ep,
127 uint32_t hash)
128 {
129 const unsigned char *p = (const unsigned char*) buf;
130
131 while (*p && (*p != end) && len--)
132 hash = HASHSTEP(hash, *p++);
133
134 if (ep)
135 *ep = p;
136
137 return hash;
138 }
139 #endif /* !_SYS_HASH_H_ */
140