#include "includes.h"
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;
}
SORTED_TREE* sorted_tree_init( void *data_p,
int (cmp_fn)(void*, void*),
void (free_fn)(void*) )
{
SORTED_TREE *tree = NULL;
if ( !(tree = SMB_MALLOC_P(SORTED_TREE)) )
return NULL;
ZERO_STRUCTP( tree );
tree->compare = cmp_fn;
tree->free_func = free_fn;
if ( !(tree->root = SMB_MALLOC_P(TREE_NODE)) ) {
SAFE_FREE( tree );
return NULL;
}
ZERO_STRUCTP( tree->root );
tree->root->data_p = data_p;
return tree;
}
static void sorted_tree_destroy_children( TREE_NODE *root )
{
int i;
if ( !root )
return;
for ( i=0; i<root->num_children; i++ )
{
sorted_tree_destroy_children( root->children[i] );
}
SAFE_FREE( root->children );
SAFE_FREE( root->key );
return;
}
void sorted_tree_destroy( SORTED_TREE *tree )
{
if ( tree->root )
sorted_tree_destroy_children( tree->root );
if ( tree->free_func )
tree->free_func( tree->root );
SAFE_FREE( tree );
}
static TREE_NODE* sorted_tree_birth_child( TREE_NODE *node, char* key )
{
TREE_NODE *infant = NULL;
TREE_NODE **siblings;
int i;
if ( !(infant = SMB_MALLOC_P(TREE_NODE)) )
return NULL;
ZERO_STRUCTP( infant );
infant->key = SMB_STRDUP( key );
infant->parent = node;
siblings = SMB_REALLOC_ARRAY( node->children, TREE_NODE *, node->num_children+1 );
if ( siblings )
node->children = siblings;
node->num_children++;
if ( node->num_children == 1 ) {
DEBUG(11,("sorted_tree_birth_child: First child of node [%s]! [%s]\n",
node->key ? node->key : "NULL", infant->key ));
node->children[0] = infant;
}
else
{
for ( i = node->num_children-1; i>=1; i-- )
{
DEBUG(11,("sorted_tree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
infant->key, node->children[i-1]->key));
if ( StrCaseCmp( infant->key, node->children[i-1]->key ) > 0 ) {
DEBUG(11,("sorted_tree_birth_child: storing infant in i == [%d]\n",
i));
node->children[i] = infant;
break;
}
node->children[i] = node->children[i-1];
}
DEBUG(11,("sorted_tree_birth_child: Exiting loop (i == [%d])\n", i ));
if ( i == 0 )
node->children[0] = infant;
}
return infant;
}
static TREE_NODE* sorted_tree_find_child( TREE_NODE *node, char* key )
{
TREE_NODE *next = NULL;
int i, result;
if ( !node ) {
DEBUG(0,("sorted_tree_find_child: NULL node passed into function!\n"));
return NULL;
}
if ( !key ) {
DEBUG(0,("sorted_tree_find_child: NULL key string passed into function!\n"));
return NULL;
}
for ( i=0; i<node->num_children; i++ )
{
DEBUG(11,("sorted_tree_find_child: child key => [%s]\n",
node->children[i]->key));
result = StrCaseCmp( node->children[i]->key, key );
if ( result == 0 )
next = node->children[i];
if ( result > 0 )
break;
}
DEBUG(11,("sorted_tree_find_child: %s [%s]\n",
next ? "Found" : "Did not find", key ));
return next;
}
BOOL sorted_tree_add( SORTED_TREE *tree, const char *path, void *data_p )
{
char *str, *base, *path2;
TREE_NODE *current, *next;
BOOL ret = True;
DEBUG(8,("sorted_tree_add: Enter\n"));
if ( !path || *path != '/' ) {
DEBUG(0,("sorted_tree_add: Attempt to add a node with a bad path [%s]\n",
path ? path : "NULL" ));
return False;
}
if ( !tree ) {
DEBUG(0,("sorted_tree_add: Attempt to add a node to an uninitialized tree!\n"));
return False;
}
path++;
path2 = SMB_STRDUP( path );
if ( !path2 ) {
DEBUG(0,("sorted_tree_add: strdup() failed on string [%s]!?!?!\n", path));
return False;
}
base = path2;
str = path2;
current = tree->root;
do {
str = strchr( str, '/' );
if ( str )
*str = '\0';
next = sorted_tree_find_child( current, base );
if ( !next ) {
next = sorted_tree_birth_child( current, base );
if ( !next ) {
DEBUG(0,("sorted_tree_add: Failed to create new child!\n"));
ret = False;
goto done;
}
}
current = next;
base = str;
if ( base ) {
*base = '/';
base++;
str = base;
}
} while ( base != NULL );
current->data_p = data_p;
DEBUG(10,("sorted_tree_add: Successfully added node [%s] to tree\n",
path ));
DEBUG(8,("sorted_tree_add: Exit\n"));
done:
SAFE_FREE( path2 );
return ret;
}
static void sorted_tree_print_children( TREE_NODE *node, int debug, const char *path )
{
int i;
int num_children;
pstring path2;
if ( !node )
return;
if ( node->key )
DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
node->data_p ? "data" : "NULL" ));
*path2 = '\0';
if ( path )
pstrcpy( path2, path );
pstrcat( path2, node->key ? node->key : "NULL" );
pstrcat( path2, "/" );
num_children = node->num_children;
for ( i=0; i<num_children; i++ )
sorted_tree_print_children( node->children[i], debug, path2 );
}
void sorted_tree_print_keys( 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++ ) {
sorted_tree_print_children( tree->root->children[i], debug,
tree->root->key ? tree->root->key : "ROOT/" );
}
}
void* sorted_tree_find( SORTED_TREE *tree, char *key )
{
char *keystr, *base, *str, *p;
TREE_NODE *current;
void *result = NULL;
DEBUG(10,("sorted_tree_find: Enter [%s]\n", key ? key : "NULL" ));
if ( !key ) {
DEBUG(0,("sorted_tree_find: Attempt to search tree using NULL search string!\n"));
return NULL;
}
if ( !tree ) {
DEBUG(0,("sorted_tree_find: Attempt to search an uninitialized tree using string [%s]!\n",
key ? key : "NULL" ));
return NULL;
}
if ( !tree->root )
return NULL;
if ( *key == '/' )
keystr = SMB_STRDUP( key+1 );
else
keystr = SMB_STRDUP( key );
if ( !keystr ) {
DEBUG(0,("sorted_tree_find: strdup() failed on string [%s]!?!?!\n", key));
return NULL;
}
p = keystr;
current = tree->root;
if ( tree->root->data_p )
result = tree->root->data_p;
do
{
trim_tree_keypath( p, &base, &str );
DEBUG(11,("sorted_tree_find: [loop] base => [%s], new_path => [%s]\n",
base, str));
current = sorted_tree_find_child( current, base );
if ( current && current->data_p )
result = current->data_p;
p = str;
} while ( str && current );
if ( result )
DEBUG(11,("sorted_tree_find: Found data_p!\n"));
SAFE_FREE( keystr );
DEBUG(10,("sorted_tree_find: Exit\n"));
return result;
}