Index: uspace/Makefile =================================================================== --- uspace/Makefile (revision 09a800687151d64237aaac4e609a00fbe536a57e) +++ uspace/Makefile (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) @@ -118,6 +118,6 @@ srv/net/udp \ srv/ns \ + srv/sysman \ srv/taskmon \ - srv/sysman \ srv/vfs \ srv/bd/sata_bd \ Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision 09a800687151d64237aaac4e609a00fbe536a57e) +++ uspace/lib/c/Makefile (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) @@ -146,4 +146,5 @@ generic/adt/checksum.c \ generic/adt/circ_buf.c \ + generic/adt/dyn_array.c \ generic/adt/list.c \ generic/adt/hash_table.c \ @@ -194,4 +195,5 @@ test/casting.c \ test/double_to_str.c \ + test/dyn_array.c \ test/fibril/timer.c \ test/getopt.c \ Index: uspace/lib/c/generic/adt/dyn_array.c =================================================================== --- uspace/lib/c/generic/adt/dyn_array.c (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) +++ uspace/lib/c/generic/adt/dyn_array.c (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) @@ -0,0 +1,160 @@ +/* + * Copyright (c) 2015 Michal Koutny + * 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 + * + * Implementation of dynamic array that grows or shrinks based upon no. of + * items it contains. Non-negligible part of implementation is in @ref + * dyn_array.h because of type genericity. + */ + +#include +#include +#include +#include +#include +#include + + +static void dyn_array_clear(dyn_array_t *da) +{ + da->size = 0; +} + +static int dyn_array_realloc(dyn_array_t *da, size_t capacity) +{ + if (capacity == da->capacity) { + return EOK; + } + + void *new_data = realloc(da->_data, da->_item_size * capacity); + if (new_data) { + da->_data = new_data; + da->capacity = capacity; + } + return (new_data == NULL) ? ENOMEM : EOK; +} + +void dyn_array_destroy(dyn_array_t *da) +{ + dyn_array_clear(da); + free(da->_data); + da->capacity = 0; +} + +/** Remove item at give position, shift rest of array */ +void dyn_array_remove(dyn_array_t *da, size_t index) +{ + assert(index < da->size); + _dyn_array_unshift(da, index, 1); + int rc = _dyn_array_reserve(da, da->size); + assert(rc == EOK); +} + +int _dyn_array_initialize(dyn_array_t *da, size_t item_size, size_t capacity) +{ + da->_item_size = item_size; + da->_data = NULL; + + da->capacity = 0; + da->size = 0; + + return _dyn_array_reserve(da, capacity); +} + +void *_dyn_array_get(dyn_array_t *da, size_t index) +{ + assert(index < da->size); + return da->_data + (index * da->_item_size); +} + +/** Grows/shrinks array so that it effeciently stores desired capacity + * + * @param da + * @param[in] desired capacity of array + * + * @return EOK + * @return ENOMEM + */ +int _dyn_array_reserve(dyn_array_t *da, size_t capacity) +{ + const size_t factor = 2; + size_t new_capacity; + if (capacity > da->capacity) { + new_capacity = max(da->capacity * factor, capacity); + } else if (capacity < da->capacity / factor) { + new_capacity = min(da->capacity / factor, capacity); + } else { + new_capacity = capacity; + } + + return dyn_array_realloc(da, new_capacity); +} + +/** Shift block of array + * + * Extends size of dynamic array, assumes sufficient capacity. + * + * @param da + * @param[in] index first item shifted + * @param[in] offset shift in no. of items + */ +void _dyn_array_shift(dyn_array_t *da, size_t index, size_t offset) +{ + assert(da->capacity >= da->size + offset); + + void *src = da->_data + index * da->_item_size; + void *dst = da->_data + (index + offset) * da->_item_size; + size_t size = (da->size - index) * da->_item_size; + memmove(dst, src, size); + da->size += offset; +} + +/** Unshift block of array + * + * Reduce size of dynamic array + * + * @param da + * @param[in] index first item unshifted (removed) + * @param[in] offset shift in no. of items + */ +void _dyn_array_unshift(dyn_array_t *da, size_t index, size_t offset) +{ + void *src = da->_data + (index + offset) * da->_item_size; + void *dst = da->_data + index * da->_item_size; + size_t size = (da->size - index - offset) * da->_item_size; + memmove(dst, src, size); + da->size -= offset; +} + + +/** @} + */ Index: uspace/lib/c/include/adt/dyn_array.h =================================================================== --- uspace/lib/c/include/adt/dyn_array.h (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) +++ uspace/lib/c/include/adt/dyn_array.h (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) @@ -0,0 +1,118 @@ +/* + * Copyright (c) 2015 Michal Koutny + * 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_DYN_ARRAY_H_ +#define LIBC_DYN_ARRAY_H_ + +#include +#include + +typedef struct { + /** Data buffer of array */ + uint8_t *_data; + /** Size on bytes of a single item */ + size_t _item_size; + + /** Allocated space (in items) of the array */ + size_t capacity; + /** No. of items in the array */ + size_t size; +} dyn_array_t; + +/** Initialize dynamic array + * + * @param[in] capacity initial capacity of array + * + * @return EOK on success + * @return ENOMEM on low memory + */ +#define dyn_array_initialize(dyn_array, type, capacity) \ + _dyn_array_initialize((dyn_array), sizeof(type), capacity) + + +/** Dynamic array accessor + * + * @return lvalue for the given item + */ +#define dyn_array_at(dyn_array, type, index) \ + (*((type *) _dyn_array_get((dyn_array), index))) + +/** Insert item at given position, shift rest of array + * + * @return EOK on success + * @return ENOMEM on failure + */ +#define dyn_array_insert(dyn_array, type, index, value) \ +({ \ + size_t _index = (index); \ + dyn_array_t *_da = (dyn_array); \ + int rc = _dyn_array_reserve(_da, _da->size + 1); \ + if (!rc) { \ + _dyn_array_shift(_da, _index, 1); \ + dyn_array_at(_da, type, _index) = (value); \ + } \ + rc; \ +}) + +/** Insert item at the end of array + * + * @return EOK on success + * @return ENOMEM on failure + */ +#define dyn_array_append(dyn_array, type, value) \ + dyn_array_insert(dyn_array, type, (dyn_array)->size, (value)) + + +/** Dynamic array iteration + * + * @param[in] it name of variable used as iterator, it's pointer to @p type + */ +#define dyn_array_foreach(dyn_array, type, it) \ + for (type *it = (type *)(dyn_array)._data; \ + it != ((type *)(dyn_array)._data + (dyn_array).size); ++it) + + +extern void dyn_array_destroy(dyn_array_t *); +extern void dyn_array_remove(dyn_array_t *, size_t); + +extern int _dyn_array_initialize(dyn_array_t *, size_t, size_t); +extern void *_dyn_array_get(dyn_array_t *, size_t); +extern int _dyn_array_reserve(dyn_array_t *, size_t); +extern void _dyn_array_shift(dyn_array_t *, size_t, size_t); +extern void _dyn_array_unshift(dyn_array_t *, size_t, size_t); + +#endif + +/** @} + */ Index: uspace/lib/c/test/dyn_array.c =================================================================== --- uspace/lib/c/test/dyn_array.c (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) +++ uspace/lib/c/test/dyn_array.c (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) @@ -0,0 +1,127 @@ +/* + * Copyright (c) 2015 Michal Koutny + * 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 +#include +#include + +PCUT_INIT + +PCUT_TEST_SUITE(dyn_array); + +typedef int data_t; +static dyn_array_t da; + +PCUT_TEST_BEFORE { + int rc = dyn_array_initialize(&da, data_t, 3); + assert(rc == EOK); +} + +PCUT_TEST_AFTER { + dyn_array_destroy(&da); +} + +PCUT_TEST(initialization) { + PCUT_ASSERT_INT_EQUALS(da.capacity, 3); + PCUT_ASSERT_INT_EQUALS(da.size, 0); +} + +PCUT_TEST(append) { + dyn_array_append(&da, data_t, 42); + dyn_array_append(&da, data_t, 666); + + PCUT_ASSERT_INT_EQUALS(2, da.size); + PCUT_ASSERT_INT_EQUALS(42, dyn_array_at(&da, data_t, 0)); + PCUT_ASSERT_INT_EQUALS(666, dyn_array_at(&da, data_t, 1)); +} + +PCUT_TEST(assign) { + dyn_array_append(&da, data_t, 42); + dyn_array_at(&da, data_t, 0) = 112; + + PCUT_ASSERT_INT_EQUALS(112, dyn_array_at(&da, data_t, 0)); +} + +PCUT_TEST(remove) { + dyn_array_append(&da, data_t, 10); + dyn_array_append(&da, data_t, 11); + + dyn_array_remove(&da, 0); + + PCUT_ASSERT_INT_EQUALS(1, da.size); + PCUT_ASSERT_INT_EQUALS(11, dyn_array_at(&da, data_t, 0)); +} + +PCUT_TEST(insert) { + dyn_array_append(&da, data_t, 10); + dyn_array_append(&da, data_t, 11); + dyn_array_append(&da, data_t, 12); + dyn_array_insert(&da, data_t, 1, 99); + + PCUT_ASSERT_INT_EQUALS(4, da.size); + PCUT_ASSERT_INT_EQUALS(10, dyn_array_at(&da, data_t, 0)); + PCUT_ASSERT_INT_EQUALS(99, dyn_array_at(&da, data_t, 1)); + PCUT_ASSERT_INT_EQUALS(11, dyn_array_at(&da, data_t, 2)); + PCUT_ASSERT_INT_EQUALS(12, dyn_array_at(&da, data_t, 3)); +} + +PCUT_TEST(capacity_grow) { + dyn_array_append(&da, data_t, 42); + dyn_array_append(&da, data_t, 666); + dyn_array_append(&da, data_t, 42); + dyn_array_append(&da, data_t, 666); + + PCUT_ASSERT_TRUE(da.capacity > 3); +} + +PCUT_TEST(capacity_shrink) { + dyn_array_append(&da, data_t, 42); + dyn_array_append(&da, data_t, 666); + dyn_array_append(&da, data_t, 42); + + dyn_array_remove(&da, 0); + dyn_array_remove(&da, 0); + dyn_array_remove(&da, 0); + + PCUT_ASSERT_TRUE(da.capacity < 3); +} + +PCUT_TEST(iterator) { + for (int i = 0; i < 10; ++i) { + dyn_array_append(&da, data_t, i*i); + } + + int i = 0; + dyn_array_foreach(da, data_t, it) { + PCUT_ASSERT_INT_EQUALS(i*i, *it); + ++i; + } +} + + +PCUT_EXPORT(dyn_array); Index: uspace/lib/c/test/main.c =================================================================== --- uspace/lib/c/test/main.c (revision 09a800687151d64237aaac4e609a00fbe536a57e) +++ uspace/lib/c/test/main.c (revision 62d3d87637c2dc9028f3f0c349efe6e8567b4732) @@ -36,4 +36,5 @@ PCUT_IMPORT(circ_buf); PCUT_IMPORT(double_to_str); +PCUT_IMPORT(dyn_array); PCUT_IMPORT(fibril_timer); PCUT_IMPORT(getopt);