/*
 * Copyright 2016, FUJITSU TECHNOLOGY SOLUTIONS GMBH
 * Copyright 2012, Armon Dadgar. All rights reserved.
 * Copyright 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.
 */

/*
 * ==========================================================================
 *
 *     Filename:  art.h
 *
 *  Description:  implement ART tree using libvmem based on libart
 *
 *       Author:  Andreas Bluemle, Dieter Kasper
 *                Andreas.Bluemle.external@ts.fujitsu.com
 *                dieter.kasper@ts.fujitsu.com
 *
 * Organization:  FUJITSU TECHNOLOGY SOLUTIONS GMBH
 * ==========================================================================
 */
/*
 * based on https://github.com/armon/libart/src/art.h
 */
#include <stdint.h>
#ifndef ART_H
#define ART_H

#ifdef __cplusplus
extern "C" {
#endif

#define NODE4   1
#define NODE16  2
#define NODE48  3
#define NODE256 4

#define MAX_PREFIX_LEN 10

#if defined(__GNUC__) && !defined(__clang__)
#if __STDC_VERSION__ >= 199901L && 402 == (__GNUC__ * 100 + __GNUC_MINOR__)
/*
 * GCC 4.2.2's C99 inline keyword support is pretty broken; avoid. Introduced in
 * GCC 4.2.something, fixed in 4.3.0. So checking for specific major.minor of
 * 4.2 is fine.
 */
#define BROKEN_GCC_C99_INLINE
#endif
#endif

typedef int(*art_callback)(void *data, const unsigned char *key,
		uint32_t key_len, const unsigned char *value,
		uint32_t val_len);

/*
 * This struct is included as part
 * of all the various node sizes
 */
typedef struct {
	uint8_t type;
	uint8_t num_children;
	uint32_t partial_len;
	unsigned char partial[MAX_PREFIX_LEN];
} art_node;

/*
 * Small node with only 4 children
 */
typedef struct {
	art_node n;
	unsigned char keys[4];
	art_node *children[4];
} art_node4;

/*
 * Node with 16 children
 */
typedef struct {
	art_node n;
	unsigned char keys[16];
	art_node *children[16];
} art_node16;

/*
 * Node with 48 children, but
 * a full 256 byte field.
 */
typedef struct {
	art_node n;
	unsigned char keys[256];
	art_node *children[48];
} art_node48;

/*
 * Full node with 256 children
 */
typedef struct {
	art_node n;
	art_node *children[256];
} art_node256;

/*
 * Represents a leaf. These are
 * of arbitrary size, as they include the key.
 */
typedef struct {
	uint32_t key_len;
	uint32_t val_len;
	unsigned char *key;
	unsigned char *value;
	unsigned char data[];
} art_leaf;

/*
 * Main struct, points to root.
 */
typedef struct {
	art_node *root;
	uint64_t size;
} art_tree;

/*
 * Initializes an ART tree
 * @return 0 on success.
 */
int art_tree_init(art_tree *t);

/*
 * DEPRECATED
 * Initializes an ART tree
 * @return 0 on success.
 */
#define init_art_tree(...) art_tree_init(__VA_ARGS__)

/*
 * Destroys an ART tree
 * @return 0 on success.
 */
int art_tree_destroy(VMEM *vmp, art_tree *t);

/*
 * Returns the size of the ART tree.
 */
#ifdef BROKEN_GCC_C99_INLINE
#define art_size(t) ((t)->size)
#else
static inline uint64_t art_size(art_tree *t) {
	return t->size;
}
#endif

/*
 * Inserts a new value into the ART tree
 * @arg t The tree
 * @arg key The key
 * @arg key_len The length of the key
 * @arg value Opaque value.
 * @return NULL if the item was newly inserted, otherwise
 * the old value pointer is returned.
 */
void *art_insert(VMEM *vmp, art_tree *t, const unsigned char *key,
	    int key_len, void *value, int val_len);

/*
 * Deletes a value from the ART tree
 * @arg t The tree
 * @arg key The key
 * @arg key_len The length of the key
 * @return NULL if the item was not found, otherwise
 * the value pointer is returned.
 */
void *art_delete(VMEM *vmp, art_tree *t, const unsigned char *key,
	    int key_len);

/*
 * Searches for a value in the ART tree
 * @arg t The tree
 * @arg key The key
 * @arg key_len The length of the key
 * @return NULL if the item was not found, otherwise
 * the value pointer is returned.
 */
void *art_search(const art_tree *t, const unsigned char *key, int key_len);

/*
 * Returns the minimum valued leaf
 * @return The minimum leaf or NULL
 */
art_leaf *art_minimum(art_tree *t);

/*
 * Returns the maximum valued leaf
 * @return The maximum leaf or NULL
 */
art_leaf *art_maximum(art_tree *t);

/*
 * Iterates through the entries pairs in the map,
 * invoking a callback for each. The call back gets a
 * key, value for each and returns an integer stop value.
 * If the callback returns non-zero, then the iteration stops.
 * @arg t The tree to iterate over
 * @arg cb The callback function to invoke
 * @arg data Opaque handle passed to the callback
 * @return 0 on success, or the return of the callback.
 */
int art_iter(art_tree *t, art_callback cb, void *data);

typedef struct _cb_data {
	int node_type;
	int child_idx;
	int first_child;
	void *node;
} cb_data;

int art_iter2(art_tree *t, art_callback cb, void *data);

/*
 * Iterates through the entries pairs in the map,
 * invoking a callback for each that matches a given prefix.
 * The call back gets a key, value for each and returns an integer stop value.
 * If the callback returns non-zero, then the iteration stops.
 * @arg t The tree to iterate over
 * @arg prefix The prefix of keys to read
 * @arg prefix_len The length of the prefix
 * @arg cb The callback function to invoke
 * @arg data Opaque handle passed to the callback
 * @return 0 on success, or the return of the callback.
 */
int art_iter_prefix(art_tree *t, const unsigned char *prefix, int prefix_len,
	    art_callback cb, void *data);

#ifdef __cplusplus
}
#endif

#endif
