Index: uspace/lib/c/include/adt/hash.h =================================================================== --- uspace/lib/c/include/adt/hash.h (revision c8fccf5b75e9757a8b5d17f388f8c4e32b8d1a07) +++ uspace/lib/c/include/adt/hash.h (revision c8fccf5b75e9757a8b5d17f388f8c4e32b8d1a07) @@ -0,0 +1,112 @@ +/* + * 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); + /* + * Lower order bits are mixed more thoroughly. Swap them with + * the higher order bits and make the resulting higher order bits + * more usable. + */ + return (hash << 32) | (hash >> 32); +} + +/** 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 Index: uspace/lib/c/include/adt/hash_table.h =================================================================== --- uspace/lib/c/include/adt/hash_table.h (revision 5b382774cede49c01f80b52156d1d7532b7dc182) +++ uspace/lib/c/include/adt/hash_table.h (revision c8fccf5b75e9757a8b5d17f388f8c4e32b8d1a07) @@ -1,4 +1,6 @@ /* * Copyright (c) 2006 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -39,30 +41,25 @@ #include #include +#include +/** Opaque hash table link type. */ +typedef struct ht_link { + link_t link; +} ht_link_t; /** Set of operations for hash table. */ typedef struct { - /** Returns the hash of the key stored in the item. - */ - size_t (*hash)(const link_t *item); + /** Returns the hash of the key stored in the item (ie its lookup key). */ + size_t (*hash)(const ht_link_t *item); - /** Returns the hash of the key. - */ - size_t (*key_hash)(unsigned long key[]); + /** Returns the hash of the key. */ + size_t (*key_hash)(void *key); - /** Hash table item match function. - * - * @param key Array of keys that will be compared with item. It is - * not necessary to pass all keys. - * - * @return True if the keys match, false otherwise. - * - */ - bool (*match)(unsigned long key[], size_t keys, const link_t *item); + /** True if the items are equal (have the same lookup keys). */ + bool (*equal)(const ht_link_t *item1, const ht_link_t *item2); - /** - */ - bool (*equal)(const link_t *item1, const link_t *item2); - + /** Returns true if the key is equal to the item's lookup key. */ + bool (*key_equal)(void *key, const ht_link_t *item); + /** Hash table item removal callback. * @@ -71,29 +68,36 @@ * @param item Item that was removed from the hash table. */ - void (*remove_callback)(link_t *item); + void (*remove_callback)(ht_link_t *item); } hash_table_ops_t; /** Hash table structure. */ typedef struct { + hash_table_ops_t *op; list_t *bucket; size_t bucket_cnt; - size_t max_keys; - size_t items; - hash_table_ops_t *op; + size_t full_item_cnt; + size_t item_cnt; + size_t max_load; + bool apply_ongoing; } hash_table_t; -#define hash_table_get_instance(item, type, member) \ - list_get_instance((item), type, member) +#define hash_table_get_inst(item, type, member) \ + member_to_inst((item), type, member) extern bool hash_table_create(hash_table_t *, size_t, size_t, hash_table_ops_t *); +extern void hash_table_destroy(hash_table_t *); + +extern bool hash_table_empty(hash_table_t *); +extern size_t hash_table_size(hash_table_t *); + extern void hash_table_clear(hash_table_t *); -extern void hash_table_insert(hash_table_t *, link_t *); -extern bool hash_table_insert_unique(hash_table_t *, link_t *); -extern link_t *hash_table_find(const hash_table_t *, unsigned long []); -extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t); -extern void hash_table_remove_item(hash_table_t *, link_t *); -extern void hash_table_destroy(hash_table_t *); -extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *), +extern void hash_table_insert(hash_table_t *, ht_link_t *); +extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *); +extern ht_link_t *hash_table_find(const hash_table_t *, void *); +extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *); +extern size_t hash_table_remove(hash_table_t *, void *); +extern void hash_table_remove_item(hash_table_t *, ht_link_t *); +extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *), void *); Index: uspace/lib/c/include/adt/list.h =================================================================== --- uspace/lib/c/include/adt/list.h (revision 5b382774cede49c01f80b52156d1d7532b7dc182) +++ uspace/lib/c/include/adt/list.h (revision c8fccf5b75e9757a8b5d17f388f8c4e32b8d1a07) @@ -105,4 +105,10 @@ assert(((link)->prev == NULL) && ((link)->next == NULL)) +/** Returns true if the link is definitely part of a list. False if not sure. */ +static inline int link_in_use(link_t *link) +{ + return link->prev != NULL && link->next != NULL; +} + /** Initialize doubly-linked circular list link *