LCOV - code coverage report
Current view: top level - source3/lib - adt_tree.c (source / functions) Hit Total Coverage
Test: coverage report for abartlet/fix-coverage dd10fb34 Lines: 111 164 67.7 %
Date: 2021-09-23 10:06:22 Functions: 6 8 75.0 %

          Line data    Source code
       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    11836301 : static bool trim_tree_keypath( char *path, char **base, char **new_path )
      39             : {
      40             :         char *p;
      41             : 
      42    11836301 :         *new_path = *base = NULL;
      43             : 
      44    11836301 :         if ( !path )
      45           0 :                 return False;
      46             : 
      47    11836301 :         *base = path;
      48             : 
      49    11836301 :         p = strchr( path, '\\' );
      50             : 
      51    11836301 :         if ( p ) {
      52     9451001 :                 *p = '\0';
      53     9451001 :                 *new_path = p+1;
      54             :         }
      55             : 
      56    11835913 :         return True;
      57             : }
      58             : 
      59             : /**************************************************************************
      60             :  Initialize the tree's root.
      61             :  *************************************************************************/
      62             : 
      63         891 : struct sorted_tree *pathtree_init(void *data_p)
      64             : {
      65         891 :         struct sorted_tree *tree = NULL;
      66             : 
      67         891 :         tree = talloc_zero(NULL, struct sorted_tree);
      68         891 :         if (tree == NULL) {
      69           0 :                 return NULL;
      70             :         }
      71             : 
      72         891 :         tree->root = talloc_zero(tree, struct tree_node);
      73         891 :         if (tree->root == NULL) {
      74           0 :                 TALLOC_FREE( tree );
      75           0 :                 return NULL;
      76             :         }
      77             : 
      78         891 :         tree->root->data_p = data_p;
      79             : 
      80         891 :         return tree;
      81             : }
      82             : 
      83             : 
      84             : /**************************************************************************
      85             :  Find the next child given a key string
      86             :  *************************************************************************/
      87             : 
      88        4364 : static struct tree_node *pathtree_birth_child(struct tree_node *node,
      89             :                                               char* key )
      90             : {
      91        4364 :         struct tree_node *infant = NULL;
      92             :         struct tree_node **siblings;
      93             :         int i;
      94             : 
      95        4364 :         infant = talloc_zero(node, struct tree_node);
      96        4364 :         if (infant == NULL) {
      97           0 :                 return NULL;
      98             :         }
      99             : 
     100        4364 :         infant->key = talloc_strdup( infant, key );
     101        4364 :         infant->parent = node;
     102             : 
     103        4364 :         siblings = talloc_realloc(node, node->children, struct tree_node *,
     104             :                                   node->num_children+1);
     105             : 
     106        4364 :         if ( siblings )
     107        4364 :                 node->children = siblings;
     108             : 
     109        4364 :         node->num_children++;
     110             : 
     111             :         /* first child */
     112             : 
     113        4364 :         if ( node->num_children == 1 ) {
     114        3764 :                 DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n", 
     115             :                         node->key ? node->key : "NULL", infant->key ));
     116        3764 :                 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         880 :                 for ( i = node->num_children-1; i>=1; i-- )
     130             :                 {
     131         660 :                         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         660 :                         if ( strcasecmp_m( infant->key, node->children[i-1]->key ) > 0 ) {
     138         360 :                                 DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n", 
     139             :                                         i));
     140         360 :                                 node->children[i] = infant;
     141         360 :                                 break;
     142             :                         }
     143             : 
     144             :                         /* bump everything towards the end on slot */
     145             : 
     146         300 :                         node->children[i] = node->children[i-1];
     147             :                 }
     148             : 
     149         600 :                 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         600 :                 if ( i == 0 )
     155         240 :                         node->children[0] = infant;
     156             :         }
     157             : 
     158        4312 :         return infant;
     159             : }
     160             : 
     161             : /**************************************************************************
     162             :  Find the next child given a key string
     163             :  *************************************************************************/
     164             : 
     165    11843293 : static struct tree_node *pathtree_find_child(struct tree_node *node,
     166             :                                              char *key )
     167             : {
     168    11843293 :         struct tree_node *next = NULL;
     169             :         int i, result;
     170             : 
     171    11843293 :         if ( !node ) {
     172           0 :                 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
     173           0 :                 return NULL;
     174             :         }
     175             : 
     176    11843293 :         if ( !key ) {
     177           0 :                 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
     178           0 :                 return NULL;
     179             :         }
     180             : 
     181    24004162 :         for ( i=0; i<node->num_children; i++ )
     182             :         {       
     183    17157702 :                 DEBUG(11,("pathtree_find_child: child key => [%s]\n",
     184             :                         node->children[i]->key));
     185             : 
     186    17157702 :                 result = strcasecmp_m( node->children[i]->key, key );
     187             : 
     188    17157702 :                 if ( result == 0 )
     189     9742355 :                         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    17157702 :                 if ( result > 0 )
     196     4996153 :                         break;
     197             :         }
     198             : 
     199    11843293 :         DEBUG(11,("pathtree_find_child: %s [%s]\n",
     200             :                 next ? "Found" : "Did not find", key ));    
     201             : 
     202    11842775 :         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        1493 : 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        1493 :         bool ret = true;
     214             : 
     215        1493 :         DEBUG(8,("pathtree_add: Enter\n"));
     216             : 
     217        1493 :         if ( !path || *path != '\\' ) {
     218           0 :                 DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
     219             :                         path ? path : "NULL" ));
     220           0 :                 return false;
     221             :         }
     222             : 
     223        1493 :         if ( !tree ) {
     224           0 :                 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
     225           0 :                 return false;
     226             :         }
     227             : 
     228             :         /* move past the first '\\' */
     229             : 
     230        1493 :         path++; 
     231        1493 :         path2 = SMB_STRDUP( path );
     232        1493 :         if ( !path2 ) {
     233           0 :                 DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
     234           0 :                 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        1493 :         base = path2;
     245        1493 :         str  = path2;
     246        1493 :         current = tree->root;
     247             : 
     248             :         do {
     249             :                 /* break off the remaining part of the path */
     250             : 
     251        6992 :                 str = strchr( str, '\\' );
     252        6992 :                 if ( str )
     253        5499 :                         *str = '\0';
     254             : 
     255             :                 /* iterate to the next child--birth it if necessary */
     256             : 
     257        6992 :                 next = pathtree_find_child( current, base );
     258        6992 :                 if ( !next ) {
     259        4364 :                         next = pathtree_birth_child( current, base );
     260        4364 :                         if ( !next ) {
     261           0 :                                 DEBUG(0,("pathtree_add: Failed to create new child!\n"));
     262           0 :                                 ret = false;
     263           0 :                                 goto done;
     264             :                         }
     265             :                 }
     266        6992 :                 current = next;
     267             : 
     268             :                 /* setup the next part of the path */
     269             : 
     270        6992 :                 base = str;
     271        6992 :                 if ( base ) {
     272        5499 :                         *base = '\\';
     273        5499 :                         base++;
     274        5499 :                         str = base;
     275             :                 }
     276             : 
     277        6992 :         } while ( base != NULL );
     278             : 
     279        1493 :         current->data_p = data_p;
     280             : 
     281        1493 :         DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
     282             :                 path ));
     283             : 
     284        1493 :         DEBUG(8,("pathtree_add: Exit\n"));
     285             : 
     286        1493 : done:
     287        1493 :         SAFE_FREE( path2 );
     288        1493 :         return ret;
     289             : }
     290             : 
     291             : 
     292             : /**************************************************************************
     293             :  Recursive routine to print out all children of a struct tree_node
     294             :  *************************************************************************/
     295             : 
     296           0 : 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           0 :         char *path2 = NULL;
     304             : 
     305           0 :         if ( !node )
     306           0 :                 return;
     307             : 
     308           0 :         if ( node->key )
     309           0 :                 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
     310             :                         node->data_p ? "data" : "NULL" ));
     311             : 
     312           0 :         if ( path ) {
     313           0 :                 path2 = talloc_strdup(ctx, path);
     314           0 :                 if (!path2) {
     315           0 :                         return;
     316             :                 }
     317             :         }
     318             : 
     319           0 :         path2 = talloc_asprintf(ctx,
     320             :                         "%s%s/",
     321             :                         path ? path : "",
     322           0 :                         node->key ? node->key : "NULL");
     323           0 :         if (!path2) {
     324           0 :                 return;
     325             :         }
     326             : 
     327           0 :         num_children = node->num_children;
     328           0 :         for ( i=0; i<num_children; i++ ) {
     329           0 :                 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           0 : void pathtree_print_keys(struct sorted_tree *tree, int debug )
     338             : {
     339             :         int i;
     340           0 :         int num_children = tree->root->num_children;
     341             : 
     342           0 :         if ( tree->root->key )
     343           0 :                 DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
     344             :                         tree->root->data_p ? "data" : "NULL" ));
     345             : 
     346           0 :         for ( i=0; i<num_children; i++ ) {
     347           0 :                 TALLOC_CTX *ctx = talloc_stackframe();
     348           0 :                 pathtree_print_children(ctx, tree->root->children[i], debug,
     349           0 :                         tree->root->key ? tree->root->key : "ROOT/" );
     350           0 :                 TALLOC_FREE(ctx);
     351             :         }
     352             : 
     353           0 : }
     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     2412992 : void* pathtree_find(struct sorted_tree *tree, char *key )
     362             : {
     363     2412992 :         char *keystr, *base = NULL, *str = NULL, *p;
     364             :         struct tree_node *current;
     365     2412992 :         void *result = NULL;
     366             : 
     367     2412992 :         DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
     368             : 
     369             :         /* sanity checks first */
     370             : 
     371     2412992 :         if ( !key ) {
     372           0 :                 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
     373           0 :                 return NULL;
     374             :         }
     375             : 
     376     2412992 :         if ( !tree ) {
     377           0 :                 DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
     378             :                         key ? key : "NULL" ));
     379           0 :                 return NULL;
     380             :         }
     381             : 
     382     2412992 :         if ( !tree->root )
     383           0 :                 return NULL;
     384             : 
     385             :         /* make a copy to play with */
     386             : 
     387     2412992 :         if ( *key == '\\' )
     388     2412992 :                 keystr = SMB_STRDUP( key+1 );
     389             :         else
     390           0 :                 keystr = SMB_STRDUP( key );
     391             : 
     392     2412992 :         if ( !keystr ) {
     393           0 :                 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
     394           0 :                 return NULL;
     395             :         }
     396             : 
     397             :         /* start breaking the path apart */
     398             : 
     399     2412992 :         p = keystr;
     400     2412992 :         current = tree->root;
     401             : 
     402     2412992 :         if ( tree->root->data_p )
     403     2412992 :                 result = tree->root->data_p;
     404             : 
     405             :         do
     406             :         {
     407             :                 /* break off the remaining part of the path */
     408             : 
     409    11836301 :                 trim_tree_keypath( p, &base, &str );
     410             : 
     411    11836301 :                 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    11836301 :                 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    11836301 :                 if ( current && current->data_p )
     426     2293209 :                         result = current->data_p;
     427             : 
     428             :                 /* reset the path pointer 'p' to the remaining part of the key string */
     429             : 
     430    11836301 :                 p = str;
     431             : 
     432    11836301 :         } while ( str && current );
     433             : 
     434             :         /* result should be the data_p from the lowest match node in the tree */
     435     2412992 :         if ( result )
     436     2412992 :                 DEBUG(11,("pathtree_find: Found data_p!\n"));
     437             : 
     438     2412992 :         SAFE_FREE( keystr );
     439             : 
     440     2412992 :         DEBUG(10,("pathtree_find: Exit\n"));
     441             : 
     442     2412888 :         return result;
     443             : }
     444             : 
     445             : 

Generated by: LCOV version 1.13