← Back to branch summary

~ubuntu-branches/ubuntu/lucid/samba/lucid-proposed

« back to all changes in this revision

Viewing changes to source/lib/adt_tree.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-07-21 17:53:23 UTC
  • mfrom: (0.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20050721175323-m3oh6aoigywohfnq
Tags: 3.0.14a-6ubuntu1
Resynchronise with Debian, resolving merge conflicts (#12360)

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/lib/adt_tree.c
19
19
 */
20
20
 
21
21
#include "includes.h"
 
22
#include "adt_tree.h"
22
23
 
23
24
 
24
25
/**************************************************************************
53
54
 for comparision of two children
54
55
 *************************************************************************/
55
56
 
56
 
SORTED_TREE* sorted_tree_init( void *data_p,
 
57
 SORTED_TREE* pathtree_init( void *data_p,
57
58
                               int (cmp_fn)(void*, void*),
58
59
                               void (free_fn)(void*) )
59
60
{
83
84
 Delete a tree and free all allocated memory
84
85
 *************************************************************************/
85
86
 
86
 
static void sorted_tree_destroy_children( TREE_NODE *root )
 
87
static void pathtree_destroy_children( TREE_NODE *root )
87
88
{
88
89
        int i;
89
90
        
92
93
        
93
94
        for ( i=0; i<root->num_children; i++ )
94
95
        {
95
 
                sorted_tree_destroy_children( root->children[i] );      
 
96
                pathtree_destroy_children( root->children[i] ); 
96
97
        }
97
98
        
98
99
        SAFE_FREE( root->children );
105
106
 Delete a tree and free all allocated memory
106
107
 *************************************************************************/
107
108
 
108
 
void sorted_tree_destroy( SORTED_TREE *tree )
 
109
 void pathtree_destroy( SORTED_TREE *tree )
109
110
{
110
111
        if ( tree->root )
111
 
                sorted_tree_destroy_children( tree->root );     
 
112
                pathtree_destroy_children( tree->root );        
112
113
        
113
114
        if ( tree->free_func )
114
115
                tree->free_func( tree->root );
120
121
 Find the next child given a key string
121
122
 *************************************************************************/
122
123
 
123
 
static TREE_NODE* sorted_tree_birth_child( TREE_NODE *node, char* key )
 
124
static TREE_NODE* pathtree_birth_child( TREE_NODE *node, char* key )
124
125
{
125
126
        TREE_NODE *infant = NULL;
126
127
        TREE_NODE **siblings;
144
145
        /* first child */
145
146
        
146
147
        if ( node->num_children == 1 ) {
147
 
                DEBUG(11,("sorted_tree_birth_child: First child of node [%s]! [%s]\n", 
 
148
                DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n", 
148
149
                        node->key ? node->key : "NULL", infant->key ));
149
150
                node->children[0] = infant;
150
151
        }
161
162
        
162
163
                for ( i = node->num_children-1; i>=1; i-- )
163
164
                {
164
 
                        DEBUG(11,("sorted_tree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
 
165
                        DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
165
166
                                infant->key, node->children[i-1]->key));
166
167
                        
167
168
                        /* the strings should never match assuming that we 
168
 
                           have called sorted_tree_find_child() first */
 
169
                           have called pathtree_find_child() first */
169
170
                
170
171
                        if ( StrCaseCmp( infant->key, node->children[i-1]->key ) > 0 ) {
171
 
                                DEBUG(11,("sorted_tree_birth_child: storing infant in i == [%d]\n", 
 
172
                                DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n", 
172
173
                                        i));
173
174
                                node->children[i] = infant;
174
175
                                break;
179
180
                        node->children[i] = node->children[i-1];
180
181
                }
181
182
 
182
 
                DEBUG(11,("sorted_tree_birth_child: Exiting loop (i == [%d])\n", i ));
 
183
                DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i ));
183
184
                
184
185
                /* if we haven't found the correct slot yet, the child 
185
186
                   will be first in the list */
195
196
 Find the next child given a key string
196
197
 *************************************************************************/
197
198
 
198
 
static TREE_NODE* sorted_tree_find_child( TREE_NODE *node, char* key )
 
199
static TREE_NODE* pathtree_find_child( TREE_NODE *node, char* key )
199
200
{
200
201
        TREE_NODE *next = NULL;
201
202
        int i, result;
202
203
        
203
204
        if ( !node ) {
204
 
                DEBUG(0,("sorted_tree_find_child: NULL node passed into function!\n"));
 
205
                DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
205
206
                return NULL;
206
207
        }
207
208
        
208
209
        if ( !key ) {
209
 
                DEBUG(0,("sorted_tree_find_child: NULL key string passed into function!\n"));
 
210
                DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
210
211
                return NULL;
211
212
        }
212
213
        
213
214
        for ( i=0; i<node->num_children; i++ )
214
215
        {       
215
 
                DEBUG(11,("sorted_tree_find_child: child key => [%s]\n",
 
216
                DEBUG(11,("pathtree_find_child: child key => [%s]\n",
216
217
                        node->children[i]->key));
217
218
                        
218
219
                result = StrCaseCmp( node->children[i]->key, key );
228
229
                        break;
229
230
        }
230
231
 
231
 
        DEBUG(11,("sorted_tree_find_child: %s [%s]\n",
 
232
        DEBUG(11,("pathtree_find_child: %s [%s]\n",
232
233
                next ? "Found" : "Did not find", key ));        
233
234
        
234
235
        return next;
238
239
 Add a new node into the tree given a key path and a blob of data
239
240
 *************************************************************************/
240
241
 
241
 
BOOL sorted_tree_add( SORTED_TREE *tree, const char *path, void *data_p )
 
242
 BOOL pathtree_add( SORTED_TREE *tree, const char *path, void *data_p )
242
243
{
243
244
        char *str, *base, *path2;
244
245
        TREE_NODE *current, *next;
245
246
        BOOL ret = True;
246
247
        
247
 
        DEBUG(8,("sorted_tree_add: Enter\n"));
 
248
        DEBUG(8,("pathtree_add: Enter\n"));
248
249
                
249
250
        if ( !path || *path != '/' ) {
250
 
                DEBUG(0,("sorted_tree_add: Attempt to add a node with a bad path [%s]\n",
 
251
                DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
251
252
                        path ? path : "NULL" ));
252
253
                return False;
253
254
        }
254
255
        
255
256
        if ( !tree ) {
256
 
                DEBUG(0,("sorted_tree_add: Attempt to add a node to an uninitialized tree!\n"));
 
257
                DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
257
258
                return False;
258
259
        }
259
260
        
262
263
        path++; 
263
264
        path2 = SMB_STRDUP( path );
264
265
        if ( !path2 ) {
265
 
                DEBUG(0,("sorted_tree_add: strdup() failed on string [%s]!?!?!\n", path));
 
266
                DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
266
267
                return False;
267
268
        }
268
269
        
286
287
                        
287
288
                /* iterate to the next child--birth it if necessary */
288
289
                
289
 
                next = sorted_tree_find_child( current, base );
 
290
                next = pathtree_find_child( current, base );
290
291
                if ( !next ) {
291
 
                        next = sorted_tree_birth_child( current, base );
 
292
                        next = pathtree_birth_child( current, base );
292
293
                        if ( !next ) {
293
 
                                DEBUG(0,("sorted_tree_add: Failed to create new child!\n"));
 
294
                                DEBUG(0,("pathtree_add: Failed to create new child!\n"));
294
295
                                ret =  False;
295
296
                                goto done;
296
297
                        }
310
311
        
311
312
        current->data_p = data_p;
312
313
        
313
 
        DEBUG(10,("sorted_tree_add: Successfully added node [%s] to tree\n",
 
314
        DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
314
315
                path ));
315
316
 
316
 
        DEBUG(8,("sorted_tree_add: Exit\n"));
 
317
        DEBUG(8,("pathtree_add: Exit\n"));
317
318
 
318
319
done:
319
320
        SAFE_FREE( path2 );
325
326
 Recursive routine to print out all children of a TREE_NODE
326
327
 *************************************************************************/
327
328
 
328
 
static void sorted_tree_print_children( TREE_NODE *node, int debug, const char *path )
 
329
static void pathtree_print_children( TREE_NODE *node, int debug, const char *path )
329
330
{
330
331
        int i;
331
332
        int num_children;
347
348
                
348
349
        num_children = node->num_children;
349
350
        for ( i=0; i<num_children; i++ )
350
 
                sorted_tree_print_children( node->children[i], debug, path2 );
 
351
                pathtree_print_children( node->children[i], debug, path2 );
351
352
        
352
353
 
353
354
}
356
357
 Dump the kys for a tree to the log file
357
358
 *************************************************************************/
358
359
 
359
 
void sorted_tree_print_keys( SORTED_TREE *tree, int debug )
 
360
 void pathtree_print_keys( SORTED_TREE *tree, int debug )
360
361
{
361
362
        int i;
362
363
        int num_children = tree->root->num_children;
366
367
                        tree->root->data_p ? "data" : "NULL" ));
367
368
        
368
369
        for ( i=0; i<num_children; i++ ) {
369
 
                sorted_tree_print_children( tree->root->children[i], debug, 
 
370
                pathtree_print_children( tree->root->children[i], debug, 
370
371
                        tree->root->key ? tree->root->key : "ROOT/" );
371
372
        }
372
373
        
378
379
 the tree
379
380
 *************************************************************************/
380
381
 
381
 
void* sorted_tree_find( SORTED_TREE *tree, char *key )
 
382
 void* pathtree_find( SORTED_TREE *tree, char *key )
382
383
{
383
384
        char *keystr, *base, *str, *p;
384
385
        TREE_NODE *current;
385
386
        void *result = NULL;
386
387
        
387
 
        DEBUG(10,("sorted_tree_find: Enter [%s]\n", key ? key : "NULL" ));
 
388
        DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
388
389
 
389
390
        /* sanity checks first */
390
391
        
391
392
        if ( !key ) {
392
 
                DEBUG(0,("sorted_tree_find: Attempt to search tree using NULL search string!\n"));
 
393
                DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
393
394
                return NULL;
394
395
        }
395
396
        
396
397
        if ( !tree ) {
397
 
                DEBUG(0,("sorted_tree_find: Attempt to search an uninitialized tree using string [%s]!\n",
 
398
                DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
398
399
                        key ? key : "NULL" ));
399
400
                return NULL;
400
401
        }
410
411
                keystr = SMB_STRDUP( key );
411
412
        
412
413
        if ( !keystr ) {
413
 
                DEBUG(0,("sorted_tree_find: strdup() failed on string [%s]!?!?!\n", key));
 
414
                DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
414
415
                return NULL;
415
416
        }
416
417
 
428
429
 
429
430
                trim_tree_keypath( p, &base, &str );
430
431
                        
431
 
                DEBUG(11,("sorted_tree_find: [loop] base => [%s], new_path => [%s]\n", 
 
432
                DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n", 
432
433
                        base, str));
433
434
 
434
435
                /* iterate to the next child */
435
436
                
436
 
                current = sorted_tree_find_child( current, base );
 
437
                current = pathtree_find_child( current, base );
437
438
        
438
439
                /* 
439
440
                 * the idea is that the data_p for a parent should 
452
453
        
453
454
        /* result should be the data_p from the lowest match node in the tree */
454
455
        if ( result )
455
 
                DEBUG(11,("sorted_tree_find: Found data_p!\n"));
 
456
                DEBUG(11,("pathtree_find: Found data_p!\n"));
456
457
        
457
458
        SAFE_FREE( keystr );
458
459
        
459
 
        DEBUG(10,("sorted_tree_find: Exit\n"));
 
460
        DEBUG(10,("pathtree_find: Exit\n"));
460
461
        
461
462
        return result;
462
463
}