When it comes to deleting a directory tree most solutions that have been posted around are recursive functions, like the following:

function delete_tree($path) {
    foreach(scandir($path) as $item) {
        if($item === '.' && $item === '..') {
            continue;
        }
        if(is_dir($item)) {
            delete_tree($path . '/' . $item);
        } else {
            unlink($path . '/' . $item);
        }
    }
    rmdir($path);
}

While this is easy to implement it has some disadvantages when it comes to large trees:

  • performance critical because high stack usage and many function calls
  • security critical as large trees can break PHP completely

To circumvent this problems it is mostly more useful to create an iterative function to remove the tree. Following the rule every recursion can be replaced by iteration it is surely possible. I usually hack the iterative opposite of an recursive function by implementing the stack on my own – as an array.

Nothing more to say, here comes an iterative version of delete_tree():

function delete_tree($path) {
    $stack = array($path);
    do {
        // get the last element from stack
        $dir = array_pop($stack);
        $stack[]= $dir; // push it back

        foreach (scandir($path) as $item) {
            if(is_dir("$dir/$item")) {
                // push directory on top of the stack
                $stack[]= "$dir/$item";
                continue 2; // continue handling the sub directory
            } else {
                unlink("$dir/$item"); // unlink files
            }   
        }   

        // the folder is now empty. Remove it from stack
        rmdir($dir);
        array_pop($stack);
    } while (!empty($stack));
}

I’m sure the function can be even improved. I’m not happy with so much scandir() calls. This could eventually being cached. Will improve the function if I have more time for this.. Of course I would also appreciate your feedback.

cu!

6 Responses to “Iterative algorithm to remove a directory tree”

  1. David Bruchmann Says:

    Instead of noting:

    foreach (scandir($path) as $file) { … }

    it’s usually advised to note it like this:

    $tmpDir = scandir($path);
    foreach ($tmpDir as $file) { … }

    else theoretically the scandir()-function is called for any entry in the result. As I never looked up how those cases are handled internally by PHP and on level of Assembler I don’t know if the advise is right or if the internal handling changed at some time, but if someone has deeper knowledge it would be nice getting more information about this.

  2. David Bruchmann Says:

    furthermore the usage of the variable $file might be a bit confusing, better is $item as it can be either file or directory

  3. thorsten Says:

    I agree with using $item instead of $file. I’ve changed that.

    Note: scandir() will be called just once when the loop gets initialized. I’ve never heard such advice. It is plain wrong.

  4. Álvaro G. Vicario Says:

    Guilty! I’ve written many recursive file system functions myself. No idea about performance but RecursiveDirectoryIterator can surely be used for this purpose (together with RecursiveIteratorIterator). Here’s a directory listing I wrote while trying to figure out the (fairly counter-intuitive) syntax:


    <?php

    $path = '..........';
    $files = new RecursiveIteratorIterator(
    new RecursiveDirectoryIterator($path),
    RecursiveIteratorIterator::SELF_FIRST
    );
    foreach($files as $name => $object){
    echo sprintf('[%s] %s', $object->isDir() ? 'DIR' : ' ', $name) . "\n";
    }

  5. Álvaro G. Vicario Says:

    Sorry, forum software replaces quotes with fancy ones.

  6. thorsten Says:

    Yes, I’ve to improve the commenting/discussion system you are right. Being able to post, formatted, code would be nice. Also I would like the opportunity that people can login using different accounts (like stackexchange! 😉 … That time I just wanted to keep it simple as possible – and not require a login to comment.

    About the algorithm, yeah, recursive directory iterator is nice, but my attempt was to show how a(ny) recursive algorithm can be replaced by an iterative one, the recursive deletion of a folder was just an example.

Leave a Reply