/*
 * Copyright 2015-2017, Intel Corporation
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 *     * Neither the name of the copyright holder nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * btree.c -- implementation of persistent binary search tree
 */

#include "ex_common.h"
#include <stdio.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <libpmemobj.h>

POBJ_LAYOUT_BEGIN(btree);
POBJ_LAYOUT_ROOT(btree, struct btree);
POBJ_LAYOUT_TOID(btree, struct btree_node);
POBJ_LAYOUT_END(btree);

struct btree_node {
    int64_t key;
    TOID(struct btree_node) slots[2];
    char value[32];
};

struct btree {
    TOID(struct btree_node) root;
};

struct btree_node_arg {
    size_t size;
    int64_t key;
    const char *value;
};

/*
 * btree_node_construct -- constructor of btree node
 */
static int
btree_node_construct(PMEMobjpool *pop, void *ptr, void *arg)
{
    struct btree_node *node = (struct btree_node *)ptr;
    struct btree_node_arg *a = (struct btree_node_arg *)arg;

    node->key = a->key;
    strcpy(node->value, a->value);
    node->slots[0] = TOID_NULL(struct btree_node);
    node->slots[1] = TOID_NULL(struct btree_node);

    pmemobj_persist(pop, node, a->size);

    return 0;
}

/*
 * btree_insert -- inserts new element into the tree
 */
static void
btree_insert(PMEMobjpool *pop, int64_t key, const char *value)
{
    TOID(struct btree) btree = POBJ_ROOT(pop, struct btree);
    TOID(struct btree_node) *dst = &D_RW(btree)->root;

    while (!TOID_IS_NULL(*dst)) {
        dst = &D_RW(*dst)->slots[key > D_RO(*dst)->key];
    }

    struct btree_node_arg args;
    args.size = sizeof(struct btree_node) + strlen(value) + 1;
    args.key = key;
    args.value = value;

    POBJ_ALLOC(pop, dst, struct btree_node, args.size,
        btree_node_construct, &args);
}

/*
 * btree_find -- searches for key in the tree
 */
static const char *
btree_find(PMEMobjpool *pop, int64_t key)
{
    TOID(struct btree) btree = POBJ_ROOT(pop, struct btree);
    TOID(struct btree_node) node = D_RO(btree)->root;

    while (!TOID_IS_NULL(node)) {
        if (D_RO(node)->key == key)
            return D_RO(node)->value;
        else
            node = D_RO(node)->slots[key > D_RO(node)->key];
    }

    return NULL;
}

/*
 * btree_node_print -- prints content of the btree node
 */
static void
btree_node_print(const TOID(struct btree_node) node)
{
    printf("%" PRIu64 " %s\n", D_RO(node)->key, D_RO(node)->value);
}

/*
 * btree_foreach -- invoke callback for every node
 */
static void
btree_foreach(PMEMobjpool *pop, const TOID(struct btree_node) node,
    void(*cb)(const TOID(struct btree_node) node))
{
    if (TOID_IS_NULL(node))
        return;

    btree_foreach(pop, D_RO(node)->slots[0], cb);

    cb(node);

    btree_foreach(pop, D_RO(node)->slots[1], cb);
}

/*
 * btree_print -- initiates foreach node print
 */
static void
btree_print(PMEMobjpool *pop)
{
    TOID(struct btree) btree = POBJ_ROOT(pop, struct btree);

    btree_foreach(pop, D_RO(btree)->root, btree_node_print);
}

int
main(int argc, char *argv[])
{
    if (argc < 3) {
        printf("usage: %s file-name [p|i|f|s|r] [key] [value] \n", argv[0]);
        return 1;
    }

    const char *path = argv[1];

    PMEMobjpool *pop;

    if (file_exists(path) != 0) {
        if ((pop = pmemobj_create(path, POBJ_LAYOUT_NAME(btree),
            PMEMOBJ_MIN_POOL, 0666)) == NULL) {
            perror("failed to create pool\n");
            return 1;
        }
    } else {
        if ((pop = pmemobj_open(path,
                POBJ_LAYOUT_NAME(btree))) == NULL) {
            perror("failed to open pool\n");
            return 1;
        }
    }

    const char op = argv[2][0];
    int64_t key,k,len;
    const char *value;

    switch (op) {
    case 'p':
        btree_print(pop);
    break;
    case 'i':
        key = atoll(argv[3]);
        value = argv[4];
        btree_insert(pop, key, value);
    break;
    case 'f':
        key = atoll(argv[3]);
        if ((value = btree_find(pop, key)) != NULL)
            printf("%s\n", value);
        else
            printf("not found\n");
    break;
    case 's':
        len = atoll(argv[3]);
        for(k=0; k<len; k++) {
            btree_insert(pop, k, "test");
        }
        break;
    case 'r':
        len = atoll(argv[3]);
        for(long k=0; k<len; k++) {
                btree_find(pop, k);
        }
        break;
    default:
        printf("invalid operation\n");
        break;
    }

    pmemobj_close(pop);

    return 0;
}