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 */ 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 */ 44 static __inline uint32_t 45 hash32_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 */ 58 static __inline uint32_t 59 hash32_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 */ 72 static __inline uint32_t 73 hash32_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 */ 88 static __inline uint32_t 89 hash32_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 */ 107 static __inline uint32_t 108 hash32_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 #endif /* !_SYS_HASH_H_ */ 123