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.
25 /**************************************************************************
26 Initialize the tree's root. The cmp_fn is a callback function used
27 for comparision of two children
28 *************************************************************************/
30 static BOOL trim_tree_keypath( char *path, char **base, char **new_path )
34 *new_path = *base = NULL;
41 p = strchr( path, '/' );
52 /**************************************************************************
53 Initialize the tree's root. The cmp_fn is a callback function used
54 for comparision of two children
55 *************************************************************************/
57 SORTED_TREE* pathtree_init( void *data_p,
58 int (cmp_fn)(void*, void*),
59 void (free_fn)(void*) )
61 SORTED_TREE *tree = NULL;
63 if ( !(tree = SMB_MALLOC_P(SORTED_TREE)) )
68 tree->compare = cmp_fn;
69 tree->free_func = free_fn;
71 if ( !(tree->root = SMB_MALLOC_P(TREE_NODE)) ) {
76 ZERO_STRUCTP( tree->root );
77 tree->root->data_p = data_p;
83 /**************************************************************************
84 Delete a tree and free all allocated memory
85 *************************************************************************/
87 static void pathtree_destroy_children( TREE_NODE *root )
94 for ( i=0; i<root->num_children; i++ )
96 pathtree_destroy_children( root->children[i] );
99 SAFE_FREE( root->children );
100 SAFE_FREE( root->key );
105 /**************************************************************************
106 Delete a tree and free all allocated memory
107 *************************************************************************/
109 void pathtree_destroy( SORTED_TREE *tree )
112 pathtree_destroy_children( tree->root );
114 if ( tree->free_func )
115 tree->free_func( tree->root );
120 /**************************************************************************
121 Find the next child given a key string
122 *************************************************************************/
124 static TREE_NODE* pathtree_birth_child( TREE_NODE *node, char* key )
126 TREE_NODE *infant = NULL;
127 TREE_NODE **siblings;
130 if ( !(infant = SMB_MALLOC_P(TREE_NODE)) )
133 ZERO_STRUCTP( infant );
135 infant->key = SMB_STRDUP( key );
136 infant->parent = node;
138 siblings = SMB_REALLOC_ARRAY( node->children, TREE_NODE *, node->num_children+1 );
141 node->children = siblings;
143 node->num_children++;
147 if ( node->num_children == 1 ) {
148 DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
149 node->key ? node->key : "NULL", infant->key ));
150 node->children[0] = infant;
155 * multiple siblings .... (at least 2 children)
157 * work from the end of the list forward
158 * The last child is not set at this point
159 * Insert the new infanct in ascending order
163 for ( i = node->num_children-1; i>=1; i-- )
165 DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
166 infant->key, node->children[i-1]->key));
168 /* the strings should never match assuming that we
169 have called pathtree_find_child() first */
171 if ( StrCaseCmp( infant->key, node->children[i-1]->key ) > 0 ) {
172 DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
174 node->children[i] = infant;
178 /* bump everything towards the end on slot */
180 node->children[i] = node->children[i-1];
183 DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i ));
185 /* if we haven't found the correct slot yet, the child
186 will be first in the list */
189 node->children[0] = infant;
195 /**************************************************************************
196 Find the next child given a key string
197 *************************************************************************/
199 static TREE_NODE* pathtree_find_child( TREE_NODE *node, char* key )
201 TREE_NODE *next = NULL;
205 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
210 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
214 for ( i=0; i<node->num_children; i++ )
216 DEBUG(11,("pathtree_find_child: child key => [%s]\n",
217 node->children[i]->key));
219 result = StrCaseCmp( node->children[i]->key, key );
222 next = node->children[i];
224 /* if result > 0 then we've gone to far because
225 the list of children is sorted by key name
226 If result == 0, then we have a match */
232 DEBUG(11,("pathtree_find_child: %s [%s]\n",
233 next ? "Found" : "Did not find", key ));
238 /**************************************************************************
239 Add a new node into the tree given a key path and a blob of data
240 *************************************************************************/
242 BOOL pathtree_add( SORTED_TREE *tree, const char *path, void *data_p )
244 char *str, *base, *path2;
245 TREE_NODE *current, *next;
248 DEBUG(8,("pathtree_add: Enter\n"));
250 if ( !path || *path != '/' ) {
251 DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
252 path ? path : "NULL" ));
257 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
261 /* move past the first '/' */
264 path2 = SMB_STRDUP( path );
266 DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
272 * this works sort of like a 'mkdir -p' call, possibly
273 * creating an entire path to the new node at once
274 * The path should be of the form /<key1>/<key2>/...
279 current = tree->root;
282 /* break off the remaining part of the path */
284 str = strchr( str, '/' );
288 /* iterate to the next child--birth it if necessary */
290 next = pathtree_find_child( current, base );
292 next = pathtree_birth_child( current, base );
294 DEBUG(0,("pathtree_add: Failed to create new child!\n"));
301 /* setup the next part of the path */
310 } while ( base != NULL );
312 current->data_p = data_p;
314 DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
317 DEBUG(8,("pathtree_add: Exit\n"));
325 /**************************************************************************
326 Recursive routine to print out all children of a TREE_NODE
327 *************************************************************************/
329 static void pathtree_print_children( TREE_NODE *node, int debug, const char *path )
340 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
341 node->data_p ? "data" : "NULL" ));
345 pstrcpy( path2, path );
346 pstrcat( path2, node->key ? node->key : "NULL" );
347 pstrcat( path2, "/" );
349 num_children = node->num_children;
350 for ( i=0; i<num_children; i++ )
351 pathtree_print_children( node->children[i], debug, path2 );
356 /**************************************************************************
357 Dump the kys for a tree to the log file
358 *************************************************************************/
360 void pathtree_print_keys( SORTED_TREE *tree, int debug )
363 int num_children = tree->root->num_children;
365 if ( tree->root->key )
366 DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
367 tree->root->data_p ? "data" : "NULL" ));
369 for ( i=0; i<num_children; i++ ) {
370 pathtree_print_children( tree->root->children[i], debug,
371 tree->root->key ? tree->root->key : "ROOT/" );
376 /**************************************************************************
377 return the data_p for for the node in tree matching the key string
378 The key string is the full path. We must break it apart and walk
380 *************************************************************************/
382 void* pathtree_find( SORTED_TREE *tree, char *key )
384 char *keystr, *base, *str, *p;
388 DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
390 /* sanity checks first */
393 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
398 DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
399 key ? key : "NULL" ));
406 /* make a copy to play with */
409 keystr = SMB_STRDUP( key+1 );
411 keystr = SMB_STRDUP( key );
414 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
418 /* start breaking the path apart */
421 current = tree->root;
423 if ( tree->root->data_p )
424 result = tree->root->data_p;
428 /* break off the remaining part of the path */
430 trim_tree_keypath( p, &base, &str );
432 DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n",
435 /* iterate to the next child */
437 current = pathtree_find_child( current, base );
440 * the idea is that the data_p for a parent should
441 * be inherited by all children, but allow it to be
442 * overridden farther down
445 if ( current && current->data_p )
446 result = current->data_p;
448 /* reset the path pointer 'p' to the remaining part of the key string */
452 } while ( str && current );
454 /* result should be the data_p from the lowest match node in the tree */
456 DEBUG(11,("pathtree_find: Found data_p!\n"));
460 DEBUG(10,("pathtree_find: Exit\n"));