summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKyle Gunger <kgunger12@gmail.com>2024-05-01 03:59:46 -0400
committerKyle Gunger <kgunger12@gmail.com>2024-05-01 03:59:46 -0400
commitaab7fe08faf2aec394174b2ee9782988bfc7fa30 (patch)
treeaa4e6cbe1fb53e908c4e9f135fb45d47107b4f1a
parentfeccf0adf3e6861b11a7768669a63c327f77ec10 (diff)
Finish vector code
-rw-r--r--include/osm/utils.h20
-rw-r--r--src/vector.c115
2 files changed, 127 insertions, 8 deletions
diff --git a/include/osm/utils.h b/include/osm/utils.h
index 5a53f41..441cce2 100644
--- a/include/osm/utils.h
+++ b/include/osm/utils.h
@@ -1,6 +1,8 @@
#ifndef OSM_UTILS_H
#define OSM_UTILS_H
+#include <stdbool.h>
+
// Vector utilities
/**
@@ -11,27 +13,30 @@ typedef struct {
void *data;
} Vector;
+/**
+ * Get an initialized vector struct
+ */
Vector vect_init(unsigned int elsz);
/**
* Add an element to an arbitrary index in the vector
*/
-void vect_add(Vector *vec, unsigned int index);
+bool vect_add(Vector *vec, unsigned int index, void *el);
/**
* Remove an element from an arbitrary index in the vector
*/
-void vect_remove(Vector *vec, unsigned int index);
+bool vect_remove(Vector *vec, unsigned int index);
/**
* Push an element to the end of the vector
*/
-void vect_push(Vector *vec, void *el);
+bool vect_push(Vector *vec, void *el);
/**
* Pop an element from the end of the vector
*/
-void vect_pop(Vector *vec);
+bool vect_pop(Vector *vec);
/**
* Get an element from the vector
@@ -41,7 +46,12 @@ void *vect_get(Vector *vec, unsigned int index);
/**
* Set an element inside the vector
*/
-void *vect_set(Vector *vec, unsigned int index, void *el);
+bool vect_set(Vector *vec, unsigned int index, void *el);
+
+/**
+ * Clear all data in a vector
+ */
+void vect_clear(Vector *vec);
/**
* Remove all associated data from the vector
diff --git a/src/vector.c b/src/vector.c
index 72b2a4f..33e3e85 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -55,7 +55,7 @@ void _vect_grow(Vector *vec)
*/
void _vect_shrink(Vector *vec)
{
- if (vec->size == 1)
+ if (vec->size / 2 < VECT_INIT_CAP)
{
return;
}
@@ -66,9 +66,13 @@ void _vect_shrink(Vector *vec)
/**
* Push a new element to the end of the vector
+ * Returns false if the vector was invalid
*/
-void vect_push(Vector *vec, void *el)
+bool vect_push(Vector *vec, void *el)
{
+ if (vec->elsz == 0 || vec->size == 0)
+ return false;
+
memcpy(vec->data + (vec->count * vec->elsz), el, vec->elsz);
vec->count++;
@@ -76,21 +80,124 @@ void vect_push(Vector *vec, void *el)
{
_vect_grow(vec);
}
+
+ return true;
}
/**
* Pop an element off of the end of the vector
+ * Returns true if an element was removed, false if there was no element to remove.
*/
-void vect_pop(Vector *vec)
+bool vect_pop(Vector *vec)
{
+ if (vec->count < 1)
+ return false;
+
vec->count--;
if (vec->count < vec->size / 3)
{
_vect_shrink(vec);
}
+
+ return true;
+}
+
+/**
+ * Get an element from the vector
+ * Returns NULL if the index is invalid
+ */
+void *vect_get(Vector *vec, unsigned int index)
+{
+ if (index >= vec->count)
+ return NULL;
+
+ return vec->data + (index * vec->elsz);
+}
+
+/**
+ * Set an element in the vector
+ * If the index is outside the vector, returns false.
+ */
+bool vect_set(Vector *vec, unsigned int index, void *el)
+{
+ if (index >= vec->count)
+ return false;
+
+ memcpy(vec->data + (index * vec->elsz), el, vec->elsz);
+ return true;
+}
+
+/**
+ * Remove an element from the given position in the vector
+ * Returns false if the index was invalid
+ * O(n)
+ */
+bool vect_remove(Vector *vec, unsigned int index)
+{
+ if (index >= vec->count)
+ return false;
+
+ if (index == vec->count - 1)
+ {
+ return vect_pop(vec);
+ }
+
+ char *curr = vec->data + (vec->elsz * index);
+ char *next = vec->data + (vec->elsz * (index + 1));
+
+ for(int i = 0; i < vec->elsz * (vec->count - (index + 1)); i++)
+ {
+ *(curr + i) = *(next + i);
+ }
+
+ return vect_pop(vec);
+}
+
+/**
+ * Add an element into the vector
+ * Returns false if the index is invalid
+ * O(n)
+ */
+bool vect_insert(Vector *vec, unsigned int index, void *el)
+{
+ if (index > vec->count)
+ return false;
+
+ if (index == vec->count)
+ return vect_push(vec, el);
+
+ char *curr = vec->data + (vec->elsz * index);
+ char *next = vec->data + (vec->elsz * (index + 1));
+
+ for (int i = vec->elsz * (vec->count - (index + 1)); i > 0; i--)
+ {
+ *(next + i - 1) = *(curr + i - 1);
+ }
+
+ vec->count++;
+
+ if (vec->size == vec->count)
+ {
+ _vect_grow(vec);
+ }
+
+ return true;
+}
+
+/**
+ * Clear all data from the vector
+ */
+void vect_clear(Vector *vec)
+{
+ int elsz = vec->elsz;
+ vect_end(vec);
+ *vec = vect_init(elsz);
}
+/**
+ * Free associated data of the vector
+ */
void vect_end(Vector *vec)
{
vec->size = 0;
@@ -99,3 +206,5 @@ void vect_end(Vector *vec)
free(vec->data);
vec->data = NULL;
}
+
+