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