Index: uspace/lib/c/generic/adt/checksum.c =================================================================== --- uspace/lib/c/generic/adt/checksum.c (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,146 +1,0 @@ -/* - * 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. - */ - -#include - -/** - * 256-value table of precomputed polynomials for CRC32. Note - * the values depend on the selected divisor polynomial (currently - * 0xedb88320) and whether the CRC computation is reflected or not. - * See http://www.repairfaq.org/filipg/LINK/F_crc_v3.html for a perfect - * source of info about this. - */ -uint32_t poly_table[256] = { - 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, - 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, - 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, - 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, - 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, - 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, - 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, - 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, - 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, - 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, - 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, - 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, - 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, - 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, - 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, - 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, - 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, - 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, - 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, - 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, - 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, - 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, - 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, - 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, - 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, - 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, - 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, - 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, - 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, - 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, - 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, - 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, - 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, - 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, - 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, - 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, - 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, - 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, - 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, - 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, - 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, - 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, - 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, - 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, - 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, - 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, - 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, - 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, - 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, - 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, - 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, - 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, - 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, - 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, - 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, - 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, - 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, - 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, - 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, - 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, - 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, - 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, - 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, - 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d -}; - -/** Compute CRC32 value. - * - * See wiki.osdev.org/CRC32 for reference. - * - * @param[in] data Data to process. - * @param[in] length Length of the data in bytes. - * - * @return Computed CRC32 of the data. - * - */ -uint32_t compute_crc32(uint8_t *data, size_t length) -{ - return compute_crc32_seed(data, length, 0); -} - -/** Compute CRC32 value with initial seed. - * - * Use this when checksumming non-continous data (linked lists, trees, - * etc.). On the first data block call compute_crc32() and use the result - * as the seed for the following call of compute_crc32_seed() on the next - * block. Then use the result of that call as the seed of the following - * call, etc. - * - * @param[in] data Fata to process. - * @param[in] length Length of the data in bytes. - * @param[in] seed The starting value of the CRC. - * - * @return Computed CRC32 of the data of all the previous blocks. - * - */ -uint32_t compute_crc32_seed(uint8_t *data, size_t length, uint32_t seed) -{ - uint32_t crc; - - for (crc = ~seed; length > 0; length--) - crc = poly_table[((uint8_t) crc ^ *(data++))] ^ (crc >> 8); - - return (~crc); -} - -/** @} - */ Index: uspace/lib/c/generic/adt/circ_buf.c =================================================================== --- uspace/lib/c/generic/adt/circ_buf.c (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,113 +1,0 @@ -/* - * 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 - */ - -#include -#include -#include -#include - -/** Initialize circular buffer. - * - * @param cbuf Circular buffer - * @param buf Buffer for storing data - * @param nmemb Number of entries in @a buf - * @param size Size of individual buffer entry - */ -void circ_buf_init(circ_buf_t *cbuf, void *buf, size_t nmemb, size_t size) -{ - cbuf->buf = buf; - cbuf->nmemb = nmemb; - cbuf->size = size; - cbuf->rp = 0; - cbuf->wp = 0; - cbuf->nused = 0; -} - -/** Return number of free buffer entries. - * - * @param cbuf Circular buffer - * @return Number of free buffer entries - */ -size_t circ_buf_nfree(circ_buf_t *cbuf) -{ - return cbuf->nmemb - cbuf->nused; -} - -/** Return number of used buffer entries. - * - * @param cbuf Circular buffer - * @return Number of used buffer entries - */ -size_t circ_buf_nused(circ_buf_t *cbuf) -{ - return cbuf->nused; -} - -/** Push new entry into circular buffer. - * - * @param cbuf Circular buffer - * @param data Pointer to entry data - * @return EOK on success, EAGAIN if circular buffer is full - */ -errno_t circ_buf_push(circ_buf_t *cbuf, const void *data) -{ - if (circ_buf_nfree(cbuf) == 0) - return EAGAIN; - - memcpy(cbuf->buf + cbuf->size * cbuf->wp, data, cbuf->size); - cbuf->wp = (cbuf->wp + 1) % cbuf->nmemb; - cbuf->nused++; - return EOK; -} - -/** Pop entry from circular buffer. - * - * @param cbuf Circular buffer - * @param datab Pointer to data buffer for storing entry - * @return EOK on success, EAGAIN if circular buffer is full - */ -errno_t circ_buf_pop(circ_buf_t *cbuf, void *datab) -{ - if (cbuf->nused == 0) - return EAGAIN; - - memcpy(datab, cbuf->buf + cbuf->size * cbuf->rp, cbuf->size); - cbuf->rp = (cbuf->rp + 1) % cbuf->nmemb; - cbuf->nused--; - return EOK; -} - -/** @} - */ Index: uspace/lib/c/generic/adt/hash_table.c =================================================================== --- uspace/lib/c/generic/adt/hash_table.c (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,474 +1,0 @@ -/* - * Copyright (c) 2008 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 - */ - -/* - * This is an implementation of a generic resizable chained hash table. - * - * The table grows to 2*n+1 buckets each time, starting at n == 89, - * per Thomas Wang's recommendation: - * http://www.concentric.net/~Ttwang/tech/hashsize.htm - * - * This policy produces prime table sizes for the first five resizes - * and generally produces table sizes which are either prime or - * have fairly large (prime/odd) divisors. Having a prime table size - * mitigates the use of suboptimal hash functions and distributes - * items over the whole table. - */ - -#include -#include -#include -#include -#include -#include - -/* Optimal initial bucket count. See comment above. */ -#define HT_MIN_BUCKETS 89 -/* The table is resized when the average load per bucket exceeds this number. */ -#define HT_MAX_LOAD 2 - -static size_t round_up_size(size_t); -static bool alloc_table(size_t, list_t **); -static void clear_items(hash_table_t *); -static void resize(hash_table_t *, size_t); -static void grow_if_needed(hash_table_t *); -static void shrink_if_needed(hash_table_t *); - -/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */ -static void nop_remove_callback(ht_link_t *item) -{ - /* no-op */ -} - -/** Create chained hash table. - * - * @param h Hash table structure. Will be initialized by this call. - * @param init_size Initial desired number of hash table buckets. Pass zero - * if you want the default initial size. - * @param max_load The table is resized when the average load per bucket - * exceeds this number. Pass zero if you want the default. - * @param op Hash table operations structure. remove_callback() - * is optional and can be NULL if no action is to be taken - * upon removal. equal() is optional if and only if - * hash_table_insert_unique() will never be invoked. - * All other operations are mandatory. - * - * @return True on success - * - */ -bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load, - const hash_table_ops_t *op) -{ - assert(h); - assert(op && op->hash && op->key_hash && op->key_equal); - - /* Check for compulsory ops. */ - if (!op || !op->hash || !op->key_hash || !op->key_equal) - return false; - - h->bucket_cnt = round_up_size(init_size); - - if (!alloc_table(h->bucket_cnt, &h->bucket)) - return false; - - h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load; - h->item_cnt = 0; - h->op = op; - h->full_item_cnt = h->max_load * h->bucket_cnt; - h->apply_ongoing = false; - - return true; -} - -/** Destroy a hash table instance. - * - * @param h Hash table to be destroyed. - * - */ -void hash_table_destroy(hash_table_t *h) -{ - assert(h && h->bucket); - assert(!h->apply_ongoing); - - clear_items(h); - - free(h->bucket); - - h->bucket = NULL; - h->bucket_cnt = 0; -} - -/** Returns true if there are no items in the table. */ -bool hash_table_empty(hash_table_t *h) -{ - assert(h && h->bucket); - return h->item_cnt == 0; -} - -/** Returns the number of items in the table. */ -size_t hash_table_size(hash_table_t *h) -{ - assert(h && h->bucket); - return h->item_cnt; -} - -/** Remove all elements from the hash table - * - * @param h Hash table to be cleared - */ -void hash_table_clear(hash_table_t *h) -{ - assert(h && h->bucket); - assert(!h->apply_ongoing); - - clear_items(h); - - /* Shrink the table to its minimum size if possible. */ - if (HT_MIN_BUCKETS < h->bucket_cnt) { - resize(h, HT_MIN_BUCKETS); - } -} - -/** Unlinks and removes all items but does not resize. */ -static void clear_items(hash_table_t *h) -{ - if (h->item_cnt == 0) - return; - - void (*remove_cb)(ht_link_t *) = h->op->remove_callback ? h->op->remove_callback : nop_remove_callback; - - for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { - list_foreach_safe(h->bucket[idx], cur, next) { - assert(cur); - ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - - list_remove(cur); - remove_cb(cur_link); - } - } - - h->item_cnt = 0; -} - -/** Insert item into a hash table. - * - * @param h Hash table. - * @param item Item to be inserted into the hash table. - */ -void hash_table_insert(hash_table_t *h, ht_link_t *item) -{ - assert(item); - assert(h && h->bucket); - assert(!h->apply_ongoing); - - size_t idx = h->op->hash(item) % h->bucket_cnt; - - list_append(&item->link, &h->bucket[idx]); - ++h->item_cnt; - grow_if_needed(h); -} - -/** Insert item into a hash table if not already present. - * - * @param h Hash table. - * @param item Item to be inserted into the hash table. - * - * @return False if such an item had already been inserted. - * @return True if the inserted item was the only item with such a lookup key. - */ -bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item) -{ - assert(item); - assert(h && h->bucket && h->bucket_cnt); - assert(h->op && h->op->hash && h->op->equal); - assert(!h->apply_ongoing); - - size_t idx = h->op->hash(item) % h->bucket_cnt; - - /* Check for duplicates. */ - list_foreach(h->bucket[idx], link, ht_link_t, cur_link) { - /* - * We could filter out items using their hashes first, but - * calling equal() might very well be just as fast. - */ - if (h->op->equal(cur_link, item)) - return false; - } - - list_append(&item->link, &h->bucket[idx]); - ++h->item_cnt; - grow_if_needed(h); - - return true; -} - -/** 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. - * - */ -ht_link_t *hash_table_find(const hash_table_t *h, const void *key) -{ - assert(h && h->bucket); - - size_t idx = h->op->key_hash(key) % h->bucket_cnt; - - list_foreach(h->bucket[idx], link, ht_link_t, cur_link) { - /* - * Is this is the item we are looking for? We could have first - * checked if the hashes match but op->key_equal() may very well be - * just as fast as op->hash(). - */ - if (h->op->key_equal(key, cur_link)) { - return cur_link; - } - } - - return NULL; -} - -/** Find the next item equal to item. */ -ht_link_t * -hash_table_find_next(const hash_table_t *h, ht_link_t *first, ht_link_t *item) -{ - assert(item); - assert(h && h->bucket); - - size_t idx = h->op->hash(item) % h->bucket_cnt; - - /* Traverse the circular list until we reach the starting item again. */ - for (link_t *cur = item->link.next; cur != &first->link; - cur = cur->next) { - assert(cur); - - if (cur == &h->bucket[idx].head) - continue; - - ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - /* - * Is this is the item we are looking for? We could have first - * checked if the hashes match but op->equal() may very well be - * just as fast as op->hash(). - */ - if (h->op->equal(cur_link, item)) { - return cur_link; - } - } - - 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. - * - * @return Returns the number of removed items. - */ -size_t hash_table_remove(hash_table_t *h, const void *key) -{ - assert(h && h->bucket); - assert(!h->apply_ongoing); - - size_t idx = h->op->key_hash(key) % h->bucket_cnt; - - size_t removed = 0; - - list_foreach_safe(h->bucket[idx], cur, next) { - ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - - if (h->op->key_equal(key, cur_link)) { - ++removed; - list_remove(cur); - - if (h->op->remove_callback) - h->op->remove_callback(cur_link); - } - } - - h->item_cnt -= removed; - shrink_if_needed(h); - - return removed; -} - -/** Removes an item already present in the table. The item must be in the table. */ -void hash_table_remove_item(hash_table_t *h, ht_link_t *item) -{ - assert(item); - assert(h && h->bucket); - assert(link_in_use(&item->link)); - - list_remove(&item->link); - --h->item_cnt; - - if (h->op->remove_callback) - h->op->remove_callback(item); - shrink_if_needed(h); -} - -/** Apply function to all items in hash table. - * - * @param h Hash table. - * @param f Function to be applied. Return false if no more items - * should be visited. The functor may only delete the supplied - * item. It must not delete the successor of the item passed - * in the first argument. - * @param arg Argument to be passed to the function. - */ -void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg) -{ - assert(f); - assert(h && h->bucket); - - if (h->item_cnt == 0) - return; - - h->apply_ongoing = true; - - for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { - list_foreach_safe(h->bucket[idx], cur, next) { - ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - /* - * The next pointer had already been saved. f() may safely - * delete cur (but not next!). - */ - if (!f(cur_link, arg)) - goto out; - } - } -out: - h->apply_ongoing = false; - - shrink_if_needed(h); - grow_if_needed(h); -} - -/** Rounds up size to the nearest suitable table size. */ -static size_t round_up_size(size_t size) -{ - size_t rounded_size = HT_MIN_BUCKETS; - - while (rounded_size < size) { - rounded_size = 2 * rounded_size + 1; - } - - return rounded_size; -} - -/** Allocates and initializes the desired number of buckets. True if successful. */ -static bool alloc_table(size_t bucket_cnt, list_t **pbuckets) -{ - assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt); - - list_t *buckets = malloc(bucket_cnt * sizeof(list_t)); - if (!buckets) - return false; - - for (size_t i = 0; i < bucket_cnt; i++) - list_initialize(&buckets[i]); - - *pbuckets = buckets; - return true; -} - -/** Shrinks the table if the table is only sparely populated. */ -static inline void shrink_if_needed(hash_table_t *h) -{ - if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) { - /* - * Keep the bucket_cnt odd (possibly also prime). - * Shrink from 2n + 1 to n. Integer division discards the +1. - */ - size_t new_bucket_cnt = h->bucket_cnt / 2; - resize(h, new_bucket_cnt); - } -} - -/** Grows the table if table load exceeds the maximum allowed. */ -static inline void grow_if_needed(hash_table_t *h) -{ - /* Grow the table if the average bucket load exceeds the maximum. */ - if (h->full_item_cnt < h->item_cnt) { - /* Keep the bucket_cnt odd (possibly also prime). */ - size_t new_bucket_cnt = 2 * h->bucket_cnt + 1; - resize(h, new_bucket_cnt); - } -} - -/** Allocates and rehashes items to a new table. Frees the old table. */ -static void resize(hash_table_t *h, size_t new_bucket_cnt) -{ - assert(h && h->bucket); - assert(HT_MIN_BUCKETS <= new_bucket_cnt); - - /* We are traversing the table and resizing would mess up the buckets. */ - if (h->apply_ongoing) - return; - - list_t *new_buckets; - - /* Leave the table as is if we cannot resize. */ - if (!alloc_table(new_bucket_cnt, &new_buckets)) - return; - - if (0 < h->item_cnt) { - /* Rehash all the items to the new table. */ - for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) { - list_foreach_safe(h->bucket[old_idx], cur, next) { - ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - - size_t new_idx = h->op->hash(cur_link) % new_bucket_cnt; - list_remove(cur); - list_append(cur, &new_buckets[new_idx]); - } - } - } - - free(h->bucket); - h->bucket = new_buckets; - h->bucket_cnt = new_bucket_cnt; - h->full_item_cnt = h->max_load * h->bucket_cnt; -} - -/** @} - */ Index: uspace/lib/c/generic/adt/list.c =================================================================== --- uspace/lib/c/generic/adt/list.c (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,117 +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 - * @brief Functions completing doubly linked circular list implementation. - * - * This file contains some of the functions implementing doubly linked circular lists. - * However, this ADT is mostly implemented in @ref list.h. - */ - -#include -#include -#include - -/** Check for membership - * - * Check whether link is contained in a list. - * Membership is defined as pointer equivalence. - * - * @param link Item to look for. - * @param list List to look in. - * - * @return true if link is contained in list, false otherwise. - * - */ -bool list_member(const link_t *link, const list_t *list) -{ - bool found = false; - link_t *hlp = list->head.next; - - while (hlp != &list->head) { - if (hlp == link) { - found = true; - break; - } - hlp = hlp->next; - } - - return found; -} - -/** Moves items of one list into another after the specified item. - * - * Inserts all items of @a list after item at @a pos in another list. - * Both lists may be empty. - * - * @param list Source list to move after pos. Empty afterwards. - * @param pos Source items will be placed after this item. - */ -void list_splice(list_t *list, link_t *pos) -{ - if (list_empty(list)) - return; - - /* Attach list to destination. */ - list->head.next->prev = pos; - list->head.prev->next = pos->next; - - /* Link destination list to the added list. */ - pos->next->prev = list->head.prev; - pos->next = list->head.next; - - list_initialize(list); -} - -/** Count list items - * - * Return the number of items in the list. - * - * @param list List to count. - * @return Number of items in the list. - */ -size_t list_count(const list_t *list) -{ - size_t count = 0; - - link_t *link = list_first(list); - while (link != NULL) { - count++; - link = list_next(link, list); - } - - return count; -} - -/** @} - */ Index: uspace/lib/c/generic/adt/odict.c =================================================================== --- uspace/lib/c/generic/adt/odict.c (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,1 +1,0 @@ -../../../../../kernel/generic/src/adt/odict.c Index: uspace/lib/c/generic/adt/prodcons.c =================================================================== --- uspace/lib/c/generic/adt/prodcons.c (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,72 +1,0 @@ -/* - * 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 - */ - -#include -#include -#include - -void prodcons_initialize(prodcons_t *pc) -{ - list_initialize(&pc->list); - fibril_mutex_initialize(&pc->mtx); - fibril_condvar_initialize(&pc->cv); -} - -void prodcons_produce(prodcons_t *pc, link_t *item) -{ - fibril_mutex_lock(&pc->mtx); - - list_append(item, &pc->list); - fibril_condvar_signal(&pc->cv); - - fibril_mutex_unlock(&pc->mtx); -} - -link_t *prodcons_consume(prodcons_t *pc) -{ - fibril_mutex_lock(&pc->mtx); - - while (list_empty(&pc->list)) - fibril_condvar_wait(&pc->cv, &pc->mtx); - - link_t *head = list_first(&pc->list); - list_remove(head); - - fibril_mutex_unlock(&pc->mtx); - - return head; -} - -/** @} - */ Index: uspace/lib/c/include/adt/checksum.h =================================================================== --- uspace/lib/c/include/adt/checksum.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,47 +1,0 @@ -/* - * 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: uspace/lib/c/include/adt/circ_buf.h =================================================================== --- uspace/lib/c/include/adt/circ_buf.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,66 +1,0 @@ -/* - * 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: uspace/lib/c/include/adt/fifo.h =================================================================== --- uspace/lib/c/include/adt/fifo.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (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/c/include/adt/gcdlcm.h =================================================================== --- uspace/lib/c/include/adt/gcdlcm.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,74 +1,0 @@ -/* - * 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: uspace/lib/c/include/adt/hash.h =================================================================== --- uspace/lib/c/include/adt/hash.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,113 +1,0 @@ -/* - * 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) -{ -#ifdef __32_BITS__ - return hash_mix32(hash); -#elif defined(__64_BITS__) - return hash_mix64(hash); -#else -#error Unknown size_t size - cannot select proper hash mix function. -#endif -} - -/** Use to create a hash from multiple values. - * - * Typical usage: - * @code - * int car_id; - * bool car_convertible; - * // .. - * size_t hash = 0; - * hash = hash_combine(hash, car_id); - * hash = hash_combine(hash, car_convertible); - * // Now use hash as a hash of both car_id and car_convertible. - * @endcode - */ -static inline size_t hash_combine(size_t seed, size_t hash) -{ - /* - * todo: use Bob Jenkin's proper mixing hash pass: - * http://burtleburtle.net/bob/c/lookup3.c - */ - seed ^= hash + 0x9e3779b9 + - ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5))); - return seed; -} - -#endif Index: uspace/lib/c/include/adt/hash_table.h =================================================================== --- uspace/lib/c/include/adt/hash_table.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,108 +1,0 @@ -/* - * 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: uspace/lib/c/include/adt/list.h =================================================================== --- uspace/lib/c/include/adt/list.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,473 +1,0 @@ -/* - * 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: uspace/lib/c/include/adt/odict.h =================================================================== --- uspace/lib/c/include/adt/odict.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,1 +1,0 @@ -../../../../../kernel/generic/include/adt/odict.h Index: uspace/lib/c/include/adt/prodcons.h =================================================================== --- uspace/lib/c/include/adt/prodcons.h (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ (revision ) @@ -1,54 +1,0 @@ -/* - * 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 - -/** @} - */ Index: uspace/lib/c/meson.build =================================================================== --- uspace/lib/c/meson.build (revision 55c5cb056e5a70788603b6b8a7c72a8ee64389b5) +++ uspace/lib/c/meson.build (revision ad9178bfd0abd33e2c68e542c8abcd630a99e3a2) @@ -61,4 +61,10 @@ src += files( + 'common/adt/checksum.c', + 'common/adt/circ_buf.c', + 'common/adt/list.c', + 'common/adt/hash_table.c', + 'common/adt/odict.c', + 'common/adt/prodcons.c', 'common/stdc/ctype.c', 'common/stdc/mem.c', @@ -143,10 +149,4 @@ 'generic/loader.c', 'generic/getopt.c', - 'generic/adt/checksum.c', - 'generic/adt/circ_buf.c', - 'generic/adt/list.c', - 'generic/adt/hash_table.c', - 'generic/adt/odict.c', - 'generic/adt/prodcons.c', 'generic/time.c', 'generic/tmpfile.c',