Index: kernel/generic/include/adt/cht.h =================================================================== --- kernel/generic/include/adt/cht.h (revision 3bb732b6ee1465b9afefb77533296351b0cb71ab) +++ kernel/generic/include/adt/cht.h (revision 3bb732b6ee1465b9afefb77533296351b0cb71ab) @@ -0,0 +1,99 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup genericadt + * @{ + */ +/** @file + */ + +#ifndef KERN_CONC_HASH_TABLE_H_ +#define KERN_CONC_HASH_TABLE_H_ + +#include +#include +#include +#include + +typedef uintptr_t cht_ptr_t; + +/** Concurrent hash table node link. */ +typedef struct cht_link { + /* Must be placed first. */ + rcu_item_t rcu_link; + /** Link to the next item in the bucket including any marks. */ + cht_ptr_t link; +} cht_link_t; + +/** Set of operations for a concurrent hash table. */ +typedef struct cht_ops { + size_t (*hash)(cht_link_t *node); + size_t (*key_hash)(void *key); + bool (*equal)(const cht_link_t *item1, const cht_link_t *item2); + bool (*key_equal)(void *key, const cht_link_t *item); + void (*remove_callback)(cht_link_t *item); +} cht_ops_t; + + +typedef struct cht_buckets { + size_t order; + cht_ptr_t head[1]; +} cht_buckets_t; + +/** Concurrent hash table structure. */ +typedef struct { + cht_ops_t *op; + + cht_buckets_t *b; + cht_buckets_t *new_b; + + atomic_t resize_reqs; + atomic_t item_cnt; +} cht_t; + +#define cht_get_inst(item, type, member) \ + member_to_inst((item), type, member) + + +#define cht_read_lock() rcu_read_lock() +#define cht_read_unlock() rcu_read_unlock() + +extern void cht_create(cht_t *h, size_t init_size, cht_ops_t *op); +extern void cht_destroy(cht_t *h); + +extern cht_link_t *cht_find(cht_t *h, void *key); +extern cht_link_t *cht_find_lazy(cht_t *h, void *key); +extern void cht_insert(cht_t *h, cht_link_t *item); +extern bool cht_insert_unique(cht_t *h, cht_link_t *item); +extern size_t cht_remove_key(cht_t *h, void *key); +extern bool cht_remove_item(cht_t *h, cht_link_t *item); + +#endif + +/** @} + */ Index: kernel/generic/include/adt/hash.h =================================================================== --- kernel/generic/include/adt/hash.h (revision 3bb732b6ee1465b9afefb77533296351b0cb71ab) +++ kernel/generic/include/adt/hash.h (revision 3bb732b6ee1465b9afefb77533296351b0cb71ab) @@ -0,0 +1,109 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup genericadt + * @{ + */ +/** @file + */ +#ifndef KERN_HASH_H_ +#define KERN_HASH_H_ + +#include + +/** Produces a uniform hash affecting all output bits from the skewed input. + */ +static inline uint32_t hash_mix32(uint32_t hash) +{ + /* + * Thomas Wang's modification of Bob Jenkin's hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + * Public domain. + */ + hash = ~hash + (hash << 15); + hash = hash ^ (hash >> 12); + hash = hash + (hash << 2); + hash = hash ^ (hash >> 4); + hash = hash * 2057; + hash = hash ^ (hash >> 16); + return hash; +} + +/** Produces a uniform hash affecting all output bits from the skewed input. + */ +static inline uint64_t hash_mix64(uint64_t hash) +{ + /* + * Thomas Wang's public domain 64-bit hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + */ + hash = (hash ^ 61) ^ (hash >> 16); + hash = hash + (hash << 3); + hash = hash ^ (hash >> 4); + hash = hash * 0x27d4eb2d; + hash = hash ^ (hash >> 15); +} + +/** Produces a uniform hash affecting all output bits from the skewed input. + */ +static inline size_t hash_mix(size_t hash) +{ +#ifdef __32_BITS__ + return hash_mix32(hash); +#elif defined(__64_BITS__) + return hash_mix64(hash); +#else +#error Unknown size_t size - cannot select proper hash mix function. +#endif +} + +/** Use to create a hash from multiple values. + * + * Typical usage: + * @code + * int car_id; + * bool car_convertible; + * // .. + * size_t hash = 0; + * hash = hash_combine(hash, car_id); + * hash = hash_combine(hash, car_convertible); + * // Now use hash as a hash of both car_id and car_convertible. + * @endcode + */ +static inline size_t hash_combine(size_t seed, size_t hash) +{ + /* + * todo: use Bob Jenkin's proper mixing hash pass: + * http://burtleburtle.net/bob/c/lookup3.c + */ + seed ^= hash + 0x9e3779b9 + + ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5))); + return seed; +} + +#endif