sys/sys/hash.h

   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  */
  45 static __inline uint32_t
  46 hash32_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  */
  59 static __inline uint32_t
  60 hash32_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  */
  73 static __inline uint32_t
  74 hash32_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  */
  89 static __inline uint32_t
  90 hash32_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  */
 108 static __inline uint32_t
 109 hash32_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  */
 127 uint32_t jenkins_hash(const void *, size_t, uint32_t);
 128 uint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t);
 129
 130 uint32_t murmur3_32_hash(const void *, size_t, uint32_t);
 131 uint32_t murmur3_32_hash32(const uint32_t *, size_t, uint32_t);
 132
 133 #endif /* _KERNEL */
 134
 135 #endif /* !_SYS_HASH_H_ */