Annotation of sys/sys/hash.h, Revision 1.1.1.1
1.1 nbrk 1: /* $OpenBSD: hash.h,v 1.4 2004/05/25 18:37:23 jmc Exp $ */
2:
3: /*
4: * Copyright (c) 2001 Tobias Weingartner
5: * All rights 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: * 1. Redistributions of source code must retain the above copyright
11: * notice, this list of conditions and the following disclaimer.
12: * 2. Redistributions in binary form must reproduce the above copyright
13: * notice, this list of conditions and the following disclaimer in the
14: * documentation and/or other materials provided with the distribution.
15: *
16: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26: */
27:
28: #ifndef _SYS_HASH_H_
29: #define _SYS_HASH_H_
30: #include <sys/types.h>
31:
32: /*
33: * Note: SMALL_KERNEL might be used to shrink these, right now I
34: * do not see the point, as my kernel did not grow appreciably when
35: * I switched to these from other inline code. This may have to be
36: * revisited when/if these functions become more prevalent in the
37: * kernel.
38: */
39:
40: /* Convenience */
41: #ifndef HASHINIT
42: #define HASHINIT 5381
43: #define HASHSTEP(x,c) (((x << 5) + x) + (c))
44: #endif
45:
46: /*
47: * Return a 32-bit hash of the given buffer. The init
48: * value should be 0, or the previous hash value to extend
49: * the previous hash.
50: */
51: static __inline uint32_t
52: hash32_buf(const void *buf, size_t len, uint32_t hash)
53: {
54: const unsigned char *p = buf;
55:
56: while (len--)
57: hash = HASHSTEP(hash, *p++);
58:
59: return hash;
60: }
61:
62: /*
63: * Return a 32-bit hash of the given string.
64: */
65: static __inline uint32_t
66: hash32_str(const void *buf, uint32_t hash)
67: {
68: const unsigned char *p = buf;
69:
70: while (*p)
71: hash = HASHSTEP(hash, *p++);
72:
73: return hash;
74: }
75:
76: /*
77: * Return a 32-bit hash of the given string, limited by N.
78: */
79: static __inline uint32_t
80: hash32_strn(const void *buf, size_t len, uint32_t hash)
81: {
82: const unsigned char *p = buf;
83:
84: while (*p && len--)
85: hash = HASHSTEP(hash, *p++);
86:
87: return hash;
88: }
89:
90: /*
91: * Return a 32-bit hash of the given string terminated by C,
92: * (as well as 0). This is mainly here as a helper for the
93: * namei() hashing of path name parts.
94: */
95: static __inline uint32_t
96: hash32_stre(const void *buf, int end, char **ep, uint32_t hash)
97: {
98: const unsigned char *p = buf;
99:
100: while (*p && (*p != end))
101: hash = HASHSTEP(hash, *p++);
102:
103: if (ep)
104: *ep = (char *)p;
105:
106: return hash;
107: }
108:
109: /*
110: * Return a 32-bit hash of the given string, limited by N,
111: * and terminated by C (as well as 0). This is mainly here
112: * as a helper for the namei() hashing of path name parts.
113: */
114: static __inline uint32_t
115: hash32_strne(const void *buf, size_t len, int end, char **ep, uint32_t hash)
116: {
117: const unsigned char *p = buf;
118:
119: while (*p && (*p != end) && len--)
120: hash = HASHSTEP(hash, *p++);
121:
122: if (ep)
123: *ep = (char *)p;
124:
125: return hash;
126: }
127: #endif /* !_SYS_HASH_H_ */
CVSweb