From d91d82d86a01e4fec91ab4c06b1d7687bd0a8b33 Mon Sep 17 00:00:00 2001 From: Dmitri Pal Date: Wed, 21 Apr 2010 21:10:10 -0400 Subject: Extending refarray interface Added functions to inert, delete, replace swap the array elements. Unit test and docs have been updated accordingly. Fixing review comments for refarray. --- common/refarray/ref_array.c | 197 +++++++++++++++++++++++++++++++- common/refarray/ref_array.h | 115 +++++++++++++++++++ common/refarray/ref_array_ut.c | 252 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 563 insertions(+), 1 deletion(-) (limited to 'common') diff --git a/common/refarray/ref_array.c b/common/refarray/ref_array.c index d33a16b4..d02f9aed 100644 --- a/common/refarray/ref_array.c +++ b/common/refarray/ref_array.c @@ -194,7 +194,7 @@ int ref_array_append(struct ref_array *ra, void *element) error = ref_array_grow(ra); if (error) { TRACE_ERROR_NUMBER("Failed to grow array.", error); - return EINVAL; + return error; } } @@ -272,6 +272,201 @@ uint32_t ref_array_len(struct ref_array *ra) } +/* Insert a new element into the array */ +int ref_array_insert(struct ref_array *ra, + uint32_t idx, + void *element) +{ + int error = EOK; + uint32_t i; + + TRACE_FLOW_STRING("ref_array_insert", "Entry"); + + if ((!ra) || (!element)) { + TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL); + return EINVAL; + } + + if (idx > ra->len) { + TRACE_ERROR_NUMBER("Index is out of range", ERANGE); + return ERANGE; + } + + /* Do we have enough room for a new element? */ + if (ra->size == ra->len) { + error = ref_array_grow(ra); + if (error) { + TRACE_ERROR_NUMBER("Failed to grow array.", error); + return error; + } + } + + /* Shift elements right */ + for (i = ra->len; i >= (idx + 1); i--) { + memcpy((unsigned char *)(ra->storage) + i * ra->elsize, + (unsigned char *)(ra->storage) + (i - 1) * ra->elsize, + ra->elsize); + } + + /* Overwrite element */ + memcpy((unsigned char *)(ra->storage) + idx * ra->elsize, + element, + ra->elsize); + + ra->len++; + + TRACE_FLOW_STRING("ref_array_insert", "Exit"); + return error; + +} + + +/* Replace element in the array */ +int ref_array_replace(struct ref_array *ra, + uint32_t idx, + void *element) +{ + int error = EOK; + + TRACE_FLOW_STRING("ref_array_replace", "Entry"); + + if ((!ra) || (!element)) { + TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL); + return EINVAL; + } + + if (idx > ra->len) { + TRACE_ERROR_NUMBER("Index is out of range", ERANGE); + return ERANGE; + } + + /* Clear old element */ + ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize, + REF_ARRAY_DELETE, ra->cb_data); + + /* Overwrite element */ + memcpy((unsigned char *)(ra->storage) + idx * ra->elsize, + element, + ra->elsize); + + + TRACE_FLOW_STRING("ref_array_replace", "Exit"); + return error; +} + + +/* Remove element from the array */ +int ref_array_remove(struct ref_array *ra, + uint32_t idx) +{ + int error = EOK; + uint32_t i; + + TRACE_FLOW_STRING("ref_array_remove", "Entry"); + + if (!ra) { + TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL); + return EINVAL; + } + + if (idx >= ra->len) { + TRACE_ERROR_NUMBER("Index is out of range", ERANGE); + return ERANGE; + } + + /* Clear old element */ + ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize, + REF_ARRAY_DELETE, ra->cb_data); + + /* Shift elements left */ + for (i = idx + 1; i < ra->len; i++) { + memcpy((unsigned char *)(ra->storage) + (i - 1) * ra->elsize, + (unsigned char *)(ra->storage) + i * ra->elsize, + ra->elsize); + } + + ra->len--; + + TRACE_FLOW_STRING("ref_array_remove", "Exit"); + return error; +} + +/* Reset array */ +void ref_array_reset(struct ref_array *ra) +{ + int idx; + + TRACE_FLOW_STRING("ref_array_reset", "Entry"); + + /* Check if array is not NULL */ + if (!ra) { + TRACE_ERROR_STRING("Uninitialized array.", "Coding error???"); + return; + } + + if (ra->cb) { + for (idx = 0; idx < ra->len; idx++) { + ra->cb((unsigned char *)(ra->storage) + idx * ra->elsize, + REF_ARRAY_DESTROY, ra->cb_data); + } + } + + free(ra->storage); + ra->storage = NULL; + ra->size = 0; + ra->len = 0; + + TRACE_FLOW_STRING("ref_array_reset", "Exit"); +} + +/* Swap two elements in the array */ +int ref_array_swap(struct ref_array *ra, + uint32_t idx1, + uint32_t idx2) +{ + int error = EOK; + void *temp = NULL; + + TRACE_FLOW_STRING("ref_array_swap", "Entry"); + + if (!ra) { + TRACE_ERROR_NUMBER("Uninitialized argument.", EINVAL); + return EINVAL; + } + + if ((idx1 >= ra->len) || + (idx2 >= ra->len)) { + TRACE_ERROR_NUMBER("Index is out of range", ERANGE); + return ERANGE; + } + + if (idx1 == idx2) { + TRACE_FLOW_STRING("ref_array_swap", "Noop return"); + return EOK; + } + + temp = malloc(ra->elsize); + if (!temp) { + TRACE_FLOW_STRING("Failed to allocate memory for temp storage.", ""); + return ENOMEM; + } + + memcpy(temp, + (unsigned char *)(ra->storage) + idx2 * ra->elsize, + ra->elsize); + memcpy((unsigned char *)(ra->storage) + idx2 * ra->elsize, + (unsigned char *)(ra->storage) + idx1 * ra->elsize, + ra->elsize); + memcpy((unsigned char *)(ra->storage) + idx1 * ra->elsize, + temp, + ra->elsize); + + free(temp); + + TRACE_FLOW_STRING("ref_array_swap", "Exit"); + return error; +} + /* Debug function */ void ref_array_debug(struct ref_array *ra) { diff --git a/common/refarray/ref_array.h b/common/refarray/ref_array.h index 004c460c..4b4b2de6 100644 --- a/common/refarray/ref_array.h +++ b/common/refarray/ref_array.h @@ -77,6 +77,7 @@ typedef enum REF_ARRAY_DELETE, } ref_array_del_enum; + /** * @brief Element cleanup callback * @@ -198,6 +199,120 @@ int ref_array_getlen(struct ref_array *ra, uint32_t *len); */ uint32_t ref_array_len(struct ref_array *ra); +/** + * @brief Insert a new element into the array + * + * Inserts an element into the array. + * If idx is 0 the element will be added + * to the beginning of the array, + * if idx is 1 the element will be added + * after the first element of the array + * and so on. + * If index is greater than the number of + * elements in the array the function + * returns error. + * + * @param[in] ra Existing array object. + * @param[in] idx Index of the array element. + * @param[in] element Pointer to data. + * The number of bytes + * defined at the array creation + * as the array size will be copied + * into the array element. + * + * @return 0 - Success. + * @return ENOMEM - No memory. + * @return EINVAL - Invalid argument. + * @return ERANGE - Index is our of range. + */ +int ref_array_insert(struct ref_array *ra, + uint32_t idx, + void *element); +/** + * @brief Replace element in the array + * + * Replace an element of the array + * identified by index with a new value. + * If index is greater than the number of + * elements in the array the function + * returns error. + * + * @param[in] ra Existing array object. + * @param[in] idx Index of the array element. + * @param[in] element Pointer to data. + * The number of bytes + * defined at the array creation + * as the array size will be copied + * into the array element. + * + * @return 0 - Success. + * @return ENOMEM - No memory. + * @return EINVAL - Invalid argument. + * @return ERANGE - Index is our of range. + */ +int ref_array_replace(struct ref_array *ra, + uint32_t idx, + void *element); + + +/** + * @brief Remove element from the array + * + * The element is removed and the length + * is decreased by 1. + * If index is greater than the number of + * elements in the array the function + * returns error. + * + * @param[in] ra Existing array object. + * @param[in] idx Index of the array element. + * + * @return 0 - Success. + * @return EINVAL - Invalid argument. + * @return ERANGE - Index is our of range. + */ +int ref_array_remove(struct ref_array *ra, + uint32_t idx); + + +/** + * @brief Swap two elements in the array + * + * If any of the indexes is greater than + * the number of elements in the array + * the function returns error. + * + * @param[in] ra Existing array object. + * @param[in] idx1 Index of the array element. + * @param[in] idx2 Index of the array element. + * + * @return 0 - Success. + * @return EINVAL - Invalid argument. + * @return ERANGE - Index is our of range. + * @return ENOMEM - No memory. + */ +int ref_array_swap(struct ref_array *ra, + uint32_t idx1, + uint32_t idx2); + + +/** + * @brief Reset array + * + * Function clears all contents without destroying + * the object. The delete callback will be called + * for every element of the array from the beginning + * to the end passing in REF_ARRAY_DESTROY value. + * All the storage for the array will be deallocated. + * After the call the array will be empty as if just created. + * + * + * @param[in] ra Existing array object. + * No return value. + * + */ +void ref_array_reset(struct ref_array *ra); + /** * @} */ diff --git a/common/refarray/ref_array_ut.c b/common/refarray/ref_array_ut.c index c85b6b26..6e6009a0 100644 --- a/common/refarray/ref_array_ut.c +++ b/common/refarray/ref_array_ut.c @@ -309,6 +309,257 @@ int ref_array_free_test(void) return EOK; } +int ref_array_adv_test(void) +{ + int error = EOK; + const char *lines[] = { "line0", + "line1", + "line2", + "line3", + "line4", + "line5", + "line6", + "line7", + "line8", + "line9" }; + char text[] = "Deleting: "; + char *str; + uint32_t i; + struct ref_array *ra; + char *ret; + void *ptr; + int expected[] = { 0, 1, 7, 8, 9 }; + int expected2[] = { 1, 7, 8, 9, 0 }; + + error = ref_array_create(&ra, + sizeof(char *), + 1, + array_cleanup, + (char *)text); + if (error) { + printf("Failed to create array %d\n", error); + return error; + } + + for (i = 0; i < 5;i++) { + + str = strdup(lines[i]); + + error = ref_array_append(ra, &str); + if (error) { + ref_array_destroy(ra); + printf("Failed to append line %d, error %d\n", + i, error); + return error; + } + } + + RAOUT(printf("\nInitial array.\n")); + + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("%s\n", ret)); + i++; + } + else break; + } + + + /* Try to remove invalid entry */ + error = ref_array_remove(ra, 1000); + if (error != ERANGE) { + ref_array_destroy(ra); + printf("Removing entry expected error got success.\n"); + return -1; + } + + /* Try to insert invalid entry */ + error = ref_array_insert(ra, 1000, &text); + if (error != ERANGE) { + ref_array_destroy(ra); + printf("Inserting entry expected error got success.\n"); + return -1; + } + + /* Try to replace invalid entry */ + error = ref_array_replace(ra, 1000, &text); + if (error != ERANGE) { + ref_array_destroy(ra); + printf("Replacing entry expected error got success.\n"); + return -1; + } + + /* Insert several entries */ + for (i = 9; i > 4; i--) { + + str = strdup(lines[i]); + + error = ref_array_insert(ra, 9 - i, &str); + if (error) { + ref_array_destroy(ra); + free(str); + printf("Failed to insert line %d, error %d\n", + i, error); + return error; + } + } + + /* Displpay array contents */ + RAOUT(printf("\nArray with inserted values.\n")); + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("%s\n", ret)); + i++; + } + else break; + } + + /* Replace everything */ + for (i = 0; i < 10;i++) { + + str = strdup(lines[i]); + + error = ref_array_replace(ra, i, &str); + if (error) { + ref_array_destroy(ra); + free(str); + printf("Failed to replace line %d, error %d\n", + i, error); + return error; + } + } + + /* Displpay array contents */ + RAOUT(printf("\nArray with replaced values.\n")); + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("%s\n", ret)); + i++; + } + else break; + } + + /* Reset */ + ref_array_reset(ra); + + /* Displpay array contents */ + RAOUT(printf("\nEmpty array.\n")); + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("%s\n", ret)); + i++; + } + else break; + } + + /* Add everything */ + for (i = 0; i < 10;i++) { + + str = strdup(lines[i]); + + error = ref_array_insert(ra, i, &str); + if (error) { + ref_array_destroy(ra); + free(str); + printf("Failed to insert into array %d\n", error); + return error; + } + } + + /* Displpay array contents */ + RAOUT(printf("\nAll added back.\n")); + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("%s\n", ret)); + i++; + } + else break; + } + + /* Remove part */ + for (i = 0; i < 5;i++) { + + error = ref_array_remove(ra, 2); + if (error) { + ref_array_destroy(ra); + printf("Failed to remive item from array %d\n", error); + return error; + } + } + + /* Displpay array contents */ + RAOUT(printf("\nCleaned array.\n")); + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("%s\n", ret)); + i++; + } + else break; + } + + RAOUT(printf("\n\nChecking for expected contents\n\n")); + + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("Comparing:\n[%s]\n[%s]\n\n", + ret, lines[expected[i]])); + if (strcmp(ret, lines[expected[i]]) != 0) { + printf("Unexpected contents of the array.\n"); + ref_array_destroy(ra); + return -1; + } + i++; + } + else break; + } + + RAOUT(printf("\n\nSwap test\n\n")); + + if ((error = ref_array_swap(ra, 0, 1)) || + (error = ref_array_swap(ra, 1, 2)) || + (error = ref_array_swap(ra, 2, 3)) || + (error = ref_array_swap(ra, 3, 4))) { + ref_array_destroy(ra); + printf("Failed to to swap %d\n", error); + return error; + } + + i = 0; + for (;;) { + ptr = ref_array_get(ra, i, &ret); + if (ptr) { + RAOUT(printf("Comparing:\n[%s]\n[%s]\n\n", + ret, lines[expected2[i]])); + if (strcmp(ret, lines[expected2[i]]) != 0) { + printf("Unexpected contents of the array.\n"); + ref_array_destroy(ra); + return -1; + } + i++; + } + else break; + } + + RAOUT(printf("\n\nDone!!!\n\n")); + + ref_array_destroy(ra); + return EOK; +} + /* Main function of the unit test */ @@ -317,6 +568,7 @@ int main(int argc, char *argv[]) int error = 0; test_fn tests[] = { ref_array_basic_test, ref_array_free_test, + ref_array_adv_test, NULL }; test_fn t; int i = 0; -- cgit