/*
* 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