adt_tree.c

/*
 *  Unix SMB/CIFS implementation.
 *  Generic Abstract Data Types
 *  Copyright (C) Gerald Carter                     2002.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, see <http://www.gnu.org/licenses/>.
 */

#include "replace.h"
#include <talloc.h>
#include "lib/util/debug.h"
#include "lib/util/samba_util.h"
#include "util/charset/charset.h"
#include "source3/include/smb_macros.h"
#include "adt_tree.h"

struct tree_node {
	struct tree_node	*parent;
	struct tree_node	**children;
	int 			num_children;
	char			*key;
	void			*data_p;
};

struct sorted_tree {
	struct tree_node *root;
};

/**************************************************************************
 *************************************************************************/

static bool trim_tree_keypath( char *path, char **base, char **new_path )
{
	char *p;

	*new_path = *base = NULL;

	if ( !path )
		return false;

	*base = path;

	p = strchr( path, '\\' );

	if ( p ) {
		*p = '\0';
		*new_path = p+1;
	}

	return true;
}

/**************************************************************************
 Initialize the tree's root.
 *************************************************************************/

struct sorted_tree *pathtree_init(void *data_p)
{
	struct sorted_tree *tree = NULL;

	tree = talloc_zero(NULL, struct sorted_tree);
	if (tree == NULL) {
		return NULL;
	}

	tree->root = talloc_zero(tree, struct tree_node);
	if (tree->root == NULL) {
		TALLOC_FREE( tree );
		return NULL;
	}

	tree->root->data_p = data_p;

	return tree;
}


/**************************************************************************
 Find the next child given a key string
 *************************************************************************/

static struct tree_node *pathtree_birth_child(struct tree_node *node,
					      char* key )
{
	struct tree_node *infant = NULL;
	struct tree_node **siblings;
	int i;

	infant = talloc_zero(node, struct tree_node);
	if (infant == NULL) {
		return NULL;
	}

	infant->key = talloc_strdup( infant, key );
	infant->parent = node;

	siblings = talloc_realloc(node, node->children, struct tree_node *,
				  node->num_children+1);

	if ( siblings )
		node->children = siblings;

	node->num_children++;

	/* first child */

	if ( node->num_children == 1 ) {
		DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
			node->key ? node->key : "NULL", infant->key ));
		node->children[0] = infant;
	}
	else
	{
		/*
		 * multiple siblings .... (at least 2 children)
		 *
		 * work from the end of the list forward
		 * The last child is not set at this point
		 * Insert the new infanct in ascending order
		 * from left to right
		 */

		for ( i = node->num_children-1; i>=1; i-- )
		{
			DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
				infant->key, node->children[i-1]->key));

			/* the strings should never match assuming that we
			   have called pathtree_find_child() first */

			if ( strcasecmp_m( infant->key, node->children[i-1]->key ) > 0 ) {
				DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
					i));
				node->children[i] = infant;
				break;
			}

			/* bump everything towards the end on slot */

			node->children[i] = node->children[i-1];
		}

		DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i ));

		/* if we haven't found the correct slot yet, the child
		   will be first in the list */

		if ( i == 0 )
			node->children[0] = infant;
	}

	return infant;
}

/**************************************************************************
 Find the next child given a key string
 *************************************************************************/

static struct tree_node *pathtree_find_child(struct tree_node *node,
					     char *key )
{
	struct tree_node *next = NULL;
	int i, result;

	if ( !node ) {
		DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
		return NULL;
	}

	if ( !key ) {
		DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
		return NULL;
	}

	for ( i=0; i<node->num_children; i++ )
	{
		DEBUG(11,("pathtree_find_child: child key => [%s]\n",
			node->children[i]->key));

		result = strcasecmp_m( node->children[i]->key, key );

		if ( result == 0 )
			next = node->children[i];

		/* if result > 0 then we've gone to far because
		   the list of children is sorted by key name
		   If result == 0, then we have a match         */

		if ( result > 0 )
			break;
	}

	DEBUG(11,("pathtree_find_child: %s [%s]\n",
		next ? "Found" : "Did not find", key ));

	return next;
}

/**************************************************************************
 Add a new node into the tree given a key path and a blob of data
 *************************************************************************/

