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$ 27 */ 28 29#ifndef _SYS_HASH_H_ 30#define _SYS_HASH_H_ 31#include <sys/types.h> 32 33/* Convenience */ 34#ifndef HASHINIT 35#define HASHINIT 5381 36#define HASHSTEP(x,c) (((x << 5) + x) + (c)) 37#endif 38 39/* 40 * Return a 32-bit hash of the given buffer. The init 41 * value should be 0, or the previous hash value to extend 42 * the previous hash. 43 */ 44static __inline uint32_t 45hash32_buf(const void *buf, size_t len, uint32_t hash) 46{ 47 const unsigned char *p = buf; 48 49 while (len--) 50 hash = HASHSTEP(hash, *p++); 51 52 return hash; 53} 54 55/* 56 * Return a 32-bit hash of the given string. 57 */ 58static __inline uint32_t 59hash32_str(const void *buf, uint32_t hash) 60{ 61 const unsigned char *p = buf; 62 63 while (*p) 64 hash = HASHSTEP(hash, *p++); 65 66 return hash; 67} 68 69/* 70 * Return a 32-bit hash of the given string, limited by N. 71 */ 72static __inline uint32_t 73hash32_strn(const void *buf, size_t len, uint32_t hash) 74{ 75 const unsigned char *p = buf; 76 77 while (*p && len--) 78 hash = HASHSTEP(hash, *p++); 79 80 return hash; 81} 82 83/* 84 * Return a 32-bit hash of the given string terminated by C, 85 * (as well as 0). This is mainly here as a helper for the 86 * namei() hashing of path name parts. 87 */ 88static __inline uint32_t 89hash32_stre(const void *buf, int end, const char **ep, uint32_t hash) 90{ 91 const unsigned char *p = buf; 92 93 while (*p && (*p != end)) 94 hash = HASHSTEP(hash, *p++); 95 96 if (ep) 97 *ep = p; 98 99 return hash; 100} 101 102/* 103 * Return a 32-bit hash of the given string, limited by N, 104 * and terminated by C (as well as 0). This is mainly here 105 * as a helper for the namei() hashing of path name parts. 106 */ 107static __inline uint32_t 108hash32_strne(const void *buf, size_t len, int end, const char **ep, 109 uint32_t hash) 110{ 111 const unsigned char *p = buf; 112 113 while (*p && (*p != end) && len--) 114 hash = HASHSTEP(hash, *p++); 115 116 if (ep) 117 *ep = p; 118 119 return hash; 120} 121 122#ifdef _KERNEL 123/* 124 * Hashing function from Bob Jenkins. Implementation in libkern/jenkins_hash.c. 125 */ 126uint32_t jenkins_hash(const void *, size_t, uint32_t); 127uint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t); 128 129uint32_t murmur3_aligned_32(const void *data, size_t len, uint32_t seed); 130 131#endif /* _KERNEL */ 132 133#endif /* !_SYS_HASH_H_ */ 134