Ignore:
Timestamp:
Nov 27, 2012, 4:43:17 PM (13 years ago)
Author:
Silvan Scherrer
Message:

Samba Server: updated trunk to 3.6.0

Location:
trunk/server
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/server

  • trunk/server/source3/lib/adt_tree.c

    r414 r745  
    2121#include "adt_tree.h"
    2222
     23struct 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
     31struct sorted_tree {
     32        struct tree_node *root;
     33};
    2334
    2435/**************************************************************************
    … …  
    2839{
    2940        char *p;
    30        
     41
    3142        *new_path = *base = NULL;
    32        
     43
    3344        if ( !path )
    3445                return False;
    35        
     46
    3647        *base = path;
    37        
    38         p = strchr( path, '/' );
    39        
     48
     49        p = strchr( path, '\\' );
     50
    4051        if ( p ) {
    4152                *p = '\0';
    4253                *new_path = p+1;
    4354        }
    44        
     55
    4556        return True;
    4657}
    4758
    48  
    49 /**************************************************************************
    50  Initialize the tree's root.  The cmp_fn is a callback function used
    51  for comparision of two children
    52  *************************************************************************/
    53 
    54  SORTED_TREE* pathtree_init( void *data_p, int (cmp_fn)(void*, void*) )
    55 {
    56         SORTED_TREE *tree = NULL;
    57        
    58         if ( !(tree = TALLOC_ZERO_P(NULL, SORTED_TREE)) )
    59                 return NULL;
    60                
    61         tree->compare = cmp_fn;
    62        
    63         if ( !(tree->root = TALLOC_ZERO_P(tree, TREE_NODE)) ) {
     59/**************************************************************************
     60 Initialize the tree's root.
     61 *************************************************************************/
     62
     63struct 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) {
    6474                TALLOC_FREE( tree );
    6575                return NULL;
    6676        }
    67        
     77
    6878        tree->root->data_p = data_p;
    69        
     79
    7080        return tree;
    7181}
    … …  
    7686 *************************************************************************/
    7787
    78 static TREE_NODE* pathtree_birth_child( TREE_NODE *node, char* key )
    79 {
    80         TREE_NODE *infant = NULL;
    81         TREE_NODE **siblings;
     88static 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;
    8293        int i;
    83        
    84         if ( !(infant = TALLOC_ZERO_P( node, TREE_NODE)) )
    85                 return NULL;
    86        
     94
     95        infant = talloc_zero(node, struct tree_node);
     96        if (infant == NULL) {
     97                return NULL;
     98        }
     99
    87100        infant->key = talloc_strdup( infant, key );
    88101        infant->parent = node;
    89        
    90         siblings = TALLOC_REALLOC_ARRAY( node, node->children, TREE_NODE *, node->num_children+1 );
    91        
     102
     103        siblings = talloc_realloc(node, node->children, struct tree_node *,
     104                                  node->num_children+1);
     105
    92106        if ( siblings )
    93107                node->children = siblings;
    94        
     108
    95109        node->num_children++;
    96        
     110
    97111        /* first child */
    98        
     112
    99113        if ( node->num_children == 1 ) {
    100114                DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
    … …  
    112126                 * from left to right
    113127                 */
    114        
     128
    115129                for ( i = node->num_children-1; i>=1; i-- )
    116130                {
    117131                        DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
    118132                                infant->key, node->children[i-1]->key));
    119                        
     133
    120134                        /* the strings should never match assuming that we
    121135                           have called pathtree_find_child() first */
    122                
     136
    123137                        if ( StrCaseCmp( infant->key, node->children[i-1]->key ) > 0 ) {
    124138                                DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
    … …  
    127141                                break;
    128142                        }
    129                        
     143
    130144                        /* bump everything towards the end on slot */
    131                        
     145
    132146                        node->children[i] = node->children[i-1];
    133147                }
    134148
    135149                DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i ));
    136                
     150
    137151                /* if we haven't found the correct slot yet, the child
    138152                   will be first in the list */
    139                    
     153
    140154                if ( i == 0 )
    141155                        node->children[0] = infant;
    … …  
    149163 *************************************************************************/
    150164
    151 static TREE_NODE* pathtree_find_child( TREE_NODE *node, char* key )
    152 {
    153         TREE_NODE *next = NULL;
     165static struct tree_node *pathtree_find_child(struct tree_node *node,
     166                                             char *key )
     167{
     168        struct tree_node *next = NULL;
    154169        int i, result;
    155        
     170
    156171        if ( !node ) {
    157172                DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
    158173                return NULL;
    159174        }
    160        
     175
    161176        if ( !key ) {
    162177                DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
    163178                return NULL;
    164179        }
    165        
     180
    166181        for ( i=0; i<node->num_children; i++ )
    167182        {       
    168183                DEBUG(11,("pathtree_find_child: child key => [%s]\n",
    169184                        node->children[i]->key));
    170                        
     185
    171186                result = StrCaseCmp( node->children[i]->key, key );
    172                
     187
    173188                if ( result == 0 )
    174189                        next = node->children[i];
    175                
     190
    176191                /* if result > 0 then we've gone to far because
    177192                   the list of children is sorted by key name
    178193                   If result == 0, then we have a match         */
    179                    
     194
    180195                if ( result > 0 )
    181196                        break;
    … …  
    184199        DEBUG(11,("pathtree_find_child: %s [%s]\n",
    185200                next ? "Found" : "Did not find", key ));       
    186        
     201
    187202        return next;
    188203}
    … …  
    192207 *************************************************************************/
    193208
    194  WERROR pathtree_add( SORTED_TREE *tree, const char *path, void *data_p )
     209WERROR pathtree_add(struct sorted_tree *tree, const char *path, void *data_p)
    195210{
    196211        char *str, *base, *path2;
    197         TREE_NODE *current, *next;
     212        struct tree_node *current, *next;
    198213        WERROR ret = WERR_OK;
    199        
     214
    200215        DEBUG(8,("pathtree_add: Enter\n"));
    201                
    202         if ( !path || *path != '/' ) {
     216
     217        if ( !path || *path != '\\' ) {
    203218                DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
    204219                        path ? path : "NULL" ));
    205220                return WERR_INVALID_PARAM;
    206221        }
    207        
     222
    208223        if ( !tree ) {
    209224                DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
    210225                return WERR_INVALID_PARAM;
    211226        }
    212        
    213         /* move past the first '/' */
    214        
     227
     228        /* move past the first '\\' */
     229
    215230        path++;
    216231        path2 = SMB_STRDUP( path );
    … …  
    219234                return WERR_NOMEM;
    220235        }
    221        
     236
    222237
    223238        /*
    … …  
    226241         * The path should be of the form /<key1>/<key2>/...
    227242         */
    228        
     243
    229244        base = path2;
    230245        str  = path2;
    231246        current = tree->root;
    232        
     247
    233248        do {
    234249                /* break off the remaining part of the path */
    235                
    236                 str = strchr( str, '/' );
     250
     251                str = strchr( str, '\\' );
    237252                if ( str )
    238253                        *str = '\0';
    239                        
     254
    240255                /* iterate to the next child--birth it if necessary */
    241                
     256
    242257                next = pathtree_find_child( current, base );
    243258                if ( !next ) {
    … …  
    250265                }
    251266                current = next;
    252                
     267
    253268                /* setup the next part of the path */
    254                
     269
    255270                base = str;
    256271                if ( base ) {
    257                         *base = '/';
     272                        *base = '\\';
    258273                        base++;
    259274                        str = base;
    260275                }
    261        
     276
    262277        } while ( base != NULL );
    263        
     278
    264279        current->data_p = data_p;
    265        
     280
    266281        DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
    267282                path ));
    … …  
    276291
    277292/**************************************************************************
    278  Recursive routine to print out all children of a TREE_NODE
     293 Recursive routine to print out all children of a struct tree_node
    279294 *************************************************************************/
    280295
    281296static void pathtree_print_children(TALLOC_CTX *ctx,
    282                                 TREE_NODE *node,
     297                                struct tree_node *node,
    283298                                int debug,
    284299                                const char *path )
    … …  
    320335 *************************************************************************/
    321336
    322  void pathtree_print_keys( SORTED_TREE *tree, int debug )
     337void pathtree_print_keys(struct sorted_tree *tree, int debug )
    323338{
    324339        int i;
    … …  
    344359 *************************************************************************/
    345360
    346  void* pathtree_find( SORTED_TREE *tree, char *key )
     361void* pathtree_find(struct sorted_tree *tree, char *key )
    347362{
    348363        char *keystr, *base = NULL, *str = NULL, *p;
    349         TREE_NODE *current;
     364        struct tree_node *current;
    350365        void *result = NULL;
    351        
     366
    352367        DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
    353368
    354369        /* sanity checks first */
    355        
     370
    356371        if ( !key ) {
    357372                DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
    358373                return NULL;
    359374        }
    360        
     375
    361376        if ( !tree ) {
    362377                DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
    … …  
    364379                return NULL;
    365380        }
    366        
     381
    367382        if ( !tree->root )
    368383                return NULL;
    369        
     384
    370385        /* make a copy to play with */
    371        
    372         if ( *key == '/' )
     386
     387        if ( *key == '\\' )
    373388                keystr = SMB_STRDUP( key+1 );
    374389        else
    375390                keystr = SMB_STRDUP( key );
    376        
     391
    377392        if ( !keystr ) {
    378393                DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
    … …  
    381396
    382397        /* start breaking the path apart */
    383        
     398
    384399        p = keystr;
    385400        current = tree->root;
    386        
     401
    387402        if ( tree->root->data_p )
    388403                result = tree->root->data_p;
    389                
     404
    390405        do
    391406        {
    … …  
    393408
    394409                trim_tree_keypath( p, &base, &str );
    395                        
     410
    396411                DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n",
    397412                        base ? base : "",
    … …  
    399414
    400415                /* iterate to the next child */
    401                
     416
    402417                current = pathtree_find_child( current, base );
    403        
     418
    404419                /*
    405420                 * the idea is that the data_p for a parent should
    … …  
    407422                 * overridden farther down
    408423                 */
    409                
     424
    410425                if ( current && current->data_p )
    411426                        result = current->data_p;
    … …  
    414429
    415430                p = str;
    416            
     431
    417432        } while ( str && current );
    418        
     433
    419434        /* result should be the data_p from the lowest match node in the tree */
    420435        if ( result )
    421436                DEBUG(11,("pathtree_find: Found data_p!\n"));
    422        
     437
    423438        SAFE_FREE( keystr );
    424        
     439
    425440        DEBUG(10,("pathtree_find: Exit\n"));
    426        
     441
    427442        return result;
    428443}
Note: See TracChangeset for help on using the changeset viewer.