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 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    = 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 )
 114                 tree->free( 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