Index: uspace/lib/libc/include/adt/fifo.h =================================================================== --- uspace/lib/libc/include/adt/fifo.h (revision bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) +++ uspace/lib/libc/include/adt/fifo.h (revision bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) @@ -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 bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) +++ uspace/lib/libc/include/adt/hash_table.h (revision bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) @@ -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 bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) +++ uspace/lib/libc/include/adt/list.h (revision bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) @@ -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 bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) @@ -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 bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) @@ -36,5 +36,5 @@ #include #include -#include +#include #define DEVMAP_NAME_MAXLEN 255 Index: uspace/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: uspace/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: uspace/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 bd8bfcbd5fb6cff623ea60c4cd7c2f0830500f1a) @@ -38,5 +38,5 @@ #include #include -#include +#include #define EOF (-1)