Index: uspace/lib/libc/generic/adt/hash_table.c =================================================================== --- uspace/lib/libc/generic/adt/hash_table.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) +++ uspace/lib/libc/generic/adt/hash_table.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -0,0 +1,196 @@ +/* + * Copyright (c) 2008 Jakub Jermar + * 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 + */ + +/* + * This is an implementation of generic chained hash table. + */ + +#include +#include +#include +#include +#include +#include +#include + +/** Create chained hash table. + * + * @param h Hash table structure. Will be initialized by this call. + * @param m Number of hash table buckets. + * @param max_keys Maximal number of keys needed to identify an item. + * @param op Hash table operations structure. + * @return True on success + */ +int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, + hash_table_operations_t *op) +{ + hash_count_t i; + + assert(h); + assert(op && op->hash && op->compare); + assert(max_keys > 0); + + h->entry = malloc(m * sizeof(link_t)); + if (!h->entry) { + printf("cannot allocate memory for hash table\n"); + return false; + } + memset((void *) h->entry, 0, m * sizeof(link_t)); + + for (i = 0; i < m; i++) + list_initialize(&h->entry[i]); + + h->entries = m; + h->max_keys = max_keys; + h->op = op; + return true; +} + +/** Destroy a hash table instance. + * + * @param h Hash table to be destroyed. + */ +void hash_table_destroy(hash_table_t *h) +{ + assert(h); + assert(h->entry); + free(h->entry); +} + +/** Insert item into a hash table. + * + * @param h Hash table. + * @param key Array of all keys necessary to compute hash index. + * @param item Item to be inserted into the hash table. + */ +void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item) +{ + hash_index_t chain; + + assert(item); + assert(h && h->op && h->op->hash && h->op->compare); + + chain = h->op->hash(key); + assert(chain < h->entries); + + list_append(item, &h->entry[chain]); +} + +/** Search hash table for an item matching keys. + * + * @param h Hash table. + * @param key Array of all keys needed to compute hash index. + * + * @return Matching item on success, NULL if there is no such item. + */ +link_t *hash_table_find(hash_table_t *h, unsigned long key[]) +{ + link_t *cur; + hash_index_t chain; + + assert(h && h->op && h->op->hash && h->op->compare); + + chain = h->op->hash(key); + assert(chain < h->entries); + + for (cur = h->entry[chain].next; cur != &h->entry[chain]; + cur = cur->next) { + if (h->op->compare(key, h->max_keys, cur)) { + /* + * The entry is there. + */ + return cur; + } + } + + return NULL; +} + +/** Remove all matching items from hash table. + * + * For each removed item, h->remove_callback() is called. + * + * @param h Hash table. + * @param key Array of keys that will be compared against items of + * the hash table. + * @param keys Number of keys in the 'key' array. + */ +void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys) +{ + hash_index_t chain; + link_t *cur; + + assert(h && h->op && h->op->hash && h->op->compare && + h->op->remove_callback); + assert(keys <= h->max_keys); + + if (keys == h->max_keys) { + + /* + * All keys are known, hash_table_find() can be used to find the + * entry. + */ + + cur = hash_table_find(h, key); + if (cur) { + list_remove(cur); + h->op->remove_callback(cur); + } + return; + } + + /* + * Fewer keys were passed. + * Any partially matching entries are to be removed. + */ + for (chain = 0; chain < h->entries; chain++) { + for (cur = h->entry[chain].next; cur != &h->entry[chain]; + cur = cur->next) { + if (h->op->compare(key, keys, cur)) { + link_t *hlp; + + hlp = cur; + cur = cur->prev; + + list_remove(hlp); + h->op->remove_callback(hlp); + + continue; + } + } + } +} + +/** @} + */ Index: uspace/lib/libc/generic/adt/list.c =================================================================== --- uspace/lib/libc/generic/adt/list.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) +++ uspace/lib/libc/generic/adt/list.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2004 Jakub Jermar + * 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 + */ + +#include + + +/** Check for membership + * + * Check whether link is contained in the list head. + * The membership is defined as pointer equivalence. + * + * @param link Item to look for. + * @param head List to look in. + * + * @return true if link is contained in head, false otherwise. + * + */ +int list_member(const link_t *link, const link_t *head) +{ + int found = 0; + link_t *hlp = head->next; + + while (hlp != head) { + if (hlp == link) { + found = 1; + break; + } + hlp = hlp->next; + } + + return found; +} + + +/** Concatenate two lists + * + * Concatenate lists head1 and head2, producing a single + * list head1 containing items from both (in head1, head2 + * order) and empty list head2. + * + * @param head1 First list and concatenated output + * @param head2 Second list and empty output. + * + */ +void list_concat(link_t *head1, link_t *head2) +{ + if (list_empty(head2)) + return; + + head2->next->prev = head1->prev; + head2->prev->next = head1; + head1->prev->next = head2->next; + head1->prev = head2->prev; + list_initialize(head2); +} + + +/** Count list items + * + * Return the number of items in the list. + * + * @param link List to count. + * + * @return Number of items in the list. + * + */ +unsigned int list_count(const link_t *link) +{ + unsigned int count = 0; + link_t *hlp = link->next; + + while (hlp != link) { + count++; + hlp = hlp->next; + } + + return count; +} + +/** @} + */ Index: uspace/lib/libc/generic/async.c =================================================================== --- uspace/lib/libc/generic/async.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/generic/async.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -96,6 +96,6 @@ #include #include -#include -#include +#include +#include #include #include Index: uspace/lib/libc/generic/fibril.c =================================================================== --- uspace/lib/libc/generic/fibril.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/generic/fibril.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -34,5 +34,5 @@ */ -#include +#include #include #include Index: uspace/lib/libc/generic/io/io.c =================================================================== --- uspace/lib/libc/generic/io/io.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/generic/io/io.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -43,5 +43,5 @@ #include #include -#include +#include static FILE stdin_null = { Index: uspace/lib/libc/generic/ipc.c =================================================================== --- uspace/lib/libc/generic/ipc.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/generic/ipc.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -44,5 +44,5 @@ #include #include -#include +#include #include #include Index: uspace/lib/libc/generic/libadt/hash_table.c =================================================================== --- uspace/lib/libc/generic/libadt/hash_table.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ (revision ) @@ -1,196 +1,0 @@ -/* - * Copyright (c) 2008 Jakub Jermar - * 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 - */ - -/* - * This is an implementation of generic chained hash table. - */ - -#include -#include -#include -#include -#include -#include -#include - -/** Create chained hash table. - * - * @param h Hash table structure. Will be initialized by this call. - * @param m Number of hash table buckets. - * @param max_keys Maximal number of keys needed to identify an item. - * @param op Hash table operations structure. - * @return True on success - */ -int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, - hash_table_operations_t *op) -{ - hash_count_t i; - - assert(h); - assert(op && op->hash && op->compare); - assert(max_keys > 0); - - h->entry = malloc(m * sizeof(link_t)); - if (!h->entry) { - printf("cannot allocate memory for hash table\n"); - return false; - } - memset((void *) h->entry, 0, m * sizeof(link_t)); - - for (i = 0; i < m; i++) - list_initialize(&h->entry[i]); - - h->entries = m; - h->max_keys = max_keys; - h->op = op; - return true; -} - -/** Destroy a hash table instance. - * - * @param h Hash table to be destroyed. - */ -void hash_table_destroy(hash_table_t *h) -{ - assert(h); - assert(h->entry); - free(h->entry); -} - -/** Insert item into a hash table. - * - * @param h Hash table. - * @param key Array of all keys necessary to compute hash index. - * @param item Item to be inserted into the hash table. - */ -void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item) -{ - hash_index_t chain; - - assert(item); - assert(h && h->op && h->op->hash && h->op->compare); - - chain = h->op->hash(key); - assert(chain < h->entries); - - list_append(item, &h->entry[chain]); -} - -/** Search hash table for an item matching keys. - * - * @param h Hash table. - * @param key Array of all keys needed to compute hash index. - * - * @return Matching item on success, NULL if there is no such item. - */ -link_t *hash_table_find(hash_table_t *h, unsigned long key[]) -{ - link_t *cur; - hash_index_t chain; - - assert(h && h->op && h->op->hash && h->op->compare); - - chain = h->op->hash(key); - assert(chain < h->entries); - - for (cur = h->entry[chain].next; cur != &h->entry[chain]; - cur = cur->next) { - if (h->op->compare(key, h->max_keys, cur)) { - /* - * The entry is there. - */ - return cur; - } - } - - return NULL; -} - -/** Remove all matching items from hash table. - * - * For each removed item, h->remove_callback() is called. - * - * @param h Hash table. - * @param key Array of keys that will be compared against items of - * the hash table. - * @param keys Number of keys in the 'key' array. - */ -void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys) -{ - hash_index_t chain; - link_t *cur; - - assert(h && h->op && h->op->hash && h->op->compare && - h->op->remove_callback); - assert(keys <= h->max_keys); - - if (keys == h->max_keys) { - - /* - * All keys are known, hash_table_find() can be used to find the - * entry. - */ - - cur = hash_table_find(h, key); - if (cur) { - list_remove(cur); - h->op->remove_callback(cur); - } - return; - } - - /* - * Fewer keys were passed. - * Any partially matching entries are to be removed. - */ - for (chain = 0; chain < h->entries; chain++) { - for (cur = h->entry[chain].next; cur != &h->entry[chain]; - cur = cur->next) { - if (h->op->compare(key, keys, cur)) { - link_t *hlp; - - hlp = cur; - cur = cur->prev; - - list_remove(hlp); - h->op->remove_callback(hlp); - - continue; - } - } - } -} - -/** @} - */ Index: uspace/lib/libc/generic/libadt/list.c =================================================================== --- uspace/lib/libc/generic/libadt/list.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ (revision ) @@ -1,112 +1,0 @@ -/* - * Copyright (c) 2004 Jakub Jermar - * 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 - */ - -#include - - -/** Check for membership - * - * Check whether link is contained in the list head. - * The membership is defined as pointer equivalence. - * - * @param link Item to look for. - * @param head List to look in. - * - * @return true if link is contained in head, false otherwise. - * - */ -int list_member(const link_t *link, const link_t *head) -{ - int found = 0; - link_t *hlp = head->next; - - while (hlp != head) { - if (hlp == link) { - found = 1; - break; - } - hlp = hlp->next; - } - - return found; -} - - -/** Concatenate two lists - * - * Concatenate lists head1 and head2, producing a single - * list head1 containing items from both (in head1, head2 - * order) and empty list head2. - * - * @param head1 First list and concatenated output - * @param head2 Second list and empty output. - * - */ -void list_concat(link_t *head1, link_t *head2) -{ - if (list_empty(head2)) - return; - - head2->next->prev = head1->prev; - head2->prev->next = head1; - head1->prev->next = head2->next; - head1->prev = head2->prev; - list_initialize(head2); -} - - -/** Count list items - * - * Return the number of items in the list. - * - * @param link List to count. - * - * @return Number of items in the list. - * - */ -unsigned int list_count(const link_t *link) -{ - unsigned int count = 0; - link_t *hlp = link->next; - - while (hlp != link) { - count++; - hlp = hlp->next; - } - - return count; -} - -/** @} - */