/*
 * Ouroboros - Copyright (C) 2016 - 2017
 *
 * Resource Information Base
 *
 *    Dimitri Staessens <dimitri.staessens@intec.ugent.be>
 *    Sander Vrijders   <sander.vrijders@intec.ugent.be>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * version 2.1 as published by the Free Software Foundation.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301 USA
 */

#include <ouroboros/config.h>
#include <ouroboros/errno.h>
#include <ouroboros/list.h>
#include <ouroboros/rib.h>
#include <ouroboros/rqueue.h>
#include <ouroboros/bitmap.h>
#include <ouroboros/crc32.h>
#include <ouroboros/time_utils.h>

#include "sha3.h"
#include "btree.h"

#include <pthread.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#define RIB_PATH_DLR     "/"
#define RIB_BTREE_ORDER   64
#define GEN_NAME_SIZE      8

struct revent {
        struct list_head next;

        char *           path;
        int32_t          flags;
};

struct rqueue {
        struct list_head events;
};

struct ro_set {
        uint32_t         sid;
};

struct rn_ptr {
        struct list_head next;

        struct rnode *   node;
};

struct rib_sub {
        struct list_head next;

        uint32_t         sid;

        struct list_head rnodes;

        struct list_head events;

        pthread_cond_t   cond;
        pthread_mutex_t  lock;
};

struct rn_sub {
        struct list_head next;

        struct rib_sub * sub;
        int32_t          flags;
};

struct rnode {
        char *           path;
        char *           name;

        uint8_t *        data;
        size_t           len;

        uint8_t          sha3[sha3_256_hash_size];

        struct rnode *   parent;

        struct list_head children;

        struct list_head subs;
};

struct child {
        struct list_head next;

        struct rnode * node;
};

struct rib {
        struct rnode *   root;

        struct btree *   idx;

        pthread_rwlock_t lock;

        struct bmp *     sids;

        struct list_head subs;

        pthread_rwlock_t s_lock;
} rib;

static void rnode_hash(struct rnode * node)
{
        struct sha3_ctx ctx;
        struct list_head * p;

        assert(node);
        assert(node->path);
        assert(node->name);

        rhash_sha3_256_init(&ctx);

        rhash_sha3_update(&ctx, (uint8_t *) node->path, strlen(node->path));

        if (node->data != NULL)
                rhash_sha3_update(&ctx, node->data, node->len);

        list_for_each(p, &node->children) {
                struct child * c = list_entry(p, struct child, next);
                rhash_sha3_update(&ctx, c->node->sha3, sha3_256_hash_size);
        }

        rhash_sha3_final(&ctx, node->sha3);
}

static void branch_hash(struct rnode * node)
{
        assert(node);

        do {
                rnode_hash(node);
                node = node->parent;
        } while (node != NULL);
}

static struct revent * revent_dup(struct revent * ev)
{
        struct revent * re;

        assert(ev);
        assert(ev->path);

        re = malloc(sizeof(*re));
        if (re == NULL)
                return NULL;

        re->path = strdup(ev->path);
        if (re->path == NULL) {
                free(re);
                return NULL;
        }

        re->flags = ev->flags;

        return re;
}

/* defined below but needed here */
static void rib_sub_del_rnode(struct rib_sub * sub,
                              struct rnode *   node);

static void rnode_notify_subs(struct rnode *  node,
                              struct rnode *  ch,
                              struct revent * ev)
{
        struct list_head * p;

        assert(node);

        list_for_each(p, &node->subs) {
                struct rn_sub * s = list_entry(p, struct rn_sub, next);
                if (s->flags & ev->flags) {
                        struct revent * e = revent_dup(ev);
                        list_add_tail(&e->next, &s->sub->events);
                }

                if (ev->flags & RO_DELETE)
                        rib_sub_del_rnode(s->sub, ch);
        }
}

static int rnode_throw_event(struct rnode * node,
                             int32_t        flags)
{
        struct revent * ev = malloc(sizeof(*ev));
        struct rnode * rn = node;

        assert(node);
        assert(node->path);

        if (ev == NULL)
                return -ENOMEM;

        list_head_init(&ev->next);

        ev->path = strdup(node->path);
        if (ev->path == NULL) {
                free(ev);
                return -ENOMEM;
        }

        ev->flags = flags;

        do {
                rnode_notify_subs(rn, node, ev);
                rn = rn->parent;
        } while (rn != NULL);

        free(ev->path);
        free(ev);

        return 0;
}

static int rnode_add_child(struct rnode * node,
                           struct rnode * child)
{
        struct child * c;

        assert(node);
        assert(child);

