nvml-sys 0.0.6

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

/*
 * ctree.c -- crit-bit tree implementation
 *
 * Crit-bit tree, or as otherwise known, a bitwise trie as implemented here
 * provides good performance for the allocator purpose as well as being
 * fairly simple. Contrary to popular balanced binary trees (rb/avl) it mostly
 * performs reads on nodes during insert.
 *
 * This structure is used throughout the libpmemobj for various tasks, the
 * primary one being to store and retrieve best-fit memory blocks.
 */
#include <stdint.h>
#include <stdlib.h>
#include <errno.h>

#include "ctree.h"
#include "out.h"
#include "sys_util.h"

#define BIT_IS_SET(n, i) (!!((n) & (1ULL << (i))))

/* internal nodes have LSB of the pointer set, leafs do not */
#define NODE_IS_INTERNAL(node) (BIT_IS_SET((uintptr_t)(node), 0))
#define NODE_INTERNAL_GET(node) ((void *)((char *)(node) - 1))
#define NODE_INTERNAL_SET(d, node) ((d) = (void *)((char *)(node) + 1))

#ifndef CTREE_FAST_RECURSIVE_DELETE
#define CTREE_FAST_RECURSIVE_DELETE 1
#endif

struct node {
	void *slots[2]; /* slots for either internal or leaf nodes */
	unsigned diff;	/* most significant differing bit */
};

struct node_leaf {
	uint64_t key;
	uint64_t value;
};

struct ctree {
	void *root;
	os_mutex_t lock;
};

/*
 * find_crit_bit -- (internal) finds the most significant differing bit
 */
static unsigned
find_crit_bit(uint64_t lhs, uint64_t rhs)
{
	/* util_mssb_index is undefined for 0 */
	uint64_t val = lhs ^ rhs;
	ASSERTne(val, 0);
	return util_mssb_index64(val);
}

/*
 * ctree_new -- allocates and initializes crit-bit tree instance
 */
struct ctree *
ctree_new(void)
{
	struct ctree *t = Malloc(sizeof(*t));
	if (t == NULL)
		return NULL;

	util_mutex_init(&t->lock);

	t->root = NULL;

	return t;
}

static void
ctree_free_internal_recursive(void *dst, ctree_destroy_cb cb, void *ctx)
{
	if (NODE_IS_INTERNAL(dst)) {
		struct node *a = NODE_INTERNAL_GET(dst);
		ctree_free_internal_recursive(a->slots[0], cb, ctx);
		ctree_free_internal_recursive(a->slots[1], cb, ctx);
		Free(a);
	} else {
		if (cb) {
			struct node_leaf *leaf = dst;
			cb(leaf->key, leaf->value, ctx);
		}
		Free(dst);
	}
}

/*
 * ctree_delete -- cleanups and frees crit-bit tree instance
 */
void
ctree_delete(struct ctree *t)
{
	ctree_clear_unlocked(t);

	util_mutex_destroy(&t->lock);

	Free(t);
}

/*
 * ctree_clear_unlocked -- removes all elements from the tree
 */
void
ctree_clear_unlocked(struct ctree *t)
{
#if	CTREE_FAST_RECURSIVE_DELETE
	if (t->root)
		ctree_free_internal_recursive(t->root, NULL, NULL);
#else
	while (t->root)
		ctree_remove_unlocked(t, 0, 0);
#endif
	t->root = NULL;
}

/*
 * ctree_clear -- removes all elements from the tree
 */
void
ctree_clear(struct ctree *t)
{
	util_mutex_lock(&t->lock);
	ctree_clear_unlocked(t);
	util_mutex_unlock(&t->lock);
}

/*
 * ctree_delete_cb -- cleanups and frees crit-bit tree instance
 */
void
ctree_delete_cb(struct ctree *t, ctree_destroy_cb cb, void *ctx)
{
	if (t->root)
		ctree_free_internal_recursive(t->root, cb, ctx);

	util_mutex_destroy(&t->lock);

	Free(t);
}

/*
 * ctree_insert_unlocked -- inserts a new key into the tree
 */
