【C】マルチバイト文字のソーティング処理について - 底辺プログラマの戯言@Wiki

とある業務でUTF-8を文字コードの基本としているプログラム中において、ソーティングを実装することになった。

普通のソーティングなら文字列をstrcmp( str1, str2 ); とやればよい。
しかし、今回は普通と違っていました。

どこが違っていたのかと言うと・・・

(1) マルチバイト文字列で半角カナを含むため1-3byteの文字が混在している
(2) ソーティングルールが文字コード昇順でなく、独自のルールがある

この内、(1)についてはマルチバイト文字列をワイド文字列に変換して一律に扱うことで解決できる。
たとえば、以下のように。

---

#include <stdio.h>
#include <string.h>
#include <wchar.h>
 
/* ↓ここの定義はてきとうです */
#define STR_BYTE_MAX  ( 24 )
 
int main( int argc, char **argv )
{
 
    char    caRefStr[STR_BYTE_MAX] = "ﾃｽﾄABCabc$%&012";
    char    *pcaRefStr = &caRefStr;
    wchar_t wcsRefStr[STR_BYTE_MAX];
    size_t  szRet = 0;
 
    /* ロケールを日本語・UTF-8エンコーディングに指定 */
    setlocal( LC_ALL, "jp_JP.UTF-8" );
 
    szRet = mbsrtowcs( wcsRefStr, &pcaRefStr, STR_BYTE_MAX, NULL );
    if( szRet == -1 ){
        fprintf( stderr, "mbsrtowcs() failed(%s/%d)", __func__, __LINE__ );
        return -1;
    }
 
    printf( "%ls\n", wcsRefStr );
 
    return 0;
}
 

---

処理系・実装依存だが、wchar_tはおおよそ2byteなので、こうすることで全ての文字を均等のバイト幅で扱える。
これによって文字の比較などが簡単になる。
こうしないと、

　・今比較対象のバイトは何byte文字の何番目のバイトか？
　・文字コード独自のヘッダ情報(BOMとか)、エスケープシーケンスはあるか？
　　etc...

こんなことを気にしてプログラミングしなければならない。
これは非常に煩雑で全てを網羅したものを作成するにはそれなりの工数がかかる。

だけど、上記のようにしておけば、マルチバイト文字を扱った検索のなどの処理を行う部分にだけ上記のような処理を
適用すればよく、文字コード・バイト列の形式とロジックを分離できる。
※関数化したりすればまったくのブラックボックスとして使用できる。

ここまでは上々だった。
問題は次だった。。。

ソーティングは普通文字コードの昇順や降順で行われることが殆どだ。
たとえば、ABCDEFG…abcdefg…という順序が普通だ。
日本語なら、あいうえお…たちつてと…という順序だろう。

しかし、今回は違った。
まず検索に使用する文字が半角カナ(！)・ASCII英数字・ASCII記号の一部で、半角カナはUTF-8では3byte文字だ。
(これが困る…)
次に、ソーティングルールが特徴的で例えば「ｱｲｳｴｵ」「ｱｲｳｪｵ」「ｱｲｳｵｱ」では、
①「ｱｲｳｴｵ」→②「ｱｲｳｪｵ」→③「ｱｲｳｵｱ」となる。

これが余計に難しくしている。

今回はソーティング対象のデータが最大500件であり、また工期も十分に確保できないことから、ソーティング
処理としてはC標準ライブラリのqsortを使用することにした。
※qsortについては各種リファレンスやWEBの情報をご参照ください。

qsortでは値の大小を決める比較関数をユーザが定義できる。
例えば、次のように。

int compare( const void *left_value, const void *right_value )
{
    return ( *( int * )left_value - *( int * )right_value );
}
 

今回もこのcompareをうまいこと作ればやれると思い、実験を開始した。

今回の実験の肝は、ソーティングルールをどうやって実現し、compareが要求する形式に合わせこむか、だった。

まず、ソーティングルールの実現方法だ。

これは文字コード順でないため、strcmpなどのように文字コード値で判断する処理は使用できない。
というか、使用しづらい。
そこで、考えたのが、テーブルからindex値を引っ張ってきてそれを比較するというものだ。
もう世の中にはあるんだろうけど、私的には大ヒットだった(笑)

例えば次のようにする。

---

/* ソーティングルール文字列 */
static const wchar_t gwcsSortRule[] = { "ｱｧｲｨｳｩｴｪｵｫ" };
 
int compare( const void *left_value, const void *right_value )
{
    int iLefIndex, iRightIndex;
    wchar_t *pwcsLeftHit, *pwcsRightHit;
 
    /* ソーティングルール文字列の中で、今検索対照の文字がどの位置か、ポインタで取得する */
    pwcsLeftHit  = wcschr( gwcsSortRule, *( wchar_t * )left_value );
    pwcsRightHit = wcschr( gwcsSortRule, *( wchar_t * )right_value );
 
    /* ソーティングルール文字列の基底アドレスからの距離を算出する */
    iLeftIndex  = ( int )( ( unsigned long )pwcsLeftHit  - ( unsigned long )gwcsSortRule );
    iRightIndex = ( int )( ( unsigned long )pwcsRightHit - ( unsigned long )gwcsSortRule );
 
    /* 距離同士の差分を返せば順位がわかる */
    return ( iLeftIndex - iRightIndex );
}
 

---

こうすることで、ソーティングルールの変化にも強いし、動作も問題なくできる上、qsortを利用するための合わせこみも
実現できてしまう！
私的大発見だったので、ちょっと興奮気味。

で、今回は上記の合わせ技で何とかソーティングは実装できた。
(ランダムに自動生成させた500個の文字列を、実装した処理で正しくソーティングできた)
ただし、x86環境・gccで。

けど。。。。

ターゲット環境(ARMv5T)に持ってくと動かない。
どうやらmbsrtowcsが失敗している様子。。。
なんだろうな…また調査だなぁ、これは。