bool pathtree_add(struct sorted_tree *tree, const char *path, void *data_p)
{
	char *str, *base, *path2;
	struct tree_node *current, *next;
	bool ret = true;

	DEBUG(8,("pathtree_add: Enter\n"));

	if ( !path || *path != '\\' ) {
		DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
			path ? path : "NULL" ));
		return false;
	}

	if ( !tree ) {
		DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
		return false;
	}

	/* move past the first '\\' */

	path++;
	path2 = SMB_STRDUP( path );
	if ( !path2 ) {
		DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
		return false;
	}


	/*
	 * this works sort of like a 'mkdir -p'	call, possibly
	 * creating an entire path to the new node at once
	 * The path should be of the form /<key1>/<key2>/...
	 */

	base = path2;
	str  = path2;
	current = tree->root;

	do {
		/* break off the remaining part of the path */

		str = strchr( str, '\\' );
		if ( str )
			*str = '\0';

		/* iterate to the next child--birth it if necessary */

		next = pathtree_find_child( current, base );
		if ( !next ) {
			next = pathtree_birth_child( current, base );
			if ( !next ) {
				DEBUG(0,("pathtree_add: Failed to create new child!\n"));
				ret = false;
				goto done;
			}
		}
		current = next;

		/* setup the next part of the path */

		base = str;
		if ( base ) {
			*base = '\\';
			base++;
			str = base;
		}

	} while ( base != NULL );

	current->data_p = data_p;

	DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
		path ));

	DEBUG(8,("pathtree_add: Exit\n"));

done:
	SAFE_FREE( path2 );
	return ret;
}


/**************************************************************************
 Recursive routine to print out all children of a struct tree_node
 *************************************************************************/

static void pathtree_print_children(TALLOC_CTX *ctx,
				struct tree_node *node,
				int debug,
				const char *path )
{
	int i;
	int num_children;
	char *path2 = NULL;

	if ( !node )
		return;

	if ( node->key )
		DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
			node->data_p ? "data" : "NULL" ));

	if ( path ) {
		path2 = talloc_strdup(ctx, path);
		if (!path2) {
			return;
		}
	}

	path2 = talloc_asprintf(ctx,
			"%s%s/",
			path ? path : "",
			node->key ? node->key : "NULL");
	if (!path2) {
		return;
	}

	num_children = node->num_children;
	for ( i=0; i<num_children; i++ ) {
		pathtree_print_children(ctx, node->children[i], debug, path2 );
	}
}

/**************************************************************************
 Dump the kys for a tree to the log file
 *************************************************************************/

void pathtree_print_keys(struct sorted_tree *tree, int debug )
{
	int i;
	int num_children = tree->root->num_children;

	if ( tree->root->key )
		DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
			tree->root->data_p ? "data" : "NULL" ));

	for ( i=0; i<num_children; i++ ) {
		TALLOC_CTX *ctx = talloc_stackframe();
		pathtree_print_children(ctx, tree->root->children[i], debug,
			tree->root->key ? tree->root->key : "ROOT/" );
		TALLOC_FREE(ctx);
	}

}

/**************************************************************************
 return the data_p for for the node in tree matching the key string
 The key string is the full path.  We must break it apart and walk
 the tree
 *************************************************************************/

void* pathtree_find(struct sorted_tree *tree, char *key )
{
	char *keystr, *base = NULL, *str = NULL, *p;
	struct tree_node *current;
	void *result = NULL;

	DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));

	/* sanity checks first */

	if ( !key ) {
		DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
		return NULL;
	}

	if ( !tree ) {
		DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
			key ? key : "NULL" ));
		return NULL;
	}

	if ( !tree->root )
		return NULL;

	/* make a copy to play with */

	if ( *key == '\\' )
		keystr = SMB_STRDUP( key+1 );
	else
		keystr = SMB_STRDUP( key );

	if ( !keystr ) {
		DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
		return NULL;
	}

	/* start breaking the path apart */

	p = keystr;
	current = tree->root;

	if ( tree->root->data_p )
		result = tree->root->data_p;

	do
	{
		/* break off the remaining part of the path */

		trim_tree_keypath( p, &base, &str );

		DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n",
			base ? base : "",
			str ? str : ""));

		/* iterate to the next child */

		current = pathtree_find_child( current, base );

		/*
		 * the idea is that the data_p for a parent should
		 * be inherited by all children, but allow it to be
		 * overridden farther down
		 */

		if ( current && current->data_p )
			result = current->data_p;

		/* reset the path pointer 'p' to the remaining part of the key string */

		p = str;

	} while ( str && current );

	/* result should be the data_p from the lowest match node in the tree */
	if ( result )
		DEBUG(11,("pathtree_find: Found data_p!\n"));

	SAFE_FREE( keystr );

	DEBUG(10,("pathtree_find: Exit\n"));

	return result;
}