Adding upstream version 9.1.upstream/9.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 212 insertions, 0 deletions

diff --git a/lib/vector.c b/lib/vector.c
new file mode 100644
index 0000000..bbea67c
--- /dev/null
+++ b/lib/vector.c
@@ -0,0 +1,212 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/* Generic vector interface routine
+ * Copyright (C) 1997 Kunihiro Ishiguro
+ */
+
+#include <zebra.h>
+
+#include "vector.h"
+#include "memory.h"
+
+DEFINE_MTYPE_STATIC(LIB, VECTOR, "Vector");
+DEFINE_MTYPE_STATIC(LIB, VECTOR_INDEX, "Vector index");
+
+/* Initialize vector : allocate memory and return vector. */
+vector vector_init(unsigned int size)
+{
+	vector v = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector));
+
+	/* allocate at least one slot */
+	if (size == 0)
+		size = 1;
+
+	v->alloced = size;
+	v->active = 0;
+	v->count = 0;
+	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);
+}
+
+vector vector_copy(vector v)
+{
+	unsigned int size;
+	vector new = XCALLOC(MTYPE_VECTOR, sizeof(struct _vector));
+
+	new->active = v->active;
+	new->alloced = v->alloced;
+	new->count = v->count;
+
+	size = sizeof(void *) * (v->alloced);
+	new->index = XCALLOC(MTYPE_VECTOR_INDEX, size);
+	memcpy(new->index, v->index, size);
+
+	return new;
+}
+
+/* Check assigned index, and if it runs short double index pointer */
+void vector_ensure(vector v, unsigned int num)
+{
+	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;
+
+	if (v->alloced <= num)
+		vector_ensure(v, num);
+}
+
+/* This function only returns next empty slot index.  It dose not mean
+   the slot's index memory is assigned, please call vector_ensure()
+   after calling this function. */
+int vector_empty_slot(vector v)
+{
+	unsigned int i;
+
+	if (v->active == v->count)
+		return v->active;
+
+	if (v->active == 0)
+		return 0;
+
+	for (i = 0; i < v->active; i++)
+		if (v->index[i] == 0)
+			return i;
+
+	return i;
+}
+
+/* Set value to the smallest empty slot. */
+int vector_set(vector v, void *val)
+{
+	unsigned int i;
+
+	i = vector_empty_slot(v);
+	vector_ensure(v, i);
+
+	if (v->index[i])
+		v->count--;
+	if (val)
+		v->count++;
+	v->index[i] = val;
+
+	if (v->active <= i)
+		v->active = i + 1;
+
+	return i;
+}
+
+/* Set value to specified index slot. */
+int vector_set_index(vector v, unsigned int i, void *val)
+{
+	vector_ensure(v, i);
+
+	if (v->index[i])
+		v->count--;
+	if (val)
+		v->count++;
+	v->index[i] = val;
+
+	if (v->active <= i)
+		v->active = i + 1;
+
+	return i;
+}
+
+/* Look up vector.  */
+void *vector_lookup(vector v, unsigned int i)
+{
+	if (i >= v->active)
+		return NULL;
+	return v->index[i];
+}
+
+/* Lookup vector, ensure it. */
+void *vector_lookup_ensure(vector v, unsigned int i)
+{
+	vector_ensure(v, i);
+	return v->index[i];
+}
+
+/* Unset value at specified index slot. */
+void vector_unset(vector v, unsigned int i)
+{
+	if (i >= v->alloced)
+		return;
+
+	if (v->index[i])
+		v->count--;
+
+	v->index[i] = NULL;
+
+	if (i + 1 == v->active) {
+		v->active--;
+		while (i && v->index[--i] == NULL && v->active--)
+			; /* Is this ugly ? */
+	}
+}
+
+void vector_remove(vector v, unsigned int ix)
+{
+	if (ix >= v->active)
+		return;
+
+	if (v->index[ix])
+		v->count--;
+
+	int n = (--v->active) - ix;
+
+	memmove(&v->index[ix], &v->index[ix + 1], n * sizeof(void *));
+	v->index[v->active] = NULL;
+}
+
+void vector_compact(vector v)
+{
+	for (unsigned int i = 0; i < vector_active(v); ++i) {
+		if (vector_slot(v, i) == NULL) {
+			vector_remove(v, i);
+			--i;
+		}
+	}
+}
+
+void vector_unset_value(vector v, void *val)
+{
+	size_t i;
+
+	for (i = 0; i < v->active; i++)
+		if (v->index[i] == val) {
+			v->index[i] = NULL;
+			v->count--;
+			break;
+		}
+
+	if (i + 1 == v->active)
+		do
+			v->active--;
+		while (i && v->index[--i] == NULL);
+}
+
+void vector_to_array(vector v, void ***dest, int *argc)
+{
+	*dest = XCALLOC(MTYPE_TMP, sizeof(void *) * v->active);
+	memcpy(*dest, v->index, sizeof(void *) * v->active);
+	*argc = v->active;
+}
+
+vector array_to_vector(void **src, int argc)
+{
+	vector v = vector_init(VECTOR_MIN_SIZE);
+
+	for (int i = 0; i < argc; i++)
+		vector_set_index(v, i, src[i]);
+	return v;
+}