Index: common/include/adt/bitmap.h =================================================================== --- common/include/adt/bitmap.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/bitmap.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,92 @@ +/* + * 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 kernel_generic_adt + * @{ + */ +/** @file + */ + +#ifndef KERN_BITMAP_H_ +#define KERN_BITMAP_H_ + +#include +#include +#include + +#define BITMAP_ELEMENT 8 +#define BITMAP_REMAINER 7 + +typedef struct { + size_t elements; + uint8_t *bits; + size_t next_fit; +} bitmap_t; + +static inline void bitmap_set(bitmap_t *bitmap, size_t element, + unsigned int value) +{ + if (element >= bitmap->elements) + return; + + size_t byte = element / BITMAP_ELEMENT; + uint8_t mask = 1 << (element & BITMAP_REMAINER); + + if (value) { + bitmap->bits[byte] |= mask; + } else { + bitmap->bits[byte] &= ~mask; + bitmap->next_fit = byte; + } +} + +static inline unsigned int bitmap_get(bitmap_t *bitmap, size_t element) +{ + if (element >= bitmap->elements) + return 0; + + size_t byte = element / BITMAP_ELEMENT; + uint8_t mask = 1 << (element & BITMAP_REMAINER); + + return !!((bitmap->bits)[byte] & mask); +} + +extern size_t bitmap_size(size_t); +extern void bitmap_initialize(bitmap_t *, size_t, void *); + +extern void bitmap_set_range(bitmap_t *, size_t, size_t); +extern void bitmap_clear_range(bitmap_t *, size_t, size_t); + +extern bool bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t, + size_t *); +extern void bitmap_copy(bitmap_t *, bitmap_t *, size_t); + +#endif + +/** @} + */ Index: common/include/adt/checksum.h =================================================================== --- common/include/adt/checksum.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/checksum.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2012 Dominik Taborsky + * 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_CHECKSUM_H_ +#define _LIBC_CHECKSUM_H_ + +#include +#include + +extern uint32_t compute_crc32(uint8_t *, size_t); +extern uint32_t compute_crc32_seed(uint8_t *, size_t, uint32_t); + +#endif + +/** @} + */ Index: common/include/adt/circ_buf.h =================================================================== --- common/include/adt/circ_buf.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/circ_buf.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2017 Jiri Svoboda + * 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 Circular buffer + */ + +#ifndef _LIBC_CIRC_BUF_H_ +#define _LIBC_CIRC_BUF_H_ + +#include +#include + +/** Circular buffer */ +typedef struct { + /** Buffer */ + void *buf; + /** Number of buffer members */ + size_t nmemb; + /** Member size */ + size_t size; + /** Read position */ + size_t rp; + /** Write position */ + size_t wp; + /** Number of used entries */ + size_t nused; +} circ_buf_t; + +extern void circ_buf_init(circ_buf_t *, void *, size_t, size_t); +extern size_t circ_buf_nfree(circ_buf_t *); +extern size_t circ_buf_nused(circ_buf_t *); +extern errno_t circ_buf_push(circ_buf_t *, const void *); +extern errno_t circ_buf_pop(circ_buf_t *, void *); + +#endif + +/** @} + */ Index: common/include/adt/fifo.h =================================================================== --- common/include/adt/fifo.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/fifo.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -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: common/include/adt/gcdlcm.h =================================================================== --- common/include/adt/gcdlcm.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/gcdlcm.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,74 @@ +/* + * Copyright (c) 2009 Martin Decky + * 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_GCDLCM_H_ +#define _LIBC_GCDLCM_H_ + +#include +#include + +#define DECLARE_GCD(type, name) \ + static inline type name(type a, type b) \ + { \ + if (a == 0) \ + return b; \ + \ + while (b != 0) { \ + if (a > b) \ + a -= b; \ + else \ + b -= a; \ + } \ + \ + return a; \ + } + +#define DECLARE_LCM(type, name, gcd) \ + static inline type name(type a, type b) \ + { \ + return (a * b) / gcd(a, b); \ + } + +DECLARE_GCD(uint32_t, gcd32); +DECLARE_GCD(uint64_t, gcd64); +DECLARE_GCD(size_t, gcd); + +DECLARE_LCM(uint32_t, lcm32, gcd32); +DECLARE_LCM(uint64_t, lcm64, gcd64); +DECLARE_LCM(size_t, lcm, gcd); + +#endif + +/** @} + */ Index: common/include/adt/hash.h =================================================================== --- common/include/adt/hash.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/hash.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,110 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ +#ifndef _LIBC_ADT_HASH_H_ +#define _LIBC_ADT_HASH_H_ + +#include +#include + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint32_t hash_mix32(uint32_t hash) +{ + /* + * Thomas Wang's modification of Bob Jenkin's hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + * Public domain. + */ + hash = ~hash + (hash << 15); + hash = hash ^ (hash >> 12); + hash = hash + (hash << 2); + hash = hash ^ (hash >> 4); + hash = hash * 2057; + hash = hash ^ (hash >> 16); + return hash; +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline uint64_t hash_mix64(uint64_t hash) +{ + /* + * Thomas Wang's public domain 64-bit hash mixing function: + * http://www.concentric.net/~Ttwang/tech/inthash.htm + */ + hash = (hash ^ 61) ^ (hash >> 16); + hash = hash + (hash << 3); + hash = hash ^ (hash >> 4); + hash = hash * 0x27d4eb2d; + hash = hash ^ (hash >> 15); + /* + * Lower order bits are mixed more thoroughly. Swap them with + * the higher order bits and make the resulting higher order bits + * more usable. + */ + return (hash << 32) | (hash >> 32); +} + +/** Produces a uniform hash affecting all output bits from the skewed input. */ +static inline size_t hash_mix(size_t hash) +{ + if (sizeof(long) == 4) + return hash_mix32(hash); + else + return hash_mix64(hash); +} + +/** Use to create a hash from multiple values. + * + * Typical usage: + * @code + * int car_id; + * bool car_convertible; + * // .. + * size_t hash = 0; + * hash = hash_combine(hash, car_id); + * hash = hash_combine(hash, car_convertible); + * // Now use hash as a hash of both car_id and car_convertible. + * @endcode + */ +static inline size_t hash_combine(size_t seed, size_t hash) +{ + /* + * todo: use Bob Jenkin's proper mixing hash pass: + * http://burtleburtle.net/bob/c/lookup3.c + */ + seed ^= hash + 0x9e3779b9 + + ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5))); + return seed; +} + +#endif Index: common/include/adt/hash_table.h =================================================================== --- common/include/adt/hash_table.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/hash_table.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,108 @@ +/* + * Copyright (c) 2006 Jakub Jermar + * Copyright (c) 2012 Adam Hraska + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +#ifndef _LIBC_HASH_TABLE_H_ +#define _LIBC_HASH_TABLE_H_ + +#include +#include +#include +#include + +/** Opaque hash table link type. */ +typedef struct ht_link { + link_t link; +} ht_link_t; + +/** Set of operations for hash table. */ +typedef struct { + /** Returns the hash of the key stored in the item (ie its lookup key). */ + size_t (*hash)(const ht_link_t *item); + + /** Returns the hash of the key. */ + size_t (*key_hash)(const void *key); + + /** True if the items are equal (have the same lookup keys). */ + bool (*equal)(const ht_link_t *item1, const ht_link_t *item2); + + /** Returns true if the key is equal to the item's lookup key. */ + bool (*key_equal)(const void *key, const ht_link_t *item); + + /** Hash table item removal callback. + * + * Must not invoke any mutating functions of the hash table. + * + * @param item Item that was removed from the hash table. + */ + void (*remove_callback)(ht_link_t *item); +} hash_table_ops_t; + +/** Hash table structure. */ +typedef struct { + const hash_table_ops_t *op; + list_t *bucket; + size_t bucket_cnt; + size_t full_item_cnt; + size_t item_cnt; + size_t max_load; + bool apply_ongoing; +} hash_table_t; + +#define hash_table_get_inst(item, type, member) \ + member_to_inst((item), type, member) + +extern bool hash_table_create(hash_table_t *, size_t, size_t, + const hash_table_ops_t *); +extern void hash_table_destroy(hash_table_t *); + +extern bool hash_table_empty(hash_table_t *); +extern size_t hash_table_size(hash_table_t *); + +extern void hash_table_clear(hash_table_t *); +extern void hash_table_insert(hash_table_t *, ht_link_t *); +extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *); +extern ht_link_t *hash_table_find(const hash_table_t *, const void *); +extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *, + ht_link_t *); +extern size_t hash_table_remove(hash_table_t *, const void *); +extern void hash_table_remove_item(hash_table_t *, ht_link_t *); +extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *), + void *); + +#endif + +/** @} + */ Index: common/include/adt/list.h =================================================================== --- common/include/adt/list.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/list.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,473 @@ +/* + * Copyright (c) 2001-2004 Jakub Jermar + * Copyright (c) 2013 Jiri Svoboda + * 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 +#include +#include +#include +#include +#include +#include <_bits/decls.h> + +#ifndef __cplusplus + +/** + * We don't define the macros in C++ to avoid polluting headers with + * namespaceless names. We don't actually need them, so this is fine. + * We still allow including the rest of the file (in `helenos` namespace) + * so that we can expose publicly visible types that have list_t members. + */ + +/** Declare and initialize statically allocated list. + * + * @param name Name of the new statically allocated list. + * + */ +#define LIST_INITIALIZE(name) \ + list_t name = LIST_INITIALIZER(name) + +/** Initializer for statically allocated list. + * + * @code + * struct named_list { + * const char *name; + * list_t list; + * } var = { + * .name = "default name", + * .list = LIST_INITIALIZER(name_list.list) + * }; + * @endcode + * + * @param name Name of the new statically allocated list. + * + */ +#define LIST_INITIALIZER(name) \ + { \ + .head = { \ + .prev = &(name).head, \ + .next = &(name).head \ + } \ + } + +#define list_get_instance(link, type, member) \ + member_to_inst(link, type, member) + +#define list_foreach(list, member, itype, iterator) \ + for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \ + for (link_t *_link = (list).head.next; \ + iterator = list_get_instance(_link, itype, member), \ + _link != &(list).head; _link = _link->next) + +#define list_foreach_rev(list, member, itype, iterator) \ + for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \ + for (link_t *_link = (list).head.prev; \ + iterator = list_get_instance(_link, itype, member), \ + _link != &(list).head; _link = _link->prev) + +/** Unlike list_foreach(), allows removing items while traversing a list. + * + * @code + * list_t mylist; + * typedef struct item { + * int value; + * link_t item_link; + * } item_t; + * + * //.. + * + * // Print each list element's value and remove the element from the list. + * list_foreach_safe(mylist, cur_link, next_link) { + * item_t *cur_item = list_get_instance(cur_link, item_t, item_link); + * printf("%d\n", cur_item->value); + * list_remove(cur_link); + * } + * @endcode + * + * @param list List to traverse. + * @param iterator Iterator to the current element of the list. + * The item this iterator points may be safely removed + * from the list. + * @param next_iter Iterator to the next element of the list. + */ +#define list_foreach_safe(list, iterator, next_iter) \ + for (link_t *iterator = (list).head.next, \ + *next_iter = iterator->next; \ + iterator != &(list).head; \ + iterator = next_iter, next_iter = iterator->next) + +#define assert_link_not_used(link) \ + assert(!link_used(link)) + +#define list_pop(list, type, member) \ + ((type *) list_pop_internal(list, \ + (list_link_to_void(&(((type *) NULL)->member)) - NULL))) + +#endif /* !__cplusplus */ + +__HELENOS_DECLS_BEGIN; + +/** Doubly linked list link. */ +typedef struct __adt_list_link { + struct __adt_list_link *prev; /**< Pointer to the previous item in the list. */ + struct __adt_list_link *next; /**< Pointer to the next item in the list. */ +} link_t; + +/** Doubly linked list. */ +typedef struct { + link_t head; /**< List head. Does not have any data. */ +} list_t; + +extern bool list_member(const link_t *, const list_t *); +extern void list_splice(list_t *, link_t *); +extern size_t list_count(const list_t *); + +/** Returns true if the link is definitely part of a list. False if not sure. */ +static inline bool link_in_use(const link_t *link) +{ + return link->prev != NULL && link->next != NULL; +} + +/** Initialize doubly-linked circular list link + * + * Initialize doubly-linked list link. + * + * @param link Pointer to link_t structure to be initialized. + * + */ +_NO_TRACE 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 list Pointer to list_t structure. + * + */ +_NO_TRACE static inline __CONSTEXPR void list_initialize(list_t *list) +{ + list->head.prev = &list->head; + list->head.next = &list->head; +} + +/** Insert item before another item in doubly-linked circular list. + * + */ +static inline void list_insert_before(link_t *lnew, link_t *lold) +{ + lnew->next = lold; + lnew->prev = lold->prev; + lold->prev->next = lnew; + lold->prev = lnew; +} + +/** Insert item after another item in doubly-linked circular list. + * + */ +static inline void list_insert_after(link_t *lnew, link_t *lold) +{ + lnew->prev = lold; + lnew->next = lold->next; + lold->next->prev = lnew; + lold->next = lnew; +} + +/** 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 list Pointer to list_t structure. + * + */ +_NO_TRACE static inline void list_prepend(link_t *link, list_t *list) +{ + list_insert_after(link, &list->head); +} + +/** 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 list Pointer to list_t structure. + * + */ +_NO_TRACE static inline void list_append(link_t *link, list_t *list) +{ + list_insert_before(link, &list->head); +} + +/** 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. + * + */ +_NO_TRACE static inline void list_remove(link_t *link) +{ + if ((link->prev != NULL) && (link->next != NULL)) { + 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 list Pointer to lins_t structure. + * + */ +_NO_TRACE static inline bool list_empty(const list_t *list) +{ + return (list->head.next == &list->head); +} + +/** Get first item in list. + * + * @param list Pointer to list_t structure. + * + * @return Head item of the list. + * @return NULL if the list is empty. + * + */ +static inline link_t *list_first(const list_t *list) +{ + return ((list->head.next == &list->head) ? NULL : list->head.next); +} + +/** Get last item in list. + * + * @param list Pointer to list_t structure. + * + * @return Head item of the list. + * @return NULL if the list is empty. + * + */ +static inline link_t *list_last(const list_t *list) +{ + return (list->head.prev == &list->head) ? NULL : list->head.prev; +} + +/** Get next item in list. + * + * @param link Current item link + * @param list List containing @a link + * + * @return Next item or NULL if @a link is the last item. + */ +static inline link_t *list_next(const link_t *link, const list_t *list) +{ + return (link->next == &list->head) ? NULL : link->next; +} + +/** Get previous item in list. + * + * @param link Current item link + * @param list List containing @a link + * + * @return Previous item or NULL if @a link is the first item. + */ +static inline link_t *list_prev(const link_t *link, const list_t *list) +{ + return (link->prev == &list->head) ? NULL : link->prev; +} + +/** 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. + * + */ +_NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2) +{ + if (part1 == NULL || part2 == NULL) + return; + + 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. + * + */ +_NO_TRACE 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. + * + */ +_NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2) +{ + headless_list_split_or_concat(part1, part2); +} + +/** Swap the contents of two lists. + * + * @param list1 + * @param list2 + */ +static inline void list_swap(list_t *list1, list_t *list2) +{ + link_t *first1 = list_first(list1); + link_t *first2 = list_first(list2); + + /* Detach both lists from their heads. */ + headless_list_split(&list1->head, first1); + headless_list_split(&list2->head, first2); + + /* Attach both lists to their new heads. */ + headless_list_concat(&list1->head, first2); + headless_list_concat(&list2->head, first1); +} + +/** Concatenate two lists + * + * Concatenate lists @a list1 and @a list2, producing a single + * list @a list1 containing items from both (in @a list1, @a list2 + * order) and empty list @a list2. + * + * @param list1 First list and concatenated output + * @param list2 Second list and empty output. + * + */ +_NO_TRACE static inline void list_concat(list_t *list1, list_t *list2) +{ + list_splice(list2, list1->head.prev); +} + +/** Get n-th item in a list. + * + * @param list Pointer to link_t structure representing the list. + * @param n Item number (indexed from zero). + * + * @return n-th item of the list. + * @return NULL if no n-th item found. + * + */ +static inline link_t *list_nth(const list_t *list, size_t n) +{ + size_t cnt = 0; + + link_t *link = list_first(list); + while (link != NULL) { + if (cnt == n) + return link; + + cnt++; + link = list_next(link, list); + } + + return NULL; +} + +/** Verify that argument type is a pointer to link_t (at compile time). + * + * This can be used to check argument type in a macro. + */ +static inline const void *list_link_to_void(const link_t *link) +{ + return link; +} + +/** Determine if link is used. + * + * @param link Link + * @return @c true if link is used, @c false if not. + */ +static inline bool link_used(link_t *link) +{ + if (link->prev == NULL && link->next == NULL) + return false; + + assert(link->prev != NULL && link->next != NULL); + return true; +} + +static inline void *list_pop_internal(list_t *list, ptrdiff_t offset) +{ + link_t *tmp = list_first(list); + if (tmp == NULL) + return NULL; + + list_remove(tmp); + return (void *) (((uint8_t *) tmp) - offset); +} + +__HELENOS_DECLS_END; + +#endif + +/** @} + */ Index: common/include/adt/odict.h =================================================================== --- common/include/adt/odict.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/odict.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,71 @@ +/* + * Copyright (c) 2016 Jiri Svoboda + * 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 kernel_generic_adt + * @{ + */ +/** @file + */ + +#ifndef _LIBC_ODICT_H_ +#define _LIBC_ODICT_H_ + +#include +#include +#include +#include +#include + +#define odict_get_instance(odlink, type, member) \ + member_to_inst(odlink, type, member) + +extern void odict_initialize(odict_t *, odgetkey_t, odcmp_t); +extern void odict_finalize(odict_t *); +extern void odlink_initialize(odlink_t *); +extern void odict_insert(odlink_t *, odict_t *, odlink_t *); +extern void odict_remove(odlink_t *); +extern void odict_key_update(odlink_t *, odict_t *); +extern bool odlink_used(odlink_t *); +extern bool odict_empty(odict_t *); +extern unsigned long odict_count(odict_t *); +extern odlink_t *odict_first(odict_t *); +extern odlink_t *odict_last(odict_t *); +extern odlink_t *odict_prev(odlink_t *, odict_t *); +extern odlink_t *odict_next(odlink_t *, odict_t *); +extern odlink_t *odict_find_eq(odict_t *, void *, odlink_t *); +extern odlink_t *odict_find_eq_last(odict_t *, void *, odlink_t *); +extern odlink_t *odict_find_geq(odict_t *, void *, odlink_t *); +extern odlink_t *odict_find_gt(odict_t *, void *, odlink_t *); +extern odlink_t *odict_find_leq(odict_t *, void *, odlink_t *); +extern odlink_t *odict_find_lt(odict_t *, void *, odlink_t *); +extern errno_t odict_validate(odict_t *); + +#endif + +/** @} + */ Index: common/include/adt/prodcons.h =================================================================== --- common/include/adt/prodcons.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) +++ common/include/adt/prodcons.h (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2011 Martin Decky + * 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_PRODCONS_H_ +#define _LIBC_PRODCONS_H_ + +#include +#include + +typedef struct { + fibril_mutex_t mtx; + fibril_condvar_t cv; + list_t list; +} prodcons_t; + +extern void prodcons_initialize(prodcons_t *); +extern void prodcons_produce(prodcons_t *, link_t *); +extern link_t *prodcons_consume(prodcons_t *); + +#endif + +/** @} + */