        c = malloc(sizeof(*c));
        if (c == NULL)
                return -ENOMEM;

        c->node = child;
        list_add(&c->next, &node->children);

        return 0;
}

static void rnode_remove_child(struct rnode * node,
                               struct rnode * child)
{
        struct list_head * p;
        struct list_head * h;

        assert(node);
        assert(child);

        list_for_each_safe(p, h, &node->children) {
                struct child * c = list_entry(p, struct child, next);
                if (c->node == child) {
                        list_del(&c->next);
                        free(c);
                        return;
                }
        }
}

static struct rnode * rnode_create(struct rnode *  parent,
                                   const char *    name)
{
        struct rnode * node;
        char * parent_path;

        assert(name);

        node = malloc(sizeof(*node));
        if (node == NULL)
                return NULL;

        list_head_init(&node->children);
        list_head_init(&node->subs);

        if (parent == NULL)
                parent_path = "";
        else
                parent_path = parent->path;

        node->path = malloc(strlen(parent_path)
                            + strlen(RIB_PATH_DLR)
                            + strlen(name)
                            + 1);
        if (node->path == NULL) {
                free(node);
                return NULL;
        }

        strcpy(node->path, parent_path);
        node->name = node->path + strlen(parent_path);
        if (parent != NULL) {
                strcpy(node->name, RIB_PATH_DLR);
                node->name += strlen(RIB_PATH_DLR);
        }

        strcpy(node->name, name);

        if (parent != NULL) {
                if (rnode_add_child(parent, node)) {
                        free(node->path);
                        free(node);
                        return NULL;
                }
        }

        node->data = NULL;
        node->len = 0;

        node->parent = parent;

        branch_hash(node);
        rnode_throw_event(node, RO_CREATE);

        return node;
}

static void destroy_rnode(struct rnode * node)
{
        struct list_head * p;
        struct list_head * h;

        assert(node);

        if (node != rib.root) {
                rnode_remove_child(node->parent, node);
                branch_hash(node->parent);
        }

        rnode_throw_event(node, RO_DELETE);

        list_for_each_safe(p, h, &node->subs) {
                struct rn_sub * s = list_entry(p, struct rn_sub, next);
                list_del(&s->next);
                free(s);
        }

        free(node->path);
        if (node->data != NULL)
                free(node->data);

        free(node);
}

static void destroy_rtree(struct rnode * node)
{
        struct list_head * p;
        struct list_head * h;

        assert(node);

        list_for_each_safe(p, h, &node->children) {
                struct child * c = list_entry(p, struct child, next);
                destroy_rtree(c->node);
        }

        destroy_rnode(node);
}

static int rnode_update(struct rnode *  node,
                        uint8_t *       data,
                        size_t          len)
{
        assert(node);
        assert(!(data == NULL && len != 0));
        assert(!(data != NULL && len == 0));

        if (node->data != NULL)
                free(node->data);

        node->data = data;
        node->len = len;

        rnode_throw_event(node, RO_MODIFY);

        branch_hash(node);

        return 0;
}

static struct rn_sub * rnode_get_sub(struct rnode *   node,
                                     struct rib_sub * sub)
{
        struct list_head * p;

        list_for_each(p, &node->subs) {
                struct rn_sub * r = list_entry(p, struct rn_sub, next);
                if (r->sub == sub)
                        return r;
        }

        return NULL;
}

static int rnode_add_sub(struct rnode *   node,
                         struct rib_sub * sub,
                         int32_t          flags)
{
        struct rn_sub * rs;

        assert(node);
        assert(sub);

        rs = rnode_get_sub(node, sub);
        if (rs != NULL)
                return -EPERM;

        rs = malloc(sizeof(*rs));
        if (rs == NULL)
                return -ENOMEM;

        rs->sub = sub;
        rs->flags = flags;

        list_add(&rs->next, &node->subs);

        return 0;
}

static int rnode_del_sub(struct rnode *   node,
                         struct rib_sub * sub)
{
        struct rn_sub * rs;

        assert(node);
        assert(sub);

        rs = rnode_get_sub(node, sub);
        if (rs == NULL)
                return 0;

        list_del(&rs->next);
        free(rs);

        return 0;
}

static struct rnode * find_rnode_by_path(const char * path)
{
        uint32_t crc = 0;

        if (strcmp(path, RIB_ROOT) == 0)
                return rib.root;

        crc32(&crc, path, strlen(path));

        return (struct rnode *) btree_search(rib.idx, crc);
}

