Return to hash.h CVS log

Up to [local] / sys / sys

Annotation of sys/sys/hash.h, Revision 1.1.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_ */