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