int rib_init(void)
{
        if (rib.root != NULL)
                return -EPERM;

        rib.root = rnode_create(NULL, "");
        if (rib.root == NULL)
                return -ENOMEM;

        rib.idx = btree_create(RIB_BTREE_ORDER);
        if (rib.idx == NULL) {
                destroy_rtree(rib.root);
                rib.root = NULL;
                return -1;
        }

        rib.sids = bmp_create(32, 1);
        if (rib.sids == NULL) {
                btree_destroy(rib.idx);
                destroy_rtree(rib.root);
                rib.root = NULL;
                return -1;
        }

        if (pthread_rwlock_init(&rib.lock, NULL)) {
                bmp_destroy(rib.sids);
                btree_destroy(rib.idx);
                destroy_rtree(rib.root);
                rib.root = NULL;
                return -1;
        }

        if (pthread_rwlock_init(&rib.s_lock, NULL)) {
                pthread_rwlock_destroy(&rib.lock);
                bmp_destroy(rib.sids);
                btree_destroy(rib.idx);
                destroy_rtree(rib.root);
                rib.root = NULL;
                return -1;
        }

        list_head_init(&rib.subs);

        assert(rib.root);

        return 0;
}

void rib_fini(void)
{
        if (rib.root == NULL)
                return;

        btree_destroy(rib.idx);

        bmp_destroy(rib.sids);

        destroy_rtree(rib.root);
        rib.root = NULL;

        pthread_rwlock_destroy(&rib.lock);
}

int rib_add(const char * path,
            const char * name)
{
        struct rnode * parent;
        struct rnode * node;

        uint32_t crc = 0;

        if (name == NULL)
                return -EINVAL;

        pthread_rwlock_wrlock(&rib.lock);

        parent = find_rnode_by_path(path);
        if (parent == NULL) {
                pthread_rwlock_unlock(&rib.lock);
                return -EPERM;
        }

        node = rnode_create(parent, name);
        if (node == NULL) {
                pthread_rwlock_unlock(&rib.lock);
                return -ENOMEM;
        }

        crc32(&crc, node->path, strlen(node->path));

        btree_insert(rib.idx, crc, node);

        pthread_rwlock_unlock(&rib.lock);

        return 0;
}

int rib_del(char * path)
{
        struct rnode * node;
        uint32_t crc = 0;

        if (path == NULL)
                return -EINVAL;

        pthread_rwlock_wrlock(&rib.lock);

        node = find_rnode_by_path(path);
        if (node == NULL) {
                pthread_rwlock_unlock(&rib.lock);
                return -EINVAL;
        }

        crc32(&crc, node->path, strlen(node->path));

        btree_remove(rib.idx, crc);

        destroy_rtree(node);

        pthread_rwlock_unlock(&rib.lock);

        return 0;
}

ssize_t rib_read(const char * path,
                 void *       data,
                 size_t       len)
{
        struct rnode * node;
        ssize_t        rlen;

        if (path == NULL || data == NULL)
                return -EINVAL;

        pthread_rwlock_rdlock(&rib.lock);

        node = find_rnode_by_path(path);
        if (node == NULL) {
                pthread_rwlock_unlock(&rib.lock);
                return -EPERM;
        }

        if (len < node->len) {
                pthread_rwlock_unlock(&rib.lock);
                return -EFBIG;
        }

        memcpy(data, node->data, node->len);
        rlen = node->len;

        rnode_throw_event(node, RO_READ);

        pthread_rwlock_unlock(&rib.lock);

        return rlen;
}

int rib_write(const char * path,
              const void * data,
              size_t       len)
{
        struct rnode * node;
        int            ret = -1;

        uint8_t * cdata;

        if (path == NULL)
                return -EINVAL;

        cdata = malloc(len);
        if (cdata == NULL)
                return -ENOMEM;

        memcpy(cdata, data, len);

        pthread_rwlock_rdlock(&rib.lock);

        node = find_rnode_by_path(path);
        if (node != NULL)
                ret = rnode_update(node, cdata, len);

        pthread_rwlock_unlock(&rib.lock);

        return ret;
}

int rib_put(const char * path,
            void *       data,
            size_t       len)
{
        struct rnode * node;
        int            ret = -1;

        if (path == NULL)
                return -EINVAL;

        pthread_rwlock_rdlock(&rib.lock);

        node = find_rnode_by_path(path);
        if (node != NULL)
                ret = rnode_update(node, (uint8_t *) data, len);

        pthread_rwlock_unlock(&rib.lock);

        return ret;
}

bool rib_has(const char * path)
{
        struct rnode * node;

        assert(path);

        pthread_rwlock_rdlock(&rib.lock);

        node = find_rnode_by_path(path);

        pthread_rwlock_unlock(&rib.lock);

        return node != NULL;
}

