/*
* COPYRIGHT (c) International Business Machines Corp. 2005-2017
*
* This program is provided under the terms of the Common Public License,
* version 1.0 (CPL-1.0). Any use, reproduction or distribution for this
* software constitutes recipient's acceptance of CPL-1.0 terms which can be
* found in the file LICENSE file or at
* https://opensource.org/licenses/cpl1.0.php
*/
/*
* btree.c
* Author: Kent Yoder <yoder1@us.ibm.com>
*
* v1 Binary tree functions 4/5/2011
*
*/
#include <stdio.h>
#include <malloc.h>
#include "pkcs11types.h"
#include "local_types.h"
#include "trace.h"
#define GET_NODE_HANDLE(n) get_node_handle(n, 1)
#define TREE_DUMP(t) tree_dump((t)->top, 0)
/*
* __bt_get_node() - Low level function, needs proper locking before invocation.
*/
static struct btnode *__bt_get_node(struct btree *t, unsigned long node_num)
{
struct btnode *temp;
unsigned long i;
temp = t->top;
if (!node_num || node_num > t->size)
return NULL;
if (node_num == 1) {
temp = t->top;
return (temp->flags & BT_FLAG_FREE) ? NULL : temp;
}
i = node_num;
while (i != 1) {
if (i & 1) {
/* If the bit is 1, traverse right */
temp = temp->right;
} else {
/* If the bit is 0, traverse left */
temp = temp->left;
}
i >>= 1;
}
return (temp->flags & BT_FLAG_FREE) ? NULL : temp;
}
/*
* bt_get_node
*
* Return a node of the tree @t with position @node_num. If the node has been
* freed or doesn't exist, return NULL
*/
struct btnode *bt_get_node(struct btree *t, unsigned long node_num)
{
__transaction_atomic { /* start transaction */
return __bt_get_node(t, node_num);
} /* end transaction */
}
/*
* Get the value of the specified node. Returns NULL if the node has been
* deleted. Increases the value's reference counter to prevent it from being
* freed while in use. The caller needs to call bt_put_node_value() to
* decrease the reference counter when the value is no longer used.
*/
void *bt_get_node_value(struct btree *t, unsigned long node_num)
{
struct btnode *n;
void *v;
__transaction_atomic { /* start transaction */
/*
* Get the value within the transaction block, to ensure that the node
* is not deleted after it was obtained via bt_get_node, but before the
* value is obtained from the node. For a deleted node, the node->value
* points to another node in the free list.
*/
n = __bt_get_node(t, node_num);
v = ((n) ? n->value : NULL);
if (v != NULL)
((struct bt_ref_hdr *)v)->ref++;
} /* end transaction */
if (v != NULL) {
TRACE_DEBUG("bt_get_node_value: Btree: %p Value: %p Ref: %lu\n",
(void *)t, v, ((struct bt_ref_hdr *)v)->ref);
}
return v;
}
/*
* Decrease the node values reference counter.
* If the reference counter reaches zero, then the btree's delete callback
* function is called to delete the value.
* Returns 1 of the value has been deleted, 0 otherwise.
*/
int bt_put_node_value(struct btree *t, void *value)
{
int rc = 0;
unsigned long ref;
int warn = 0;
if (value == NULL)
return 0;
__transaction_atomic { /* start transaction */
if (((struct bt_ref_hdr *)value)->ref > 0) {
ref = --((struct bt_ref_hdr *)value)->ref;
} else {
warn = 1;
ref = 0;
}
} /* end transaction */
if (warn) {
TRACE_WARNING("bt_put_node_value: BTree: %p Value %p Ref already 0.\n",
(void *)t, value);
} else {
TRACE_DEBUG("bt_put_node_value: Btree: %p Value: %p Ref: %lu\n",
(void *)t, value, ref);
}
if (ref == 0 && t->delete_func) {
TRACE_DEBUG("delete_func: Btree: %p Value: %p\n", (void *)t, value);
t->delete_func(value);
rc = 1;
}
return rc;
}
/* create a new node and set @parent_ptr to its location */
static struct btnode *node_create(struct btnode **child_ptr,
struct btnode *parent_ptr, void *value)
{
struct btnode *node = malloc(sizeof(struct btnode));
if (!node)
return NULL;
node->left = node->right = NULL;
node->flags = 0;
node->value = value;
*child_ptr = node;
node->parent = parent_ptr;
return node;
}
/*
* get_node_handle
*
* Recursively construct a node's handle by tracing its path back to the root
* node
*/
static unsigned long get_node_handle(struct btnode *node,
unsigned long handle_so_far)
{
if (!node->parent)
return handle_so_far;
else if (node->parent->left == node)
return get_node_handle(node->parent, handle_so_far << 1);
else
return get_node_handle(node->parent, (handle_so_far << 1) + 1);
}
/*
* Return node number (handle) of newly created node, or 0 for failure.
* Value must start with struct bt_ref_hdr to maintain the reference counter.
* The reference counter is initialized to 1.
*/
unsigned long bt_node_add(struct btree *t, void *value)
{
TRACE_DEBUG("bt_node_add: Btree: %p Value: %p Ref: 1\n", (void *)t, value);
__transaction_atomic { /*start transaction */
struct btnode *temp = t->top;
unsigned long new_node_index;
((struct bt_ref_hdr *)value)->ref = 1;
if (!temp) { /* no root node yet exists, create it */
t->size = 1;
if (!node_create(&t->top, NULL, value)) {
return 0;
}
return 1;
} else if (t->free_list) {
/* there's a node on the free list,
* use it instead of mallocing new
*/
temp = t->free_list;
t->free_list = temp->value;
temp->value = value;
temp->flags &= (~BT_FLAG_FREE);
t->free_nodes--;
new_node_index = GET_NODE_HANDLE(temp);
return new_node_index;
}
new_node_index = t->size + 1;
while (new_node_index != 1) {
if (new_node_index & 1) {
if (!temp->right) {
if (!(node_create(&temp->right, temp, value))) {
return 0;
}
break;
} else {
/* If the bit is 1, traverse right */
temp = temp->right;
}
} else {
if (!temp->left) {
if (!(node_create(&temp->left, temp, value))) {
return 0;
}
break;
} else {
/* If the bit is 0, traverse left */
temp = temp->left;
}
}
new_node_index >>= 1;
}
t->size++;
return t->size;
} /* end transaction */
}
void tree_dump(struct btnode *n, int depth)
{
int i;
if (!n)
return;
for (i = 0; i < depth; i++)
printf(" ");
if (n->flags & BT_FLAG_FREE)
printf("`- (deleted node)\n");
else
printf("`- %p\n", n->value);
tree_dump(n->left, depth + 1);
tree_dump(n->right, depth + 1);
}
/*
* bt_node_free
*
* Move @node_num in tree @t to the free list, decrease the value's reference
* counter, and if the reference counter reaches zero, calls the dbtree's
* delete callback on its value.
* Return the deleted value. Note that if the callback routine frees
* the value, then the returned value might have already been freed. You still
* can use it as indication that it found the node_num in the tree and moved
* it to the free list.
*
* Note that bt_get_node will return NULL if the node is already on the free
* list, so no double freeing can occur
*/
void *bt_node_free(struct btree *t, unsigned long node_num,
int put_value)
{
struct btnode *node;
void *value = NULL;
#ifdef DEBUG
unsigned long int ref;
#endif
__transaction_atomic { /* start transaction */
node = __bt_get_node(t, node_num);
if (node) {
/*
* Need to get the node value within the transaction block,
* otherwise the node might be deleted concurrently before the
* value was obtained from the node.
*/
value = node->value;
node->flags |= BT_FLAG_FREE;
/* add node to the free list,
* which is chained by using
* the value pointer
*/
node->value = t->free_list;
t->free_list = node;
t->free_nodes++;
#ifdef DEBUG
ref = ((struct bt_ref_hdr *)value)->ref;
#endif
}
} /* end transaction */
if (value != NULL) {
TRACE_DEBUG("bt_node_free: Btree: %p Value: %p Ref: %lu\n", (void *)t,
value, ref);
}
if (value && put_value)
bt_put_node_value(t, value);
return value;
}
/* bt_is_empty
*
* return 0 if binary tree has at least 1 node in use, !0 otherwise
*/
int bt_is_empty(struct btree *t)
{
__transaction_atomic { /* start transaction */
return (t->free_nodes == t->size);
} /* end transaction */
}
/* bt_nodes_in_use
*
* return the number of nodes in the binary tree that are not free'd
*/
unsigned long bt_nodes_in_use(struct btree *t)
{
__transaction_atomic { /* start transaction */
return (t->size - t->free_nodes);
} /* end transaction */
}
/* bt_for_each_node
*
* For each non-free'd node in the tree, run @func on it
*
* @func:
* p1 is the node's value
* p2 is the node's handle
* p3 is passed through this function for the caller
*/
void bt_for_each_node(STDLL_TokData_t *tokdata, struct btree *t, void (*func)
(STDLL_TokData_t *tokdata, void *p1, unsigned long p2,
void *p3), void *p3)
{
unsigned int i;
void *value;
for (i = 1; i < t->size + 1; i++) {
/*
* Get the node value, not the node itself. This ensures that we either
* get the value from a valid node, or NULL in case of a deleted node.
* If we would get the node and then get the value from it without
* being in the transaction block, the node could have been deleted after
* the node was obtained, but before the value was obtained.
*/
value = bt_get_node_value(t, i);
if (value) {
(*func) (tokdata, value, i, p3);
bt_put_node_value(t, value);
value = NULL;
}
}
}
/* bt_destroy
*
* Walk a binary tree backwards (largest index to smallest), deleting nodes
* along the way.
* Call the btree's delete callback on node->value before freeing the node.
*/
void bt_destroy(struct btree *t)
{
unsigned long i;
struct btnode *temp;
while (t->size) {
__transaction_atomic { /* start transaction */
temp = t->top;
i = t->size;
while (i != 1) {
if (i & 1) {
/* If the bit is 1, traverse right */
temp = temp->right;
} else {
/* If the bit is 0, traverse left */
temp = temp->left;
}
i >>= 1;
}
} /* end transaction */
/*
* The value pointed by value in a node marked as freed points
* to the next node element in free_list and it shouldn't be
* freed here because the loop will iterate through each node,
* freed or not.
* ATTENTION:
* This might not be 100% thread save when using __transaction_atomic,
* since the node might get deleted concurrently while we are outside
* of the transaction block. It is assumed that bt_destroy is called
* during final cleanup, and thus is not used concurrently with
* bt_node_free() or bt_destroy() in other threads.
*/
if (t->delete_func && !(temp->flags & BT_FLAG_FREE)) {
TRACE_DEBUG("bt_destroy: Btree: %p Value: %p Ref: %lu\n", (void *)t,
temp->value, ((struct bt_ref_hdr *)temp->value)->ref);
t->delete_func(temp->value);
}
__transaction_atomic { /* start transaction */
free(temp);
t->size--;
} /* end transaction */
}
__transaction_atomic { /* start transaction */
/* the tree is gone now, clear all the other variables */
t->top = NULL;
t->free_list = NULL;
t->free_nodes = 0;
t->delete_func = NULL;
} /* end transaction */
}
/* bt_init
*
* Initialize a btree with a delete callback function that is used to delete
* values during bt_node_free() and bt_destroy().
*/
void bt_init(struct btree *t, void (*delete_func)(void *))
{
t->free_list = NULL;
t->top = NULL;
t->size = 0;
t->free_nodes = 0;
t->delete_func = delete_func;
}