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