static struct rib_sub * rib_get_sub(uint32_t sid)
{
        struct list_head * p;
        struct list_head * h;

        list_for_each_safe(p, h, &rib.subs) {
                struct rib_sub * r = list_entry(p, struct rib_sub, next);
                if (r->sid == sid)
                        return r;
        }

        return 0;
}

static struct rib_sub * rib_sub_create(uint32_t sid)
{
        struct rib_sub * sub = malloc(sizeof(*sub));
        if (sub == NULL)
                return NULL;

        if (pthread_cond_init(&sub->cond, NULL)) {
                free(sub);
                return NULL;
        }

        if (pthread_mutex_init(&sub->lock, NULL)) {
                pthread_cond_destroy(&sub->cond);
                free(sub);
                return NULL;
        }

        list_head_init(&sub->rnodes);
        list_head_init(&sub->events);

        sub->sid = sid;

        return sub;
}

static void rib_sub_zero(struct rib_sub * sub)
{
        struct list_head * p;
        struct list_head * h;

        assert(sub);

        list_for_each_safe(p, h, &sub->rnodes) {
                struct rn_ptr * r = list_entry(p, struct rn_ptr, next);
                assert(r->node);
                rnode_del_sub(r->node, sub);
                list_del(&r->next);
                free(r);
        }

        list_for_each_safe(p, h, &sub->events) {
                struct revent * r = list_entry(p, struct revent, next);
                list_del(&r->next);
                assert(r->path);
                free(r->path);
                free(r);
        }
}

static struct rn_ptr * rib_sub_get_rn_ptr(struct rib_sub * sub,
                                          struct rnode *   node)
{
        struct list_head * p;

        list_for_each(p, &sub->rnodes) {
                struct rn_ptr * r = list_entry(p, struct rn_ptr, next);
                assert(r->node);
                if (r->node == node)
                        return r;
        }

        return NULL;
}

static int rib_sub_add_rnode(struct rib_sub * sub,
                             struct rnode *   node)
{
        struct rn_ptr * rn;

        assert(sub);
        assert(node);

        if (rib_sub_get_rn_ptr(sub, node) != NULL)
                return 0;

        rn = malloc(sizeof(*rn));
        if (rn == NULL)
                return -ENOMEM;

        rn->node = node;

        list_add(&rn->next, &sub->rnodes);

        return 0;
}

static void rib_sub_del_rnode(struct rib_sub * sub,
                              struct rnode *   node)
{
        struct rn_ptr * rn;

        assert(sub);
        assert(node);

        rn = rib_sub_get_rn_ptr(sub, node);
        if (rn == NULL)
                return;

        list_del(&rn->next);

        free(rn);
}

static void rib_sub_destroy(struct rib_sub * sub)
{
        assert(sub);

        rib_sub_zero(sub);

        free(sub);
}

/* Event calls from rqueue.h. */
ro_set_t * ro_set_create(void)
{
        ro_set_t * set;
        struct rib_sub * sub;

        set = malloc(sizeof(*set));
        if (set == NULL)
                return NULL;

        pthread_rwlock_wrlock(&rib.s_lock);

        set->sid = bmp_allocate(rib.sids);
        if (!bmp_is_id_valid(rib.sids, set->sid)) {
                pthread_rwlock_unlock(&rib.s_lock);
                free(set);
                return NULL;
        }

        pthread_rwlock_unlock(&rib.s_lock);

        pthread_rwlock_wrlock(&rib.lock);

        sub = rib_sub_create(set->sid);
        if (sub == NULL) {
                pthread_rwlock_unlock(&rib.lock);
                free(set);
                return NULL;
        }

        list_add(&sub->next, &rib.subs);

        pthread_rwlock_unlock(&rib.lock);

        return set;
}

void ro_set_destroy(ro_set_t * set)
{
        struct rib_sub * sub = NULL;

        struct list_head * p;
        struct list_head * h;

        pthread_rwlock_wrlock(&rib.lock);

        list_for_each_safe(p, h, &rib.subs) {
                struct rib_sub * r = list_entry(p, struct rib_sub, next);
                if (r->sid == set->sid) {
                        sub = r;
                        break;
                }
        }

        if (sub != NULL)
                rib_sub_destroy(sub);

        pthread_rwlock_unlock(&rib.lock);

        pthread_rwlock_wrlock(&rib.s_lock);

        bmp_release(rib.sids, set->sid);

        pthread_rwlock_unlock(&rib.s_lock);

        free(set);
}

rqueue_t * rqueue_create(void)
{
        rqueue_t * rq = malloc(sizeof(*rq));
        if (rq == NULL)
                return NULL;

        list_head_init(&rq->events);

        return rq;
}

