summaryrefslogtreecommitdiff
path: root/test/test_hashlist.c
diff options
context:
space:
mode:
Diffstat (limited to 'test/test_hashlist.c')
-rw-r--r--test/test_hashlist.c284
1 files changed, 284 insertions, 0 deletions
diff --git a/test/test_hashlist.c b/test/test_hashlist.c
new file mode 100644
index 0000000..a0dbbf0
--- /dev/null
+++ b/test/test_hashlist.c
@@ -0,0 +1,284 @@
+#include "common.h"
+
+#include <glib.h>
+#include <stdio.h>
+#include <string.h>
+
+typedef struct _hashlist_t
+{
+ gchar** data;
+ gboolean* mark;
+ gsize size, fill;
+
+ const gchar** added;
+ const gchar** removed;
+} hashlist_t;
+
+static void hashlist_init(hashlist_t* hlist);
+static void hashlist_clear(hashlist_t* hlist);
+static void hashlist_free(hashlist_t* hlist);
+static gboolean hashlist_sync(hashlist_t* hlist,
+ const gchar** list, gsize count);
+
+static gboolean check(const gchar* name, hashlist_t* hlist, ...);
+
+#define CHECK(name, args...) \
+ do { \
+ ++tot; ok += check(name, &list, args) ? 1 : 0; \
+ } while (0)
+
+int main(int argc, char** argv)
+{
+ static const gchar* data[] = { "foo", "bar", "meh", "muh" };
+ int tot = 0, ok = 0;
+ hashlist_t list;
+
+ hashlist_init(&list);
+
+ hashlist_sync(&list, data, 0);
+ CHECK("nop sync", NULL, NULL);
+
+ hashlist_sync(&list, data, 2);
+ CHECK("add foo,bar", "foo", "bar", NULL, NULL);
+
+ hashlist_sync(&list, data, 4);
+ CHECK("add meh,muh", "meh", "muh", NULL, NULL);
+
+ hashlist_sync(&list, data + 2, 2);
+ CHECK("remove foo,bar", NULL, "foo", "bar", NULL);
+
+ hashlist_sync(&list, data, 4);
+ CHECK("add foo,bar", "foo", "bar", NULL, NULL);
+
+ hashlist_sync(&list, data, 3);
+ CHECK("remove muh", NULL, "muh", NULL);
+
+ hashlist_sync(&list, data + 1, 1);
+ CHECK("remove foo,meh", NULL, "meh", "foo", NULL);
+
+ hashlist_sync(&list, data + 2, 2);
+ CHECK("remove bar, add meh,muh", "meh", "muh", NULL, "bar", NULL);
+
+ hashlist_clear(&list);
+ CHECK("clear", NULL, NULL);
+
+ hashlist_free(&list);
+
+ fprintf(stdout, "OK %d/%d\n", ok, tot);
+ return EXIT_SUCCESS;
+}
+
+void hashlist_init(hashlist_t* hlist)
+{
+ hlist->fill = 0;
+ hlist->size = 10;
+ hlist->data = g_new0(gchar*, hlist->size);
+ hlist->mark = g_new0(gboolean, hlist->size);
+ hlist->added = (const gchar**)hlist->data;
+ hlist->removed = (const gchar**)hlist->data + hlist->size - 1;
+}
+
+void hashlist_clear(hashlist_t* hlist)
+{
+ gsize i, a, r;
+ for (a = hlist->added - (const gchar**)hlist->data; hlist->data[a]; ++a);
+ r = hlist->removed - (const gchar**)hlist->data;
+ for (i = 0; i < a; ++i)
+ {
+ g_free(hlist->data[i]);
+ }
+ for (i = r; hlist->data[i]; ++i)
+ {
+ g_free(hlist->data[i]);
+ }
+ hlist->data[0] = NULL;
+ hlist->fill = 0;
+ hlist->added = (const gchar**)hlist->data;
+ hlist->removed = (const gchar**)hlist->data + hlist->size - 1;
+}
+
+void hashlist_free(hashlist_t* hlist)
+{
+ hashlist_clear(hlist);
+ g_free(hlist->data);
+ g_free(hlist->mark);
+}
+
+gboolean hashlist_resize(hashlist_t* hlist, gsize* a, gsize* r)
+{
+ gsize ns = hlist->size * 2;
+ gchar** tmp;
+ g_assert(*r == hlist->size - 1);
+ if (ns < 10) ns = 10;
+ tmp = realloc(hlist->data, ns * sizeof(gchar**));
+ if (tmp == NULL)
+ {
+ hlist->added = (const gchar**)hlist->data + hlist->fill;
+ hlist->removed = (const gchar**)hlist->data + *r;
+ return FALSE;
+ }
+ memset(tmp + hlist->size, 0, (ns - hlist->size) * sizeof(gchar*));
+ hlist->data = tmp;
+ hlist->size = ns;
+ *r = hlist->size - 1;
+ return TRUE;
+}
+
+gboolean hashlist_sync(hashlist_t* hlist, const gchar** list, gsize count)
+{
+ gsize i, j, a, r;
+ gsize found = 0;
+ g_assert((const gchar**)hlist->data + hlist->fill == hlist->added);
+ for (a = hlist->added - (const gchar**)hlist->data; hlist->data[a]; ++a);
+ hlist->fill = a;
+ hlist->added = (const gchar**)hlist->data + a;
+ for (r = hlist->removed - (const gchar**)hlist->data; hlist->data[r]; ++r)
+ {
+ g_free(hlist->data[r]);
+ }
+ g_assert(r == hlist->size - 1);
+ if (a + 5 > r)
+ {
+ gsize ns = a + 10;
+ gchar** tmp = realloc(hlist->data, ns * sizeof(gchar*));
+ if (tmp != NULL)
+ {
+ hlist->data = tmp;
+ memset(hlist->data + hlist->size, 0,
+ (ns - hlist->size) * sizeof(gchar*));
+ hlist->size = ns;
+ r = hlist->size - 1;
+ }
+ }
+ memset(hlist->mark, 0, hlist->fill * sizeof(gboolean));
+ for (i = 0; i < count; ++i)
+ {
+ const gchar* hash = list[i];
+ if (found == hlist->fill)
+ {
+ if (a + 1 == r &&
+ !hashlist_resize(hlist, &a, &r))
+ {
+ return FALSE;
+ }
+ hlist->data[a++] = g_strdup(hash);
+ continue;
+ }
+ /* Quick path */
+ if (i < hlist->fill && !hlist->mark[i] &&
+ strcmp(hlist->data[i], hash) == 0)
+ {
+ hlist->mark[i] = TRUE;
+ found++;
+ continue;
+ }
+ for (j = i + 1; j != i; ++j)
+ {
+ if (j >= hlist->fill)
+ {
+ j = 0;
+ if (i == 0)
+ {
+ break;
+ }
+ }
+ if (hlist->mark[j])
+ {
+ continue;
+ }
+ if (strcmp(hlist->data[j], hash) == 0)
+ {
+ break;
+ }
+ }
+ if (j != i)
+ {
+ hlist->mark[j] = TRUE;
+ found++;
+ }
+ else
+ {
+ /* New */
+ if (a + 1 == r &&
+ !hashlist_resize(hlist, &a, &r))
+ {
+ return FALSE;
+ }
+ hlist->data[a++] = g_strdup(hash);
+ }
+ }
+ if (found < hlist->fill)
+ {
+ gsize n = hlist->fill - found;
+ for (j = hlist->fill - 1; n > 0; --j)
+ {
+ if (!hlist->mark[j])
+ {
+ hlist->data[--r] = hlist->data[j];
+ a--;
+ hlist->fill--;
+ memmove(hlist->data + j, hlist->data + j + 1,
+ (a - j) * sizeof(gchar*));
+ hlist->data[a] = NULL;
+ n--;
+ }
+ }
+ }
+ hlist->added = (const gchar**)hlist->data + hlist->fill;
+ hlist->removed = (const gchar**)hlist->data + r;
+ return TRUE;
+}
+
+gboolean check(const gchar* name, hashlist_t* hlist, ...)
+{
+ va_list args;
+ const gchar* x, **a, **r;
+ va_start(args, hlist);
+ a = hlist->added;
+ while ((x = va_arg(args, const gchar*)) != NULL)
+ {
+ if (*a == NULL)
+ {
+ fprintf(stderr, "%s: Expected added `%s` got EOL\n",
+ name, x);
+ return FALSE;
+ }
+ if (strcmp(*a, x) != 0)
+ {
+ fprintf(stderr, "%s: Expected added `%s` got `%s`\n", name, x, *a);
+ return FALSE;
+ }
+ ++a;
+ }
+ if (*a != NULL)
+ {
+ fprintf(stderr, "%s: Expected added EOL got `%s`\n",
+ name, *a);
+ return FALSE;
+ }
+ r = hlist->removed;
+ while ((x = va_arg(args, const gchar*)) != NULL)
+ {
+ if (*r == NULL)
+ {
+ fprintf(stderr, "%s: Expected removed `%s` got EOL\n",
+ name, x);
+ return FALSE;
+ }
+ if (strcmp(*r, x) != 0)
+ {
+ fprintf(stderr, "%s: Expected removed `%s` got `%s`\n",
+ name, x, *r);
+ return FALSE;
+ }
+ ++r;
+ }
+ va_end(args);
+ if (*r != NULL)
+ {
+ fprintf(stderr, "%s: Expected removed EOL got `%s`\n",
+ name, *r);
+ return FALSE;
+ }
+ return TRUE;
+}
generated by cgit v1.2.3-70-g09d2 (git 2.52.0) at 2025-12-07 01:31:01 +0000