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