From ef26defe61683bd3a5a542fa86171187731fede6 Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Fri, 5 Apr 2013 21:52:17 -0400 Subject: [PATCH] Added partial vector implementation --- premake4.lua | 1 + source/vector/vec.c | 175 ++++++++++++++++++++++ source/vector/vec.h | 40 +++++- tests/test_vec.cpp | 343 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 552 insertions(+), 7 deletions(-) create mode 100644 source/vector/vec.c create mode 100644 tests/test_vec.cpp diff --git a/premake4.lua b/premake4.lua index 36e5da4..2374a71 100644 --- a/premake4.lua +++ b/premake4.lua @@ -13,6 +13,7 @@ project "cds" language "C" location "build" files { "source/**.*" } + buildflags { "extra-warnings", "fatal-warnings", "no-symbols", "optimize" } project "tests" kind "ConsoleApp" diff --git a/source/vector/vec.c b/source/vector/vec.c new file mode 100644 index 0000000..f108a54 --- /dev/null +++ b/source/vector/vec.c @@ -0,0 +1,175 @@ +/** + @file vec.c + @brief See header for details + $Revision$ + $HeadURL$ +*/ +#include "vec.h" +#include +#include + +vec_t* vec_new(bool own_contents, size_t num_elements, ...) +{ + vec_t* p_vec; + va_list elements; + size_t index; + + /* Allocate and construct the vector object */ + p_vec = (vec_t*)malloc( sizeof(vec_t) ); + p_vec->own_contents = own_contents; + p_vec->size = num_elements; + p_vec->capacity = (0 == num_elements) ? DEFAULT_VEC_CAPACITY : num_elements; + p_vec->p_buffer = (void**)malloc( sizeof(void*) * p_vec->capacity ); + + /* Populate the array with the elements list */ + va_start(elements, num_elements); + for (index = 0; index < num_elements; index++) + { + p_vec->p_buffer[index] = va_arg(elements,void*); + } + va_end(elements); + + return p_vec; +} + +void vec_free(vec_t* p_vec) +{ + if (p_vec->own_contents) + { + vec_clear(p_vec); + } + free(p_vec->p_buffer); + free(p_vec); +} + +void vec_free_range(void** p_buffer, size_t start_idx, size_t end_idx) +{ + size_t i; + for(i = start_idx; i < end_idx; i++) + { + free(p_buffer[i]); + } +} + +size_t vec_size(vec_t* p_vec) +{ + return p_vec->size; +} + +size_t vec_max_size(void) +{ + return (size_t)-1; +} + +bool vec_empty(vec_t* p_vec) +{ + return (0 == vec_size(p_vec)); +} + +void vec_resize(vec_t* p_vec, size_t size, void* data) +{ + if (size > p_vec->size) + { + vec_reserve(p_vec,size); + for (p_vec->size; p_vec->size < size; p_vec->size++) + { + p_vec->p_buffer[ p_vec->size ] = data; + } + } + else if (size < p_vec->size) + { + if (p_vec->own_contents) + vec_free_range(p_vec->p_buffer, size-1, p_vec->size); + p_vec->size = size; + } +} + +void vec_shrink_to_fit(vec_t* p_vec) +{ + p_vec->p_buffer = realloc( p_vec->p_buffer, sizeof(void*) * p_vec->size ); + p_vec->capacity = p_vec->size; +} + +size_t vec_capacity(vec_t* p_vec) +{ + return p_vec->capacity; +} + +void vec_reserve(vec_t* p_vec, size_t size) +{ + p_vec->p_buffer = realloc( p_vec->p_buffer, sizeof(void*) * size ); + p_vec->capacity = size; +} + +void* vec_at(vec_t* p_vec, size_t index) +{ + void* p_ret = NULL; + if (index < p_vec->size) + { + p_ret = p_vec->p_buffer[index]; + } + return p_ret; +} + +bool vec_set(vec_t* p_vec, size_t index, void* data) +{ + bool ret = false; + if (index < p_vec->size) + { + p_vec->p_buffer[index] = data; + ret = true; + } + return ret; +} + +bool vec_insert(vec_t* p_vec, size_t index, size_t num_elements, ...) +{ + bool ret = false; + return ret; +} + +bool vec_erase(vec_t* p_vec, size_t start_idx, size_t end_idx) +{ + bool ret = false; + size_t index; + /* if the range is valid */ + if ((start_idx < p_vec->size) && (end_idx < p_vec->size) && (start_idx <= end_idx)) + { + /* Free the range of data */ + if (p_vec->own_contents) + { + vec_free_range(p_vec->p_buffer, start_idx, end_idx + 1); + } + /* Compact the remaining data */ + memcpy( &(p_vec->p_buffer[start_idx]), /* Destination is beginning of erased range */ + &(p_vec->p_buffer[end_idx+1]), /* Source is end of erased range */ + sizeof(void*) * (p_vec->size - end_idx)); + /* Shrink the size */ + p_vec->size = p_vec->size - ((end_idx - start_idx) + 1); + ret = true; + } + return ret; +} + +void vec_push_back(vec_t* p_vec, void* data) +{ + vec_resize(p_vec, p_vec->size+1, data); +} + +void* vec_pop_back(vec_t* p_vec) +{ + void* p_ret = NULL; + if (p_vec->size > 0) + { + p_vec->size = p_vec->size - 1; + p_ret = p_vec->p_buffer[p_vec->size]; + } + return p_ret; +} + +void vec_clear(vec_t* p_vec) +{ + vec_free_range(p_vec->p_buffer, 0, p_vec->size); + p_vec->size = 0; +} + diff --git a/source/vector/vec.h b/source/vector/vec.h index 18c5d60..99125ae 100644 --- a/source/vector/vec.h +++ b/source/vector/vec.h @@ -9,15 +9,26 @@ #include #include +#include /** A vector implementation */ typedef struct { - bool own_contents; - size_t capacity; - size_t size; - void** p_buffer; + bool own_contents; /*< Whether the vector is responsible for freeing it's contents */ + size_t size; /*< The number of elements currently in the array */ + size_t capacity; /*< The size of the internal array */ + void** p_buffer; /*< Pointer to the array */ } vec_t; +#ifdef __cplusplus +extern "C" { +#endif + +/** The default capacity of the vector if no initializing elements have been + * provided. */ +#ifndef DEFAULT_VEC_CAPACITY +#define DEFAULT_VEC_CAPACITY (size_t)8 +#endif + /** * @brief Creates a new vector initialized with the given elements. * @@ -37,6 +48,15 @@ vec_t* vec_new(bool own_contents, size_t num_elements, ...); */ void vec_free(vec_t* p_vec); +/** + * @brief Calls free on a range of pointers in an array. + * + * @param p_buffer Pointer to the array. + * @param start_idx The index at which the process will start. + * @param end_idx The index at which the process will end. + */ +void vec_free_range(void** p_buffer, size_t start_idx, size_t end_idx); + /** * @brief Returns the number of items in the vector. * @@ -112,7 +132,7 @@ void* vec_at(vec_t* p_vec, size_t index); * @param index The index of the element to set. * @param data The new data for the indexed element. */ -void vec_set(vec_t* p_vec, size_t index, void* data); +bool vec_set(vec_t* p_vec, size_t index, void* data); /** * @brief Inserts the provided elements at the given index. @@ -122,7 +142,7 @@ void vec_set(vec_t* p_vec, size_t index, void* data); * @param num_elements The number of elements to insert. * @param ... The elements to insert. */ -void vec_insert(vec_t* p_vec, size_t index, size_t num_elements, ...); +bool vec_insert(vec_t* p_vec, size_t index, size_t num_elements, ...); /** * @brief Erases elements from the vector that fall into the given range. @@ -130,8 +150,10 @@ void vec_insert(vec_t* p_vec, size_t index, size_t num_elements, ...); * @param p_vec Pointer to the vector. * @param start_idx The start of the range. * @param end_idx The end of the range. + * + * @return Whether the operation was successful. */ -void vec_erase(vec_t* p_vec, size_t start_idx, size_t end_idx); +bool vec_erase(vec_t* p_vec, size_t start_idx, size_t end_idx); /** * @brief Pushes the provided element on to the back of the vector. @@ -157,4 +179,8 @@ void* vec_pop_back(vec_t* p_vec); */ void vec_clear(vec_t* p_vec); +#ifdef __cplusplus +} +#endif + #endif /* VEC_H */ diff --git a/tests/test_vec.cpp b/tests/test_vec.cpp new file mode 100644 index 0000000..c94052a --- /dev/null +++ b/tests/test_vec.cpp @@ -0,0 +1,343 @@ +// Unit Test Framework Includes +#include "UnitTest++.h" +#include +#include + +// File To Test +#include "vec.h" + +using namespace UnitTest; + +//----------------------------------------------------------------------------- +// Begin Unit Tests +//----------------------------------------------------------------------------- +namespace { + //------------------------------------------------------------------------- + // Test vec_new function + //------------------------------------------------------------------------- + TEST(Verify_vec_new_returns_newly_allocated_vector_with_default_capacity) + { + vec_t* p_vec = vec_new(true,0); + CHECK(NULL != p_vec); + CHECK(true == p_vec->own_contents); + CHECK(0 == p_vec->size); + CHECK(DEFAULT_VEC_CAPACITY == p_vec->capacity); + CHECK(NULL != p_vec->p_buffer); + vec_free(p_vec); + } + + TEST(Verify_vec_new_returns_newly_allocated_vector_with_the_provided_elements) + { + vec_t* p_vec = vec_new(false,2,(void*)0x1234,(void*)0x4321); + CHECK(NULL != p_vec); + CHECK(false == p_vec->own_contents); + CHECK(2 == p_vec->size); + CHECK(2 == p_vec->capacity); + CHECK(NULL != p_vec->p_buffer); + CHECK((void*)0x1234 == p_vec->p_buffer[0]); + CHECK((void*)0x4321 == p_vec->p_buffer[1]); + vec_free(p_vec); + } + + //------------------------------------------------------------------------- + // Test vec_free function + //------------------------------------------------------------------------- + TEST(Verify_vec_free_frees_the_vector_and_contents) + { + vec_t* p_vec = vec_new(true,0); + vec_free(p_vec); + } + + TEST(Verify_vec_free_frees_the_vector) + { + vec_t* p_vec = vec_new(false,0); + vec_free(p_vec); + } + + //------------------------------------------------------------------------- + // Test vec_size function + //------------------------------------------------------------------------- + TEST(Verify_vec_size_returns_the_correct_size) + { + vec_t vector = { false, 42, 24, NULL }; + CHECK(42 == vec_size(&vector)); + } + + //------------------------------------------------------------------------- + // Test vec_max_size function + //------------------------------------------------------------------------- + TEST(Verify_vec_max_size_returns_the_correct_size) + { + CHECK((size_t)-1 == vec_max_size()); + } + + //------------------------------------------------------------------------- + // Test vec_empty function + //------------------------------------------------------------------------- + TEST(Verify_vec_empty_returns_true_if_empty) + { + vec_t vector = { false, 0, 24, NULL }; + CHECK(true == vec_empty(&vector)); + } + + TEST(Verify_vec_empty_returns_false_if_not_empty) + { + vec_t vector = { false, 42, 24, NULL }; + CHECK(false == vec_empty(&vector)); + } + + //------------------------------------------------------------------------- + // Test vec_resize function + //------------------------------------------------------------------------- + TEST(Verify_vec_resize_does_nothing_if_size_is_the_same) + { + vec_t* p_vec = vec_new(false,3,0,1,2); + vec_resize( p_vec, 3, (void*)0x2A ); + + CHECK( false == p_vec->own_contents ); + CHECK( 3 == p_vec->size ); + CHECK( 3 == p_vec->capacity ); + + vec_free( p_vec ); + } + + TEST(Verify_vec_resize_should_erase_the_last_element) + { + vec_t* p_vec = vec_new(false,3,0,1,2); + vec_resize( p_vec, 2, (void*)0x2A ); + + CHECK( false == p_vec->own_contents ); + CHECK( 2 == p_vec->size ); + CHECK( 3 == p_vec->capacity ); + + vec_free( p_vec ); + } + + TEST(Verify_vec_resize_should_erase_the_last_two_elements) + { + vec_t* p_vec = vec_new(false,3,0,1,2); + vec_resize( p_vec, 1, (void*)0x2A ); + + CHECK( false == p_vec->own_contents ); + CHECK( 1 == p_vec->size ); + CHECK( 3 == p_vec->capacity ); + + vec_free( p_vec ); + } + + TEST(Verify_vec_resize_should_add_a_new_element) + { + vec_t* p_vec = vec_new(false,3,0,1,2); + vec_resize( p_vec, 4, (void*)0x2A ); + + CHECK( false == p_vec->own_contents ); + CHECK( 4 == p_vec->size ); + CHECK( 4 == p_vec->capacity ); + CHECK( (void*)0x2A == p_vec->p_buffer[3] ); + + vec_free( p_vec ); + } + + TEST(Verify_vec_resize_should_add_two_new_elements) + { + vec_t* p_vec = vec_new(false,3,0,1,2); + vec_resize( p_vec, 5, (void*)0x2A ); + + CHECK( false == p_vec->own_contents ); + CHECK( 5 == p_vec->size ); + CHECK( 5 == p_vec->capacity ); + CHECK( (void*)0x2A == p_vec->p_buffer[3] ); + CHECK( (void*)0x2A == p_vec->p_buffer[4] ); + + vec_free( p_vec ); + } + + //------------------------------------------------------------------------- + // Test vec_shrink_to_fit function + //------------------------------------------------------------------------- + TEST(Verify_vec_shrink_to_fit_shrinks_capacity_to_equal_the_size) + { + vec_t vector = { false, 1, 2, (void**)malloc(sizeof(void*) * 2) }; + vec_shrink_to_fit(&vector); + CHECK( vector.size == vector.capacity ); + free( vector.p_buffer ); + } + + //------------------------------------------------------------------------- + // Test vec_capacity function + //------------------------------------------------------------------------- + TEST(Verify_vec_capacity_returns_the_correct_size) + { + vec_t vector = { false, 42, 24, NULL }; + CHECK(24 == vec_capacity(&vector)); + } + + //------------------------------------------------------------------------- + // Test vec_reserve function + //------------------------------------------------------------------------- + TEST(Verify_vec_reserve_reserves_a_buffer_of_the_desired_size) + { + vec_t vector = { false, 0, 0, NULL }; + vec_reserve(&vector,5); + CHECK( 5 == vector.capacity ); + free( vector.p_buffer ); + } + + //------------------------------------------------------------------------- + // Test vec_at function + //------------------------------------------------------------------------- + TEST(Verify_vec_at_returns_an_item_at_the_provided_index) + { + void* array[2] = { (void*)0x1234, (void*)0x4321 }; + vec_t vector = { false, 2, 2, array }; + CHECK((void*)0x4321 == vec_at(&vector,1)); + + } + + TEST(Verify_vec_at_returns_null_if_index_out_of_range) + { + void* array[2] = { (void*)0x1234, (void*)0x4321 }; + vec_t vector = { false, 2, 2, array }; + CHECK(NULL == vec_at(&vector,2)); + } + + //------------------------------------------------------------------------- + // Test vec_set function + //------------------------------------------------------------------------- + TEST(Verify_vec_set_sets_the_value_at_the_given_index) + { + void* data[3] = { (void*)0x1234, NULL, NULL }; + vec_t vector = { false, 2, 3, data }; + CHECK(true == vec_set(&vector,1,(void*)0x4321)); + CHECK((void*)0x4321 == data[1]); + CHECK(NULL == data[2]); + } + + TEST(Verify_vec_set_returns_false_if_index_out_of_range) + { + void* data[3] = { (void*)0x1234, NULL, NULL }; + vec_t vector = { false, 2, 3, data }; + CHECK(false == vec_set(&vector,2,(void*)0x4321)); + CHECK(NULL == data[1]); + CHECK(NULL == data[2]); + } + + //------------------------------------------------------------------------- + // Test vec_insert function + //------------------------------------------------------------------------- + //------------------------------------------------------------------------- + // Test vec_erase function + //------------------------------------------------------------------------- + TEST(Verify_vec_erase_erases_a_single_item) + { + void* data[3] = { (void*)0x1, (void*)0x2, (void*)0x3 }; + vec_t vector = { false, 3, 3, data }; + CHECK(true == vec_erase( &vector, 1, 1 )); + CHECK(2 == vector.size); + CHECK((void*)0x1 == data[0]); + CHECK((void*)0x3 == data[1]); + } + + TEST(Verify_vec_erase_erases_a_multiple_items) + { + void* data[4] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 }; + vec_t vector = { false, 4, 4, data }; + CHECK(true == vec_erase( &vector, 1, 2 )); + CHECK(2 == vector.size); + CHECK((void*)0x1 == data[0]); + CHECK((void*)0x4 == data[1]); + } + + TEST(Verify_vec_erase_erases_everything) + { + void* data[4] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 }; + vec_t vector = { false, 4, 4, data }; + CHECK(true == vec_erase( &vector, 0, 3 )); + CHECK(0 == vector.size); + } + + TEST(Verify_vec_erase_should_fail_for_invalid_ranges) + { + void* data[4] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 }; + vec_t vector = { false, 4, 4, data }; + CHECK(false == vec_erase( &vector, 0, 4 )); + } + + TEST(Verify_vec_erase_everything_but_last) + { + void* data[4] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 }; + vec_t vector = { false, 4, 4, data }; + CHECK(true == vec_erase( &vector, 0, 2 )); + CHECK((void*)0x4 == data[0]); + CHECK(1 == vector.size); + } + + TEST(Verify_vec_erase_everything_but_first) + { + void* data[4] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 }; + vec_t vector = { false, 4, 4, data }; + CHECK(true == vec_erase( &vector, 1, 3 )); + CHECK((void*)0x1 == data[0]); + CHECK(1 == vector.size); + } + + //------------------------------------------------------------------------- + // Test vec_push_back function + //------------------------------------------------------------------------- + TEST(Verify_vec_push_back_should_push_a_new_element_to_the_end) + { + vec_t* p_vec = vec_new(false,3,0,1,2); + vec_push_back( p_vec, (void*)0x2A ); + + CHECK( false == p_vec->own_contents ); + CHECK( 4 == p_vec->size ); + CHECK( 4 == p_vec->capacity ); + CHECK( (void*)0x2A == p_vec->p_buffer[3] ); + + vec_free( p_vec ); + } + + TEST(Verify_vec_push_back_should_push_a_new_element_to_the_end_of_empty_vector) + { + vec_t* p_vec = vec_new(false,0); + vec_push_back( p_vec, (void*)0x2A ); + + CHECK( false == p_vec->own_contents ); + CHECK( 1 == p_vec->size ); + CHECK( 1 == p_vec->capacity ); + CHECK( (void*)0x2A == p_vec->p_buffer[0] ); + + vec_free( p_vec ); + } + + //------------------------------------------------------------------------- + // Test vec_pop_back function + //------------------------------------------------------------------------- + TEST(Verify_vec_pop_back_returns_last_element) + { + void* data[4] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 }; + vec_t vector = { false, 4, 4, data }; + CHECK( (void*)0x4 == vec_pop_back( &vector ) ); + CHECK( 4 == vector.capacity ); + CHECK( 3 == vector.size ); + } + + TEST(Verify_vec_pop_back_does_nothing_if_no_elements) + { + vec_t vector = { false, 0, 0, NULL }; + CHECK( NULL == vec_pop_back( &vector ) ); + CHECK( 0 == vector.capacity ); + CHECK( 0 == vector.size ); + } + + //------------------------------------------------------------------------- + // Test vec_clear function + //------------------------------------------------------------------------- + TEST(Verify_vec_clear_clears_the_vector) + { + void* data[4] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 }; + vec_t vector = { false, 4, 4, data }; + vec_clear( &vector ); + CHECK(0 == vector.size); + } +} -- 2.52.0