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 3 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, see <http://www.gnu.org/licenses/>.
24 struct tree_node
*parent
;
25 struct tree_node
**children
;
32 struct tree_node
*root
;
35 /**************************************************************************
36 *************************************************************************/
38 static bool trim_tree_keypath( char *path
, char **base
, char **new_path
)
42 *new_path
= *base
= NULL
;
49 p
= strchr( path
, '\\' );
59 /**************************************************************************
60 Initialize the tree's root.
61 *************************************************************************/
63 struct sorted_tree
*pathtree_init(void *data_p
)
65 struct sorted_tree
*tree
= NULL
;
67 tree
= talloc_zero(NULL
, struct sorted_tree
);
72 tree
->root
= talloc_zero(tree
, struct tree_node
);
73 if (tree
->root
== NULL
) {
78 tree
->root
->data_p
= data_p
;
84 /**************************************************************************
85 Find the next child given a key string
86 *************************************************************************/
88 static struct tree_node
*pathtree_birth_child(struct tree_node
*node
,
91 struct tree_node
*infant
= NULL
;
92 struct tree_node
**siblings
;
95 infant
= talloc_zero(node
, struct tree_node
);
100 infant
->key
= talloc_strdup( infant
, key
);
101 infant
->parent
= node
;
103 siblings
= talloc_realloc(node
, node
->children
, struct tree_node
*,
104 node
->num_children
+1);
107 node
->children
= siblings
;
109 node
->num_children
++;
113 if ( node
->num_children
== 1 ) {
114 DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
115 node
->key
? node
->key
: "NULL", infant
->key
));
116 node
->children
[0] = infant
;
121 * multiple siblings .... (at least 2 children)
123 * work from the end of the list forward
124 * The last child is not set at this point
125 * Insert the new infanct in ascending order
129 for ( i
= node
->num_children
-1; i
>=1; i
-- )
131 DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
132 infant
->key
, node
->children
[i
-1]->key
));
134 /* the strings should never match assuming that we
135 have called pathtree_find_child() first */
137 if ( strcasecmp_m( infant
->key
, node
->children
[i
-1]->key
) > 0 ) {
138 DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
140 node
->children
[i
] = infant
;
144 /* bump everything towards the end on slot */
146 node
->children
[i
] = node
->children
[i
-1];
149 DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i
));
151 /* if we haven't found the correct slot yet, the child
152 will be first in the list */
155 node
->children
[0] = infant
;
161 /**************************************************************************
162 Find the next child given a key string
163 *************************************************************************/
165 static struct tree_node
*pathtree_find_child(struct tree_node
*node
,
168 struct tree_node
*next
= NULL
;
172 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
177 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
181 for ( i
=0; i
<node
->num_children
; i
++ )
183 DEBUG(11,("pathtree_find_child: child key => [%s]\n",
184 node
->children
[i
]->key
));
186 result
= strcasecmp_m( node
->children
[i
]->key
, key
);
189 next
= node
->children
[i
];
191 /* if result > 0 then we've gone to far because
192 the list of children is sorted by key name
193 If result == 0, then we have a match */
199 DEBUG(11,("pathtree_find_child: %s [%s]\n",
200 next
? "Found" : "Did not find", key
));
205 /**************************************************************************
206 Add a new node into the tree given a key path and a blob of data
207 *************************************************************************/
209 bool pathtree_add(struct sorted_tree
*tree
, const char *path
, void *data_p
)
211 char *str
, *base
, *path2
;
212 struct tree_node
*current
, *next
;
215 DEBUG(8,("pathtree_add: Enter\n"));
217 if ( !path
|| *path
!= '\\' ) {
218 DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
219 path
? path
: "NULL" ));
224 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
228 /* move past the first '\\' */
231 path2
= SMB_STRDUP( path
);
233 DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path
));
239 * this works sort of like a 'mkdir -p' call, possibly
240 * creating an entire path to the new node at once
241 * The path should be of the form /<key1>/<key2>/...
246 current
= tree
->root
;
249 /* break off the remaining part of the path */
251 str
= strchr( str
, '\\' );
255 /* iterate to the next child--birth it if necessary */
257 next
= pathtree_find_child( current
, base
);
259 next
= pathtree_birth_child( current
, base
);
261 DEBUG(0,("pathtree_add: Failed to create new child!\n"));
268 /* setup the next part of the path */
277 } while ( base
!= NULL
);
279 current
->data_p
= data_p
;
281 DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
284 DEBUG(8,("pathtree_add: Exit\n"));
292 /**************************************************************************
293 Recursive routine to print out all children of a struct tree_node
294 *************************************************************************/
296 static void pathtree_print_children(TALLOC_CTX
*ctx
,
297 struct tree_node
*node
,
309 DEBUG(debug
,("%s: [%s] (%s)\n", path
? path
: "NULL", node
->key
,
310 node
->data_p
? "data" : "NULL" ));
313 path2
= talloc_strdup(ctx
, path
);
319 path2
= talloc_asprintf(ctx
,
322 node
->key
? node
->key
: "NULL");
327 num_children
= node
->num_children
;
328 for ( i
=0; i
<num_children
; i
++ ) {
329 pathtree_print_children(ctx
, node
->children
[i
], debug
, path2
);
333 /**************************************************************************
334 Dump the kys for a tree to the log file
335 *************************************************************************/
337 void pathtree_print_keys(struct sorted_tree
*tree
, int debug
)
340 int num_children
= tree
->root
->num_children
;
342 if ( tree
->root
->key
)
343 DEBUG(debug
,("ROOT/: [%s] (%s)\n", tree
->root
->key
,
344 tree
->root
->data_p
? "data" : "NULL" ));
346 for ( i
=0; i
<num_children
; i
++ ) {
347 TALLOC_CTX
*ctx
= talloc_stackframe();
348 pathtree_print_children(ctx
, tree
->root
->children
[i
], debug
,
349 tree
->root
->key
? tree
->root
->key
: "ROOT/" );
355 /**************************************************************************
356 return the data_p for for the node in tree matching the key string
357 The key string is the full path. We must break it apart and walk
359 *************************************************************************/
361 void* pathtree_find(struct sorted_tree
*tree
, char *key
)
363 char *keystr
, *base
= NULL
, *str
= NULL
, *p
;
364 struct tree_node
*current
;
367 DEBUG(10,("pathtree_find: Enter [%s]\n", key
? key
: "NULL" ));
369 /* sanity checks first */
372 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
377 DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
378 key
? key
: "NULL" ));
385 /* make a copy to play with */
388 keystr
= SMB_STRDUP( key
+1 );
390 keystr
= SMB_STRDUP( key
);
393 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key
));
397 /* start breaking the path apart */
400 current
= tree
->root
;
402 if ( tree
->root
->data_p
)
403 result
= tree
->root
->data_p
;
407 /* break off the remaining part of the path */
409 trim_tree_keypath( p
, &base
, &str
);
411 DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n",
415 /* iterate to the next child */
417 current
= pathtree_find_child( current
, base
);
420 * the idea is that the data_p for a parent should
421 * be inherited by all children, but allow it to be
422 * overridden farther down
425 if ( current
&& current
->data_p
)
426 result
= current
->data_p
;
428 /* reset the path pointer 'p' to the remaining part of the key string */
432 } while ( str
&& current
);
434 /* result should be the data_p from the lowest match node in the tree */
436 DEBUG(11,("pathtree_find: Found data_p!\n"));
440 DEBUG(10,("pathtree_find: Exit\n"));