int rqueue_destroy(struct rqueue * rq)
{
        struct list_head * p;
        struct list_head * h;

        list_for_each_safe(p, h, &rq->events) {
                struct revent * e = list_entry(p, struct revent, next);
                list_del(&e->next);
                free(e->path);
                free(e);
        }

        free(rq);

        return 0;
}

int ro_set_zero(ro_set_t * set)
{
        struct rib_sub * sub;

        if (set == NULL)
                return -EINVAL;

        pthread_rwlock_wrlock(&rib.lock);

        sub = rib_get_sub(set->sid);

        assert(sub);

        rib_sub_zero(sub);

        pthread_rwlock_unlock(&rib.lock);

        return 0;
}

int ro_set_add(ro_set_t *   set,
               const char * path,
               int32_t      flags)
{
        struct rib_sub * sub;
        struct rnode * node;

        if (set == NULL)
                return -EINVAL;

        pthread_rwlock_wrlock(&rib.lock);

        sub = rib_get_sub(set->sid);

        assert(sub);

        node = find_rnode_by_path(path);
        if (node == NULL) {
                pthread_rwlock_unlock(&rib.lock);
                return -1;
        }

        if (rnode_add_sub(node, sub, flags)) {
                pthread_rwlock_unlock(&rib.lock);
                return -ENOMEM;
        }

        if (rib_sub_add_rnode(sub, node)) {
                pthread_rwlock_unlock(&rib.lock);
                return -ENOMEM;
        }

        pthread_rwlock_unlock(&rib.lock);

        return 0;
}

int ro_set_del(ro_set_t *   set,
               const char * path)
{
        struct rib_sub * sub;
        struct rnode * node;

        if (set == NULL)
                return -EINVAL;

        pthread_rwlock_wrlock(&rib.lock);

        sub = rib_get_sub(set->sid);

        assert(sub);

        node = find_rnode_by_path(path);
        if (node == NULL) {
                pthread_rwlock_unlock(&rib.lock);
                return -1;
        }

        rnode_del_sub(node, sub);

        rib_sub_del_rnode(sub, node);

        pthread_rwlock_unlock(&rib.lock);

        return 0;
}

int32_t rqueue_next(rqueue_t * rq,
                    char *     path)
{
        struct revent * ev;
        int32_t         ret;

        if (list_is_empty(&rq->events))
                return -1;

        ev = list_first_entry(&rq->events, struct revent, next);
        list_del(&ev->next);

        strcpy(path, ev->path);
        ret = ev->flags;

        free(ev->path);
        free(ev);

        return ret;
}

int rib_event_wait(ro_set_t *              set,
                   rqueue_t *              rq,
                   const struct timespec * timeout)
{
        struct rib_sub * sub;
        struct timespec abstime;

        ssize_t ret = 0;

        if (set == NULL || rq == NULL)
                return -EINVAL;

        if (!list_is_empty(&rq->events))
                return 0;

        if (timeout != NULL) {
                clock_gettime(PTHREAD_COND_CLOCK, &abstime);
                ts_add(&abstime, timeout, &abstime);
        }

        pthread_rwlock_rdlock(&rib.lock);

        sub = rib_get_sub(set->sid);

        pthread_rwlock_unlock(&rib.lock);

        pthread_mutex_lock(&sub->lock);

        while (list_is_empty(&sub->events) && ret != -ETIMEDOUT) {
                if (timeout != NULL)
                        ret = -pthread_cond_timedwait(&sub->cond ,
                                                      &sub->lock,
                                                      &abstime);
                else
                        ret = -pthread_cond_wait(&sub->cond, &sub->lock);
        }

        pthread_mutex_unlock(&sub->lock);

        pthread_rwlock_wrlock(&rib.lock);

        if (ret != -ETIMEDOUT)
                list_move(&rq->events, &sub->events);

        pthread_rwlock_wrlock(&rib.lock);

        return ret;
}

/* Path name management. */
char * rib_path_append(char *       path,
                       const char * name)
{
        char * pos;

        if (path == NULL || name == NULL || strstr(name, RIB_PATH_DLR))
                return NULL;

        pos = path + strlen(path);
        memcpy(pos++, RIB_PATH_DLR, 1);
        strcpy(pos, name);

        return path;
}

char * rib_name_gen(void *       data,
                    size_t       len)
{
        uint32_t crc = 0;
        char * name;

        if (data == NULL || len == 0)
                return NULL;

        name= malloc(GEN_NAME_SIZE + 1);
        if (name == NULL)
                return NULL;

        crc32(&crc, data, len);

        sprintf(name, "%08x", crc);

        return name;
}