diff options
| -rw-r--r-- | include/osm/utils.h | 20 | ||||
| -rw-r--r-- | src/vector.c | 115 |
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; } + + |