X-Git-Url: https://git.sommitrealweird.co.uk/onak.git/blobdiff_plain/17623ae905ff751306ed51a30fd0ee97ffd00d01..be024aa68a513a2a85a7cddb28de4664b0b96144:/keyarray.c

diff --git a/keyarray.c b/keyarray.c
new file mode 100644
index 0000000..389eb0d
--- /dev/null
+++ b/keyarray.c
@@ -0,0 +1,105 @@
+/*
+ * keyarray.c - routines to maintain a sorted array of keyids.
+ *
+ * Jonathan McDowell <noodles@earth.li>
+ *
+ * Copyright 2004 Project Purple
+ */
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "keyarray.h"
+
+bool array_find(struct keyarray *array, uint64_t key)
+{
+	bool found;
+	int  top = 0;
+	int  bottom = 0;
+	int  curpos;
+
+	found = false;
+	if (array->keys != NULL && array->count > 0) {
+		bottom = -1;
+		top = array->count - 1;
+		while ((top - bottom) > 1) {
+			curpos = (top + bottom) / 2;
+			if (key > array->keys[curpos]) {
+				bottom = curpos;
+			} else {
+				top = curpos;
+			}
+		}
+		found = (array->keys[top] == key);
+	}
+
+	return found;
+}
+
+bool array_add(struct keyarray *array, uint64_t key)
+{
+	bool found;
+	int  top = 0;
+	int  bottom = 0;
+	int  curpos = 0;
+
+	found = false;
+	if (array->keys != NULL && array->count > 0) {
+		bottom = -1;
+		top = array->count - 1;
+		while ((top - bottom) > 1) {
+			curpos = (top + bottom) / 2;
+			if (key > array->keys[curpos]) {
+				bottom = curpos;
+			} else {
+				top = curpos;
+			}
+		}
+		found = (array->keys[top] == key);
+
+		if (key > array->keys[top]) {
+			curpos = top + 1;
+		} else {
+			curpos = top;
+		}
+	}
+
+	if (!found) {
+		if (array->size == 0) {
+			array->keys = malloc(16 * sizeof(uint64_t));
+			array->size = 16;
+			array->count = 1;
+			array->keys[0] = key;
+		} else {
+			if (array->count >= array->size) {
+				array->size *= 2;
+				array->keys = realloc(array->keys,
+						array->size * sizeof(uint64_t));
+			}
+			if (curpos < array->count) {
+				memmove(&array->keys[curpos+1],
+					&array->keys[curpos],
+					sizeof(uint64_t) *
+						(array->count - curpos));
+			}
+			array->keys[curpos] = key;
+			array->count++;
+		}
+	}
+
+	return !found;
+}
+
+void array_free(struct keyarray *array)
+{
+	if (array->keys) {
+		free(array->keys);
+		array->keys = NULL;
+	}
+	array->count = array->size = 0;
+
+	return;
+}