From 06ae9ac5d98a752d8ca17686a4a3b1786fbe520d Mon Sep 17 00:00:00 2001 From: Gerald Carter Date: Thu, 18 Jul 2002 23:00:24 +0000 Subject: virtual registry framework with initial printing hooks. (This used to be commit a43d9788fa8823d678ee72470421b980165ec2b0) --- source3/lib/adt_tree.c | 414 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 414 insertions(+) create mode 100644 source3/lib/adt_tree.c (limited to 'source3/lib') diff --git a/source3/lib/adt_tree.c b/source3/lib/adt_tree.c new file mode 100644 index 0000000000..e3519c6c41 --- /dev/null +++ b/source3/lib/adt_tree.c @@ -0,0 +1,414 @@ +/* + * 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 + *************************************************************************/ + +SORTED_TREE* sorted_tree_init( 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 ); + + 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; inum_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 *child, *crib; + TREE_NODE **siblings; + int i, result; + + 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-- ) + { + crib = node->children[i]; + child = node->children[i-1]; + + DEBUG(10,("sorted_tree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n", + infant->key, child->key)); + + /* the strings should never match assuming that we + have called sorted_tree_find_child() first */ + + result = StrCaseCmp( infant->key, child->key ); + if ( result > 0 ) { + crib = infant; + break; + } + + crib = child; + } + } + + 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++ ) + { + result = StrCaseCmp( key, node->children[i]->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: Did %s find [%s]\n", + next ? "" : "not", 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 ///... + */ + + 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; ichildren[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; iroot->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; + 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 */ + + keystr = strdup( key ); + if ( !keystr ) { + DEBUG(0,("sorted_tree_find: strdup() failed on string [%s]!?!?!\n", key)); + return NULL; + } + + /* start breaking the path apart */ + + base = keystr; + str = keystr; + current = tree->root; + + do + { + /* break off the remaining part of the path */ + + str = strchr( str, '/' ); + if ( str ) + *str = '\0'; + + DEBUG(10,("sorted_tree_find: [loop] key => [%s]\n", base)); + + /* iterate to the next child */ + + current = sorted_tree_find_child( current, base ); + + /* setup the next part of the path */ + + base = str; + if ( base ) { + *base = '/'; + base++; + str = base; + } + + } while ( base && current ); + + if ( current ) + result = current->data_p; + + SAFE_FREE( keystr ); + + DEBUG(10,("sorted_tree_find: Exit\n")); + + return result; +} + + -- cgit