LCOV - code coverage report
Current view: top level - source3/lib - adt_tree.c (source / functions) Hit Total Coverage
Test: coverage report for master 2b515b7d Lines: 120 176 68.2 %
Date: 2024-02-28 12: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 "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    19170506 : static bool trim_tree_keypath( char *path, char **base, char **new_path )
      44             : {
      45         859 :         char *p;
      46             : 
      47    19170506 :         *new_path = *base = NULL;
      48             : 
      49    19170506 :         if ( !path )
      50           0 :                 return false;
      51             : 
      52    19170506 :         *base = path;
      53             : 
      54    19170506 :         p = strchr( path, '\\' );
      55             : 
      56    19170506 :         if ( p ) {
      57    15316128 :                 *p = '\0';
      58    15316128 :                 *new_path = p+1;
      59             :         }
      60             : 
      61    19169647 :         return true;
      62             : }
      63             : 
      64             : /**************************************************************************
      65             :  Initialize the tree's root.
      66             :  *************************************************************************/
      67             : 
      68        1223 : struct sorted_tree *pathtree_init(void *data_p)
      69             : {
      70        1223 :         struct sorted_tree *tree = NULL;
      71             : 
      72        1223 :         tree = talloc_zero(NULL, struct sorted_tree);
      73        1223 :         if (tree == NULL) {
      74           0 :                 return NULL;
      75             :         }
      76             : 
      77        1223 :         tree->root = talloc_zero(tree, struct tree_node);
      78        1223 :         if (tree->root == NULL) {
      79           0 :                 TALLOC_FREE( tree );
      80           0 :                 return NULL;
      81             :         }
      82             : 
      83        1223 :         tree->root->data_p = data_p;
      84             : 
      85        1223 :         return tree;
      86             : }
      87             : 
      88             : 
      89             : /**************************************************************************
      90             :  Find the next child given a key string
      91             :  *************************************************************************/
      92             : 
      93        8486 : static struct tree_node *pathtree_birth_child(struct tree_node *node,
      94             :                                               char* key )
      95             : {
      96        8486 :         struct tree_node *infant = NULL;
      97           4 :         struct tree_node **siblings;
      98           4 :         int i;
      99             : 
     100        8486 :         infant = talloc_zero(node, struct tree_node);
     101        8486 :         if (infant == NULL) {
     102           0 :                 return NULL;
     103             :         }
     104             : 
     105        8486 :         infant->key = talloc_strdup( infant, key );
     106        8486 :         infant->parent = node;
     107             : 
     108        8486 :         siblings = talloc_realloc(node, node->children, struct tree_node *,
     109             :                                   node->num_children+1);
     110             : 
     111        8486 :         if ( siblings )
     112        8486 :                 node->children = siblings;
     113             : 
     114        8486 :         node->num_children++;
     115             : 
     116             :         /* first child */
     117             : 
     118        8486 :         if ( node->num_children == 1 ) {
     119        6616 :                 DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
     120             :                         node->key ? node->key : "NULL", infant->key ));
     121        6616 :                 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        2805 :                 for ( i = node->num_children-1; i>=1; i-- )
     135             :                 {
     136        2057 :                         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        2057 :                         if ( strcasecmp_m( infant->key, node->children[i-1]->key ) > 0 ) {
     143        1122 :                                 DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
     144             :                                         i));
     145        1122 :                                 node->children[i] = infant;
     146        1122 :                                 break;
     147             :                         }
     148             : 
     149             :                         /* bump everything towards the end on slot */
     150             : 
     151         935 :                         node->children[i] = node->children[i-1];
     152             :                 }
     153             : 
     154        1870 :                 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        1870 :                 if ( i == 0 )
     160         748 :                         node->children[0] = infant;
     161             :         }
     162             : 
     163        8482 :         return infant;
     164             : }
     165             : 
     166             : /**************************************************************************
     167             :  Find the next child given a key string
     168             :  *************************************************************************/
     169             : 
     170    19186905 : static struct tree_node *pathtree_find_child(struct tree_node *node,
     171             :                                              char *key )
     172             : {
     173    19186905 :         struct tree_node *next = NULL;
     174         907 :         int i, result;
     175             : 
     176    19186905 :         if ( !node ) {
     177           0 :                 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
     178           0 :                 return NULL;
     179             :         }
     180             : 
     181    19186905 :         if ( !key ) {
     182           0 :                 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
     183           0 :                 return NULL;
     184             :         }
     185             : 
     186    38595120 :         for ( i=0; i<node->num_children; i++ )
     187             :         {
     188    27127642 :                 DEBUG(11,("pathtree_find_child: child key => [%s]\n",
     189             :                         node->children[i]->key));
     190             : 
     191    27127642 :                 result = strcasecmp_m( node->children[i]->key, key );
     192             : 
     193    27127642 :                 if ( result == 0 )
     194    15625422 :                         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    27127642 :                 if ( result > 0 )
     201     7719427 :                         break;
     202             :         }
     203             : 
     204    19186905 :         DEBUG(11,("pathtree_find_child: %s [%s]\n",
     205             :                 next ? "Found" : "Did not find", key ));
     206             : 
     207    19185998 :         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        3305 : bool pathtree_add(struct sorted_tree *tree, const char *path, void *data_p)
     215             : {
     216          12 :         char *str, *base, *path2;
     217          12 :         struct tree_node *current, *next;
     218        3305 :         bool ret = true;
     219             : 
     220        3305 :         DEBUG(8,("pathtree_add: Enter\n"));
     221             : 
     222        3305 :         if ( !path || *path != '\\' ) {
     223           0 :                 DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
     224             :                         path ? path : "NULL" ));
     225           0 :                 return false;
     226             :         }
     227             : 
     228        3305 :         if ( !tree ) {
     229           0 :                 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
     230           0 :                 return false;
     231             :         }
     232             : 
     233             :         /* move past the first '\\' */
     234             : 
     235        3305 :         path++;
     236        3305 :         path2 = SMB_STRDUP( path );
     237        3305 :         if ( !path2 ) {
     238           0 :                 DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
     239           0 :                 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        3305 :         base = path2;
     250        3305 :         str  = path2;
     251        3305 :         current = tree->root;
     252             : 
     253          48 :         do {
     254             :                 /* break off the remaining part of the path */
     255             : 
     256       16399 :                 str = strchr( str, '\\' );
     257       16399 :                 if ( str )
     258       13094 :                         *str = '\0';
     259             : 
     260             :                 /* iterate to the next child--birth it if necessary */
     261             : 
     262       16399 :                 next = pathtree_find_child( current, base );
     263       16399 :                 if ( !next ) {
     264        8486 :                         next = pathtree_birth_child( current, base );
     265        8486 :                         if ( !next ) {
     266           0 :                                 DEBUG(0,("pathtree_add: Failed to create new child!\n"));
     267           0 :                                 ret = false;
     268           0 :                                 goto done;
     269             :                         }
     270             :                 }
     271       16399 :                 current = next;
     272             : 
     273             :                 /* setup the next part of the path */
     274             : 
     275       16399 :                 base = str;
     276       16399 :                 if ( base ) {
     277       13094 :                         *base = '\\';
     278       13094 :                         base++;
     279       13094 :                         str = base;
     280             :                 }
     281             : 
     282       16399 :         } while ( base != NULL );
     283             : 
     284        3305 :         current->data_p = data_p;
     285             : 
     286        3305 :         DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
     287             :                 path ));
     288             : 
     289        3305 :         DEBUG(8,("pathtree_add: Exit\n"));
     290             : 
     291        3305 : done:
     292        3305 :         SAFE_FREE( path2 );
     293        3305 :         return ret;
     294             : }
     295             : 
     296             : 
     297             : /**************************************************************************
     298             :  Recursive routine to print out all children of a struct tree_node
     299             :  *************************************************************************/
     300             : 
     301           0 : static void pathtree_print_children(TALLOC_CTX *ctx,
     302             :                                 struct tree_node *node,
     303             :                                 int debug,
     304             :                                 const char *path )
     305             : {
     306           0 :         int i;
     307           0 :         int num_children;
     308           0 :         char *path2 = NULL;
     309             : 
     310           0 :         if ( !node )
     311           0 :                 return;
     312             : 
     313           0 :         if ( node->key )
     314           0 :                 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
     315             :                         node->data_p ? "data" : "NULL" ));
     316             : 
     317           0 :         if ( path ) {
     318           0 :                 path2 = talloc_strdup(ctx, path);
     319           0 :                 if (!path2) {
     320           0 :                         return;
     321             :                 }
     322             :         }
     323             : 
     324           0 :         path2 = talloc_asprintf(ctx,
     325             :                         "%s%s/",
     326             :                         path ? path : "",
     327           0 :                         node->key ? node->key : "NULL");
     328           0 :         if (!path2) {
     329           0 :                 return;
     330             :         }
     331             : 
     332           0 :         num_children = node->num_children;
     333           0 :         for ( i=0; i<num_children; i++ ) {
     334           0 :                 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           0 : void pathtree_print_keys(struct sorted_tree *tree, int debug )
     343             : {
     344           0 :         int i;
     345           0 :         int num_children = tree->root->num_children;
     346             : 
     347           0 :         if ( tree->root->key )
     348           0 :                 DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
     349             :                         tree->root->data_p ? "data" : "NULL" ));
     350             : 
     351           0 :         for ( i=0; i<num_children; i++ ) {
     352           0 :                 TALLOC_CTX *ctx = talloc_stackframe();
     353           0 :                 pathtree_print_children(ctx, tree->root->children[i], debug,
     354           0 :                         tree->root->key ? tree->root->key : "ROOT/" );
     355           0 :                 TALLOC_FREE(ctx);
     356             :         }
     357             : 
     358           0 : }
     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     3874879 : void* pathtree_find(struct sorted_tree *tree, char *key )
     367             : {
     368     3874879 :         char *keystr, *base = NULL, *str = NULL, *p;
     369         220 :         struct tree_node *current;
     370     3874879 :         void *result = NULL;
     371             : 
     372     3874879 :         DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
     373             : 
     374             :         /* sanity checks first */
     375             : 
     376     3874879 :         if ( !key ) {
     377           0 :                 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
     378           0 :                 return NULL;
     379             :         }
     380             : 
     381     3874879 :         if ( !tree ) {
     382           0 :                 DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
     383             :                         key ? key : "NULL" ));
     384           0 :                 return NULL;
     385             :         }
     386             : 
     387     3874879 :         if ( !tree->root )
     388           0 :                 return NULL;
     389             : 
     390             :         /* make a copy to play with */
     391             : 
     392     3874879 :         if ( *key == '\\' )
     393     3874879 :                 keystr = SMB_STRDUP( key+1 );
     394             :         else
     395           0 :                 keystr = SMB_STRDUP( key );
     396             : 
     397     3874879 :         if ( !keystr ) {
     398           0 :                 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
     399           0 :                 return NULL;
     400             :         }
     401             : 
     402             :         /* start breaking the path apart */
     403             : 
     404     3874879 :         p = keystr;
     405     3874879 :         current = tree->root;
     406             : 
     407     3874879 :         if ( tree->root->data_p )
     408     3874879 :                 result = tree->root->data_p;
     409             : 
     410         859 :         do
     411             :         {
     412             :                 /* break off the remaining part of the path */
     413             : 
     414    19170506 :                 trim_tree_keypath( p, &base, &str );
     415             : 
     416    19170506 :                 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    19170506 :                 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    19170506 :                 if ( current && current->data_p )
     431     3760704 :                         result = current->data_p;
     432             : 
     433             :                 /* reset the path pointer 'p' to the remaining part of the key string */
     434             : 
     435    19170506 :                 p = str;
     436             : 
     437    19170506 :         } while ( str && current );
     438             : 
     439             :         /* result should be the data_p from the lowest match node in the tree */
     440     3874879 :         if ( result )
     441     3874879 :                 DEBUG(11,("pathtree_find: Found data_p!\n"));
     442             : 
     443     3874879 :         SAFE_FREE( keystr );
     444             : 
     445     3874879 :         DEBUG(10,("pathtree_find: Exit\n"));
     446             : 
     447     3874659 :         return result;
     448             : }

Generated by: LCOV version 1.14