2 * Unix SMB/CIFS implementation.
3 * Generic Abstract Data Types
4 * Copyright (C) Gerald Carter 2002.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 /**************************************************************************
25 Initialize the tree's root. The cmp_fn is a callback function used
26 for comparision of two children
27 *************************************************************************/
29 static BOOL trim_tree_keypath( char *path, char **base, char **new_path )
33 *new_path = *base = NULL;
40 p = strchr( path, '/' );
51 /**************************************************************************
52 Initialize the tree's root. The cmp_fn is a callback function used
53 for comparision of two children
54 *************************************************************************/
56 SORTED_TREE* sorted_tree_init( void *data_p,
57 int (cmp_fn)(void*, void*),
58 void (free_fn)(void*) )
60 SORTED_TREE *tree = NULL;
62 if ( !(tree = (SORTED_TREE*)malloc( sizeof(SORTED_TREE) )) )
67 tree->compare = cmp_fn;
68 tree->free_func = free_fn;
70 if ( !(tree->root = (TREE_NODE*)malloc( sizeof(TREE_NODE) )) ) {
75 ZERO_STRUCTP( tree->root );
76 tree->root->data_p = data_p;
82 /**************************************************************************
83 Delete a tree and free all allocated memory
84 *************************************************************************/
86 static void sorted_tree_destroy_children( TREE_NODE *root )
93 for ( i=0; i<root->num_children; i++ )
95 sorted_tree_destroy_children( root->children[i] );
98 SAFE_FREE( root->children );
99 SAFE_FREE( root->key );
104 /**************************************************************************
105 Delete a tree and free all allocated memory
106 *************************************************************************/
108 void sorted_tree_destroy( SORTED_TREE *tree )
111 sorted_tree_destroy_children( tree->root );
113 if ( tree->free_func )
114 tree->free_func( tree->root );
119 /**************************************************************************
120 Find the next child given a key string
121 *************************************************************************/
123 static TREE_NODE* sorted_tree_birth_child( TREE_NODE *node, char* key )
125 TREE_NODE *infant = NULL;
126 TREE_NODE **siblings;
129 if ( !(infant = (TREE_NODE*)malloc( sizeof(TREE_NODE) )) )
132 ZERO_STRUCTP( infant );
134 infant->key = strdup( key );
135 infant->parent = node;
137 siblings = Realloc( node->children, sizeof(TREE_NODE*)*(node->num_children+1) );
140 node->children = siblings;
142 node->num_children++;
146 if ( node->num_children == 1 ) {
147 DEBUG(11,("sorted_tree_birth_child: First child of node [%s]! [%s]\n",
148 node->key ? node->key : "NULL", infant->key ));
149 node->children[0] = infant;
154 * multiple siblings .... (at least 2 children)
156 * work from the end of the list forward
157 * The last child is not set at this point
158 * Insert the new infanct in ascending order
162 for ( i = node->num_children-1; i>=1; i-- )
164 DEBUG(11,("sorted_tree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
165 infant->key, node->children[i-1]->key));
167 /* the strings should never match assuming that we
168 have called sorted_tree_find_child() first */
170 if ( StrCaseCmp( infant->key, node->children[i-1]->key ) > 0 ) {
171 DEBUG(11,("sorted_tree_birth_child: storing infant in i == [%d]\n",
173 node->children[i] = infant;
177 /* bump everything towards the end on slot */
179 node->children[i] = node->children[i-1];
182 DEBUG(11,("sorted_tree_birth_child: Exiting loop (i == [%d])\n", i ));
184 /* if we haven't found the correct slot yet, the child
185 will be first in the list */
188 node->children[0] = infant;
194 /**************************************************************************
195 Find the next child given a key string
196 *************************************************************************/
198 static TREE_NODE* sorted_tree_find_child( TREE_NODE *node, char* key )
200 TREE_NODE *next = NULL;
204 DEBUG(0,("sorted_tree_find_child: NULL node passed into function!\n"));
209 DEBUG(0,("sorted_tree_find_child: NULL key string passed into function!\n"));
213 for ( i=0; i<node->num_children; i++ )
215 DEBUG(11,("sorted_tree_find_child: child key => [%s]\n",
216 node->children[i]->key));
218 result = StrCaseCmp( node->children[i]->key, key );
221 next = node->children[i];
223 /* if result > 0 then we've gone to far because
224 the list of children is sorted by key name
225 If result == 0, then we have a match */
231 DEBUG(11,("sorted_tree_find_child: %s [%s]\n",
232 next ? "Found" : "Did not find", key ));
237 /**************************************************************************
238 Add a new node into the tree given a key path and a blob of data
239 *************************************************************************/
241 BOOL sorted_tree_add( SORTED_TREE *tree, const char *path, void *data_p )
243 char *str, *base, *path2;
244 TREE_NODE *current, *next;
247 DEBUG(8,("sorted_tree_add: Enter\n"));
249 if ( !path || *path != '/' ) {
250 DEBUG(0,("sorted_tree_add: Attempt to add a node with a bad path [%s]\n",
251 path ? path : "NULL" ));
256 DEBUG(0,("sorted_tree_add: Attempt to add a node to an uninitialized tree!\n"));
260 /* move past the first '/' */
263 path2 = strdup( path );
265 DEBUG(0,("sorted_tree_add: strdup() failed on string [%s]!?!?!\n", path));
271 * this works sort of like a 'mkdir -p' call, possibly
272 * creating an entire path to the new node at once
273 * The path should be of the form /<key1>/<key2>/...
278 current = tree->root;
281 /* break off the remaining part of the path */
283 str = strchr( str, '/' );
287 /* iterate to the next child--birth it if necessary */
289 next = sorted_tree_find_child( current, base );
291 next = sorted_tree_birth_child( current, base );
293 DEBUG(0,("sorted_tree_add: Failed to create new child!\n"));
300 /* setup the next part of the path */
309 } while ( base != NULL );
311 current->data_p = data_p;
313 DEBUG(10,("sorted_tree_add: Successfully added node [%s] to tree\n",
316 DEBUG(8,("sorted_tree_add: Exit\n"));
324 /**************************************************************************
325 Recursive routine to print out all children of a TREE_NODE
326 *************************************************************************/
328 static void sorted_tree_print_children( TREE_NODE *node, int debug, const char *path )
339 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
340 node->data_p ? "data" : "NULL" ));
344 pstrcpy( path2, path );
345 pstrcat( path2, node->key ? node->key : "NULL" );
346 pstrcat( path2, "/" );
348 num_children = node->num_children;
349 for ( i=0; i<num_children; i++ )
350 sorted_tree_print_children( node->children[i], debug, path2 );
355 /**************************************************************************
356 Dump the kys for a tree to the log file
357 *************************************************************************/
359 void sorted_tree_print_keys( SORTED_TREE *tree, int debug )
362 int num_children = tree->root->num_children;
364 if ( tree->root->key )
365 DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
366 tree->root->data_p ? "data" : "NULL" ));
368 for ( i=0; i<num_children; i++ ) {
369 sorted_tree_print_children( tree->root->children[i], debug,
370 tree->root->key ? tree->root->key : "ROOT/" );
375 /**************************************************************************
376 return the data_p for for the node in tree matching the key string
377 The key string is the full path. We must break it apart and walk
379 *************************************************************************/
381 void* sorted_tree_find( SORTED_TREE *tree, char *key )
383 char *keystr, *base, *str, *p;
387 DEBUG(10,("sorted_tree_find: Enter [%s]\n", key ? key : "NULL" ));
389 /* sanity checks first */
392 DEBUG(0,("sorted_tree_find: Attempt to search tree using NULL search string!\n"));
397 DEBUG(0,("sorted_tree_find: Attempt to search an uninitialized tree using string [%s]!\n",
398 key ? key : "NULL" ));
405 /* make a copy to play with */
408 keystr = strdup( key+1 );
410 keystr = strdup( key );
413 DEBUG(0,("sorted_tree_find: strdup() failed on string [%s]!?!?!\n", key));
417 /* start breaking the path apart */
420 current = tree->root;
422 if ( tree->root->data_p )
423 result = tree->root->data_p;
427 /* break off the remaining part of the path */
429 trim_tree_keypath( p, &base, &str );
431 DEBUG(11,("sorted_tree_find: [loop] base => [%s], new_path => [%s]\n",
434 /* iterate to the next child */
436 current = sorted_tree_find_child( current, base );
439 * the idea is that the data_p for a parent should
440 * be inherited by all children, but allow it to be
441 * overridden farther down
444 if ( current && current->data_p )
445 result = current->data_p;
447 /* reset the path pointer 'p' to the remaining part of the key string */
451 } while ( str && current );
453 /* result should be the data_p from the lowest match node in the tree */
455 DEBUG(11,("sorted_tree_find: Found data_p!\n"));
459 DEBUG(10,("sorted_tree_find: Exit\n"));