summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--deps.mk6
-rw-r--r--src/vector.c130
-rw-r--r--src/vector.h15
-rw-r--r--tests/vector.c140
4 files changed, 109 insertions, 182 deletions
diff --git a/deps.mk b/deps.mk
index 0b113b5..5fb0961 100644
--- a/deps.mk
+++ b/deps.mk
@@ -80,7 +80,7 @@ src/random.o: src/logerr.h
src/string.o:
src/testing.o:
src/util.o: src/logerr.h
-src/vector.o: src/logerr.h src/catalog.h src/i18n.h
+src/vector.o: src/logerr.h src/catalog.h src/i18n.h src/math.h
tests/catalog.o: src/logerr.h src/testing.h tests/slurp.h
tests/i18n.o: src/catalog.h src/logerr.h
@@ -91,7 +91,7 @@ tests/random.o: src/logerr.h src/testing.h
tests/string.o:
tests/testing.o:
tests/util.o: src/logerr.h src/testing.h tests/slurp.h
-tests/vector.o: src/logerr.h src/catalog.h src/i18n.h src/testing.h
+tests/vector.o: src/logerr.h src/catalog.h src/i18n.h src/math.h src/testing.h
tests/catalog.a: src/logerr.o src/testing.o tests/slurp.o
tests/i18n.a: src/catalog.o src/logerr.o
@@ -102,4 +102,4 @@ tests/random.a: src/logerr.o src/testing.o
tests/string.a:
tests/testing.a:
tests/util.a: src/logerr.o src/testing.o tests/slurp.o
-tests/vector.a: src/logerr.o src/catalog.o src/i18n.o src/testing.o
+tests/vector.a: src/logerr.o src/catalog.o src/i18n.o src/math.o src/testing.o
diff --git a/src/vector.c b/src/vector.c
index 65f004f..77a6a8a 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -11,6 +11,7 @@
#include "logerr.h"
#include "catalog.h"
#include "i18n.h"
+#include "math.h"
#include "vector.h"
@@ -18,8 +19,7 @@
struct Vector {
void **values;
size_t capacity;
- size_t back_count;
- size_t front_count;
+ size_t count;
const size_t max_capacity;
const size_t multiplier;
const size_t value_size;
@@ -41,20 +41,19 @@ vector_new_with(
const size_t max_capacity,
const size_t multiplier,
const size_t value_size,
- struct Vector **const out
+ const struct Vector **const out
) {
int rc = -1;
struct Vector v = {
.values = NULL,
.capacity = capacity,
- .back_count = 0U,
- .front_count = 0U,
+ .count = 0U,
.max_capacity = max_capacity,
.multiplier = multiplier,
.value_size = value_size,
};
- struct Vector *restrict vref = NULL;
+ struct Vector *restrict ret = NULL;
assert(capacity > 0);
if (capacity > max_capacity) {
@@ -74,19 +73,19 @@ vector_new_with(
goto out;
}
- vref = malloc(sizeof(*vref));
- if (vref == NULL) {
- logerr("malloc(%ld): %s\n", sizeof(vref), strerror(errno));
+ ret = malloc(sizeof(*ret));
+ if (ret == NULL) {
+ logerr("malloc(%ld): %s\n", sizeof(ret), strerror(errno));
goto out;
}
- memcpy(vref, &v, sizeof(v));
+ memcpy(ret, &v, sizeof(v));
- *out = vref;
+ *out = ret;
rc = 0;
out:
if (rc) {
- if (vref != NULL) {
- free(vref);
+ if (ret != NULL) {
+ free(ret);
}
if (v.values != NULL) {
free(v.values);
@@ -96,7 +95,7 @@ out:
}
int
-vector_new(const size_t value_size, struct Vector **const out) {
+vector_new(const size_t value_size, const struct Vector **const out) {
return vector_new_with(
VECTOR_DEFAULT_CAPACITY,
VECTOR_MAX_CAPACITY,
@@ -115,9 +114,22 @@ vector_free(const struct Vector *const v) {
size_t
vector_count(const struct Vector *const v) {
- const size_t count = v->back_count + v->front_count;
- assert(count <= v->capacity);
- return count;
+ return v->count;
+}
+
+static size_t
+next_capacity(const struct Vector *const v) {
+ size_t ret;
+ if (mul_size(v->capacity, v->multiplier, &ret)) {
+ return v->max_capacity;
+ }
+
+ return ret;
+}
+
+static int
+next_size(const struct Vector *const v, const size_t capacity, size_t *const out) {
+ return mul_size(v->value_size, capacity, out);
}
int
@@ -136,20 +148,12 @@ out:
return rc;
}
-static size_t
-next_capacity(const struct Vector *const v) {
- if (v->capacity > v->max_capacity / v->multiplier) {
- return v->max_capacity;
- } else {
- return v->capacity * v->multiplier;
- }
-}
-
int
-vector_push_back(struct Vector *const v, void *const value) {
+vector_push_back(const struct Vector *const v, const void *const value) {
int rc = -1;
void *new_values = NULL;
+ struct Vector *const v_mut = (struct Vector *const)v;
const size_t count = vector_count(v);
if (count == v->capacity) {
@@ -164,50 +168,17 @@ vector_push_back(struct Vector *const v, void *const value) {
}
const size_t new_capacity = next_capacity(v);
- const size_t new_size = new_capacity * v->value_size;
- new_values = realloc(v->values, new_size);
- if (new_values == NULL) {
- logerr(
- "realloc(v->values, %ld): %s\n",
- new_size,
- strerror(errno)
- );
- goto out;
- }
- v->capacity = new_capacity;
- v->values = new_values;
- }
-
- v->values[v->back_count] = value;
- v->back_count++;
- rc = 0;
-out:
- if (rc) {
- if (new_values != NULL) {
- free(new_values);
- }
- }
- return rc;
-}
-
-int
-vector_push_front(struct Vector *const v, void *const value) {
- int rc = -1;
-
- void *new_values = NULL;
-
- const size_t count = vector_count(v);
- if (count == v->capacity) {
- if (count == v->max_capacity) {
+ size_t new_size;
+ if (next_size(v, new_capacity, &new_size)) {
logerr(
_(MSG_ERR_VECTOR_MAX_CAPACITY),
v->max_capacity,
strerror(EOVERFLOW)
);
+ rc = EOVERFLOW;
+ goto out;
}
- const size_t new_capacity = next_capacity(v);
- const size_t new_size = new_capacity * v->value_size;
new_values = realloc(v->values, new_size);
if (new_values == NULL) {
logerr(
@@ -217,12 +188,12 @@ vector_push_front(struct Vector *const v, void *const value) {
);
goto out;
}
- v->capacity = new_capacity;
- // FIXME: copy, but leaving things at the beginning
+ v_mut->capacity = new_capacity;
+ v_mut->values = new_values;
}
- v->values[v->front_count] = value;
- v->front_count++;
+ memcpy(&v->values[v->count], value, v->value_size);
+ v_mut->count++;
rc = 0;
out:
if (rc) {
@@ -234,25 +205,10 @@ out:
}
int
-vector_pop_back(struct Vector *const v, const void **const out) {
+vector_pop_back(const struct Vector *const v, const void **const out) {
int rc = -1;
- const size_t count = vector_count(v);
- if (count == 0) {
- logerr(_(MSG_ERR_VECTOR_UNDERFLOW));
- goto out;
- }
-
- *out = v->values[v->back_count - 1]; // FIXME: can become negative!
- v->back_count--;
- rc = 0;
-out:
- return rc;
-}
-
-int
-vector_pop_front(struct Vector *const v, const void **const out) {
- int rc = -1;
+ struct Vector *const v_mut = (struct Vector *const)v;
const size_t count = vector_count(v);
if (count == 0) {
@@ -260,8 +216,8 @@ vector_pop_front(struct Vector *const v, const void **const out) {
goto out;
}
- *out = v->values[v->front_count - 1]; // FIXME: can become negative!
- v->front_count--;
+ v_mut->count--;
+ *out = v->values[v->count];
rc = 0;
out:
return rc;
diff --git a/src/vector.h b/src/vector.h
index cc3c96a..7d83594 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -1,29 +1,28 @@
struct Vector;
-
-int
-vector_new(const size_t value_size, struct Vector **out);
-
int
vector_new_with(
const size_t capacity,
const size_t max_capacity,
const size_t multiplier,
const size_t value_size,
- struct Vector **out
+ const struct Vector **const out
);
+int
+vector_new(const size_t value_size, const struct Vector **const out);
+
void
vector_free(const struct Vector *const v);
size_t
-vector_count(const struct Vector *v);
+vector_count(const struct Vector *const v);
int
vector_nth(const struct Vector *const v, const size_t idx, const void **const out);
int
-vector_push_back(struct Vector *const v, void *const value);
+vector_push_back(const struct Vector *const v, const void *const value);
int
-vector_pop_back(struct Vector *const v, const void **const out);
+vector_pop_back(const struct Vector *const v, const void **const out);
diff --git a/tests/vector.c b/tests/vector.c
index 74bffc7..8f4a20c 100644
--- a/tests/vector.c
+++ b/tests/vector.c
@@ -15,7 +15,7 @@ static int
test_vector_new_with(void) {
int rc = -1;
- struct Vector *v = NULL;
+ const struct Vector *v = NULL;
test_start("vector_new_with()");
{
@@ -38,8 +38,7 @@ test_vector_new_with(void) {
}
assert(v->capacity == capacity);
- assert(v->back_count == 0U);
- assert(v->front_count == 0U);
+ assert(v->count == 0U);
assert(v->max_capacity == max_capacity);
assert(v->multiplier == multiplier);
assert(v->value_size == size);
@@ -81,7 +80,7 @@ static int
test_vector_new(void) {
int rc = -1;
- struct Vector *v = NULL;
+ const struct Vector *v = NULL;
test_start("vector_new()");
{
@@ -94,8 +93,7 @@ test_vector_new(void) {
}
assert(v->capacity == VECTOR_DEFAULT_CAPACITY);
- assert(v->back_count == 0);
- assert(v->front_count == 0);
+ assert(v->count == 0);
assert(v->max_capacity == VECTOR_MAX_CAPACITY);
assert(v->multiplier == GROWTH_MULTIPLIER);
assert(v->value_size == size);
@@ -121,8 +119,7 @@ test_vector_new(void) {
}
assert(v->capacity == VECTOR_DEFAULT_CAPACITY);
- assert(v->back_count == 0);
- assert(v->front_count == 0);
+ assert(v->count == 0);
assert(v->max_capacity == VECTOR_MAX_CAPACITY);
assert(v->multiplier == GROWTH_MULTIPLIER);
assert(v->value_size == size);
@@ -146,7 +143,7 @@ static int
test_vector_free(void) {
int rc = -1;
- struct Vector *v = NULL;
+ const struct Vector *v = NULL;
test_start("vector_free()");
{
@@ -173,7 +170,7 @@ static int
test_vector_count(void) {
int rc = -1;
- struct Vector *v = NULL;
+ const struct Vector *v = NULL;
test_start("vector_count()");
{
@@ -185,17 +182,16 @@ test_vector_count(void) {
}
assert(vector_count(v) == 0);
- assert(v->back_count == 0);
- assert(v->front_count == 0);
+ assert(v->count == 0);
- if (vector_push_back(v, (void *)123)) {
+ const unsigned long value = 123;
+ if (vector_push_back(v, &value)) {
logerr("vector_push_back()");
goto out;
}
assert(vector_count(v) == 1);
- assert(v->back_count == 1);
- assert(v->front_count == 0);
+ assert(v->count == 1);
vector_free(v);
v = NULL;
@@ -212,19 +208,29 @@ out:
return rc;
}
+static void
+test_next_capacity(void) {
+ test_start("next_capacity()");
+ // FIXME: write tests
+}
+
+static void
+test_next_size(void) {
+ test_start("next_size()");
+ // FIXME: write tests
+}
+
static int
test_vector_nth(void) {
int rc = -1;
- struct Vector *v = NULL;
- int first = 123;
- int second = 321;
- int third = 555;
- // const int values[] = { first, second, third };
- int values[] = { first, second, third };
+ const struct Vector *v = NULL;
+ const int first = 123;
+ const int second = 321;
+ const int third = 555;
+ const int values[] = { first, second, third };
const size_t values_len = sizeof(values) / sizeof(values[0]);
- return 0;
test_start("vector_nth()");
{
testing("nth with growth");
@@ -241,14 +247,14 @@ test_vector_nth(void) {
}
}
- int ret;
+ int nth;
- assert(vector_nth(v, 0U, (void *)&ret) == 0);
- assert(ret == 123);
- assert(vector_nth(v, 1U, (void *)&ret) == 0);
- assert(ret == 321);
- assert(vector_nth(v, 2U, (void *)&ret) == 0);
- assert(ret == 555);
+ assert(vector_nth(v, 0U, (void *)&nth) == 0);
+ assert(nth == 123);
+ assert(vector_nth(v, 1U, (void *)&nth) == 0);
+ assert(nth == 321);
+ assert(vector_nth(v, 2U, (void *)&nth) == 0);
+ assert(nth == 555);
vector_free(v);
v = NULL;
@@ -270,9 +276,9 @@ test_vector_nth(void) {
}
}
- int ret = 222;
- assert(vector_nth(v, 4U, (void *)&ret) == -1);
- assert(ret == 222);
+ int nth = 222;
+ assert(vector_nth(v, 4U, (void *)&nth) != 0);
+ assert(nth == 222);
vector_free(v);
v = NULL;
@@ -289,16 +295,11 @@ out:
return rc;
}
-static void
-test_next_capacity(void) {
- test_start("next_capacity()");
-}
-
static int
test_vector_push_back(void) {
int rc = -1;
- struct Vector *v = NULL;
+ const struct Vector *v = NULL;
test_start("vector_push_back()");
{
@@ -309,14 +310,14 @@ test_vector_push_back(void) {
goto out;
}
- long long before = 123;
- long long after = 321;
- v->values[0] = &before;
+ const long long before = 123;
+ const long long after = 321;
+ v->values[0] = (void *)before;
if (vector_push_back(v, &after)) {
logerr("vector_push_back()");
goto out;
}
- assert(v->values[0] == &after);
+ assert(v->values[0] == (void *)after);
vector_free(v);
v = NULL;
@@ -326,7 +327,7 @@ test_vector_push_back(void) {
{
testing("push back beyond capacity causes reallocation");
- unsigned long data = 2222U;
+ const unsigned long data = 2222U;
if (vector_new(sizeof(unsigned long), &v)) {
logerr("vector_new()");
@@ -341,30 +342,23 @@ test_vector_push_back(void) {
goto out;
}
}
-
- assert(v->capacity == vector_count(v));
assert(v->values[0] == (void *)data);
- if (vector_push_back(v, &data)) {
- logerr("vector_push_vack()");
- goto out;
- }
- assert(v->capacity == (v->capacity * v->multiplier));
- assert(vector_count(v) == v->capacity);
- assert(v->values[1] == &data);
+ const size_t capacity = v->capacity;
+ assert(capacity == vector_count(v));
+ // we grow the vector here
if (vector_push_back(v, &data)) {
- logerr("vector_push_back()");
+ logerr("vector_push_vack()");
goto out;
}
- assert(v->capacity == 4);
- // assert(v->count == 3);
- assert(v->values[2] == &data);
+ const size_t new_capacity = capacity * v->multiplier;
+ assert(v->capacity == new_capacity);
+ assert(vector_count(v) == capacity + 1U);
assert(vector_push_back(v, &data) == 0);
- assert(v->capacity == 4);
- // assert(v->count == 4);
- assert(v->values[3] == &data);
+ assert(v->capacity == new_capacity);
+ assert(v->count == capacity + 2U);
vector_free(v);
v = NULL;
@@ -382,23 +376,11 @@ out:
}
static int
-test_vector_push_front(void) {
- test_start("vector_push_front()");
- return 0;
-}
-
-static int
test_vector_pop_back(void) {
test_start("vector_pop_back()");
return 0;
}
-static int
-test_vector_pop_front(void) {
- test_start("vector_pop_front()");
- return 0;
-}
-
int
main(void) {
@@ -424,34 +406,24 @@ main(void) {
goto out;
}
+ test_next_capacity();
+ test_next_size();
+
if (test_vector_nth()) {
logerr("test_vector_nth()");
goto out;
}
- return 0;
- test_next_capacity();
-
if (test_vector_push_back()) {
logerr("test_vector_push_back()");
goto out;
}
- if (test_vector_push_front()) {
- logerr("test_vector_push_front()");
- goto out;
- }
-
if (test_vector_pop_back()) {
logerr("test_vector_pop_back()");
goto out;
}
- if (test_vector_pop_front()) {
- logerr("test_vector_pop_front()");
- goto out;
- }
-
rc = 0;
out:
return !!rc;
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 12:46:03 +0000