sys/sys/hash.h

   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_ */