Annotation of sys/sys/hash.h, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: hash.h,v 1.4 2004/05/25 18:37:23 jmc Exp $ */
! 2:
! 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:
! 28: #ifndef _SYS_HASH_H_
! 29: #define _SYS_HASH_H_
! 30: #include <sys/types.h>
! 31:
! 32: /*
! 33: * Note: SMALL_KERNEL might be used to shrink these, right now I
! 34: * do not see the point, as my kernel did not grow appreciably when
! 35: * I switched to these from other inline code. This may have to be
! 36: * revisited when/if these functions become more prevalent in the
! 37: * kernel.
! 38: */
! 39:
! 40: /* Convenience */
! 41: #ifndef HASHINIT
! 42: #define HASHINIT 5381
! 43: #define HASHSTEP(x,c) (((x << 5) + x) + (c))
! 44: #endif
! 45:
! 46: /*
! 47: * Return a 32-bit hash of the given buffer. The init
! 48: * value should be 0, or the previous hash value to extend
! 49: * the previous hash.
! 50: */
! 51: static __inline uint32_t
! 52: hash32_buf(const void *buf, size_t len, uint32_t hash)
! 53: {
! 54: const unsigned char *p = buf;
! 55:
! 56: while (len--)
! 57: hash = HASHSTEP(hash, *p++);
! 58:
! 59: return hash;
! 60: }
! 61:
! 62: /*
! 63: * Return a 32-bit hash of the given string.
! 64: */
! 65: static __inline uint32_t
! 66: hash32_str(const void *buf, uint32_t hash)
! 67: {
! 68: const unsigned char *p = buf;
! 69:
! 70: while (*p)
! 71: hash = HASHSTEP(hash, *p++);
! 72:
! 73: return hash;
! 74: }
! 75:
! 76: /*
! 77: * Return a 32-bit hash of the given string, limited by N.
! 78: */
! 79: static __inline uint32_t
! 80: hash32_strn(const void *buf, size_t len, uint32_t hash)
! 81: {
! 82: const unsigned char *p = buf;
! 83:
! 84: while (*p && len--)
! 85: hash = HASHSTEP(hash, *p++);
! 86:
! 87: return hash;
! 88: }
! 89:
! 90: /*
! 91: * Return a 32-bit hash of the given string terminated by C,
! 92: * (as well as 0). This is mainly here as a helper for the
! 93: * namei() hashing of path name parts.
! 94: */
! 95: static __inline uint32_t
! 96: hash32_stre(const void *buf, int end, char **ep, uint32_t hash)
! 97: {
! 98: const unsigned char *p = buf;
! 99:
! 100: while (*p && (*p != end))
! 101: hash = HASHSTEP(hash, *p++);
! 102:
! 103: if (ep)
! 104: *ep = (char *)p;
! 105:
! 106: return hash;
! 107: }
! 108:
! 109: /*
! 110: * Return a 32-bit hash of the given string, limited by N,
! 111: * and terminated by C (as well as 0). This is mainly here
! 112: * as a helper for the namei() hashing of path name parts.
! 113: */
! 114: static __inline uint32_t
! 115: hash32_strne(const void *buf, size_t len, int end, char **ep, uint32_t hash)
! 116: {
! 117: const unsigned char *p = buf;
! 118:
! 119: while (*p && (*p != end) && len--)
! 120: hash = HASHSTEP(hash, *p++);
! 121:
! 122: if (ep)
! 123: *ep = (char *)p;
! 124:
! 125: return hash;
! 126: }
! 127: #endif /* !_SYS_HASH_H_ */
CVSweb