int
ctree_insert_unlocked(struct ctree *t, uint64_t key, uint64_t value)
{
	void **dst = &t->root;
	struct node *a = NULL;
	int err = 0;

	/* descend the path until a best matching key is found */
	while (NODE_IS_INTERNAL(*dst)) {
		a = NODE_INTERNAL_GET(*dst);
		dst = &a->slots[BIT_IS_SET(key, a->diff)];
	}

	struct node_leaf *dstleaf = *dst;
	struct node_leaf *nleaf = Malloc(sizeof(*nleaf));
	if (nleaf == NULL)
		return ENOMEM;

	nleaf->key = key;
	nleaf->value = value;

	if (dstleaf == NULL) { /* root */
		*dst = nleaf;
		goto out;
	}

	struct node *n = Malloc(sizeof(*n)); /* internal node */
	if (n == NULL) {
		err = ENOMEM;
		goto error_internal_malloc;
	}

	if (dstleaf->key == key) {
		err = EEXIST;
		goto error_duplicate;
	}

	n->diff = find_crit_bit(dstleaf->key, key);

	/* insert the node at the direction based on the critical bit */
	int d = BIT_IS_SET(key, n->diff);
	n->slots[d] = nleaf;

	/* find the appropriate position in the tree to insert the node */
	dst = &t->root;
	while (NODE_IS_INTERNAL(*dst)) {
		a = NODE_INTERNAL_GET(*dst);

		/* the critical bits have to be sorted */
		if (a->diff < n->diff)
			break;
		dst = &a->slots[BIT_IS_SET(key, a->diff)];
	}

	/* insert the found destination in the other slot */
	n->slots[!d] = *dst;
	NODE_INTERNAL_SET(*dst, n);

out:
	return 0;

error_duplicate:
	Free(n);
error_internal_malloc:
	Free(nleaf);
	return err;
}

/*
 * ctree_insert -- inserts a new key into the tree
 */
int
ctree_insert(struct ctree *t, uint64_t key, uint64_t value)
{
	util_mutex_lock(&t->lock);
	int ret = ctree_insert_unlocked(t, key, value);
	util_mutex_unlock(&t->lock);
	return ret;
}

/*
 * ctree_find_unlocked -- searches for an equal key in the tree
 */
uint64_t
ctree_find_unlocked(struct ctree *t, uint64_t key)
{
	struct node_leaf *dst = t->root;
	struct node *a = NULL;

	while (NODE_IS_INTERNAL(dst)) {
		a = NODE_INTERNAL_GET(dst);
		dst = a->slots[BIT_IS_SET(key, a->diff)];
	}

	if (dst && dst->key == key)
		return key;
	else
		return 0;
}

/*
 * ctree_find -- searches for an equal key in the tree
 */
uint64_t
ctree_find(struct ctree *t, uint64_t key)
{
	util_mutex_lock(&t->lock);
	uint64_t ret = ctree_find_unlocked(t, key);
	util_mutex_unlock(&t->lock);
	return ret;
}

/*
 * ctree_find_le_unlocked -- searches for a (less or equal) key in the tree
 */
uint64_t
ctree_find_le_unlocked(struct ctree *t, uint64_t *key)
{
	struct node_leaf *dst = t->root;
	struct node *a = NULL;

	while (NODE_IS_INTERNAL(dst)) {
		a = NODE_INTERNAL_GET(dst);
		dst = a->slots[BIT_IS_SET(*key, a->diff)];
	}

	if (dst == NULL || dst->key == *key)
		goto out;

	unsigned diff = find_crit_bit(dst->key, *key);

	struct node *top = NULL;
	dst = t->root;
	while (NODE_IS_INTERNAL(dst)) {
		a = NODE_INTERNAL_GET(dst);
		if (a->diff < diff)
			break;

		if (BIT_IS_SET(*key, a->diff)) {
			top = a->slots[0];
			dst = a->slots[1];
		} else {
			dst = a->slots[0];
		}
	}

	if (!BIT_IS_SET(*key, diff))
		dst = (struct node_leaf *)top;

	while (NODE_IS_INTERNAL(dst)) {
		a = NODE_INTERNAL_GET(dst);
		dst = a->slots[1];
	}

	if (dst && dst->key > *key)
		dst = NULL;

out:
	*key = dst ? dst->key : 0;
	uint64_t ret = dst ? dst->value : 0;
	return ret;
}

/*
 * ctree_find_le -- searches for a (less or equal) key in the tree
 */
uint64_t
ctree_find_le(struct ctree *t, uint64_t *key)
{
	util_mutex_lock(&t->lock);
	uint64_t ret = ctree_find_le_unlocked(t, key);
	util_mutex_unlock(&t->lock);
	return ret;
}

/*
 * ctree_remove_leaf -- (internal) removes provided root leaf
 */
