The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/sys/hash.h

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: cac62436f968788a1e2ca5ec21089218


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.