diff options
Diffstat (limited to 'source3/lib/adt_tree.c')
| -rw-r--r-- | source3/lib/adt_tree.c | 464 |
1 files changed, 464 insertions, 0 deletions
diff --git a/source3/lib/adt_tree.c b/source3/lib/adt_tree.c new file mode 100644 index 0000000000..2c18bb1198 --- /dev/null +++ b/source3/lib/adt_tree.c @@ -0,0 +1,464 @@ +/* + * 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 2 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, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +#include "includes.h" + + +/************************************************************************** + Initialize the tree's root. The cmp_fn is a callback function used + for comparision of two children + *************************************************************************/ + +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. The cmp_fn is a callback function used + for comparision of two children + *************************************************************************/ + +SORTED_TREE* sorted_tree_init( void *data_p, + int (cmp_fn)(void*, void*), + void (free_fn)(void*) ) +{ + SORTED_TREE *tree = NULL; + + if ( !(tree = (SORTED_TREE*)malloc( sizeof(SORTED_TREE) )) ) + return NULL; + + ZERO_STRUCTP( tree ); + + tree->compare = cmp_fn; + tree->free = free_fn; + + if ( !(tree->root = (TREE_NODE*)malloc( sizeof(TREE_NODE) )) ) { + SAFE_FREE( tree ); + return NULL; + } + + ZERO_STRUCTP( tree->root ); + tree->root->data_p = data_p; + + return tree; +} + + +/************************************************************************** + Delete a tree and free all allocated memory + *************************************************************************/ + +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; +} + +/************************************************************************** + Delete a tree and free all allocated memory + *************************************************************************/ + +void sorted_tree_destroy( SORTED_TREE *tree ) +{ + if ( tree->root ) + sorted_tree_destroy_children( tree->root ); + + if ( tree->free ) + tree->free( tree->root ); + + SAFE_FREE( tree ); +} + +/************************************************************************** + Find the next child given a key string + *************************************************************************/ + +static TREE_NODE* sorted_tree_birth_child( TREE_NODE *node, char* key ) +{ + TREE_NODE *infant = NULL; + TREE_NODE **siblings; + int i; + + if ( !(infant = (TREE_NODE*)malloc( sizeof(TREE_NODE) )) ) + return NULL; + + ZERO_STRUCTP( infant ); + + infant->key = strdup( key ); + infant->parent = node; + + siblings = Realloc( node->children, sizeof(TREE_NODE*)*(node->num_children+1) ); + + if ( siblings ) + node->children = siblings; + + node->num_children++; + + /* first child */ + + 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 + { + /* + * 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,("sorted_tree_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 sorted_tree_find_child() first */ + + 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; + } + + /* bump everything towards the end on slot */ + + node->children[i] = node->children[i-1]; + } + + DEBUG(11,("sorted_tree_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 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 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,("sorted_tree_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 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; + } + + /* move past the first '/' */ + + path++; + path2 = strdup( path ); + if ( !path2 ) { + DEBUG(0,("sorted_tree_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 = 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; + + /* 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,("sorted_tree_add: Successfully added node [%s] to tree\n", + path )); + + DEBUG(8,("sorted_tree_add: Exit\n")); + +done: + SAFE_FREE( path2 ); + return ret; +} + + +/************************************************************************** + Recursive routine to print out all children of a TREE_NODE + *************************************************************************/ + +static void sorted_tree_print_children( TREE_NODE *node, int debug, 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 ); + + +} + +/************************************************************************** + Dump the kys for a tree to the log file + *************************************************************************/ + +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/" ); + } + +} + +/************************************************************************** + 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* 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" )); + + /* sanity checks first */ + + 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; + + /* make a copy to play with */ + + if ( *key == '/' ) + keystr = strdup( key+1 ); + else + keystr = strdup( key ); + + if ( !keystr ) { + DEBUG(0,("sorted_tree_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,("sorted_tree_find: [loop] base => [%s], new_path => [%s]\n", + base, str)); + + /* iterate to the next child */ + + current = sorted_tree_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,("sorted_tree_find: Found data_p!\n")); + + SAFE_FREE( keystr ); + + DEBUG(10,("sorted_tree_find: Exit\n")); + + return result; +} + + |