static void
ctree_remove_leaf(struct ctree *t, void **dst, void **pparent)
{
	/*
	 * If the node that is being removed isn't root then simply swap the
	 * remaining child with the parent.
	 */
	if (t->root == *dst) {
		Free(*dst);
		*dst = NULL;
	} else {
		struct node *parent = NODE_INTERNAL_GET(*pparent);
		*pparent = parent->slots[parent->slots[0] == *dst];
		/* Free the internal node and the leaf */
		Free(*dst);
		Free(parent);
	}
}

/*
 * ctree_remove_max_unlocked -- removes the biggest element from the tree
 */
int
ctree_remove_max_unlocked(struct ctree *t, uint64_t *key, uint64_t *value)
{
	void **dst = &t->root;
	void **p = NULL; /* parent ref */
	struct node *a = NULL;

	while (NODE_IS_INTERNAL(*dst)) {
		a = NODE_INTERNAL_GET(*dst);
		p = dst;
		dst = &a->slots[1];
	}

	struct node_leaf *leaf = *dst;
	if (leaf == NULL) {
		return -1;
	}

	*key =  leaf->key;
	*value = leaf->value;
	ctree_remove_leaf(t, dst, p);

	return 0;
}

/*
 * ctree_remove_max -- removes the biggest element from the tree
 */
int
ctree_remove_max(struct ctree *t, uint64_t *key, uint64_t *value)
{
	util_mutex_lock(&t->lock);
	int ret = ctree_remove_max_unlocked(t, key, value);
	util_mutex_unlock(&t->lock);
	return ret;
}

/*
 * ctree_remove_unlocked -- removes a (greater or equal) key from the tree
 */
uint64_t
ctree_remove_unlocked(struct ctree *t, uint64_t key, int eq)
{
	void **p = NULL; /* parent ref */
	void **dst = &t->root; /* node to remove ref */
	struct node *a = NULL; /* internal node */

	struct node_leaf *leaf = NULL;
	uint64_t k = 0;

	if (t->root == NULL)
		goto out;

	/* find the key */
	while (NODE_IS_INTERNAL(*dst)) {
		a = NODE_INTERNAL_GET(*dst);
		p = dst;
		dst = &a->slots[BIT_IS_SET(key, a->diff)];
	}

	leaf = *dst;
	k = leaf->key;

	if (leaf->key == key) {
		goto remove;
	} else if (eq && leaf->key != key) {
		k = 0;
		goto out;
	}

	unsigned diff = find_crit_bit(k, key);

	void **top = NULL; /* top pointer */
	void **topp = NULL; /* top parent */
	p = NULL;
	dst = &t->root;

	while (NODE_IS_INTERNAL(*dst)) {
		a = NODE_INTERNAL_GET(*dst);
		p = dst;

		if (a->diff < diff)
			break;

		if (BIT_IS_SET(key, a->diff)) {
			dst = &a->slots[1];
		} else {
			topp = dst;
			top = &a->slots[1];
			dst = &a->slots[0];
		}
	}

	if (BIT_IS_SET(key, diff)) {
		dst = top;
		p = topp;
		a = p ? NODE_INTERNAL_GET(*p) : NULL;
	}

	if (dst == NULL) {
		k = 0;
		goto out;
	}

	while (NODE_IS_INTERNAL(*dst)) {
		a = NODE_INTERNAL_GET(*dst);
		p = dst;
		dst = &a->slots[0];
	}

	leaf = *dst;
	k = leaf->key;

	ASSERT(k > key);

remove:
	/*
	 * If the node that is being removed isn't root then simply swap the
	 * remaining child with the parent.
	 */
	if (a == NULL) {
		Free(*dst);
		*dst = NULL;
	} else {
		ASSERTne(p, NULL);
		*p = a->slots[a->slots[0] == *dst];
		/* Free the internal node and the leaf */
		Free(*dst);
		Free(a);
	}

out:
	return k;
}

/*
 * ctree_remove -- removes a (greater or equal) key from the tree
 */
uint64_t
ctree_remove(struct ctree *t, uint64_t key, int eq)
{
	util_mutex_lock(&t->lock);
	uint64_t ret = ctree_remove_unlocked(t, key, eq);
	util_mutex_unlock(&t->lock);
	return ret;
}

/*
 * ctree_is_empty_unlocked -- checks whether the tree is empty
 */
int
ctree_is_empty_unlocked(struct ctree *t)
{
	return t->root == NULL;
}

/*
 * ctree_is_empty -- checks whether the tree is empty
 */
int
ctree_is_empty(struct ctree *t)
{
	util_mutex_lock(&t->lock);

	int ret = ctree_is_empty_unlocked(t);

	util_mutex_unlock(&t->lock);

	return ret;
}