脚本的最初原型是当年用 fvwm 的时候为了山寨一个生成家目录下的树形结构菜单写的一个广度优先遍历；后来在把文件系统从 ext3 转到 ext4 的时候重新分区，把文件备份到 windows 上，结果还原回来的时候权限都乱了，于是把 queue 整理了一下写成一个单独的脚本用来改权限；后来还实现了一个深度优先遍历的版本。今天把这两个函数都整理一下。一般来说简单的操作用 find + 各种工具就行了，除非是对遍历顺序有要求或操作比较复杂。

#!/bin/bash

# http://ouonline.net/

IFS=$(echo -en "\n\b") # in case of space(s) in dentry name

# -------------------------------------------------------------------------- #

function dfs()
{
    #if [ $# -ne 2 ]; then
        #echo "function call error: dfs callback root_dir" >&2
        #exit -1
    #fi

    callback=$1
    root=$2

    let top=1
    stack[0]="$root" # root dir

    while [ $top -gt 0 ]; do
        let top=$top-1
        parent="${stack[$top]}"
        for i in `ls "$parent"`; do
            fpath="$parent/$i"
            $callback "$fpath" # do whatever you want
            if [ -d "$fpath" ]; then
                stack[$top]="$fpath"
                let top=$top+1
            fi
        done
    done
}

function bfs()
{
    #if [ $# -ne 2 ]; then
        #echo "function call error: bfs callback root_dir" >&2
        #exit -1
    #fi

    callback=$1
    root=$2

    let begin=0
    let end=1
    queue[0]="$root" # root dir

    while [ $begin -lt $end ]; do
        for i in `ls "${queue[$begin]}"`; do
            fpath="${queue[$begin]}/$i"
            $callback "$fpath" # do whatever you want
            if [ -d "$fpath" ]; then
                queue[$end]="$fpath"
                let end=$end+1
            fi  
        done
        unset queue[$begin]
        let begin=$begin+1
    done
}

这里之所以用了“ls dir”而不是用“dir/”这样的格式是因为当 dir 为空的时候直接给的字符串“dir/”而不是不进入循环，这样在循环内还得先判断一下 dentry 是否存在。

这两个函数可以用来做一些复杂一点的遍历工作，例如用来统计代码行数：

let sum=0

function count_line()
{
    if ! [ -d "$1" ]; then
        fname=`basename "$1"`
        ftype=`echo "$fname" | awk -F. '{print $NF}'`
        if [[ $ftype == "c" || $ftype == "cpp" || $ftype == "h" || "$fname" == "Makefile" ]]; then
            let n=`wc -l "$1" | awk '{print $1}'`
            echo -e "$n\t\t$1"
            let sum=$sum+$n
        fi
    fi
}

dfs count_line /path/to/project

echo "----------------------------------------------------"
echo -e "$sum\t\ttotal"

还有当时用来生成 fvwm 菜单的脚本，不过现在已经折腾不动了。

#!/bin/bash

editor="leafpad"
browser="opera"
pdfviewer="kpdf"
picviewer="gpicview"
docviewer="ooffice -writer"
pptviewer=""
videoplayer="gmplayer"
audioplayer="audacious2"
tarviewer=""

# 生成的该目录菜单名称是MainDirMenu

function makemenu()
{
   # makemenu接受四个参数：第一个是目录(注意是绝对路径)，第二个是该目录在队列中的位置，
   # 第三个是该目录下第一个子目录在队列中的位置，第四个是要建立目录列表的根目录名称。

   counter=0

   echo "DestroyMenu $4$2Menu"
   echo "AddToMenu $4$2Menu"

   for i in "$1"/*;do
      fname=`basename "$i"`

      if [ -d "$i" ];then
         echo "+ \"$fname%folder-32.png%\" PopUp `expr $3 + $counter`Menu Item 100 0"
         let counter=$counter+1

      else
         case "`echo $fname | awk -F "." '{print $NF}'`" in # 判断类型
            "pdf")
               echo "+ \"$fname%pdf-32.png%\" Exec exec $pdfviewer \"$i\"";;
            "doc" | "docx" | "odt" | "rtf" | "xml")
               echo "+ \"$fname%document-32.png%\" Exec exec $docviewer \"$i\"";;
            "ppt")
               echo "+ \"$fname%presentation-32.png%\" Exec exec $pptviewer \"$i\"";;
            "jpg" | "png")
               echo "+ \"$fname%image-32.png%\" Exec exec $picviewer \"$i\"";;
            "avi" | "mkv" | "rm" | "rmvb" | "wmv")
               echo "+ \"$fname%video-32.png%\" Exec exec $videoplayer \"$i\"";;
            "mp3" | "wma")
               echo "+ \"$fname%audio-32.png%\" Exec exec $audioplayer \"$i\"";;
            "gz" | "bz2" | "tar" | "zip" | "rar" | "deb" | "rpm")
               echo "+ \"$fname%tarball-32.png%\" Exec exec $tarviewer \"$i\"";;
            "iso")
               echo "+ \"$fname%iso-32.png%\" Exec exec $tarviewer \"$i\"";;
            "htm" | "html" | "mht" | "xml")
               echo "+ \"$fname%html-32.png%\" Exec exec $browser \"$i\"";;
            "exe" | "msi")
               echo "+ \"$fname%bin-32.png%\"";;
            "ttf")
               echo "+ \"$fname%font-32.png%\"";;
            *)
               if [ -f "$i" ] && [ -x "$i" ];then
                  echo "+ \"$fname%script-32.png%\" Exec exec $editor \"$i\""
               else # 不能识别类型的一律用记事本打开
                  echo "+ \"$fname%text-32.png%\" Exec exec $editor \"$i\""
               fi
               ;;
         esac
      fi
   done
}

if [ $# -eq 1 ];then
   makemenu "$1" "" 1 "MainDir" # 生成主目录菜单，第四个参数仅在此处使用
elif [ $# -eq 2 ] && [ "$1" = "-r" ];then
   makemenu "$2" "" 1 "MainDir"
   x=1
   p=0
   queue[0]="$2" # 要生成菜单的主目录入队

   while [ $p -lt $x ];do
      for i in "${queue[$p]}"/*;do
         if [ -d "$i" ];then
            queue[$x]="$i"
            let x=$x+1
         fi
      done
      let p=$p+1
      #if [ $p -lt $x ];then
         makemenu "${queue[$p]}" $p $x "" # x是该目录下第一个子目录的位置，注意第四个参数为空
      #fi
   done
else
   echo "Usage: `basename $0` [ -r ] absolute path(without trailing slash)"
fi