Index: uspace/app/trace/ipcp.c =================================================================== --- uspace/app/trace/ipcp.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/app/trace/ipcp.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -35,5 +35,5 @@ #include #include -#include +#include #include "ipc_desc.h" Index: uspace/app/trace/proto.c =================================================================== --- uspace/app/trace/proto.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/app/trace/proto.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -36,5 +36,5 @@ #include #include -#include +#include #include "trace.h" Index: uspace/app/trace/proto.h =================================================================== --- uspace/app/trace/proto.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/app/trace/proto.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -36,5 +36,5 @@ #define PROTO_H_ -#include +#include #include #include "trace.h" Index: uspace/lib/libblock/libblock.c =================================================================== --- uspace/lib/libblock/libblock.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libblock/libblock.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -48,6 +48,6 @@ #include #include -#include -#include +#include +#include #include Index: uspace/lib/libblock/libblock.h =================================================================== --- uspace/lib/libblock/libblock.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libblock/libblock.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -42,6 +42,6 @@ #include #include -#include -#include +#include +#include /* Index: uspace/lib/libc/Makefile =================================================================== --- uspace/lib/libc/Makefile (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/Makefile (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -73,6 +73,6 @@ generic/loader.c \ generic/getopt.c \ - generic/libadt/list.o \ - generic/libadt/hash_table.o \ + generic/adt/list.o \ + generic/adt/hash_table.o \ generic/time.c \ generic/err.c \ 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: pace/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: pace/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; -} - -/** @} - */ Index: uspace/lib/libc/include/adt/fifo.h =================================================================== --- uspace/lib/libc/include/adt/fifo.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) +++ uspace/lib/libc/include/adt/fifo.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -0,0 +1,127 @@ +/* + * Copyright (c) 2006 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 implementation of FIFO stores values in an array + * (static or dynamic). As such, these FIFOs have upper bound + * on number of values they can store. Push and pop operations + * are done via accessing the array through head and tail indices. + * Because of better operation ordering in fifo_pop(), the access + * policy for these two indices is to 'increment (mod size of FIFO) + * and use'. + */ + +#ifndef LIBC_FIFO_H_ +#define LIBC_FIFO_H_ + +#include + +typedef unsigned long fifo_count_t; +typedef unsigned long fifo_index_t; + +#define FIFO_CREATE_STATIC(name, t, itms) \ + struct { \ + t fifo[(itms)]; \ + fifo_count_t items; \ + fifo_index_t head; \ + fifo_index_t tail; \ + } name + +/** Create and initialize static FIFO. + * + * FIFO is allocated statically. + * This macro is suitable for creating smaller FIFOs. + * + * @param name Name of FIFO. + * @param t Type of values stored in FIFO. + * @param itms Number of items that can be stored in FIFO. + */ +#define FIFO_INITIALIZE_STATIC(name, t, itms) \ + FIFO_CREATE_STATIC(name, t, itms) = { \ + .items = (itms), \ + .head = 0, \ + .tail = 0 \ + } + +/** Create and prepare dynamic FIFO. + * + * FIFO is allocated dynamically. + * This macro is suitable for creating larger FIFOs. + * + * @param name Name of FIFO. + * @param t Type of values stored in FIFO. + * @param itms Number of items that can be stored in FIFO. + */ +#define FIFO_INITIALIZE_DYNAMIC(name, t, itms) \ + struct { \ + t *fifo; \ + fifo_count_t items; \ + fifo_index_t head; \ + fifo_index_t tail; \ + } name = { \ + .fifo = NULL, \ + .items = (itms), \ + .head = 0, \ + .tail = 0 \ + } + +/** Pop value from head of FIFO. + * + * @param name FIFO name. + * + * @return Leading value in FIFO. + */ +#define fifo_pop(name) \ + name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0] + +/** Push value to tail of FIFO. + * + * @param name FIFO name. + * @param value Value to be appended to FIFO. + * + */ +#define fifo_push(name, value) \ + name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value) + +/** Allocate memory for dynamic FIFO. + * + * @param name FIFO name. + */ +#define fifo_create(name) \ + name.fifo = malloc(sizeof(*name.fifo) * name.items) + +#endif + +/** @} + */ Index: uspace/lib/libc/include/adt/hash_table.h =================================================================== --- uspace/lib/libc/include/adt/hash_table.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) +++ uspace/lib/libc/include/adt/hash_table.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -0,0 +1,94 @@ +/* + * Copyright (c) 2006 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 + */ + +#ifndef LIBC_HASH_TABLE_H_ +#define LIBC_HASH_TABLE_H_ + +#include +#include + +typedef unsigned long hash_count_t; +typedef unsigned long hash_index_t; +typedef struct hash_table hash_table_t; +typedef struct hash_table_operations hash_table_operations_t; + +/** Hash table structure. */ +struct hash_table { + link_t *entry; + hash_count_t entries; + hash_count_t max_keys; + hash_table_operations_t *op; +}; + +/** Set of operations for hash table. */ +struct hash_table_operations { + /** 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[]); + + /** 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); + + /** Hash table item removal callback. + * + * @param item Item that was removed from the hash table. + */ + void (*remove_callback)(link_t *item); +}; + +#define hash_table_get_instance(item, type, member) \ + list_get_instance((item), type, member) + +extern int hash_table_create(hash_table_t *, hash_count_t, hash_count_t, + hash_table_operations_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 *); + +#endif + +/** @} + */ Index: uspace/lib/libc/include/adt/list.h =================================================================== --- uspace/lib/libc/include/adt/list.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) +++ uspace/lib/libc/include/adt/list.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -0,0 +1,201 @@ +/* + * Copyright (c) 2001-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 + */ + +#ifndef LIBC_LIST_H_ +#define LIBC_LIST_H_ + +#include + +/** Doubly linked list head and link type. */ +typedef struct link { + struct link *prev; /**< Pointer to the previous item in the list. */ + struct link *next; /**< Pointer to the next item in the list. */ +} link_t; + +/** Declare and initialize statically allocated list. + * + * @param name Name of the new statically allocated list. + */ +#define LIST_INITIALIZE(name) link_t name = { \ + .prev = &name, \ + .next = &name \ +} + +/** Initialize doubly-linked circular list link + * + * Initialize doubly-linked list link. + * + * @param link Pointer to link_t structure to be initialized. + */ +static inline void link_initialize(link_t *link) +{ + link->prev = NULL; + link->next = NULL; +} + +/** Initialize doubly-linked circular list + * + * Initialize doubly-linked circular list. + * + * @param head Pointer to link_t structure representing head of the list. + */ +static inline void list_initialize(link_t *head) +{ + head->prev = head; + head->next = head; +} + +/** Add item to the beginning of doubly-linked circular list + * + * Add item to the beginning of doubly-linked circular list. + * + * @param link Pointer to link_t structure to be added. + * @param head Pointer to link_t structure representing head of the list. + */ +static inline void list_prepend(link_t *link, link_t *head) +{ + link->next = head->next; + link->prev = head; + head->next->prev = link; + head->next = link; +} + +/** Add item to the end of doubly-linked circular list + * + * Add item to the end of doubly-linked circular list. + * + * @param link Pointer to link_t structure to be added. + * @param head Pointer to link_t structure representing head of the list. + */ +static inline void list_append(link_t *link, link_t *head) +{ + link->prev = head->prev; + link->next = head; + head->prev->next = link; + head->prev = link; +} + +/** Insert item before another item in doubly-linked circular list. */ +static inline void list_insert_before(link_t *l, link_t *r) +{ + list_append(l, r); +} + +/** Insert item after another item in doubly-linked circular list. */ +static inline void list_insert_after(link_t *r, link_t *l) +{ + list_prepend(l, r); +} + +/** Remove item from doubly-linked circular list + * + * Remove item from doubly-linked circular list. + * + * @param link Pointer to link_t structure to be removed from the list it is contained in. + */ +static inline void list_remove(link_t *link) +{ + link->next->prev = link->prev; + link->prev->next = link->next; + link_initialize(link); +} + +/** Query emptiness of doubly-linked circular list + * + * Query emptiness of doubly-linked circular list. + * + * @param head Pointer to link_t structure representing head of the list. + */ +static inline int list_empty(link_t *head) +{ + return ((head->next == head) ? 1 : 0); +} + + +/** Split or concatenate headless doubly-linked circular list + * + * Split or concatenate headless doubly-linked circular list. + * + * Note that the algorithm works both directions: + * concatenates splitted lists and splits concatenated lists. + * + * @param part1 Pointer to link_t structure leading the first (half of the headless) list. + * @param part2 Pointer to link_t structure leading the second (half of the headless) list. + */ +static inline void headless_list_split_or_concat(link_t *part1, link_t *part2) +{ + part1->prev->next = part2; + part2->prev->next = part1; + + link_t *hlp = part1->prev; + + part1->prev = part2->prev; + part2->prev = hlp; +} + + +/** Split headless doubly-linked circular list + * + * Split headless doubly-linked circular list. + * + * @param part1 Pointer to link_t structure leading the first half of the headless list. + * @param part2 Pointer to link_t structure leading the second half of the headless list. + */ +static inline void headless_list_split(link_t *part1, link_t *part2) +{ + headless_list_split_or_concat(part1, part2); +} + +/** Concatenate two headless doubly-linked circular lists + * + * Concatenate two headless doubly-linked circular lists. + * + * @param part1 Pointer to link_t structure leading the first headless list. + * @param part2 Pointer to link_t structure leading the second headless list. + */ +static inline void headless_list_concat(link_t *part1, link_t *part2) +{ + headless_list_split_or_concat(part1, part2); +} + +#define list_get_instance(link, type, member) ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member)))) + +extern int list_member(const link_t *link, const link_t *head); +extern void list_concat(link_t *head1, link_t *head2); +extern unsigned int list_count(const link_t *link); + +#endif + +/** @} + */ Index: uspace/lib/libc/include/fibril.h =================================================================== --- uspace/lib/libc/include/fibril.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/include/fibril.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -37,5 +37,5 @@ #include -#include +#include #include Index: uspace/lib/libc/include/ipc/devmap.h =================================================================== --- uspace/lib/libc/include/ipc/devmap.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/include/ipc/devmap.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -36,5 +36,5 @@ #include #include -#include +#include #define DEVMAP_NAME_MAXLEN 255 Index: pace/lib/libc/include/libadt/fifo.h =================================================================== --- uspace/lib/libc/include/libadt/fifo.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ (revision ) @@ -1,127 +1,0 @@ -/* - * Copyright (c) 2006 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 implementation of FIFO stores values in an array - * (static or dynamic). As such, these FIFOs have upper bound - * on number of values they can store. Push and pop operations - * are done via accessing the array through head and tail indices. - * Because of better operation ordering in fifo_pop(), the access - * policy for these two indices is to 'increment (mod size of FIFO) - * and use'. - */ - -#ifndef LIBC_FIFO_H_ -#define LIBC_FIFO_H_ - -#include - -typedef unsigned long fifo_count_t; -typedef unsigned long fifo_index_t; - -#define FIFO_CREATE_STATIC(name, t, itms) \ - struct { \ - t fifo[(itms)]; \ - fifo_count_t items; \ - fifo_index_t head; \ - fifo_index_t tail; \ - } name - -/** Create and initialize static FIFO. - * - * FIFO is allocated statically. - * This macro is suitable for creating smaller FIFOs. - * - * @param name Name of FIFO. - * @param t Type of values stored in FIFO. - * @param itms Number of items that can be stored in FIFO. - */ -#define FIFO_INITIALIZE_STATIC(name, t, itms) \ - FIFO_CREATE_STATIC(name, t, itms) = { \ - .items = (itms), \ - .head = 0, \ - .tail = 0 \ - } - -/** Create and prepare dynamic FIFO. - * - * FIFO is allocated dynamically. - * This macro is suitable for creating larger FIFOs. - * - * @param name Name of FIFO. - * @param t Type of values stored in FIFO. - * @param itms Number of items that can be stored in FIFO. - */ -#define FIFO_INITIALIZE_DYNAMIC(name, t, itms) \ - struct { \ - t *fifo; \ - fifo_count_t items; \ - fifo_index_t head; \ - fifo_index_t tail; \ - } name = { \ - .fifo = NULL, \ - .items = (itms), \ - .head = 0, \ - .tail = 0 \ - } - -/** Pop value from head of FIFO. - * - * @param name FIFO name. - * - * @return Leading value in FIFO. - */ -#define fifo_pop(name) \ - name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0] - -/** Push value to tail of FIFO. - * - * @param name FIFO name. - * @param value Value to be appended to FIFO. - * - */ -#define fifo_push(name, value) \ - name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value) - -/** Allocate memory for dynamic FIFO. - * - * @param name FIFO name. - */ -#define fifo_create(name) \ - name.fifo = malloc(sizeof(*name.fifo) * name.items) - -#endif - -/** @} - */ Index: pace/lib/libc/include/libadt/hash_table.h =================================================================== --- uspace/lib/libc/include/libadt/hash_table.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ (revision ) @@ -1,94 +1,0 @@ -/* - * Copyright (c) 2006 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 - */ - -#ifndef LIBC_HASH_TABLE_H_ -#define LIBC_HASH_TABLE_H_ - -#include -#include - -typedef unsigned long hash_count_t; -typedef unsigned long hash_index_t; -typedef struct hash_table hash_table_t; -typedef struct hash_table_operations hash_table_operations_t; - -/** Hash table structure. */ -struct hash_table { - link_t *entry; - hash_count_t entries; - hash_count_t max_keys; - hash_table_operations_t *op; -}; - -/** Set of operations for hash table. */ -struct hash_table_operations { - /** 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[]); - - /** 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); - - /** Hash table item removal callback. - * - * @param item Item that was removed from the hash table. - */ - void (*remove_callback)(link_t *item); -}; - -#define hash_table_get_instance(item, type, member) \ - list_get_instance((item), type, member) - -extern int hash_table_create(hash_table_t *, hash_count_t, hash_count_t, - hash_table_operations_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 *); - -#endif - -/** @} - */ Index: pace/lib/libc/include/libadt/list.h =================================================================== --- uspace/lib/libc/include/libadt/list.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ (revision ) @@ -1,201 +1,0 @@ -/* - * Copyright (c) 2001-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 - */ - -#ifndef LIBC_LIST_H_ -#define LIBC_LIST_H_ - -#include - -/** Doubly linked list head and link type. */ -typedef struct link { - struct link *prev; /**< Pointer to the previous item in the list. */ - struct link *next; /**< Pointer to the next item in the list. */ -} link_t; - -/** Declare and initialize statically allocated list. - * - * @param name Name of the new statically allocated list. - */ -#define LIST_INITIALIZE(name) link_t name = { \ - .prev = &name, \ - .next = &name \ -} - -/** Initialize doubly-linked circular list link - * - * Initialize doubly-linked list link. - * - * @param link Pointer to link_t structure to be initialized. - */ -static inline void link_initialize(link_t *link) -{ - link->prev = NULL; - link->next = NULL; -} - -/** Initialize doubly-linked circular list - * - * Initialize doubly-linked circular list. - * - * @param head Pointer to link_t structure representing head of the list. - */ -static inline void list_initialize(link_t *head) -{ - head->prev = head; - head->next = head; -} - -/** Add item to the beginning of doubly-linked circular list - * - * Add item to the beginning of doubly-linked circular list. - * - * @param link Pointer to link_t structure to be added. - * @param head Pointer to link_t structure representing head of the list. - */ -static inline void list_prepend(link_t *link, link_t *head) -{ - link->next = head->next; - link->prev = head; - head->next->prev = link; - head->next = link; -} - -/** Add item to the end of doubly-linked circular list - * - * Add item to the end of doubly-linked circular list. - * - * @param link Pointer to link_t structure to be added. - * @param head Pointer to link_t structure representing head of the list. - */ -static inline void list_append(link_t *link, link_t *head) -{ - link->prev = head->prev; - link->next = head; - head->prev->next = link; - head->prev = link; -} - -/** Insert item before another item in doubly-linked circular list. */ -static inline void list_insert_before(link_t *l, link_t *r) -{ - list_append(l, r); -} - -/** Insert item after another item in doubly-linked circular list. */ -static inline void list_insert_after(link_t *r, link_t *l) -{ - list_prepend(l, r); -} - -/** Remove item from doubly-linked circular list - * - * Remove item from doubly-linked circular list. - * - * @param link Pointer to link_t structure to be removed from the list it is contained in. - */ -static inline void list_remove(link_t *link) -{ - link->next->prev = link->prev; - link->prev->next = link->next; - link_initialize(link); -} - -/** Query emptiness of doubly-linked circular list - * - * Query emptiness of doubly-linked circular list. - * - * @param head Pointer to link_t structure representing head of the list. - */ -static inline int list_empty(link_t *head) -{ - return ((head->next == head) ? 1 : 0); -} - - -/** Split or concatenate headless doubly-linked circular list - * - * Split or concatenate headless doubly-linked circular list. - * - * Note that the algorithm works both directions: - * concatenates splitted lists and splits concatenated lists. - * - * @param part1 Pointer to link_t structure leading the first (half of the headless) list. - * @param part2 Pointer to link_t structure leading the second (half of the headless) list. - */ -static inline void headless_list_split_or_concat(link_t *part1, link_t *part2) -{ - part1->prev->next = part2; - part2->prev->next = part1; - - link_t *hlp = part1->prev; - - part1->prev = part2->prev; - part2->prev = hlp; -} - - -/** Split headless doubly-linked circular list - * - * Split headless doubly-linked circular list. - * - * @param part1 Pointer to link_t structure leading the first half of the headless list. - * @param part2 Pointer to link_t structure leading the second half of the headless list. - */ -static inline void headless_list_split(link_t *part1, link_t *part2) -{ - headless_list_split_or_concat(part1, part2); -} - -/** Concatenate two headless doubly-linked circular lists - * - * Concatenate two headless doubly-linked circular lists. - * - * @param part1 Pointer to link_t structure leading the first headless list. - * @param part2 Pointer to link_t structure leading the second headless list. - */ -static inline void headless_list_concat(link_t *part1, link_t *part2) -{ - headless_list_split_or_concat(part1, part2); -} - -#define list_get_instance(link, type, member) ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member)))) - -extern int list_member(const link_t *link, const link_t *head); -extern void list_concat(link_t *head1, link_t *head2); -extern unsigned int list_count(const link_t *link); - -#endif - -/** @} - */ Index: uspace/lib/libc/include/stdio.h =================================================================== --- uspace/lib/libc/include/stdio.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/lib/libc/include/stdio.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -38,5 +38,5 @@ #include #include -#include +#include #define EOF (-1) Index: uspace/srv/console/console.c =================================================================== --- uspace/srv/console/console.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/console/console.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -45,5 +45,5 @@ #include #include -#include +#include #include #include Index: uspace/srv/fs/devfs/devfs_ops.c =================================================================== --- uspace/srv/fs/devfs/devfs_ops.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/fs/devfs/devfs_ops.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -42,5 +42,5 @@ #include #include -#include +#include #include "devfs.h" #include "devfs_ops.h" Index: uspace/srv/fs/fat/fat_idx.c =================================================================== --- uspace/srv/fs/fat/fat_idx.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/fs/fat/fat_idx.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -40,6 +40,6 @@ #include #include -#include -#include +#include +#include #include #include Index: uspace/srv/fs/fat/fat_ops.c =================================================================== --- uspace/srv/fs/fat/fat_ops.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/fs/fat/fat_ops.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -49,6 +49,6 @@ #include #include -#include -#include +#include +#include #include #include Index: uspace/srv/fs/tmpfs/tmpfs.h =================================================================== --- uspace/srv/fs/tmpfs/tmpfs.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/fs/tmpfs/tmpfs.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -39,5 +39,5 @@ #include #include -#include +#include #ifndef dprintf Index: uspace/srv/fs/tmpfs/tmpfs_ops.c =================================================================== --- uspace/srv/fs/tmpfs/tmpfs_ops.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/fs/tmpfs/tmpfs_ops.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -48,5 +48,5 @@ #include #include -#include +#include #include #include Index: uspace/srv/kbd/Makefile =================================================================== --- uspace/srv/kbd/Makefile (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/kbd/Makefile (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -35,5 +35,5 @@ include $(LIBC_PREFIX)/Makefile.toolchain -CFLAGS += -Iinclude -I../libadt/include +CFLAGS += -Iinclude LIBS = $(LIBC_PREFIX)/libc.a Index: uspace/srv/kbd/genarch/gsp.c =================================================================== --- uspace/srv/kbd/genarch/gsp.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/kbd/genarch/gsp.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -50,5 +50,5 @@ #include -#include +#include #include #include Index: uspace/srv/kbd/generic/kbd.c =================================================================== --- uspace/srv/kbd/generic/kbd.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/kbd/generic/kbd.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -46,5 +46,5 @@ #include #include -#include +#include #include #include Index: uspace/srv/kbd/include/gsp.h =================================================================== --- uspace/srv/kbd/include/gsp.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/kbd/include/gsp.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -38,5 +38,5 @@ #define KBD_GSP_H_ -#include +#include enum { Index: uspace/srv/ns/clonable.c =================================================================== --- uspace/srv/ns/clonable.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/ns/clonable.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -33,5 +33,5 @@ #include #include -#include +#include #include #include Index: uspace/srv/ns/service.c =================================================================== --- uspace/srv/ns/service.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/ns/service.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -32,5 +32,5 @@ #include -#include +#include #include #include Index: uspace/srv/ns/task.c =================================================================== --- uspace/srv/ns/task.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/ns/task.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -32,5 +32,5 @@ #include -#include +#include #include #include Index: uspace/srv/vfs/vfs.c =================================================================== --- uspace/srv/vfs/vfs.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/vfs/vfs.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -44,5 +44,5 @@ #include #include -#include +#include #include #include "vfs.h" Index: uspace/srv/vfs/vfs.h =================================================================== --- uspace/srv/vfs/vfs.h (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/vfs/vfs.h (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -35,5 +35,5 @@ #include -#include +#include #include #include Index: uspace/srv/vfs/vfs_lookup.c =================================================================== --- uspace/srv/vfs/vfs_lookup.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/vfs/vfs_lookup.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -44,5 +44,5 @@ #include #include -#include +#include #include Index: uspace/srv/vfs/vfs_node.c =================================================================== --- uspace/srv/vfs/vfs_node.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/vfs/vfs_node.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -41,5 +41,5 @@ #include #include -#include +#include #include #include Index: uspace/srv/vfs/vfs_ops.c =================================================================== --- uspace/srv/vfs/vfs_ops.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/vfs/vfs_ops.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -46,5 +46,5 @@ #include #include -#include +#include #include #include Index: uspace/srv/vfs/vfs_register.c =================================================================== --- uspace/srv/vfs/vfs_register.c (revision a68f7375e3e4f83a6876853e429edc329d00e4e4) +++ uspace/srv/vfs/vfs_register.c (revision d9c8c81f21850cb9e08890ce3919e1d8e253e810) @@ -47,5 +47,5 @@ #include #include -#include +#include #include #include