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 *************************************************************************/
28 static BOOL
trim_tree_keypath( char *path
, char **base
, char **new_path
)
32 *new_path
= *base
= NULL
;
39 p
= strchr( path
, '/' );
50 /**************************************************************************
51 Initialize the tree's root. The cmp_fn is a callback function used
52 for comparision of two children
53 *************************************************************************/
55 SORTED_TREE
* pathtree_init( void *data_p
, int (cmp_fn
)(void*, void*) )
57 SORTED_TREE
*tree
= NULL
;
59 if ( !(tree
= TALLOC_ZERO_P(NULL
, SORTED_TREE
)) )
62 tree
->compare
= cmp_fn
;
64 if ( !(tree
->root
= TALLOC_ZERO_P(tree
, TREE_NODE
)) ) {
69 tree
->root
->data_p
= data_p
;
75 /**************************************************************************
76 Find the next child given a key string
77 *************************************************************************/
79 static TREE_NODE
* pathtree_birth_child( TREE_NODE
*node
, char* key
)
81 TREE_NODE
*infant
= NULL
;
85 if ( !(infant
= TALLOC_ZERO_P( node
, TREE_NODE
)) )
88 infant
->key
= talloc_strdup( infant
, key
);
89 infant
->parent
= node
;
91 siblings
= TALLOC_REALLOC_ARRAY( node
, node
->children
, TREE_NODE
*, node
->num_children
+1 );
94 node
->children
= siblings
;
100 if ( node
->num_children
== 1 ) {
101 DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
102 node
->key
? node
->key
: "NULL", infant
->key
));
103 node
->children
[0] = infant
;
108 * multiple siblings .... (at least 2 children)
110 * work from the end of the list forward
111 * The last child is not set at this point
112 * Insert the new infanct in ascending order
116 for ( i
= node
->num_children
-1; i
>=1; i
-- )
118 DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
119 infant
->key
, node
->children
[i
-1]->key
));
121 /* the strings should never match assuming that we
122 have called pathtree_find_child() first */
124 if ( StrCaseCmp( infant
->key
, node
->children
[i
-1]->key
) > 0 ) {
125 DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
127 node
->children
[i
] = infant
;
131 /* bump everything towards the end on slot */
133 node
->children
[i
] = node
->children
[i
-1];
136 DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i
));
138 /* if we haven't found the correct slot yet, the child
139 will be first in the list */
142 node
->children
[0] = infant
;
148 /**************************************************************************
149 Find the next child given a key string
150 *************************************************************************/
152 static TREE_NODE
* pathtree_find_child( TREE_NODE
*node
, char* key
)
154 TREE_NODE
*next
= NULL
;
158 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
163 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
167 for ( i
=0; i
<node
->num_children
; i
++ )
169 DEBUG(11,("pathtree_find_child: child key => [%s]\n",
170 node
->children
[i
]->key
));
172 result
= StrCaseCmp( node
->children
[i
]->key
, key
);
175 next
= node
->children
[i
];
177 /* if result > 0 then we've gone to far because
178 the list of children is sorted by key name
179 If result == 0, then we have a match */
185 DEBUG(11,("pathtree_find_child: %s [%s]\n",
186 next
? "Found" : "Did not find", key
));
191 /**************************************************************************
192 Add a new node into the tree given a key path and a blob of data
193 *************************************************************************/
195 BOOL
pathtree_add( SORTED_TREE
*tree
, const char *path
, void *data_p
)
197 char *str
, *base
, *path2
;
198 TREE_NODE
*current
, *next
;
201 DEBUG(8,("pathtree_add: Enter\n"));
203 if ( !path
|| *path
!= '/' ) {
204 DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
205 path
? path
: "NULL" ));
210 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
214 /* move past the first '/' */
217 path2
= SMB_STRDUP( path
);
219 DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path
));
225 * this works sort of like a 'mkdir -p' call, possibly
226 * creating an entire path to the new node at once
227 * The path should be of the form /<key1>/<key2>/...
232 current
= tree
->root
;
235 /* break off the remaining part of the path */
237 str
= strchr( str
, '/' );
241 /* iterate to the next child--birth it if necessary */
243 next
= pathtree_find_child( current
, base
);
245 next
= pathtree_birth_child( current
, base
);
247 DEBUG(0,("pathtree_add: Failed to create new child!\n"));
254 /* setup the next part of the path */
263 } while ( base
!= NULL
);
265 current
->data_p
= data_p
;
267 DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
270 DEBUG(8,("pathtree_add: Exit\n"));
278 /**************************************************************************
279 Recursive routine to print out all children of a TREE_NODE
280 *************************************************************************/
282 static void pathtree_print_children( TREE_NODE
*node
, int debug
, const char *path
)
293 DEBUG(debug
,("%s: [%s] (%s)\n", path
? path
: "NULL", node
->key
,
294 node
->data_p
? "data" : "NULL" ));
298 pstrcpy( path2
, path
);
299 pstrcat( path2
, node
->key
? node
->key
: "NULL" );
300 pstrcat( path2
, "/" );
302 num_children
= node
->num_children
;
303 for ( i
=0; i
<num_children
; i
++ )
304 pathtree_print_children( node
->children
[i
], debug
, path2
);
309 /**************************************************************************
310 Dump the kys for a tree to the log file
311 *************************************************************************/
313 void pathtree_print_keys( SORTED_TREE
*tree
, int debug
)
316 int num_children
= tree
->root
->num_children
;
318 if ( tree
->root
->key
)
319 DEBUG(debug
,("ROOT/: [%s] (%s)\n", tree
->root
->key
,
320 tree
->root
->data_p
? "data" : "NULL" ));
322 for ( i
=0; i
<num_children
; i
++ ) {
323 pathtree_print_children( tree
->root
->children
[i
], debug
,
324 tree
->root
->key
? tree
->root
->key
: "ROOT/" );
329 /**************************************************************************
330 return the data_p for for the node in tree matching the key string
331 The key string is the full path. We must break it apart and walk
333 *************************************************************************/
335 void* pathtree_find( SORTED_TREE
*tree
, char *key
)
337 char *keystr
, *base
, *str
, *p
;
341 DEBUG(10,("pathtree_find: Enter [%s]\n", key
? key
: "NULL" ));
343 /* sanity checks first */
346 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
351 DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
352 key
? key
: "NULL" ));
359 /* make a copy to play with */
362 keystr
= SMB_STRDUP( key
+1 );
364 keystr
= SMB_STRDUP( key
);
367 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key
));
371 /* start breaking the path apart */
374 current
= tree
->root
;
376 if ( tree
->root
->data_p
)
377 result
= tree
->root
->data_p
;
381 /* break off the remaining part of the path */
383 trim_tree_keypath( p
, &base
, &str
);
385 DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n",
388 /* iterate to the next child */
390 current
= pathtree_find_child( current
, base
);
393 * the idea is that the data_p for a parent should
394 * be inherited by all children, but allow it to be
395 * overridden farther down
398 if ( current
&& current
->data_p
)
399 result
= current
->data_p
;
401 /* reset the path pointer 'p' to the remaining part of the key string */
405 } while ( str
&& current
);
407 /* result should be the data_p from the lowest match node in the tree */
409 DEBUG(11,("pathtree_find: Found data_p!\n"));
413 DEBUG(10,("pathtree_find: Exit\n"));