wafsamba.samba_abi: Refactor abi_write_vscript to take file argument.
[Samba/bb.git] / source3 / lib / adt_tree.c
blobb6b5a98da044ce826364dc236460252453633665
1 /*
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/>.
20 #include "includes.h"
21 #include "adt_tree.h"
23 struct tree_node {
24 struct tree_node *parent;
25 struct tree_node **children;
26 int num_children;
27 char *key;
28 void *data_p;
31 struct sorted_tree {
32 struct tree_node *root;
35 /**************************************************************************
36 *************************************************************************/
38 static bool trim_tree_keypath( char *path, char **base, char **new_path )
40 char *p;
42 *new_path = *base = NULL;
44 if ( !path )
45 return False;
47 *base = path;
49 p = strchr( path, '\\' );
51 if ( p ) {
52 *p = '\0';
53 *new_path = p+1;
56 return True;
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);
68 if (tree == NULL) {
69 return NULL;
72 tree->root = talloc_zero(tree, struct tree_node);
73 if (tree->root == NULL) {
74 TALLOC_FREE( tree );
75 return NULL;
78 tree->root->data_p = data_p;
80 return tree;
84 /**************************************************************************
85 Find the next child given a key string
86 *************************************************************************/
88 static struct tree_node *pathtree_birth_child(struct tree_node *node,
89 char* key )
91 struct tree_node *infant = NULL;
92 struct tree_node **siblings;
93 int i;
95 infant = talloc_zero(node, struct tree_node);
96 if (infant == NULL) {
97 return NULL;
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);
106 if ( siblings )
107 node->children = siblings;
109 node->num_children++;
111 /* first child */
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;
118 else
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
126 * from left to right
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",
139 i));
140 node->children[i] = infant;
141 break;
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 */
154 if ( i == 0 )
155 node->children[0] = infant;
158 return infant;
161 /**************************************************************************
162 Find the next child given a key string
163 *************************************************************************/
165 static struct tree_node *pathtree_find_child(struct tree_node *node,
166 char *key )
168 struct tree_node *next = NULL;
169 int i, result;
171 if ( !node ) {
172 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
173 return NULL;
176 if ( !key ) {
177 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
178 return NULL;
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 );
188 if ( result == 0 )
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 */
195 if ( result > 0 )
196 break;
199 DEBUG(11,("pathtree_find_child: %s [%s]\n",
200 next ? "Found" : "Did not find", key ));
202 return next;
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;
213 bool ret = true;
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" ));
220 return false;
223 if ( !tree ) {
224 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
225 return false;
228 /* move past the first '\\' */
230 path++;
231 path2 = SMB_STRDUP( path );
232 if ( !path2 ) {
233 DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
234 return false;
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>/...
244 base = path2;
245 str = path2;
246 current = tree->root;
248 do {
249 /* break off the remaining part of the path */
251 str = strchr( str, '\\' );
252 if ( str )
253 *str = '\0';
255 /* iterate to the next child--birth it if necessary */
257 next = pathtree_find_child( current, base );
258 if ( !next ) {
259 next = pathtree_birth_child( current, base );
260 if ( !next ) {
261 DEBUG(0,("pathtree_add: Failed to create new child!\n"));
262 ret = false;
263 goto done;
266 current = next;
268 /* setup the next part of the path */
270 base = str;
271 if ( base ) {
272 *base = '\\';
273 base++;
274 str = base;
277 } while ( base != NULL );
279 current->data_p = data_p;
281 DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
282 path ));
284 DEBUG(8,("pathtree_add: Exit\n"));
286 done:
287 SAFE_FREE( path2 );
288 return ret;
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,
298 int debug,
299 const char *path )
301 int i;
302 int num_children;
303 char *path2 = NULL;
305 if ( !node )
306 return;
308 if ( node->key )
309 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
310 node->data_p ? "data" : "NULL" ));
312 if ( path ) {
313 path2 = talloc_strdup(ctx, path);
314 if (!path2) {
315 return;
319 path2 = talloc_asprintf(ctx,
320 "%s%s/",
321 path ? path : "",
322 node->key ? node->key : "NULL");
323 if (!path2) {
324 return;
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 )
339 int i;
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/" );
350 TALLOC_FREE(ctx);
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
358 the tree
359 *************************************************************************/
361 void* pathtree_find(struct sorted_tree *tree, char *key )
363 char *keystr, *base = NULL, *str = NULL, *p;
364 struct tree_node *current;
365 void *result = NULL;
367 DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
369 /* sanity checks first */
371 if ( !key ) {
372 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
373 return NULL;
376 if ( !tree ) {
377 DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
378 key ? key : "NULL" ));
379 return NULL;
382 if ( !tree->root )
383 return NULL;
385 /* make a copy to play with */
387 if ( *key == '\\' )
388 keystr = SMB_STRDUP( key+1 );
389 else
390 keystr = SMB_STRDUP( key );
392 if ( !keystr ) {
393 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
394 return NULL;
397 /* start breaking the path apart */
399 p = keystr;
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",
412 base ? base : "",
413 str ? str : ""));
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 */
430 p = str;
432 } while ( str && current );
434 /* result should be the data_p from the lowest match node in the tree */
435 if ( result )
436 DEBUG(11,("pathtree_find: Found data_p!\n"));
438 SAFE_FREE( keystr );
440 DEBUG(10,("pathtree_find: Exit\n"));
442 return result;