Make WordPress Core

Changeset 32355


Ignore:
Timestamp:
05/05/2015 07:36:58 PM (10 years ago)
Author:
boonebgorges
Message:

Improve performance of get_page_children().

The new algorithm uses a hash table rather than function recursion, reducing
complexity to O(N). On large numbers of pages, the performance improvement is
several orders of magnitude.

Props santagada, hailin, mihai.
Fixes #10852.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/wp-includes/post.php

    r32350 r32355  
    43184318
    43194319/**
    4320  * Retrieve child pages from list of pages matching page ID.
    4321  *
    4322  * Matches against the pages parameter against the page ID. Also matches all
    4323  * children for the same to retrieve all children of a page. Does not make any
    4324  * SQL queries to get the children.
     4320 * Identify descendants of a given page ID in a list of page objects.
     4321 *
     4322 * Descendants are identified from the `$pages` array passed to the function. No database queries are performed.
    43254323 *
    43264324 * @since 1.5.1
    43274325 *
    4328  * @param int   $page_id    Page ID.
    4329  * @param array $pages      List of pages' objects.
     4326 * @param int   $page_id Page ID.
     4327 * @param array $pages   List of page objects from which descendants should be identified.
    43304328 * @return array List of page children.
    43314329 */
    43324330function get_page_children( $page_id, $pages ) {
     4331    // Build a hash of ID -> children.
     4332    $children = array();
     4333    foreach ( (array) $pages as $page ) {
     4334        $children[ intval( $page->post_parent ) ][] = $page;
     4335    }
     4336
    43334337    $page_list = array();
    4334     foreach ( (array) $pages as $page ) {
    4335         if ( $page->post_parent == $page_id ) {
    4336             $page_list[] = $page;
    4337             if ( $children = get_page_children( $page->ID, $pages ) ) {
    4338                 $page_list = array_merge( $page_list, $children );
     4338
     4339    // Start the search by looking at immediate children.
     4340    if ( isset( $children[ $page_id ] ) ) {
     4341        // Always start at the end of the stack in order to preserve original `$pages` order.
     4342        $to_look = array_reverse( $children[ $page_id ] );
     4343
     4344        while ( $to_look ) {
     4345            $p = array_pop( $to_look );
     4346            $page_list[] = $p;
     4347            if ( isset( $children[ $p->ID ] ) ) {
     4348                foreach ( array_reverse( $children[ $p->ID ] ) as $child ) {
     4349                    // Append to the `$to_look` stack to descend the tree.
     4350                    $to_look[] = $child;
     4351                }
    43394352            }
    43404353        }
Note: See TracChangeset for help on using the changeset viewer.