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