torture3: Fix CID 1435119 Error handling issues (CHECKED_RETURN)
[samba.git] / source3 / lib / adt_tree.c
1 /* 
2  *  Unix SMB/CIFS implementation.
3  *  Generic Abstract Data Types
4  *  Copyright (C) Gerald Carter                     2002.
5  *
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.
10  *  
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.
15  *  
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/>.
18  */
19
20 #include "includes.h"
21 #include "adt_tree.h"
22
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;
29 };
30
31 struct sorted_tree {
32         struct tree_node *root;
33 };
34
35 /**************************************************************************
36  *************************************************************************/
37
38 static bool trim_tree_keypath( char *path, char **base, char **new_path )
39 {
40         char *p;
41
42         *new_path = *base = NULL;
43
44         if ( !path )
45                 return False;
46
47         *base = path;
48
49         p = strchr( path, '\\' );
50
51         if ( p ) {
52                 *p = '\0';
53                 *new_path = p+1;
54         }
55
56         return True;
57 }
58
59 /**************************************************************************
60  Initialize the tree's root.
61  *************************************************************************/
62
63 struct sorted_tree *pathtree_init(void *data_p)
64 {
65         struct sorted_tree *tree = NULL;
66
67         tree = talloc_zero(NULL, struct sorted_tree);
68         if (tree == NULL) {
69                 return NULL;
70         }
71
72         tree->root = talloc_zero(tree, struct tree_node);
73         if (tree->root == NULL) {
74                 TALLOC_FREE( tree );
75                 return NULL;
76         }
77
78         tree->root->data_p = data_p;
79
80         return tree;
81 }
82
83
84 /**************************************************************************
85  Find the next child given a key string
86  *************************************************************************/
87
88 static struct tree_node *pathtree_birth_child(struct tree_node *node,
89                                               char* key )
90 {
91         struct tree_node *infant = NULL;
92         struct tree_node **siblings;
93         int i;
94
95         infant = talloc_zero(node, struct tree_node);
96         if (infant == NULL) {
97                 return NULL;
98         }
99
100         infant->key = talloc_strdup( infant, key );
101         infant->parent = node;
102
103         siblings = talloc_realloc(node, node->children, struct tree_node *,
104                                   node->num_children+1);
105
106         if ( siblings )
107                 node->children = siblings;
108
109         node->num_children++;
110
111         /* first child */
112
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;
117         }
118         else 
119         {
120                 /* 
121                  * multiple siblings .... (at least 2 children)
122                  * 
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
127                  */
128
129                 for ( i = node->num_children-1; i>=1; i-- )
130                 {
131                         DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
132                                 infant->key, node->children[i-1]->key));
133
134                         /* the strings should never match assuming that we 
135                            have called pathtree_find_child() first */
136
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;
142                         }
143
144                         /* bump everything towards the end on slot */
145
146                         node->children[i] = node->children[i-1];
147                 }
148
149                 DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i ));
150
151                 /* if we haven't found the correct slot yet, the child 
152                    will be first in the list */
153
154                 if ( i == 0 )
155                         node->children[0] = infant;
156         }
157
158         return infant;
159 }
160
161 /**************************************************************************
162  Find the next child given a key string
163  *************************************************************************/
164
165 static struct tree_node *pathtree_find_child(struct tree_node *node,
166                                              char *key )
167 {
168         struct tree_node *next = NULL;
169         int i, result;
170
171         if ( !node ) {
172                 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
173                 return NULL;
174         }
175
176         if ( !key ) {
177                 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
178                 return NULL;
179         }
180
181         for ( i=0; i<node->num_children; i++ )
182         {       
183                 DEBUG(11,("pathtree_find_child: child key => [%s]\n",
184                         node->children[i]->key));
185
186                 result = strcasecmp_m( node->children[i]->key, key );
187
188                 if ( result == 0 )
189                         next = node->children[i];
190
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         */
194
195                 if ( result > 0 )
196                         break;
197         }
198
199         DEBUG(11,("pathtree_find_child: %s [%s]\n",
200                 next ? "Found" : "Did not find", key ));        
201
202         return next;
203 }
204
205 /**************************************************************************
206  Add a new node into the tree given a key path and a blob of data
207  *************************************************************************/
208
209 bool pathtree_add(struct sorted_tree *tree, const char *path, void *data_p)
210 {
211         char *str, *base, *path2;
212         struct tree_node *current, *next;
213         bool ret = true;
214
215         DEBUG(8,("pathtree_add: Enter\n"));
216
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;
221         }
222
223         if ( !tree ) {
224                 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
225                 return false;
226         }
227
228         /* move past the first '\\' */
229
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;
235         }
236
237
238         /* 
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>/...
242          */
243
244         base = path2;
245         str  = path2;
246         current = tree->root;
247
248         do {
249                 /* break off the remaining part of the path */
250
251                 str = strchr( str, '\\' );
252                 if ( str )
253                         *str = '\0';
254
255                 /* iterate to the next child--birth it if necessary */
256
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;
264                         }
265                 }
266                 current = next;
267
268                 /* setup the next part of the path */
269
270                 base = str;
271                 if ( base ) {
272                         *base = '\\';
273                         base++;
274                         str = base;
275                 }
276
277         } while ( base != NULL );
278
279         current->data_p = data_p;
280
281         DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
282                 path ));
283
284         DEBUG(8,("pathtree_add: Exit\n"));
285
286 done:
287         SAFE_FREE( path2 );
288         return ret;
289 }
290
291
292 /**************************************************************************
293  Recursive routine to print out all children of a struct tree_node
294  *************************************************************************/
295
296 static void pathtree_print_children(TALLOC_CTX *ctx,
297                                 struct tree_node *node,
298                                 int debug,
299                                 const char *path )
300 {
301         int i;
302         int num_children;
303         char *path2 = NULL;
304
305         if ( !node )
306                 return;
307
308         if ( node->key )
309                 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
310                         node->data_p ? "data" : "NULL" ));
311
312         if ( path ) {
313                 path2 = talloc_strdup(ctx, path);
314                 if (!path2) {
315                         return;
316                 }
317         }
318
319         path2 = talloc_asprintf(ctx,
320                         "%s%s/",
321                         path ? path : "",
322                         node->key ? node->key : "NULL");
323         if (!path2) {
324                 return;
325         }
326
327         num_children = node->num_children;
328         for ( i=0; i<num_children; i++ ) {
329                 pathtree_print_children(ctx, node->children[i], debug, path2 );
330         }
331 }
332
333 /**************************************************************************
334  Dump the kys for a tree to the log file
335  *************************************************************************/
336
337 void pathtree_print_keys(struct sorted_tree *tree, int debug )
338 {
339         int i;
340         int num_children = tree->root->num_children;
341
342         if ( tree->root->key )
343                 DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
344                         tree->root->data_p ? "data" : "NULL" ));
345
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);
351         }
352
353 }
354
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  *************************************************************************/
360
361 void* pathtree_find(struct sorted_tree *tree, char *key )
362 {
363         char *keystr, *base = NULL, *str = NULL, *p;
364         struct tree_node *current;
365         void *result = NULL;
366
367         DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
368
369         /* sanity checks first */
370
371         if ( !key ) {
372                 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
373                 return NULL;
374         }
375
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;
380         }
381
382         if ( !tree->root )
383                 return NULL;
384
385         /* make a copy to play with */
386
387         if ( *key == '\\' )
388                 keystr = SMB_STRDUP( key+1 );
389         else
390                 keystr = SMB_STRDUP( key );
391
392         if ( !keystr ) {
393                 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
394                 return NULL;
395         }
396
397         /* start breaking the path apart */
398
399         p = keystr;
400         current = tree->root;
401
402         if ( tree->root->data_p )
403                 result = tree->root->data_p;
404
405         do
406         {
407                 /* break off the remaining part of the path */
408
409                 trim_tree_keypath( p, &base, &str );
410
411                 DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n", 
412                         base ? base : "",
413                         str ? str : ""));
414
415                 /* iterate to the next child */
416
417                 current = pathtree_find_child( current, base );
418
419                 /* 
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
423                  */
424
425                 if ( current && current->data_p )
426                         result = current->data_p;
427
428                 /* reset the path pointer 'p' to the remaining part of the key string */
429
430                 p = str;
431
432         } while ( str && current );
433
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"));
437
438         SAFE_FREE( keystr );
439
440         DEBUG(10,("pathtree_find: Exit\n"));
441
442         return result;
443 }
444
445