bd857e205ac150dfcc944e569b7991b3cd676ade
[tprouty/samba.git] / source / 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 2 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, write to the Free Software
18  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19  */
20
21 #include "includes.h"
22
23
24 /**************************************************************************
25  Initialize the tree's root.  The cmp_fn is a callback function used
26  for comparision of two children
27  *************************************************************************/
28
29 static BOOL trim_tree_keypath( char *path, char **base, char **new_path )
30 {
31         char *p;
32         
33         *new_path = *base = NULL;
34         
35         if ( !path )
36                 return False;
37         
38         *base = path;
39         
40         p = strchr( path, '/' );
41         
42         if ( p ) {
43                 *p = '\0';
44                 *new_path = p+1;
45         }
46         
47         return True;
48 }
49
50  
51 /**************************************************************************
52  Initialize the tree's root.  The cmp_fn is a callback function used
53  for comparision of two children
54  *************************************************************************/
55
56 SORTED_TREE* sorted_tree_init( void *data_p,
57                                int (cmp_fn)(void*, void*),
58                                void (free_fn)(void*) )
59 {
60         SORTED_TREE *tree = NULL;
61         
62         if ( !(tree = (SORTED_TREE*)malloc( sizeof(SORTED_TREE) )) )
63                 return NULL;
64                 
65         ZERO_STRUCTP( tree );
66         
67         tree->compare = cmp_fn;
68         tree->free_func    = free_fn;
69         
70         if ( !(tree->root = (TREE_NODE*)malloc( sizeof(TREE_NODE) )) ) {
71                 SAFE_FREE( tree );
72                 return NULL;
73         }
74         
75         ZERO_STRUCTP( tree->root );
76         tree->root->data_p = data_p;
77         
78         return tree;
79 }
80
81
82 /**************************************************************************
83  Delete a tree and free all allocated memory
84  *************************************************************************/
85
86 static void sorted_tree_destroy_children( TREE_NODE *root )
87 {
88         int i;
89         
90         if ( !root )
91                 return;
92         
93         for ( i=0; i<root->num_children; i++ )
94         {
95                 sorted_tree_destroy_children( root->children[i] );      
96         }
97         
98         SAFE_FREE( root->children );
99         SAFE_FREE( root->key );
100         
101         return;
102 }
103
104 /**************************************************************************
105  Delete a tree and free all allocated memory
106  *************************************************************************/
107
108 void sorted_tree_destroy( SORTED_TREE *tree )
109 {
110         if ( tree->root )
111                 sorted_tree_destroy_children( tree->root );     
112         
113         if ( tree->free_func )
114                 tree->free_func( tree->root );
115         
116         SAFE_FREE( tree );
117 }
118
119 /**************************************************************************
120  Find the next child given a key string
121  *************************************************************************/
122
123 static TREE_NODE* sorted_tree_birth_child( TREE_NODE *node, char* key )
124 {
125         TREE_NODE *infant = NULL;
126         TREE_NODE **siblings;
127         int i;
128         
129         if ( !(infant = (TREE_NODE*)malloc( sizeof(TREE_NODE) )) )
130                 return NULL;
131         
132         ZERO_STRUCTP( infant );
133                 
134         infant->key = strdup( key );
135         infant->parent = node;
136         
137         siblings = Realloc( node->children, sizeof(TREE_NODE*)*(node->num_children+1) );
138         
139         if ( siblings )
140                 node->children = siblings;
141         
142         node->num_children++;
143         
144         /* first child */
145         
146         if ( node->num_children == 1 ) {
147                 DEBUG(11,("sorted_tree_birth_child: First child of node [%s]! [%s]\n", 
148                         node->key ? node->key : "NULL", infant->key ));
149                 node->children[0] = infant;
150         }
151         else 
152         {
153                 /* 
154                  * multiple siblings .... (at least 2 children)
155                  * 
156                  * work from the end of the list forward 
157                  * The last child is not set at this point 
158                  * Insert the new infanct in ascending order 
159                  * from left to right
160                  */
161         
162                 for ( i = node->num_children-1; i>=1; i-- )
163                 {
164                         DEBUG(11,("sorted_tree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
165                                 infant->key, node->children[i-1]->key));
166                         
167                         /* the strings should never match assuming that we 
168                            have called sorted_tree_find_child() first */
169                 
170                         if ( StrCaseCmp( infant->key, node->children[i-1]->key ) > 0 ) {
171                                 DEBUG(11,("sorted_tree_birth_child: storing infant in i == [%d]\n", 
172                                         i));
173                                 node->children[i] = infant;
174                                 break;
175                         }
176                         
177                         /* bump everything towards the end on slot */
178                         
179                         node->children[i] = node->children[i-1];
180                 }
181
182                 DEBUG(11,("sorted_tree_birth_child: Exiting loop (i == [%d])\n", i ));
183                 
184                 /* if we haven't found the correct slot yet, the child 
185                    will be first in the list */
186                    
187                 if ( i == 0 )
188                         node->children[0] = infant;
189         }
190
191         return infant;
192 }
193
194 /**************************************************************************
195  Find the next child given a key string
196  *************************************************************************/
197
198 static TREE_NODE* sorted_tree_find_child( TREE_NODE *node, char* key )
199 {
200         TREE_NODE *next = NULL;
201         int i, result;
202         
203         if ( !node ) {
204                 DEBUG(0,("sorted_tree_find_child: NULL node passed into function!\n"));
205                 return NULL;
206         }
207         
208         if ( !key ) {
209                 DEBUG(0,("sorted_tree_find_child: NULL key string passed into function!\n"));
210                 return NULL;
211         }
212         
213         for ( i=0; i<node->num_children; i++ )
214         {       
215                 DEBUG(11,("sorted_tree_find_child: child key => [%s]\n",
216                         node->children[i]->key));
217                         
218                 result = StrCaseCmp( node->children[i]->key, key );
219                 
220                 if ( result == 0 )
221                         next = node->children[i];
222                 
223                 /* if result > 0 then we've gone to far because
224                    the list of children is sorted by key name 
225                    If result == 0, then we have a match         */
226                    
227                 if ( result > 0 )
228                         break;
229         }
230
231         DEBUG(11,("sorted_tree_find_child: %s [%s]\n",
232                 next ? "Found" : "Did not find", key ));        
233         
234         return next;
235 }
236
237 /**************************************************************************
238  Add a new node into the tree given a key path and a blob of data
239  *************************************************************************/
240
241 BOOL sorted_tree_add( SORTED_TREE *tree, const char *path, void *data_p )
242 {
243         char *str, *base, *path2;
244         TREE_NODE *current, *next;
245         BOOL ret = True;
246         
247         DEBUG(8,("sorted_tree_add: Enter\n"));
248                 
249         if ( !path || *path != '/' ) {
250                 DEBUG(0,("sorted_tree_add: Attempt to add a node with a bad path [%s]\n",
251                         path ? path : "NULL" ));
252                 return False;
253         }
254         
255         if ( !tree ) {
256                 DEBUG(0,("sorted_tree_add: Attempt to add a node to an uninitialized tree!\n"));
257                 return False;
258         }
259         
260         /* move past the first '/' */
261         
262         path++; 
263         path2 = strdup( path );
264         if ( !path2 ) {
265                 DEBUG(0,("sorted_tree_add: strdup() failed on string [%s]!?!?!\n", path));
266                 return False;
267         }
268         
269
270         /* 
271          * this works sort of like a 'mkdir -p' call, possibly 
272          * creating an entire path to the new node at once
273          * The path should be of the form /<key1>/<key2>/...
274          */
275         
276         base = path2;
277         str  = path2;
278         current = tree->root;
279         
280         do {
281                 /* break off the remaining part of the path */
282                 
283                 str = strchr( str, '/' );
284                 if ( str )
285                         *str = '\0';
286                         
287                 /* iterate to the next child--birth it if necessary */
288                 
289                 next = sorted_tree_find_child( current, base );
290                 if ( !next ) {
291                         next = sorted_tree_birth_child( current, base );
292                         if ( !next ) {
293                                 DEBUG(0,("sorted_tree_add: Failed to create new child!\n"));
294                                 ret =  False;
295                                 goto done;
296                         }
297                 }
298                 current = next;
299                 
300                 /* setup the next part of the path */
301                 
302                 base = str;
303                 if ( base ) {
304                         *base = '/';
305                         base++;
306                         str = base;
307                 }
308         
309         } while ( base != NULL );
310         
311         current->data_p = data_p;
312         
313         DEBUG(10,("sorted_tree_add: Successfully added node [%s] to tree\n",
314                 path ));
315
316         DEBUG(8,("sorted_tree_add: Exit\n"));
317
318 done:
319         SAFE_FREE( path2 );
320         return ret;
321 }
322
323
324 /**************************************************************************
325  Recursive routine to print out all children of a TREE_NODE
326  *************************************************************************/
327
328 static void sorted_tree_print_children( TREE_NODE *node, int debug, const char *path )
329 {
330         int i;
331         int num_children;
332         pstring path2;
333         
334         if ( !node )
335                 return;
336         
337         
338         if ( node->key )
339                 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
340                         node->data_p ? "data" : "NULL" ));
341
342         *path2 = '\0';
343         if ( path )
344                 pstrcpy( path2, path );
345         pstrcat( path2, node->key ? node->key : "NULL" );
346         pstrcat( path2, "/" );
347                 
348         num_children = node->num_children;
349         for ( i=0; i<num_children; i++ )
350                 sorted_tree_print_children( node->children[i], debug, path2 );
351         
352
353 }
354
355 /**************************************************************************
356  Dump the kys for a tree to the log file
357  *************************************************************************/
358
359 void sorted_tree_print_keys( SORTED_TREE *tree, int debug )
360 {
361         int i;
362         int num_children = tree->root->num_children;
363         
364         if ( tree->root->key )
365                 DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
366                         tree->root->data_p ? "data" : "NULL" ));
367         
368         for ( i=0; i<num_children; i++ ) {
369                 sorted_tree_print_children( tree->root->children[i], debug, 
370                         tree->root->key ? tree->root->key : "ROOT/" );
371         }
372         
373 }
374
375 /**************************************************************************
376  return the data_p for for the node in tree matching the key string
377  The key string is the full path.  We must break it apart and walk 
378  the tree
379  *************************************************************************/
380
381 void* sorted_tree_find( SORTED_TREE *tree, char *key )
382 {
383         char *keystr, *base, *str, *p;
384         TREE_NODE *current;
385         void *result = NULL;
386         
387         DEBUG(10,("sorted_tree_find: Enter [%s]\n", key ? key : "NULL" ));
388
389         /* sanity checks first */
390         
391         if ( !key ) {
392                 DEBUG(0,("sorted_tree_find: Attempt to search tree using NULL search string!\n"));
393                 return NULL;
394         }
395         
396         if ( !tree ) {
397                 DEBUG(0,("sorted_tree_find: Attempt to search an uninitialized tree using string [%s]!\n",
398                         key ? key : "NULL" ));
399                 return NULL;
400         }
401         
402         if ( !tree->root )
403                 return NULL;
404         
405         /* make a copy to play with */
406         
407         if ( *key == '/' )
408                 keystr = strdup( key+1 );
409         else
410                 keystr = strdup( key );
411         
412         if ( !keystr ) {
413                 DEBUG(0,("sorted_tree_find: strdup() failed on string [%s]!?!?!\n", key));
414                 return NULL;
415         }
416
417         /* start breaking the path apart */
418         
419         p = keystr;
420         current = tree->root;
421         
422         if ( tree->root->data_p )
423                 result = tree->root->data_p;
424                 
425         do
426         {
427                 /* break off the remaining part of the path */
428
429                 trim_tree_keypath( p, &base, &str );
430                         
431                 DEBUG(11,("sorted_tree_find: [loop] base => [%s], new_path => [%s]\n", 
432                         base, str));
433
434                 /* iterate to the next child */
435                 
436                 current = sorted_tree_find_child( current, base );
437         
438                 /* 
439                  * the idea is that the data_p for a parent should 
440                  * be inherited by all children, but allow it to be 
441                  * overridden farther down
442                  */
443                 
444                 if ( current && current->data_p )
445                         result = current->data_p;
446
447                 /* reset the path pointer 'p' to the remaining part of the key string */
448
449                 p = str;
450            
451         } while ( str && current );
452         
453         /* result should be the data_p from the lowest match node in the tree */
454         if ( result )
455                 DEBUG(11,("sorted_tree_find: Found data_p!\n"));
456         
457         SAFE_FREE( keystr );
458         
459         DEBUG(10,("sorted_tree_find: Exit\n"));
460         
461         return result;
462 }
463
464