changeset 99:7b041326c9f7

base/vec: Implement push_front* and reverse functions
author Lewin Bormann <lbo@spheniscida.de>
date Wed, 28 Aug 2019 09:41:02 +0200
parents 8498c1faba07
children 58553c702903
files src/base/vec.c src/base/vec.h src/base/vec_test.c
diffstat 3 files changed, 101 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/src/base/vec.c	Mon Aug 26 17:01:40 2019 +0200
+++ b/src/base/vec.c	Wed Aug 28 09:41:02 2019 +0200
@@ -79,6 +79,15 @@
     assert(vec->len <= vec->cap);
 }
 
+bool yvec_pop(yvec_t* vec, void* dst) {
+    if (vec->len == 0) {
+        return false;
+    }
+    memcpy(dst, yvec_at(vec, vec->len-1), vec->size);
+    vec->len--;
+    return true;
+}
+
 size_t yvec_push(yvec_t *vec, const void *element) {
     if (vec->len >= vec->cap) {
         yvec_grow(vec);
@@ -89,15 +98,6 @@
     return vec->len - 1;
 }
 
-bool yvec_pop(yvec_t* vec, void* dst) {
-    if (vec->len == 0) {
-        return false;
-    }
-    memcpy(dst, yvec_at(vec, vec->len-1), vec->size);
-    vec->len--;
-    return true;
-}
-
 void yvec_push_multi(yvec_t *vec, const void *elements, size_t n) {
     yvec_growcap(vec, vec->len + n);  // Grow capacity to at least len+n.
     memcpy(yvec_at_nocheck(vec, vec->len), elements, n * vec->size);
@@ -105,6 +105,34 @@
     assert(vec->len <= vec->cap);
 }
 
+void yvec_push_front(yvec_t* vec, const void *element) {
+    yvec_push_front_multi(vec, element, 1);
+}
+
+void yvec_push_front_multi(yvec_t* vec, const void *elements, size_t n) {
+    if (vec->cap < vec->len + n) {
+        yvec_growcap(vec, vec->len+n);
+    }
+    yvec_resize(vec, vec->len+n);
+    memmove(yvec_at_nocheck(vec, n), vec->base, n*vec->size);
+    memcpy(vec->base, elements, n*vec->size);
+}
+
+void yvec_reverse(yvec_t* vec) {
+    char tmp[128];
+    assert(vec->size < 128);
+    for (size_t i = 0; i < vec->len/2; i++) {
+        void* front = yvec_at(vec, i);
+        void* back = yvec_at(vec, vec->len - 1 - i);
+        // front -> tmp
+        memcpy(tmp, front, vec->size);
+        // back -> front
+        memcpy(front, back, vec->size);
+        // tmp -> back
+        memcpy(back, tmp, vec->size);
+    }
+}
+
 void yvec_append(yvec_t *v1, yvec_t *v2) {
     assert(v1->size == v2->size);
     yvec_growcap(v1, v1->len + v2->len);
--- a/src/base/vec.h	Mon Aug 26 17:01:40 2019 +0200
+++ b/src/base/vec.h	Wed Aug 28 09:41:02 2019 +0200
@@ -65,6 +65,13 @@
 void yvec_init(yvec_t *vec, size_t size, size_t len);
 
 /**
+ * @brief Remove an element and returns true if the vector had at least one
+ * element. The element is stored into `dst`, which must point to a memory area
+ * of at least `vec->size` bytes.
+ */
+bool yvec_pop(yvec_t *vec, void *dst);
+
+/**
  * @brief Append an element. See also `yvec_push()`, which asserts that the
  * element size matches the size expected by the vector. Returns the index of
  * the pushed element.
@@ -75,19 +82,27 @@
 size_t yvec_push(yvec_t *vec, const void *element);
 
 /**
- * @brief Remove an element and returns true if the vector had at least one
- * element. The element is stored into `dst`, which must point to a memory area
- * of at least `vec->size` bytes.
- */
-bool yvec_pop(yvec_t *vec, void *dst);
-
-/**
  * @brief Append several elements from a raw array. The size of elements must
  * be equal to `vec->size`.
  */
 void yvec_push_multi(yvec_t *vec, const void *elements, size_t n);
 
 /**
+ * @brief Prepend an element to the vector.
+ */
+void yvec_push_front(yvec_t* vec, const void *element);
+
+/**
+ * @brief Prepend multiple elements to the vector.
+ */
+void yvec_push_front_multi(yvec_t* vec, const void *element, size_t n);
+
+/**
+ * @brief Reverse a vec in-place.
+ */
+void yvec_reverse(yvec_t* vec);
+
+/**
  * @brief Append `v2` to `v1`, leaving `v2` untouched.
  */
 void yvec_append(yvec_t *v1, yvec_t *v2);
--- a/src/base/vec_test.c	Mon Aug 26 17:01:40 2019 +0200
+++ b/src/base/vec_test.c	Wed Aug 28 09:41:02 2019 +0200
@@ -80,9 +80,51 @@
     yvec_destroy(&v3);
 }
 
+void test_vec_push_front(void) {
+    int a[] = {4, 5, 6};
+    int b = 9, c = 10;
+    yvec_t vec = YVEC_NEW(a, 3, int);
+    yvec_push_front(&vec, &b);
+    yvec_push_front(&vec, &c);
+    assert(10 == *YVEC_AT(&vec, 0, int));
+    assert(9 == *YVEC_AT(&vec, 1, int));
+    yvec_push_front_multi(&vec, a, 3);
+    assert(4 == *YVEC_AT(&vec, 0, int));
+    assert(10 == *YVEC_AT(&vec, 3, int));
+    assert(9 == *YVEC_AT(&vec, 4, int));
+    yvec_destroy(&vec);
+}
+
+void test_vec_reverse(void) {
+    int a[] = {7, 8, 9};
+    int b[] = {10, 11, 12, 13};
+
+    yvec_t vec = YVEC_NEW(a, 3, int);
+    assert(7 == *YVEC_AT(&vec, 0, int));
+    yvec_reverse(&vec);
+    assert(9 == *YVEC_AT(&vec, 0, int));
+    assert(8 == *YVEC_AT(&vec, 1, int));
+    assert(7 == *YVEC_AT(&vec, 2, int));
+    yvec_destroy(&vec);
+
+    vec = YVEC_NEW(b, 4, int);
+    assert(10 == *YVEC_AT(&vec, 0, int));
+    assert(11 == *YVEC_AT(&vec, 1, int));
+    assert(12 == *YVEC_AT(&vec, 2, int));
+    assert(13 == *YVEC_AT(&vec, 3, int));
+    yvec_reverse(&vec);
+    assert(10 == *YVEC_AT(&vec, 3, int));
+    assert(11 == *YVEC_AT(&vec, 2, int));
+    assert(12 == *YVEC_AT(&vec, 1, int));
+    assert(13 == *YVEC_AT(&vec, 0, int));
+    yvec_destroy(&vec);
+}
+
 int main(void) {
     test_vec_new();
     test_vec_init_use();
     test_vec_append();
+    test_vec_push_front();
+    test_vec_reverse();
     return 0;
 }