php natsort內(nèi)核函數(shù)淺析

更新時(shí)間：2009年08月10日 10:32:08 作者：

今天發(fā)現(xiàn)了php有個(gè)自然排序的函數(shù)----natsort，第一次聽說(shuō)了原來(lái)還有一種叫做“自然排序”的算法，很好奇

/* {{{ compare_right 
*/ 
static int 
compare_right(char const **a, char const *aend, char const **b, char const *bend) 
{ 
    int bias = 0; 
    /* The longest run of digits wins. That aside, the greatest 
     value wins, but we can't know that it will until we've scanned 
     both numbers to know that they have the same magnitude, so we 
     remember it in BIAS. */ 
    for(;; (*a)++, (*b)++) { 
        if ((*a == aend || !isdigit((int)(unsigned char)**a)) && 
            (*b == bend || !isdigit((int)(unsigned char)**b))) 
            return bias; 
        else if (*a == aend || !isdigit((int)(unsigned char)**a)) 
            return -1; 
        else if (*b == bend || !isdigit((int)(unsigned char)**b)) 
            return +1; 
        else if (**a < **b) { 
            if (!bias) 
                bias = -1; 
        } else if (**a > **b) { 
            if (!bias) 
                bias = +1; 
        } 
} 
return 0; 
} 
/* }}} */ 
/* {{{ compare_left 
*/ 
static int 
compare_left(char const **a, char const *aend, char const **b, char const *bend) 
{ 
/* Compare two left-aligned numbers: the first to have a 
different value wins. */ 
    for(;; (*a)++, (*b)++) { 
        if ((*a == aend || !isdigit((int)(unsigned char)**a)) && 
            (*b == bend || !isdigit((int)(unsigned char)**b))) 
            return 0; 
        else if (*a == aend || !isdigit((int)(unsigned char)**a)) 
            return -1; 
        else if (*b == bend || !isdigit((int)(unsigned char)**b)) 
            return +1; 
         else if (**a < **b) 
             return -1; 
         else if (**a > **b) 
             return +1; 
} 

return 0; 
} 
/* }}} */ 
/* {{{ strnatcmp_ex 
* call in array.c: strnatcmp_ex(Z_STRVAL(first), Z_STRLEN(first), Z_STRVAL(second), Z_STRLEN(second), fold_case); 
*/ 
PHPAPI int strnatcmp_ex(char const *a, size_t a_len, char const *b, size_t b_len, int fold_case) 
{ 
    char ca, cb; 
    char const *ap, *bp; 
    char const *aend = a + a_len, 
             *bend = b + b_len; 
    int fractional, result; 
    if (a_len == 0 || b_len == 0) 
        return a_len - b_len; 
    ap = a; 
    bp = b; 
    while (1) { 
        ca = *ap; cb = *bp; 
        /* skip over leading spaces or zeros */ 
        while (isspace((int)(unsigned char)ca) || (ca == '0' && (ap+1 < aend) && (*(ap+1)!='.'))) 
            ca = *++ap; 
        while (isspace((int)(unsigned char)cb) || (cb == '0' && (bp+1 < bend) && (*(bp+1)!='.'))) 
            cb = *++bp; 
        /* process run of digits */ 
        if (isdigit((int)(unsigned char)ca) && isdigit((int)(unsigned char)cb)) { 
            fractional = (ca == '0' || cb == '0'); 
            if (fractional) 
                result = compare_left(&ap, aend, &bp, bend); 
            else 
                result = compare_right(&ap, aend, &bp, bend); 
            if (result != 0) 
                return result; 
            else if (ap == aend && bp == bend) 
                /* End of the strings. Let caller sort them out. */ 
                return 0; 
            else { 
                /* Keep on comparing from the current point. */ 
                ca = *ap; cb = *bp; 
            } 
        } 
        if (fold_case) { 
            ca = toupper((int)(unsigned char)ca); 
            cb = toupper((int)(unsigned char)cb); 
        } 
        if (ca < cb) 
            return -1; 
        else if (ca > cb) 
            return +1; 
        ++ap; ++bp; 
        if (ap >= aend && bp >= bend) 
            /* The strings compare the same. Perhaps the caller 
             will want to call strcmp to break the tie. */ 
            return 0; 
        else if (ap >= aend) 
            return -1; 
        else if (bp >= bend) 
            return 1; 
    } 
} 
/* }}} */

從strnatcmp_ex函數(shù)中的：

復(fù)制代碼代碼如下:

while (isspace((int)(unsigned char)ca) || (ca == '0' && (ap+1 < aend) && (*(ap+1)!='.'))) 
    ca = *++ap; 
while (isspace((int)(unsigned char)cb) || (cb == '0' && (bp+1 < bend) && (*(bp+1)!='.'))) 
    cb = *++bp;

所以，我覺(jué)得應(yīng)該字符串（當(dāng)前位置開始）中前面的空字符和數(shù)字前面的‘0'不會(huì)參與比較，比較的結(jié)果應(yīng)該和

http://us.php.net/manual/en/function.natsort.php

http://sourcefrog.net/projects/natsort/example-out.txt

所說(shuō)的一樣，但是在我的php5.2.9中對(duì)于“0”的處理結(jié)果卻不一樣（例如“img002.png”與“img1.png”，我的理解應(yīng)該是前者大于后者，不過(guò)在我的5.2.9中卻是前者小于后者），原因還沒(méi)想清楚，可能是5.2.9的一個(gè)bug，也可能是自己還沒(méi)有理解清楚源碼的意思。下次配置好環(huán)境再好好測(cè)試，好好消化～～

在array.c中有兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu)很值得我們關(guān)注

您可能感興趣的文章: