From 0bf664527d003cb3670529f0609d51ce38bcf0ab Mon Sep 17 00:00:00 2001
From: David Lamparter <equinox@opensourcerouting.org>
Date: Sat, 20 Jul 2024 18:28:53 -0700
Subject: [PATCH] lib: allow static/pre-initialized vectors

Use alloced=0 to indicate that the array used in a vector is not in fact
dynamically allocated memory (yet).

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
---
 lib/vector.c | 35 +++++++++++++++++++++++++----------
 lib/vector.h | 21 +++++++++++++++++++--
 2 files changed, 44 insertions(+), 12 deletions(-)

diff --git a/lib/vector.c b/lib/vector.c
index 16b45254cb..0636154960 100644
--- a/lib/vector.c
+++ b/lib/vector.c
@@ -24,29 +24,44 @@ vector vector_init(unsigned int size)
 	v->alloced = size;
 	v->active = 0;
 	v->count = 0;
+	v->dynamic = true;
 	v->index = XCALLOC(MTYPE_VECTOR_INDEX, sizeof(void *) * size);
 	return v;
 }
 
 void vector_free(vector v)
 {
-	XFREE(MTYPE_VECTOR_INDEX, v->index);
-	XFREE(MTYPE_VECTOR, v);
+	if (v->alloced)
+		XFREE(MTYPE_VECTOR_INDEX, v->index);
+	if (v->dynamic)
+		XFREE(MTYPE_VECTOR, v);
 }
 
-/* Check assigned index, and if it runs short double index pointer */
+/* resize vector to a minimum of num
+ * may resize larger to avoid excessive realloc overhead
+ */
 void vector_ensure(vector v, unsigned int num)
 {
+	unsigned int newsz;
+
 	if (v->alloced > num)
 		return;
 
-	v->index = XREALLOC(MTYPE_VECTOR_INDEX, v->index,
-			    sizeof(void *) * (v->alloced * 2));
-	memset(&v->index[v->alloced], 0, sizeof(void *) * v->alloced);
-	v->alloced *= 2;
+	newsz = MAX(v->active * 2, num + 1);
+
+	if (!v->alloced && v->index) {
+		/* currently using global variable, not malloc'd memory */
+		void **orig_index = v->index;
 
-	if (v->alloced <= num)
-		vector_ensure(v, num);
+		v->index = XMALLOC(MTYPE_VECTOR_INDEX, sizeof(void *) * newsz);
+		memcpy(v->index, orig_index, v->active * sizeof(void *));
+		v->alloced = v->active;
+	} else
+		v->index = XREALLOC(MTYPE_VECTOR_INDEX, v->index,
+				    sizeof(void *) * newsz);
+
+	memset(&v->index[v->alloced], 0, sizeof(void *) * (newsz - v->alloced));
+	v->alloced = newsz;
 }
 
 /* This function only returns next empty slot index.  It dose not mean
@@ -124,7 +139,7 @@ void *vector_lookup_ensure(vector v, unsigned int i)
 /* Unset value at specified index slot. */
 void vector_unset(vector v, unsigned int i)
 {
-	if (i >= v->alloced)
+	if (i >= v->active)
 		return;
 
 	if (v->index[i])
diff --git a/lib/vector.h b/lib/vector.h
index 534def4f37..ae05d4d3e0 100644
--- a/lib/vector.h
+++ b/lib/vector.h
@@ -15,9 +15,26 @@ extern "C" {
 
 /* struct for vector */
 struct _vector {
-	unsigned int active;  /* number of active slots */
-	unsigned int alloced; /* number of allocated slot */
+	/* active: index of last non-NULL item (+1)
+	 * count:  number of non-NULL items (+1)
+	 *
+	 * the two will be different if a slot is set to NULL (without pulling
+	 * up later items in the array).  Whether this happens depends on
+	 * which vector functions are used.  If no empty slots are used, the
+	 * two fields will be identical.
+	 *
+	 * alloced: size of array pointed to by index.  If this is 0, index
+	 * points at a global variable rather than a malloc'd bit of memory.
+	 * The vector code will convert to malloc'd memory if necessary to
+	 * perform updates.
+	 */
+	unsigned int active;
+	unsigned int alloced;
 	unsigned int count;
+
+	/* whether struct _vector itself is dynamically allocated */
+	bool dynamic;
+
 	void **index;	 /* index to data */
 };
 typedef struct _vector *vector;
-- 
2.39.5