Changeset 14785

Show
Ignore:
Timestamp:
06/28/08 19:36:56 (5 months ago)
Author:
rouault
Message:

Improve performance of CPLParseXMLString from O(n*n) to O(n) where n is the number of siblings node

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/gdal/port/cpl_minixml.cpp

    r14693 r14785  
    6060} XMLTokenType; 
    6161 
     62typedef struct 
     63{ 
     64    CPLXMLNode *psFirstNode; 
     65    CPLXMLNode *psLastChild; 
     66} StackContext; 
     67 
    6268typedef struct { 
    6369    const char *pszInput; 
    …… 
    7278    int        nStackMaxSize; 
    7379    int        nStackSize; 
    74     CPLXMLNode **papsStack; 
     80    StackContext *papsStack; 
    7581 
    7682    CPLXMLNode *psFirstNode; 
     83    CPLXMLNode *psLastNode; 
    7784} ParseContext; 
    7885 
    …… 
    441448    { 
    442449        psContext->nStackMaxSize += 10; 
    443         psContext->papsStack = (CPLXMLNode **) 
     450        psContext->papsStack = (StackContext *) 
    444451            CPLRealloc(psContext->papsStack,  
    445                        sizeof(CPLXMLNode*) * psContext->nStackMaxSize); 
    446     } 
    447  
    448     psContext->papsStack[psContext->nStackSize++] = psNode; 
     452                       sizeof(StackContext) * psContext->nStackMaxSize); 
     453    } 
     454 
     455    psContext->papsStack[psContext->nStackSize].psFirstNode = psNode; 
     456    psContext->papsStack[psContext->nStackSize].psLastChild = NULL; 
     457    psContext->nStackSize ++; 
    449458} 
    450459     
    …… 
    461470{ 
    462471    if( psContext->psFirstNode == NULL ) 
     472    { 
    463473        psContext->psFirstNode = psNode; 
     474        psContext->psLastNode = psNode; 
     475    } 
    464476    else if( psContext->nStackSize == 0 ) 
    465477    { 
    466         CPLXMLNode *psSibling; 
    467  
    468         psSibling = psContext->psFirstNode; 
    469         while( psSibling->psNext != NULL ) 
    470             psSibling = psSibling->psNext; 
    471         psSibling->psNext = psNode; 
    472     } 
    473     else if( psContext->papsStack[psContext->nStackSize-1]->psChild == NULL ) 
    474     { 
    475         psContext->papsStack[psContext->nStackSize-1]->psChild = psNode; 
     478        psContext->psLastNode->psNext = psNode; 
     479        psContext->psLastNode = psNode; 
     480    } 
     481    else if( psContext->papsStack[psContext->nStackSize-1].psFirstNode->psChild == NULL ) 
     482    { 
     483        psContext->papsStack[psContext->nStackSize-1].psFirstNode->psChild = psNode; 
     484        psContext->papsStack[psContext->nStackSize-1].psLastChild = psNode; 
    476485    } 
    477486    else 
    478487    { 
    479         CPLXMLNode *psSibling; 
    480  
    481         psSibling = psContext->papsStack[psContext->nStackSize-1]->psChild; 
    482         while( psSibling->psNext != NULL ) 
    483             psSibling = psSibling->psNext; 
    484         psSibling->psNext = psNode; 
     488        psContext->papsStack[psContext->nStackSize-1].psLastChild->psNext = psNode; 
     489        psContext->papsStack[psContext->nStackSize-1].psLastChild = psNode; 
    485490    } 
    486491} 
    …… 
    542547    sContext.papsStack = NULL; 
    543548    sContext.psFirstNode = NULL; 
     549    sContext.psLastNode = NULL; 
    544550 
    545551    /* ensure token is initialized */ 
    …… 
    577583                if( sContext.nStackSize == 0 
    578584                    || !EQUAL(sContext.pszToken+1, 
    579                          sContext.papsStack[sContext.nStackSize-1]->pszValue) ) 
     585                         sContext.papsStack[sContext.nStackSize-1].psFirstNode->pszValue) ) 
    580586                { 
    581587                    CPLError( CE_Failure, CPLE_AppDefined,  
    …… 
    676682                break; 
    677683            } 
    678             else if( sContext.papsStack[sContext.nStackSize-1]->pszValue[0] != '?' ) 
     684            else if( sContext.papsStack[sContext.nStackSize-1].psFirstNode->pszValue[0] != '?' ) 
    679685            { 
    680686                CPLError( CE_Failure, CPLE_AppDefined,  
    …… 
    741747                  "Parse error at EOF, not all elements have been closed,\n" 
    742748                  "starting with %.500s\n",  
    743                   sContext.papsStack[sContext.nStackSize-1]->pszValue ); 
     749                  sContext.papsStack[sContext.nStackSize-1].psFirstNode->pszValue ); 
    744750    } 
    745751 
    …… 
    755761        CPLDestroyXMLNode( sContext.psFirstNode ); 
    756762        sContext.psFirstNode = NULL; 
     763        sContext.psLastNode = NULL; 
    757764    } 
    758765