#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;
}