Index: uspace/lib/c/include/adt/hash.h =================================================================== --- uspace/lib/c/include/adt/hash.h (revision 2708f6aa00d00b5d4b4fa38d184dbe4b24ff32f1) +++ uspace/lib/c/include/adt/hash.h (revision 2708f6aa00d00b5d4b4fa38d184dbe4b24ff32f1) @@ -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_set.h =================================================================== --- uspace/lib/c/include/adt/hash_set.h (revision 111d2d6731b1fbc5a2181c92094ca7b8dbaf9d2f) +++ (revision ) @@ -1,84 +1,0 @@ -/* - * Copyright (c) 2006 Jakub Jermar - * Copyright (c) 2011 Radim Vansa - * 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 libc - * @{ - */ -/** @file - */ - -#ifndef LIBC_HASH_SET_H_ -#define LIBC_HASH_SET_H_ - -#include -#include - -#define HASH_SET_MIN_SIZE 8 - -typedef unsigned long (*hash_set_hash)(const link_t *); -typedef int (*hash_set_equals)(const link_t *, const link_t *); - -/** Hash table structure. */ -typedef struct { - list_t *table; - - /** Current table size */ - size_t size; - - /** - * Current number of entries. If count > size, - * the table is rehashed into table with double - * size. If (4 * count < size) && (size > min_size), - * the table is rehashed into table with half the size. - */ - size_t count; - - /** Hash function */ - hash_set_hash hash; - - /** Hash table item equals function */ - hash_set_equals equals; -} hash_set_t; - -extern int hash_set_init(hash_set_t *, hash_set_hash, hash_set_equals, size_t); -extern int hash_set_insert(hash_set_t *, link_t *); -extern link_t *hash_set_find(hash_set_t *, const link_t *); -extern int hash_set_contains(const hash_set_t *, const link_t *); -extern size_t hash_set_count(const hash_set_t *); -extern link_t *hash_set_remove(hash_set_t *, const link_t *); -extern void hash_set_remove_selected(hash_set_t *, - int (*)(link_t *, void *), void *); -extern void hash_set_destroy(hash_set_t *); -extern void hash_set_apply(hash_set_t *, void (*)(link_t *, void *), void *); -extern void hash_set_clear(hash_set_t *, void (*)(link_t *, void *), void *); - -#endif - -/** @} - */ Index: uspace/lib/c/include/adt/hash_table.h =================================================================== --- uspace/lib/c/include/adt/hash_table.h (revision 111d2d6731b1fbc5a2181c92094ca7b8dbaf9d2f) +++ uspace/lib/c/include/adt/hash_table.h (revision 2708f6aa00d00b5d4b4fa38d184dbe4b24ff32f1) @@ -1,4 +1,6 @@ /* * Copyright (c) 2006 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * * All rights reserved. * @@ -39,58 +41,65 @@ #include #include +#include -typedef unsigned long hash_count_t; -typedef unsigned long hash_index_t; +/** Opaque hash table link type. */ +typedef struct ht_link { + link_t link; +} ht_link_t; /** Set of operations for hash table. */ typedef struct { - /** Hash function. - * - * @param key Array of keys needed to compute hash index. - * All keys must be passed. - * - * @return Index into hash table. - * - */ - hash_index_t (*hash)(unsigned long key[]); + /** Returns the hash of the key stored in the item (ie its lookup key). */ + size_t (*hash)(const ht_link_t *item); - /** Hash table item comparison 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. - * - */ - int (*compare)(unsigned long key[], hash_count_t keys, link_t *item); + /** Returns the hash of the key. */ + size_t (*key_hash)(void *key); + /** True if the items are equal (have the same lookup keys). */ + bool (*equal)(const ht_link_t *item1, const ht_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. + * + * Must not invoke any mutating functions of the hash table. * * @param item Item that was removed from the hash table. - * */ - void (*remove_callback)(link_t *item); -} hash_table_operations_t; + void (*remove_callback)(ht_link_t *item); +} hash_table_ops_t; /** Hash table structure. */ typedef struct { - list_t *entry; - hash_count_t entries; - hash_count_t max_keys; - hash_table_operations_t *op; + hash_table_ops_t *op; + list_t *bucket; + size_t bucket_cnt; + 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 *, hash_count_t, hash_count_t, - hash_table_operations_t *); +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 *, unsigned long [], link_t *); -extern link_t *hash_table_find(hash_table_t *, unsigned long []); -extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t); -extern void hash_table_destroy(hash_table_t *); -extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *), - 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 *); + #endif Index: uspace/lib/c/include/adt/list.h =================================================================== --- uspace/lib/c/include/adt/list.h (revision 111d2d6731b1fbc5a2181c92094ca7b8dbaf9d2f) +++ uspace/lib/c/include/adt/list.h (revision 2708f6aa00d00b5d4b4fa38d184dbe4b24ff32f1) @@ -71,6 +71,43 @@ iterator != &(list).head; iterator = iterator->next) +/** Unlike list_foreach(), allows removing items while traversing a list. + * + * @code + * list_t mylist; + * typedef struct item { + * int value; + * link_t item_link; + * } item_t; + * + * //.. + * + * // Print each list element's value and remove the element from the list. + * list_foreach_safe(mylist, cur_link, next_link) { + * item_t *cur_item = list_get_instance(cur_link, item_t, item_link); + * printf("%d\n", cur_item->value); + * list_remove(cur_link); + * } + * @endcode + * + * @param list List to traverse. + * @param iterator Iterator to the current element of the list. + * The item this iterator points may be safely removed + * from the list. + * @param next_iter Iterator to the next element of the list. + */ +#define list_foreach_safe(list, iterator, next_iter) \ + for (link_t *iterator = (list).head.next, \ + *next_iter = iterator->next; \ + iterator != &(list).head; \ + iterator = next_iter, next_iter = iterator->next) + #define assert_link_not_used(link) \ 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 Index: uspace/lib/c/include/macros.h =================================================================== --- uspace/lib/c/include/macros.h (revision 111d2d6731b1fbc5a2181c92094ca7b8dbaf9d2f) +++ uspace/lib/c/include/macros.h (revision 2708f6aa00d00b5d4b4fa38d184dbe4b24ff32f1) @@ -52,4 +52,10 @@ | ((((uint64_t) (up)) & 0xffffffff) << 32)) +#ifndef member_to_inst +#define member_to_inst(ptr_member, type, member_identif) \ + ((type*) (((void*)(ptr_member)) - ((void*)&(((type*)0)->member_identif)))) +#endif + + #endif