From 65ddeea23e1303d0b2d9656601b90df138d19e6c Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Wed, 1 Jul 2020 16:19:16 -0400 Subject: Add start to vector --- collections/vector/vector.c | 53 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100644 collections/vector/vector.c (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c new file mode 100644 index 0000000..2c75bc1 --- /dev/null +++ b/collections/vector/vector.c @@ -0,0 +1,53 @@ +#include "vector.h" + +#include +#include +#include + +#include + +#define START_SIZE 64; + +struct vector { + void **base; + int end, limit; +}; + +vec* vec_new() +{ + vec *root; + + root = malloc(sizeof(vec)); + assert(root); + + root->limit = START_SIZE; + root->base = malloc(root->limit * sizeof(void*)); + assert(root->base); + + return root; +} + +vec* vec_with_capacity(n) +int n; +{ + vec *root; + + root = malloc(sizeof(vec)); + assert(root); + + root->limit = n; + root->base = malloc(root->limit * sizeof(void*)); + assert(root->base); + + return root; +} + +int vec_size(root) +vec *root; +{ + if (!root) { + return -1; + } + return root->end; +} + -- cgit v1.1 From bc9e78bb7e3fd57a3683e6c8a848b5769d2b21f7 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Wed, 1 Jul 2020 16:43:07 -0400 Subject: Add resize function for vector --- collections/vector/vector.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 2c75bc1..c2668e4 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -51,3 +51,13 @@ vec *root; return root->end; } +void vec_resize(root) +vec *root; +{ + if (!root) + return; + + root->base = reallocarray(root->base, root->limit * 2, sizeof(void*)); + assert(root->base); +} + -- cgit v1.1 From 0d09851c392829a6cbbd047f9a374b5c66eb4c98 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Thu, 2 Jul 2020 17:32:56 -0400 Subject: Add push for vector --- collections/vector/vector.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index c2668e4..afe99de 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -61,3 +61,17 @@ vec *root; assert(root->base); } +void vec_push(root, item) +vec *root; +void *item; +{ + if (!root) { + return; + } + + if (root->end >= root->limit) { + vec_resize(root); + } + + root->base[root->end++] = item; +} -- cgit v1.1 From 264857903db99135c8c09d12b3e8af93ac1c7f88 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Thu, 2 Jul 2020 19:07:46 -0400 Subject: Add index functionality to vectors --- collections/vector/vector.c | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index afe99de..9d895d5 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -75,3 +75,14 @@ void *item; root->base[root->end++] = item; } + +void* vec_index(root, index) +vec *root; +int index; +{ + if (!root || index >= root->end || index < 0) { + return NULL; + } + + return root->base[index]; +} -- cgit v1.1 From 98454f841b5ac87d2253c2fae0aba2525853f907 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Thu, 2 Jul 2020 19:16:19 -0400 Subject: Add pop to vectors --- collections/vector/vector.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 9d895d5..936c0c8 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -86,3 +86,13 @@ int index; return root->base[index]; } + +void* vec_pop(root) +vec *root; +{ + if (!root || root->end == 0) { + return NULL; + } + + return root->base[--root->end]; +} -- cgit v1.1 From e4ea23a6c23acdec86e5b5fcd34c653118f6898e Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Thu, 2 Jul 2020 19:20:05 -0400 Subject: Adds free & clear functions to vectors --- collections/vector/vector.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 936c0c8..9544917 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -96,3 +96,25 @@ vec *root; return root->base[--root->end]; } + +void vec_free(root) +vec *root; +{ + free(root->base); + root->base = NULL; + + free(root); +} + +void vec_clear(root) +vec *root; +{ + int i; + + for (i = 0; i < root->end; i++) { + free(vec_index(root, i)); + } + + root->end = 0; +} + -- cgit v1.1 From 80d98a39a6bc4b71c74f240df617495e816b98b9 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Thu, 2 Jul 2020 20:21:28 -0400 Subject: Add printing functions for vectors --- collections/vector/vector.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 9544917..b3751dd 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -118,3 +118,29 @@ vec *root; root->end = 0; } +void vec_print(root, to_string) +vec *root; +char* to_string(void*); +{ + int i; + + printf("["); + for(i = 0; i < root->end; i++) { + printf("%s", to_string(vec_index(root, i))); + } + printf("\b]\n"); + +} + +void vec_debug_print(root) +vec *root; +{ + int i; + + fprintf(stderr, "VEC[base: %p, end: %p, limit:%p]:\n\t ", + root->base, root->end, root->limit); + for (i=0; i < root->end; i++){ + fprintf(stderr, "[%p]", vec_index(root,i)); + } + fprintf(stderr, "\n"); +} -- cgit v1.1 From 8d5b381b540fe1d780311e4f4059dce014a6cb91 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 00:13:04 -0400 Subject: Add copy function for vector --- collections/vector/vector.c | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index b3751dd..8aaffb6 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -144,3 +144,23 @@ vec *root; } fprintf(stderr, "\n"); } + +vec* vec_cp(root) +vec *root; +{ + vec *copy; + + if (!root) + return NULL; + + copy = vec_with_capacity(root->limit); + + copy->base = memcpy(copy->base, root->base, + vec_size(root) * sizeof(void*)); + assert(copy->base); + + copy->end = root->end; + copy->limit = root->limit; + + return copy; +} -- cgit v1.1 From aeee67bdda0e0f8834cbd3f65da99e3c79f69f65 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 00:28:23 -0400 Subject: Fix organize function order in vector docs and src Functions now ordered roughly to what they do/deal with. --- collections/vector/vector.c | 117 ++++++++++++++++++++++---------------------- 1 file changed, 58 insertions(+), 59 deletions(-) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 8aaffb6..23e5c47 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -1,11 +1,10 @@ #include "vector.h" +#include #include #include #include -#include - #define START_SIZE 64; struct vector { @@ -13,6 +12,19 @@ struct vector { int end, limit; }; +void vec_debug_print(root) +vec *root; +{ + int i; + + fprintf(stderr, "VEC[base: %p, end: %p, limit:%p]:\n\t ", + root->base, root->end, root->limit); + for (i=0; i < root->end; i++){ + fprintf(stderr, "[%p]", vec_index(root,i)); + } + fprintf(stderr, "\n"); +} + vec* vec_new() { vec *root; @@ -61,6 +73,40 @@ vec *root; assert(root->base); } +vec* vec_cp(root) +vec *root; +{ + vec *copy; + + if (!root) + return NULL; + + copy = vec_with_capacity(root->limit); + + copy->base = memcpy(copy->base, root->base, + vec_size(root) * sizeof(void*)); + assert(copy->base); + + copy->end = root->end; + copy->limit = root->limit; + + return copy; +} + +void vec_print(root, to_string) +vec *root; +char* to_string(void*); +{ + int i; + + printf("["); + for(i = 0; i < root->end; i++) { + printf("%s", to_string(vec_index(root, i))); + } + printf("\b]\n"); + +} + void vec_push(root, item) vec *root; void *item; @@ -76,17 +122,6 @@ void *item; root->base[root->end++] = item; } -void* vec_index(root, index) -vec *root; -int index; -{ - if (!root || index >= root->end || index < 0) { - return NULL; - } - - return root->base[index]; -} - void* vec_pop(root) vec *root; { @@ -97,13 +132,15 @@ vec *root; return root->base[--root->end]; } -void vec_free(root) +void* vec_index(root, index) vec *root; +int index; { - free(root->base); - root->base = NULL; + if (!root || index >= root->end || index < 0) { + return NULL; + } - free(root); + return root->base[index]; } void vec_clear(root) @@ -118,49 +155,11 @@ vec *root; root->end = 0; } -void vec_print(root, to_string) -vec *root; -char* to_string(void*); -{ - int i; - - printf("["); - for(i = 0; i < root->end; i++) { - printf("%s", to_string(vec_index(root, i))); - } - printf("\b]\n"); - -} - -void vec_debug_print(root) -vec *root; -{ - int i; - - fprintf(stderr, "VEC[base: %p, end: %p, limit:%p]:\n\t ", - root->base, root->end, root->limit); - for (i=0; i < root->end; i++){ - fprintf(stderr, "[%p]", vec_index(root,i)); - } - fprintf(stderr, "\n"); -} - -vec* vec_cp(root) +void vec_free(root) vec *root; { - vec *copy; - - if (!root) - return NULL; - - copy = vec_with_capacity(root->limit); - - copy->base = memcpy(copy->base, root->base, - vec_size(root) * sizeof(void*)); - assert(copy->base); - - copy->end = root->end; - copy->limit = root->limit; + free(root->base); + root->base = NULL; - return copy; + free(root); } -- cgit v1.1 From 4832ab4b43a2e9fb72b1814b32421de1dba1edcb Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 00:40:50 -0400 Subject: Add function to get capacity of a vector --- collections/vector/vector.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 23e5c47..b8f83de 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -63,6 +63,16 @@ vec *root; return root->end; } +int vec_capacity(root) +vec *root; +{ + if (!root) { + return -1; + } + + return root->limit; +} + void vec_resize(root) vec *root; { -- cgit v1.1 From f900066b813fac2f34798c39f16dacda9a878610 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 00:52:26 -0400 Subject: Add back function to vectors back() returns the element in the last position without removing it. --- collections/vector/vector.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index b8f83de..0b816b7 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -142,6 +142,16 @@ vec *root; return root->base[--root->end]; } +void* vec_back(root) +vec *root; +{ + if (!root || root->end == 0) { + return NULL; + } + + return root->base[root->end - 1]; +} + void* vec_index(root, index) vec *root; int index; -- cgit v1.1 From b253b373ea74539a0f29a88ac2be728aa8158d2a Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 00:57:58 -0400 Subject: Add set index function for vectors --- collections/vector/vector.c | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 0b816b7..5cb56ef 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -152,6 +152,17 @@ vec *root; return root->base[root->end - 1]; } +void vec_set(root, index, item) +vec *root; +int index; +void *item; +{ + if (!root || index >= root->end || index < 0) + return; + + root->base[index] = item; +} + void* vec_index(root, index) vec *root; int index; -- cgit v1.1 From 72cb2e77024970509ff403670f9e4245bcefebd6 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 01:05:09 -0400 Subject: Add swap function to vectors --- collections/vector/vector.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 5cb56ef..a7e0845 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -174,6 +174,22 @@ int index; return root->base[index]; } +void vec_swap(root, i, j) +vec *root; +int i,j; +{ + void *tmp; + + if (!root || i >= root->end || i < 0 || j >= root->end || j < 0) + return; + + tmp = root->base[i]; + root->base[i] = root->base[j]; + root->base[j] = tmp; + + return; +} + void vec_clear(root) vec *root; { -- cgit v1.1 From 1a41fe605ab6bde15f622e72abb7aee846531fcf Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 01:18:17 -0400 Subject: Add swap_pop function for vectors --- collections/vector/vector.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index a7e0845..9ae30c7 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -190,6 +190,20 @@ int i,j; return; } +void* vec_swap_pop(root, i) +vec *root; +int i; +{ + void *tmp; + int j; + + if (!root || i >= root->end || i < 0 || root->end <= 0) + return NULL; + + vec_swap(root, i, root->end - 1); + return vec_pop(root); +} + void vec_clear(root) vec *root; { -- cgit v1.1 From a691f4d4b0a57d62eb792e6ede0c0fa5334e3e61 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 01:18:39 -0400 Subject: Fix bounds checking for vector pop Would have failed given a negative index. --- collections/vector/vector.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 9ae30c7..79e31a4 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -135,7 +135,7 @@ void *item; void* vec_pop(root) vec *root; { - if (!root || root->end == 0) { + if (!root || root->end <= 0) { return NULL; } -- cgit v1.1 From e6af2f70ec910ee8cb3813fa1e5b1c7d6e3ead60 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 23:49:15 -0400 Subject: Add insert function for vectors --- collections/vector/vector.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 79e31a4..2ae748f 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -174,6 +174,23 @@ int index; return root->base[index]; } +void vec_insert(root, index, item) +vec *root; +int index; +void *item; +{ + if (!root || index > root->end || index < 0) + return; + + if (root->end >= root->limit) + vec_resize(root); + + memmove(root->base + index + 1, root->base + index, + (root->end++ - index) * sizeof(void*)); + + root->base[index] = item; +} + void vec_swap(root, i, j) vec *root; int i,j; -- cgit v1.1 From a1d4279c40612e6f98564db43192929b41c59d40 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Fri, 3 Jul 2020 23:57:45 -0400 Subject: Add remove function for vectors Removes element at an index. --- collections/vector/vector.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 2ae748f..5c473a4 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -191,6 +191,22 @@ void *item; root->base[index] = item; } +void* vec_remove(root, index) +vec *root; +int index; +{ + void *tmp; + + if (!root || index > root->end || index < 0) + return NULL; + + tmp = vec_index(root, index); + memmove(root->base + index, root->base + index + 1, + (--root->end - index) * sizeof(void*)); + + return tmp; +} + void vec_swap(root, i, j) vec *root; int i,j; -- cgit v1.1 From 8874cf97227139ed10e75fe13108988b45492172 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Sat, 4 Jul 2020 22:06:49 -0400 Subject: Add truncate to vectors --- collections/vector/vector.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 5c473a4..c456d8a 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -237,6 +237,16 @@ int i; return vec_pop(root); } +void vec_truncate(root, size) +vec *root; +int size; +{ + if (!root || size < 0 || size >= root->end) + return; + + root->end = size; +} + void vec_clear(root) vec *root; { -- cgit v1.1 From 8aa9f42d914a453a0570752ee292b9a9cfcae9d6 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Sat, 4 Jul 2020 22:07:23 -0400 Subject: Fix vector print function now frees string representations --- collections/vector/vector.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index c456d8a..391b5a6 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -108,10 +108,13 @@ vec *root; char* to_string(void*); { int i; + char *tmp; printf("["); for(i = 0; i < root->end; i++) { - printf("%s", to_string(vec_index(root, i))); + printf("%s", tmp = to_string(vec_index(root, i))); + free(tmp); + tmp = NULL; } printf("\b]\n"); -- cgit v1.1 From 5fa1551b4a0acc28d5c656479806511ab0c81a18 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Sat, 4 Jul 2020 22:17:27 -0400 Subject: Add reserve function to vectors --- collections/vector/vector.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'collections/vector/vector.c') diff --git a/collections/vector/vector.c b/collections/vector/vector.c index 391b5a6..f14c302 100644 --- a/collections/vector/vector.c +++ b/collections/vector/vector.c @@ -250,6 +250,20 @@ int size; root->end = size; } +void vec_reserve(root, n) +vec *root; +int n; +{ + int i; + + if (!root || n + root->end <= root->limit) + return; + + for (i = root->limit; i < root->end + n; i*=2); + + root->base = reallocarray(root->base, i, sizeof(void*)); +} + void vec_clear(root) vec *root; { -- cgit v1.1