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