C言語の学習：標準関数を自作してみよう！【上級編】

基本的には、src から dst にデータを 1 バイトずつコピーしていくことになります。そしてそれを n バイト分繰り返します。また、コピーは代入によって実現することができます。

そういう意味では、strcpy 関数に似ています。strcpy 関数を自作するときにも src から dst に 1 バイトずつ（１文字ずつ）コピーしましたよね？

MEMO

strcpy 関数の自作については初級編で紹介していますので、strcpy の自作の仕方が分からない方は下記ページをご参照いただければと思います

C言語の学習：標準関数を自作してみよう！【初級編】

ただし、strcpy 関数とは異なり、文字列をコピーするわけではないので、最後にヌル文字を付加する処理は不要です。また、コピーを行うループの終了条件は、src の文字がヌル文字になった時ではなく、n バイトコピーした時になります。

この辺りを考慮すると、memcpy は下記のようなループで実現できそうですよね？

size_t i;

for (i = 0; i < n; i++) {
    dst[i] = src[i];
}

ですが、上記を実装してコンパイルすると、コンパイルエラーが発生します。

理由は src と dst の型が void * だからです。void * 型のポインタ 変数に対しては、添字演算子（[]）や間接演算子（*）が使用できません。 

つまり、void * 型のポインタ変数からは、これらのポインタが指す先のデータにはアクセスできない（データの取得ができない・データの格納ができない）ことになります。

ですので、src と dst は void * 型以外の型に変換してからコピーを行う必要があります。

この変換は、void * 型のポインタ引数を、下記のように異なるポインタ型の変数に代入することで実現することができます（src_byte の型に const を付けているのは、src の型にも const が付いているからです）。

型名 *dst_byte = dst;
const 型名 *src_byte = src;

上記変数を用いた場合、コピーを行う際のループ内の処理は下記のようになります。

size_t i;
型名 *dst_byte = dst;
const 型名 *src_byte = src;

for (i = 0; i < n; i++) {
    dst_byte[i] = src_byte[i];
}

型名 と書いた部分には、int や short などの型名を指定する必要があります。

ただし、memcpy の場合、１バイトずつデータをコピーする必要があります。１バイトずつコピーするには 型名 は何にする必要があるでしょうか？

ここが memcpy を自作する上での最大のポイントになります。

例えば 型名 を short にした場合、下記の代入では２バイトのデータのコピーが行われることになります。これは、short の型のサイズが２バイトだからです。

short *dst_byte = dst;
const short *src_byte = src;

dst_byte[i] = src_byte[i];

memcpy の戻り値は “コピー先のメモリの先頭アドレス” です。

ですので、引数の dst のアドレスそのものを返却すれば良いです。

memcpy を自作する上で一番のポイントになるのが、引数 src と dst の型が void * であるところです。

MEMO

この解説では const については省略して説明していきます

const について詳しく知りたい方は下記ページをご参照いただければと思います

【C言語】constの使い方・メリットを解説

引数 src と dst の型を char * もしくは unsigned char * に変換すれば良いことに気づけば、あとは一瞬で自作することができると思います。ですが、深いC言語の知識を持っていないと、このことに気づくのが難しいです。

コピーの仕方がわからない時のヒントでも解説したように、void * 型のポインタ変数に対しては添字演算子（[]）や間接演算子（*）が使用できません。

そのため、src の指す先のメモリからデータを取得し、dst の指す先のメモリへデータを格納するためには、これらの変数を一旦他のポインタ型に変換する必要があります。これは、ポインタの指す先のデータへのアクセス（取得や格納）は、添字演算子（[]）と間接演算子（*）でしか行うことができないからです（他の関数を利用しない場合）。

この変換先の型は、char * or unsigned char * である必要があります。これは、char と unsigned char の型のサイズが 1 バイトだからです。

ポインタ変数を使用した時の動作は、そのポインタ変数の型の “基になる型” によって異なります（”基になる型” とは、例えば int * なら int 型、char * なら char 型のように、ポインタ変数宣言時に * の前に指定する “型” のことを言っています）。

例えば、ポインタ変数には加算や減算を行うことが可能ですが、ポインタ変数に +1 した際には、ポインタ変数に格納されているアドレスが、そのポインタ変数の型の “基になる型” のサイズ分増加することになります（逆に -1 した際にはそのサイズ分減少する）。

また、ポインタ変数には添字演算子（[]）を使用して “ポインタ変数が指すデータ” にアクセスすることが可能です。

この添字演算子に指定する値を 1 増加させた場合、アクセス先のアドレスは、そのポインタ変数の型の “基になる型” のサイズ分増加することになります（つまり各要素のサイズが “基になる型” のサイズとして扱われる）。

また、ポインタ変数に添字演算子（[]）や間接演算子（*）を利用して代入を行う場合、代入されるデータのサイズは、そのポインタ変数の型の “基になる型” のサイズとなります。

ここまでの解説を踏まえて、例えば下記のように src と dst の型を int * に変換してデータのコピーを行なった場合について考えてみましょう。

size_t i;

/* int*型に変換 */
int *dst_int = dst;
const int *src_int = src;

for (i = 0; i < n; i++) {
    dst_int[i] = src_int[i];
}

まず１回目のループで dst のアドレスに src のアドレスから 4 バイト分のデータがコピーされることになります。

さらに、２回目のループでは dst から 4 バイト上位のアドレスに、src から 4 バイト上位のアドレスの 4 バイト分のデータがコピーされることになります。

３回目のループでは dst から 8 バイト上位のアドレスに、src から 8 バイト上位のアドレスの 4 バイト分のデータがコピーされることになります。

こんな感じで、int 型のサイズ分ずつ一気にコピーが行われてしまうため、n 回ループしてしまうと、 n  * int 型のサイズ バイト分のコピーが行われてしまうことになります。これは明らかに memcpy の仕様と異なります（仕様では、コピーするバイト数は n のみ）。

ループ回数を n / int 型のサイズ にすれば解決しそうでもありますが、n が int 型のサイズ で割り切れない場合はデータのコピーバイト数が n よりも少なくなってしまいます。

size_t i;

/* int*型に変換 */
int *dst_int = dst;
const int *src_int =src;

for (i = 0; i < n / sizeof(int); i++) {
    /* n / sizeof(int) * sizeof(int) バイトのみコピーが行われる */
    dst_int[i] = src_int[i];
}

ですので、ポインタ変数から１バイト単位でデータを処理したい場合は、そのポインタ変数の型は、型のサイズが１バイトである char もしくは unsigned char 型を基にしたポインタ型、つまり char * or unsigned char * にする必要があります。

特に char 型は “文字を扱う型” と覚えている方もおられるかもしれませんが、”１バイト単位で処理するための型” という側面もあることを覚えておくと良いと思います。

むしろ重要なのは後者の方です。英字は１バイト単位で表現可能なので（アルファベット大文字 26 文字 + 小文字 26 文字 + その他の文字の数 < 256）、char 型を利用して扱うことが多いというだけです。

基本的には、プログラムで扱うデータの最小単位はバイトですので、その最小単位でデータを扱うことができる char や unsigned char は非常に便利です。それよりも大きいデータは、結局は１バイトが集まって出来たデータですので、極論すれば、char や unsigned char 型の変数のみで処理することが可能です。

現に自作した memcpy により、１バイトよりも大きな int 型のデータや TEST 型のデータのコピーも、char 型のデータの代入により実現できていますよね？

また、例えば下記のように、int 型のデータを１バイト単位で扱うようなこともできます。

int x = 0x12345678;
char *p_x;
int i;

/* １バイト単位で扱うためにchar*型のポインタに指させる */
p_x = &x;

for (i = 0; i < sizeof(int); i++) {
    /* １バイト単位で表示 */
    printf("0x%x, ", p_x[i]);
}

上記のソースコードをコンパイルして実行すると、結果として 0x78, 0x56, 0x34, 0x12 が表示されると思います。

これはつまり、変数 x には、４バイト単位で見ると 0x12345678 が格納されているようにも思えますが、１バイト単位でみると下の図のように 0x78, 0x56, 0x34, 0x12 の順でメモリに格納されているようなことを示しています。

ちょっと横道に逸れてしまいましたが、ではなぜ、memcpy 関数ではこんなにややこしい void * 型を引数として使用しているのでしょうか？

これは memcpy 関数でどんな型のデータでもコピーできるようにするためです。

void * 型の変数では、どんな型のデータでも指すことができるため、引数を void * 型にしてしまえば、どんなデータのアドレスでも指定することができることになります。

例えば、引数の型を int * にしてしまうと、基本的には int 型の配列や int 型の変数のコピーしかできなくなってしまいます。

引数を void * 型にすることで、関数内部で型を変換する必要が出てきますが、それでもどんなデータでも入力できるという、汎用性の面で大きなメリットを得ることができます。

次に自作する関数 qsort に関しても、引数の１つが void * 型になります。この関数を自作してみることで、 void * の扱いにさらに慣れることができると思います。

また、この解説では void * や “ポインタの型” について説明しましたが、これらの詳細は下記ページでも行なっていますので、詳しく知りたい方はぜひ読んでみて下さい！

【C言語】void型とvoid*型（void型ポインタ）について解説

【C言語】ポインタの「型」について解説

そもそもソートの仕方がわからないという方は、選択ソートとクイックソートのアルゴリズムについては下記ページで解説していますので、こちらを参考にしていただければと思います。

選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

上記のページでは、int 型の配列をソートするためのソート関数も紹介しています。が、今回はどんな型の配列でもソートを行えるようにするため、上記のページで紹介している関数を作成するよりも難易度は高いです。

ですので、まだソートを実装したことないという方は、まずは上記ページを参考にして int 型の配列をソートする関数を作成することをオススメします。

まず void * の扱い方がわからない方は、memcpy の自作を思い出しましょう！

void * はどんな型のデータも指せる（どんな型のデータのアドレスも格納できる）反面、間接演算子（*）や添字演算子（[]）を利用できません。

また、void * 型ポインタへの加算や減算も動作が未定義のため行わない方が無難です。

ですので、void * 型ポインタ変数は、データを指すだけであれば便利ですが、そのポインタ変数が指すデータを扱って処理を行うには不便です。従って、一旦関数内部では、処理を行いやすくするために他の型に変換した方が良いです。

また、１バイト単位で処理できた方が便利なので、char * もしくは unsigned char * に型変換するのが良いです。

例えば、my_qsort 関数の第１引数 elems を下記のように char * 型の byte_elems に代入すれば、これにより elems のアドレスを char * 型のアドレスとして扱うことができます。

char *byte_elems = elems;

さらに、第３引数 size_elem でソート対象の各データのサイズが指定されています。

つまり、ソート対象の各データの先頭アドレスは、データ同士で size_elem ずつ離れていることになります。

ソートを開始するデータの先頭アドレスは byte_elems になりますので、その先頭のデータを第 0 個目のデータとすれば、第 i 個目のデータの先頭アドレスは byte_elems + i * size_elem として計算することができます。

ですので、例えば第 i 個目のデータと、第 j 個目のデータを比較する際には、アドレス byte_elems + i * size_elem に存在するデータとアドレス byte_elems + j * size_elem に存在するデータを比較することになります。

今回の my_qsort を実装する上でポイントになるのがデータ同士の比較です。

この比較は my_qsort 関数の第４引数 compare のアドレスの関数を呼び出しにより行う必要があります。

この compare は、関数のアドレスを格納するポインタになります。つまり、関数ポインタです。

ちなみに、main 関数での my_qsort 関数の実行部分を見ればわかるとおり、関数のアドレスは 関数名 のみを記述することで指定することが可能です。

例えば下記は、関数 compare_int のアドレスを指定するために、関数名 compare_int を引数に指定する例になります。 

my_qsort(&array2[0], 1024, sizeof(array2[0]), compare_int);

関数ポインタを利用した際の関数呼び出しは、関数ポインタを 関数名 のように捉えて行います。

つまり、今回は関数ポインタの変数名が compare なので下記のようにして関数を呼び出すことができます。

戻り値を受け取る変数 = compare(引数１, 引数2, ...);

じゃあ、この関数呼び出し時に指定する引数や、関数呼び出しして受け取る戻り値の型が何になるかというと、これは、my_qsort 関数の第４引数の型を見ればわかります。

void my_qsort(void *elems, size_t num_elem, size_t size_elem, int (*compare)(const void *, const void *);

上記の第４引数において、(*compare) の前に記述されている型が、compare の関数を呼び出した際の “戻り値の型” となります。つまり、compare の関数の戻り値の型は int になります。

さらに (*compare) の後ろに記述されている () 内が、compare の関数を呼び出す際に指定する引数になります。つまり、compare の関数には、void * 型の変数を引数として２つ指定する必要があります（要はどんな型のポインタ変数でも良いということです）。

ですので、例えば my_qsort の中でソート対象のデータの中から “第 i 個目のデータ” と “第 j 個目のデータ” を比較したいときには、下記のようにして関数を実行して比較を行うことになります。

int ret;

ret = compare(第 i 個目のデータの先頭アドレス, 第 j 個目のデータの先頭アドレス)

第 i 個目のデータの先頭アドレス の求め方については、void * の扱いがわからない時のヒントで説明していますので、求め方が分からない時はこちらをご参照ください。

上記を実行することで、ret に compare の指す関数の実行結果が格納されます。

戻り値の詳細は回答のテンプレートの補足１に記載していますが、要は戻り値が 0 よりも小さいデータの場合、第１引数に指定したアドレスのデータ（第 i 個目のデータ）の方が、第２引数に指定したアドレスのデータ（第 j 個目のデータ）よりも値が小さい（or アルファベット順的に前側）ということになります。

今回は昇順ソートを行いますので、my_qsort 実行後には、第 i 個目のデータは第 j個目のデータよりも前側にないといけないことになります。

逆に、戻り値が 0 よりも大きいデータの場合、第１引数に指定したアドレスのデータ（第 i 個目のデータ）の方が、第２引数に指定したアドレスのデータ（第 j 個目のデータ）よりも値が大きい（or アルファベット順的に後ろ側）ということになります。

したがって、my_qsort 実行後には、第 i 個目のデータは第 j 個目のデータよりも後ろ側にないといけないことになります。

クイックソートや選択ソートでは、ソートを進める上でデータの交換が必要になります。

my_qsort 関数内でデータの交換を行う際には、交換する各データのサイズが第３引数の size_elem により決まるところがポイントになります。

void my_qsort(void *elems, size_t num_elem, size_t size_elem, int (*compare)(const void *, const void *);

例えば第 i 個目のデータと第 j 個目のデータを交換する場合、”第 i 個目のデータの先頭アドレス から size_elem バイト分のデータ” と “第 j 個目のデータの先頭アドレス から size_elem バイト分のデータ” の交換を行う必要があります（先頭のデータを “第 0 個目” のデータとしています）。

さらに、この交換は次の３ステップの処理により実現する必要があります。

1. “第 i 個目のデータの先頭アドレス から size_elem バイト分のデータ” を 退避先メモリの先頭アドレス にコピーする
2. “第 j 個目のデータの先頭アドレス から size_elem バイト分のデータ” を 第 i 個目のデータの先頭アドレス にコピーする
3. “退避先メモリの先頭アドレス から size_elem バイト分のデータ” を 第 j 個目のデータの先頭アドレス にコピーする
   

いきなり 2. の処理を行なってしまうと第 i 個目のデータが上書きされて無くなってしまうので、これを防ぐために 1. で一旦そのデータを退避してから交換を行う必要があります。

このデータの交換を行う上でのポイントは下記の３つです。

• アドレスの求め方
• コピーの仕方
• 退避先メモリの確保の仕方

まずポイントの１つ目は “アドレスの求め方” です。

データを交換する際には、交換するデータのアドレスを求める必要があります。

例えば 第 i 個目のデータ と 第 j 個目のデータ を交換する場合、第 i 個目のデータの先頭アドレス と 第 j 個目のデータの先頭アドレス のアドレスを求める必要があります。

このアドレスの求め方については、void *の扱いがわからない時のヒントで説明していますので、求め方がわからない方はこのヒントを参照していただければと思います。

ポイントの２つ目は “コピーの仕方” です。

これは、要は最初に自作した memcpy と同じです。

つまり、void * の引数を他の型（char * or unsigned char *）に変換してから１バイトずつ代入演算子（=）で代入しましょうということです。この代入はデータのサイズ分、つまり size_elem バイト分繰り返し行う必要があります。

ただ、今回は memcpy は使用しても良いことにしていますので、memcpy でコピーしてしまっても良いです。

ポイントの３つ目は “退避先メモリの確保の仕方” です。

前述の通り、データの交換を行う際には退避先となるデータの置き場（メモリ）が必要です。

退避するデータのサイズは size_elem バイトですので、データの交換を行う際には、事前に size_elem バイトのメモリを用意しておく必要があります。

このメモリは malloc 関数で確保することができます。

malloc 関数は、引数に指定したサイズ（バイト単位）のメモリを動的に確保する関数です。

ですので、下記のように malloc 関数を実行してやれば、データの退避先となるメモリを用意することができます。

tmp = malloc(size_elem);

さらに、malloc 関数の戻り値は確保したメモリの先頭アドレスとなります。つまり、この malloc 関数の戻り値が、退避先メモリの先頭アドレス となります。

今回はソートするアルゴリズムに応じた２つのソート例を示します。２つとも再帰呼び出しを用いて実装した例になりますが、再帰呼び出しを行わなくても、ソートができていればオーケーです。

クイックソートでソートする場合

クイックソートによりソートを行う関数 my_qsort は下記のようになります。my_qsort から quickSort 関数を呼び出して、ソートを実行しています。

/* クイックソートを行う関数 */
void quickSort(void *elems, int left, int right, size_t size_elem, int (*compare)(const void *, const void *)) {
    void *pivot; /* ピボットを指すポインタ */
    void *tmp; /* データ退避用のメモリを指すポインタ */
    int i, j;

    /* elemsをchar*に変換 */
    char *byte_elems = elems;

    /* ソートを行う範囲が１以下の場合 */
    if(left >= right) {
        return;
    }

    /* 退避用のメモリを確保 */
    tmp = malloc(size_elem);
    if (tmp == NULL) {
        /* メモリ確保に失敗 */

        return;
    }

    /* pivot の決定 */
    pivot = byte_elems + size_elem * left;

    i = left;
    j = right;

    /* pivot以下のデータを配列の前半に
       pivot以上のデータを配列の後半に集める */
    while(1) {
        /* pivot以上のデータを左側から探索 */
        while (compare(byte_elems + size_elem * i, pivot) < 0) {
            i++;
        }

        /* pivot以下のデータを右側から探索 */
        while (compare(byte_elems + size_elem * j, pivot) > 0) {
            j--;
        }

        /* i >= j になったということは
           配列の左側にpivot以下のデータが、
        　　配列の右側にpivot以上のデータが集まったということ */
        if (i >= j) {
            /* 集合の分割処理は終了 */
            break;
        }

        /* 探索した２つのデータを交換 */
        memcpy(tmp, byte_elems + i * size_elem, size_elem);
        memcpy(byte_elems + i * size_elem, byte_elems + j * size_elem, size_elem);
        memcpy(byte_elems + j * size_elem, tmp, size_elem);
 
        /* 交換後のデータの次から探索再開 */
        i++;
        j--;

    }

    free(tmp);

    /* 小さいデータを集めた範囲に対してソート */
    quickSort(elems, left, i - 1, size_elem, compare);

    /* 大きいデータを集めた範囲に対してソート */
    quickSort(elems, j + 1, right, size_elem, compare);

}

void my_qsort(void *elems, size_t num_elem, size_t size_elem, int (*compare)(const void *, const void *)) {

    /* 実処理はquickSort関数で実行 */
    quickSort(elems, 0, num_elem - 1, size_elem, compare);
}

選択ソートでソートする場合

選択ソートによりソートを行う関数 my_qsort は下記のようになります。my_qsort から selectionSort 関数を呼び出して、ソートを実行しています。

/* 選択ソートを行う関数 */
void selectionSort(void *elems, int left, int right, size_t size_elem, int (*compare)(const void *, const void *)) {
    int i;
    void *min;
    void *tmp;

    /* elemsをchar*に変換 */
    char *byte_elems = elems;

    /* データ数が１の場合はソート済みなのでソート終了 */    
    if (left == right) {
        return;
    }

    /* 退避用のメモリを確保 */
    tmp = malloc(size_elem);
    if (tmp == NULL) {
        /* メモリ確保に失敗 */

        return;
    }

    /* ひとまずソート範囲の先頭を最小値とみなす */
    min = byte_elems + left * size_elem;

    /* ソート範囲の中から最小値を探索 */
    for (i = left; i <= right; i++) {
        if (compare(min, byte_elems + i * size_elem) > 0) {
            /* 最小値を更新 */
            min = byte_elems + i * size_elem;
        }
    }

    /* ソート範囲の終了点と最小値を交換 */
    memcpy(tmp, byte_elems + left * size_elem, size_elem);
    memcpy(byte_elems + left * size_elem, min, size_elem);
    memcpy(min, tmp, size_elem);

    free(tmp);

    /* ソート範囲を狭めて再度選択ソート */
    selectionSort(elems, left + 1, right, size_elem, compare);
}

void my_qsort(void *elems, size_t num_elem, size_t size_elem, int (*compare)(const void *, const void *)) {

    /* 実処理はselectionSort関数で実行 */
    selectionSort(elems, 0, num_elem - 1, size_elem, compare);
}

それでは、qsort 関数を自作する上でのポイントを解説していきたいと思います。

ソートの仕方もポイントの１つではあるのですが、これについては下記のページ等で解説していますので、ソートの仕方のポイントを知りたい方は別途下記ページを参照していただければと思います。

選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

ここでは、ソートの仕方以外の部分のポイントを解説していきます。

今回の qsort 関数の自作におけるポイントは、int 型の配列ソート時の関数と比較すると分かりやすいと思います。

ここでは、int 型の配列をソートする選択ソートの関数と比較することで、ポイントを解説していきたいと思います（選択ソートで解説するのは、クイックソートよりも実装内容が簡単だからです）。

int 型の配列をソートする関数 selectionSort は下記になります。

void selectionSort(int *elems, int left, int right) {
    int i;
    int *min;
    int tmp;

    /* データ数が１の場合はソート済みなのでソート終了 */    
    if (left == right) {
        return;
    }

    /* ひとまずソート範囲の先頭を最小値とみなす */
    min = elems + left;
    

    /* ソート範囲の中から最小値を探索 */
    for (i = left; i <= right; i++) {
        if (*min > *(elems + i)) {
            /* 最小値を更新 */
            min = elems + i;
        }
    }

    /* ソート範囲の終了点と最小値を交換 */
    tmp = *(elems + left);
    *(elems + left) = *min;
    *min = tmp;

    /* ソート範囲を狭めて再度選択ソート */
    selectionSort(elems, left + 1, right);
}

上記は、下記ページで紹介している selectionSort 関数を、第１引数を int data[] から int *elems に、また関数内部の処理を添字演算子ではなく間接演算子を利用するように変更したものになります（変更していますが、動作は全く同じです）。

選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

また、上記の関数相当の動作をする関数が、解答例の選択ソートの場合で紹介した selectionSort 関数になります。

同じ関数名で分かりにくいので、これらを intSort と voidSort として呼び分けたいと思います。

この intSort と voidSort とで異なる点は、下記の３つになります。

• 引数
• 代入の仕方
• 比較の仕方

この３つの違いそれぞれについて解説していきたいと思います。

void * 型のポインタを扱うにはサイズが必要なことが多い

まず引数が違いますね！

void selectionSort(void *elems, int left, int right, size_t size_elem, int (*compare)(const void *, const void *))

void selectionSort(int *elems, int left, int right)

第１引数は両者ともにソートを開始するデータの先頭アドレスになりますが、両者で型が異なります。voidSort では、どんな型のデータでもソートできるように、第１引数の方が void * 型になっています。

また、voidSort でのみ、各データのサイズ size_elem と、比較を行う関数のアドレス compare を受け取るように引数を設定しています。

size_elem を受け取るようにしているのは、voidSort では intSort とは異なり、ソート対象の各データのサイズがわからないためです。このサイズが分からないと、各データがどのアドレスに存在するかも分かりませんし、後に説明する代入も行うことができません。

例えばアドレスに関していうと、第 i 個目のデータ（先頭のデータを第 0 個目のデータとしています）の先頭アドレスは、各データのサイズ size_elem を用いて byte_elems + size_elem * i として計算しますので、この計算式より、サイズの情報がないと各データのアドレスの計算のしようがないというところが理解していただけるのではないかと思います（byte_elems は void * 型の elems を char * 型に変換したポインタ変数です）。

一方で、void * 型以外の型のポインタの場合、その変数への加算や減算は、その変数の “基となる型”（例えば int * であれば int、char * であれば char）のサイズを考慮して計算が行われます。

例えば int * 型のポインタに +1 すれば、そのポインタに格納されているアドレスは 4 増加することになります。これは int 型のサイズが 4 バイトだからです。また、+2 すれば、アドレスは 8 が増加することになります。

ですので、ソート対象のデータが int 型の配列で、その先頭アドレスが elems に格納されているのであれば、第 i 個目のデータのアドレスは単純に elems + i により計算することが可能です。つまり、void * 型の時とは異なり、各データのサイズはわざわざ引数としてしてもらう必要はありません。

こんな感じで、引数が void * 型の関数の場合、そのポインタ引数の指しているデータのサイズが分からないので、関数内部でアドレス計算などを行う際には、サイズの情報を別途引数で指定してもらう必要があることが多いです。

逆にいうと、サイズさえきちんと引数で受け取れば、どんなサイズのデータでも（どんな型のデータでも）アドレス計算等ができますので、汎用性の高い関数を作成することが可能です。

また、voidSort でのみ比較を行う関数のアドレス compare を受け取るようにしているのは、この関数の内部ではデータの比較を行うことができないからです。これについては後述の関数ポインタを利用して汎用的な比較を実現で説明したいと思います。

memcpy により汎用的な代入が可能

続いて、代入の処理の違いについて解説します。

intSort と voidSort ともに、ソートを行う上でデータの交換を行なっています。

この時に、intSort では代入演算子（=）を利用して処理を行なっていますが、voidSort では memcpy 関数を利用して処理を行っているという違いがあることが確認できると思います。

memcpy(tmp, byte_elems + left * size_elem, size_elem);
memcpy(byte_elems + left * size_elem, min, size_elem);
memcpy(min, tmp, size_elem);

tmp = *(elems + left);
*(elems + left) = *min;
*min = tmp;

上記の、特に voidSort の処理で何を行なっているかよくわからないという方や tmp がどういった変数かが分からない方は、データの交換の仕方がわからない時のヒントを参照していただければと思います。

C言語では、データのコピーを行う処理は、代入演算子（=）による代入 or memcpy 等の標準関数により行うことができます。ただし、前者の代入の場合、右辺と左辺の変数の型により、コピーできるデータの量（バイト数）が固定されてしまいます。

例えば intSort で行っている下記の処理は、tmp のアドレスに対して、elems + left のアドレスのデータをコピーしている処理と捉えることができます。

tmp = *(elems + left);

コピーされるデータの量（バイト数）は、int 型のサイズ となります。これは、両辺の変数の型が int だからです。こんな感じで、代入によりデータのコピーは行えますが、コピーされるサイズが変数の型によって固定されてしまいます。

なので、intSort は、int 型のデータのソートにしか利用できません。

その一方で qsort関数では、どんなサイズのデータ（どんな型のデータ）に対してもソートが行えるように、どんな型のデータでもコピーできるように処理する必要があります。

ですので、どんなサイズのデータでもコピーできるように memcpy を利用しています。memcpy であれば、第３引数に指定する値（バイト数）を変更することで、どんなサイズのデータでもコピーすることができます。

ただし、コピーするサイズが分からないとコピーできないので、１つのデータのサイズを引数として渡してもらう必要があります。今回の場合は voidSort 関数の第４引数  size_elem が、そのサイズとなります。

void selectionSort(void *elems, int left, int right, size_t size_elem, int (*compare)(const void *, const void *))

以上が、voidSort で memcpy 関数を利用している理由になります。

ここからは補足ですが、前述の通り、memcpy 関数はどんなサイズのデータでもコピーできますので、intSort で行っている代入処理も、下記のように memcpy 関数による処理に置き換えることができます。

memcpy(tmp, elems + left, sizeof(int));
memcpy(elems + left, min, sizeof(int));
memcpy(min, tmp, sizeof(int));

つまり、やろうと思えば、代入は memcpy 関数でのデータコピーにより代用することができます。

ただし、代入ができるのであれば、代入を行なった方が安全です。特に、コピー先のデータの型とコピー元のデータの型が異なる場合、代入によるデータのコピーと memcpy によるデータのコピーの結果が異なることがあるので注意が必要です。

例えば下記は、int 型の変数 dst に char 型の変数 src をコピーする処理を、代入と memcpy それぞれで行なったときの結果を表示するものになります。

char src;
int dst;

src = 0x12;

/* memcpyによるデータのコピー */
dst = 0xFFFFFFFF;
memcpy(&dst, &src, sizeof(char));
printf("%x\n", dst);

/* 代入によるデータのコピー */
dst = 0xFFFFFFFF;
dst = src;
printf("%x\n", dst);

memcpy によるデータのコピー後に表示される結果は ffffff12 になります。つまり、char 型のサイズの１バイト分のみコピーされ（12 の部分）、その他の部分（ffffff の部分） はコピー前の状態が維持されてしまっています。

一方で、代入によるデータのコピー後に表示される結果は 12 になります。つまり、char 型のサイズの１バイト分のみコピーされ（12 の部分）、その他の部分は 0 に置き換わっています。結果として得たい値はおそらくこっちですよね。

こんな感じで、特にコピー先とコピー元とでデータの型が異なる場合、memcpy でデータのコピーを行うと意図しない結果になる可能性が高いので、代入が用いれる場合は代入を利用した方が良いです。

関数ポインタを利用して汎用的な比較を実現

また、intSort と voidSort とでは、比較の仕方が異なります。

if (compare(min, byte_elems + i * size_elem) > 0) {
    /* 略 */
}

if (*min > *(elems + i)) {
    /* 略 */
}

intSort では、比較演算子（<、>）を利用して直接比較を行なっていますが、voidSort では、関数ポインタ compare を呼び出して比較を行なっています。この compare は、引数として関数呼び出し側から渡されてくる関数ポインタ（関数のアドレス）になります。

なぜ voidSort では、わざわざ引数として関数ポインタ（関数のアドレス）を受け取るようになっているのでしょうか？なぜ voidSort では、intSort 関数のように、直接自身で比較を行わないのでしょうか？

まず、わざわざ引数として関数ポインタを受け取る理由について説明すると、これは voidSort で、どんな型の配列のデータでもソートできるようにするためです。

今回用意した回答のテンプレートでは下記の３つの比較関数を定義していますが、もし voidSort からこれらの関数を直接呼び出してしまうと、特定の型の配列のみのソートしか行えなくなってしまいます。

• compare_int：２つの引数のデータを int 型として大小関係を比較する
• compare_str：２つの引数のデータを文字列としてアルファベットの前後関係を比較する
• compare_age：２つの引数のデータを PERSON 型として、age メンバの大小関係を比較する

例えば、voidSort で下記のように compare_int を直接呼び出してしまうと、比較時には毎回 compare_int 関数が呼び出されるようになります。

if (compare_int(min, byte_elems + i * size_elem) > 0) {
    /* 略 */
}

compare_int は２つの int 型の整数を比較する関数になっているので、voidSort では int 型の配列のソートしかできなくなってしまうことになります。

その一方で、解答例で示した voidSort のように、引数として関数ポインタ compare を受け取るようにし、比較時にその関数ポインタ compare から関数呼び出すようにすれば、引数 compare のアドレスに応じて呼び出す関数が切り替わるようになります。

void selectionSort(void *elems, int left, int right, size_t size_elem, int (*compare)(const void *, const void *)) {
    /* 略 */
    
    /* 引数で指定されたcompareによって呼び出す関数が切り替わる */
    if (compare(min, byte_elems + i * size_elem) > 0) {
        /* 略 */
    }
    /* 略 */
}

つまり、関数利用者がソートしたい配列の型に応じて適切に比較を行う関数を指定すれば、関数内から実行される比較関数が自動的に切り替わり、その型に応じた適切な比較および適切なソートを行うことができるようになっています。

例えば回答のテンプレートの main 関数でも、整数をソートする場合は compare_int、文字列をソートする場合は compare_str、構造体を age メンバでソートする場合は compare_age という風に、ソートしたいデータに合わせて my_qsort 関数の第４引数に指定する関数を切り替えるようにしています。

こんな感じで、どんな型の配列でもソートできるようにするために、引数として関数ポインタを受け取るようになっています。

続いて、voidSort で intSort のように、直接自身で比較を行わない理由について解説しておきます。

理由は２つあって、１つ目の理由は、前述のようにどんな型の配列でもソートできるようにするためです。どんな型の配列でもソートできるように、引数として関数ポインタを受け取り、その関数ポインタから比較を行う関数を呼び出すようになっています。

もう１つの理由は、そもそも比較を行うことが無理だからです。

無理な理由は、比較を行うための情報が足りていないからです。比較を行うためには、データのサイズとデータの符号の有無の情報が必要です（ここでは説明は省略しますが、整数 or 浮動小数点数 or 構造体のうちのどの型であるかという情報も必要）。

intSort の場合、ソートする配列の各データが int 型であることが前提として作られています。

ですので、その int 型であるという情報から、ソート（比較）を行う対象がサイズ 4 バイトで “符号あり” のデータであるということが関数内で分かります。

その一方で voidSort の場合、ソート（比較）を行う対象のデータのサイズや符号の有無がわかりません。

これは、voidSort では、ソートする配列へのアドレスが void * の引数として渡されるからです。

void * 型のポインタはどの型のデータも指すことができるメリットがある一方、なんの型のデータを指しているのかが分からないというデメリットがあります。

そして、なんの型のデータを指しているかが分からないので比較を行うことができません。もし比較を行うのであれば、別途サイズや符号の有無の情報を引数として受け取る必要があります。

今回の場合は、引数 size_elem で各データのサイズを受け取っていますので、例えば size_elem が 4 であれば、比較するデータのサイズが 4 バイトであることはわかります。ですが、そのデータを “符号あり” で扱って比較するのか、”符号なし” で扱って比較するのかが分からないと、正確な比較を行うことができません。

例えば “符号なし” で扱った場合の値が 4294967295 だとすれば、”符号あり” で考えると -1 になります。”符号なし” の場合と “符号あり” の場合と値の大きさが全く異なるので、符号の有無が分からないと、比較が正確に行えないことになります（ここでは詳しい説明を省略しますが、そもそも整数ではなく浮動小数点数や構造体の場合もあります）。

つまり、比較はデータのサイズと符号の有無の情報がないと行うことができないのです。これは比較だけでなく、足し算や引き算などの四則演算に関しても同様のことが言えます。

そして、そのデータのサイズと符号の有無の情報とはまさに “型” です。この型そのものが、データのサイズと符号の有無の情報になりますので、int 型や unsigned int 型、char 型等の変数では、プログラマーは演算や比較を行う処理を記述すれば、実行時に自動的にサイズや符号の有無を考慮した結果を得ることができます。

普段何気なく利用している “型” ですが、比較や演算を行う上で非常に重要な役割を果たしています（代入などでも重要）。

この qsort 関数の自作を行うことで、void * を利用したプログラミングを体験し、その中で void * の便利さと不便さの両方や、”型” の重要性を感じ取っていただけたのではないかと思います。

文字列を分離することだけを考えた場合、処理の流れは下記のようになります。

• 分離を開始する位置から区切り文字と一致する文字を探す
• 見つかった場合：
  • 見つかった区切り文字をヌル文字（'\0'）で置き換える
  • ヌル文字に置き換えた後、分離を開始した位置のアドレスを返却する
• 見つからなかった場合：
  • 分離を開始した位置のアドレスを返却する

C言語では、ヌル文字（'\0'）を文字列の終端として扱うため、上記のように区切り文字をヌル文字に置き換えてやれば、文字列を分離したことになります。

上記の処理の流れを大枠で実装すると次のようになります。分離を開始する位置のアドレスを startとしています。

/* 文字開始位置から文字列の分離を行う */
for (i = 0; i < strlen(start); i++) {
    for (j = 0; j < strlen(sep); j++) {
        if (start[i] == sep[j]) {
            /* 見つかった場合 */
            見つかった場合の処理;
        }
    }
}

/* 区切り文字が１つも見つからなかった場合 */

見つからなかった場合の処理;

strtok 関数を自作する上で１番のポイントになるのが、第１引数 str に NULL が指定されて実行されたときの分離を再開する位置です。

第１引数 str に文字列の先頭アドレスが指定された場合は、文字列の分離は str から開始すれば良いので簡単です（先頭に区切り文字がある場合は区切り文字を飛ばしてから分離を開始する必要はありますが…）。

その一方で、第１引数 str に NULL 指定された場合は、直前に分離した文字列の後ろの文字から分離を開始する必要があります。

ただし、この分離を開始する位置は引数では指定されませんので、関数内部でその位置を覚えておく必要があります。

ですが、関数内で宣言した “通常の” 変数は、関数生成とともに作成され、関数終了とともに解放されてしまうため、前に関数内部で変数に格納したデータは全て消え去ってしまいます。

つまり、直前に実行された strtok で、次に分離を開始する位置を変数に格納しておいたとしても、次に strtok が実行されたときにはその変数の中身は消え去ってしまいます。

じゃあどうすれば、次に分離を開始する位置を覚えておけるのかというと、これは static 変数を利用することで実現することができます。

static 変数は、通常の変数とは異なり、プログラムが起動してからプログラムが終了するまでずっと保持し続けられる変数になります。ですので、関数が終了しても解放されませんし、関数が終了しても、変数に格納されたデータはずっと保持し続けられます。

したがって、my_strtok 関数内で static 変数を宣言し、その static 変数に、分離した文字列の後ろの位置を格納するようにすれば、関数が終了してもその位置を関数内で保持し続けることができます。

さらに、次に第１引数 str を NULL 指定して my_strtok 関数が実行された際に、その static 変数から次に分離を開始する位置を取得することで、適切な位置から分離を再開することができます。

これらの処理の大枠を実装したものが下記となります。static 変数は、下記の next_start の変数宣言のように、通常の変数宣言の前側に static を指定することで作成することができます。

char *my_strtok(char *str, const char *sep){
    static char *next_start = NULL;
    char *start;

    if(str == NULL) {
        start = next_start;
    } else {
        start = str;
    }

    /* 文字列の分離を行う処理を行う */

    /* 次に分離を開始する位置を覚えておく */
    next_start = 分離した文字列の後ろの位置のアドレス;

    /* 略 */
}

上記では next_start を static 宣言しているので、この next_start 変数は関数が終了しても解放されません（start は static 宣言していないので解放されます）。ですので、next_start 変数には、前回関数実行時の 分離した文字列の後ろの位置のアドレス が保持し続けられることになります。

また、上記では str が NULL の場合は start を next_start に、それ以外の場合は start を str に設定するようにしていますので、start から分離を開始すれば、適切な位置から分離を開始することができます。

今回の例では next_start をポインタとし、分離した文字列の後ろの位置のアドレス を保持するようにしていますが、別にポインタにこだわる必要もなく、配列の添字を保持するようにするのでも良いです。

ここで説明した static 変数に関しては、下記ページで詳細を解説していますので、詳しく知りたい方は是非読んでみてください。

【C言語】staticローカル変数の使い方・メリットを解説

では、まずは解答例のソースコードについて簡単に解説していきたいと思います。

static 変数の宣言

今回の strtok 関数を自作する上で一番のポイントになるのは static 変数を利用する点だと思います。解答例では、下記のように next_start を static 変数として宣言しています。

static char *next_start = NULL;

static 変数を利用することで、分離を再開する位置を保持する方法がわからない時のヒントで説明したように、関数終了後も変数に格納したデータを保持し続けることが可能になります。

そして、この next_start に分離後の文字列の１つ後ろの位置のアドレスを保持するようにすることで、２回目以降の my_strtok 関数実行時（第１引数 str に NULL 指定時）に、前回の分離後の文字列の後ろから分離を再開することができるようになります。

文字列を分離する

その文字列の分離を行なっているのは下記ループの中の処理になります。このループの中では、分離を開始する位置 start を先頭にして区切り文字を探し、最初に見つけた区切り文字をヌル文字（'\0'）に置き換える処理を行なっています。

/* 文字開始位置から文字列の分離を行う */
for (i = 0; i < strlen(start); i++) {
    for (j = 0; j < strlen(sep); j++) {
        if (start[i] == sep[j]) {
            /* 区切り文字と一致した場合 */

            /* 一致した文字をNULL文字に置き換えて分離 */
            start[i] = '\0';

            /* 次に関数を呼ばれた時の分離を再開するアドレスを覚えておく */
            next_start = &start[i] + 1;

            /* 分離開始位置のアドレスを返却 */
            return start;
        }
    }
}

このヌル文字（'\0'）への置き換えが “文字列の分離” になります。なぜならC言語では、ヌル文字（'\0'）が１つ１つの文字列の終端を表すからです。

さらに、分離を開始した位置のアドレスを返却すれば、その戻り値のアドレスが、分離後の文字列の先頭アドレスとなります。

例えば下の図の文字列の場合、区切り文字を ',' とし、分離を開始した位置、つまり 'O' の位置のアドレスが返却されますので、返却されたアドレスを printf("%s") で表示すれば One と表示されることになります。

分離を再開する位置を保持する

上記の処理において１番のポイントになるのが、return する前に static 変数である next_start を設定しているところです。この next_start は、分離後の文字列の１つ後ろの位置のアドレスを設定しています。

さらに、my_strtok 関数先頭付近の下記の部分で、第１引数 str が NULL の場合は、分離を開始するアドレスを示す start に next_start を設定するようにしています。これにより、my_strtok 関数が第１引数 str を NULL として実行された際に、前回分離した文字列の１つ後ろの文字から分離を再開することができます。

/* 分離を開始する先頭アドレスを設定 */
if (str == NULL) {
    /* NULLが指定された場合は続きから */
    start = next_start;
} else {
    /* NULL以外が指定された場合はstrから */
    start = str;
    next_start = NULL;
}

区切り文字が見つからなかったときの処理

また、区切り文字が見つかった場合は、その時点で return するようにしていますので、関数最後部分の下記が実行されるのは、区切り文字が見つからなかった時になります（区切り文字よりもヌル文字が先に見つかった）。

/* 区切り文字が１つも見つからなかった場合 */

/* 次に分離を再開する位置はヌル文字なので、
    次に関数を呼ばれた時は直ちににNULLを返却するよう、
    分離を再開するアドレスをNULLに設定しておく */
next_start = NULL;

/* 分離開始位置のアドレスを返却 */
return start;

この場合、文字列の最後まで分離を行なったことになりますので、next_start を NULL に設定するようにしています。

また、関数の先頭付近では、start が NULL の場合（つまり str も next_start も NULL の場合）は、関数が NULL を返却するようにしています。ですので、上記の next_start = NULL を行なっておくことで、次回 my_strtok 関数が第１引数 str を NULL として実行された際には必ず NULL を返却することが出来ます。

おそらく、next_start を下記のように設定したとしても、次回 my_strtok 関数が第１引数 str を NULL として実行された際には、同様に NULL を返却することはできると思います（なのでどっちでも良い）。

next_start = &start[i];

先頭の区切り文字を飛ばす

さらに、my_strtok 関数の先頭付近の下記部分では、分離を開始する位置の先頭に区切り文字があった場合に、その区切り文字を飛ばす処理を行なっています。

/* 分離開始アドレスの先頭が区切り文字の場合は飛ばす */
while (start[0] != '0') {
    for (j = 0; j < strlen(sep); j++) {
        if (start[0] == sep[j]) {
            /* 区切り文字と一致した場合 */

            /* 分離開始のアドレスを１進める */
            start++;
            break;
        }
    }

    if (j == strlen(sep)) {
        /* 先頭が区切り文字でなかった場合 */

        /* 分離処理に移る */
        break;
    }
}

区切り文字が先頭にあるかどうかを調べ、あった場合は分離を開始するアドレス start を１文字分ずつ後ろにずらす処理を行なっています。

上記により、分離後の文字列が空文字列になることを防ぐことができます。

以上が、my_strtok 関数（strtok の自作関数）の解答例のソースコードの解説になります。

ポイントは static 変数

前述の通り、この strtok 関数の自作を行う上で１番のポイントになるのが static 変数です。この static 変数を実際に利用してもらうために、自作する関数にこの strtok を選びました。

static を利用することで、関数が終了してもデータを保持することができる変数を作成することができます。

これにより、今回の例のように、前回実行時に格納したデータを次の関数実行時に利用するようなことが可能です。

今回は static 変数を利用しましたが、グローバル変数も static 変数同様にプログラム開始からプログラム終了まで変数が保持されているので、このグローバル変数でも同様のことを行うことができます。

この二つの決定的な違いはスコープですね！

グローバル変数はファイル内のどの関数からも、さらには extern 宣言を利用すればどのファイルの関数からもアクセスすることが可能です。

その一方で static 変数（より詳細には static ローカル変数）は、宣言した関数内からのみアクセス可能です。

この違いを意識して使い分けると良いと思います！

ちなみに extern 宣言については下記ページで解説していますので、詳しく知りたい方は下記ページを読んでみてください！

【C言語】extern宣言について解説（ファイル間で変数を共有）

static 変数利用時は同時動作に注意

ただ、関数内で static 変数を宣言することによるデメリットもあるので注意が必要です。

それは、同時実行すると動作結果に不整合が出る可能性がある点です。C言語では、マルチスレッドを利用することで、同じ関数を同時に実行するようなことが可能です。

例えば、解説例で示した my_strtok 関数が、２つのスレッド（スレッド１ と スレッド２ とします）から異なる文字列（文字列１と 文字列２ とします）に対してほぼ同時に実行された場合について考えてみましょう。

この際、まず スレッド１ からの my_strtok 関数実行によって next_startのアドレスが 文字列１ のものに設定されます（分離した文字列の１つ後ろの位置のアドレス）。が、すぐに スレッド２ からの my_strtok 関数が実行により、その next_start のアドレスが 文字列２ に対するアドレスに上書きされてしまいます。

そうなると、次に スレッド１ から、さらに 文字列１ を分離する目的で my_strtok 関数が実行されたとしても（第１引数を NULL として実行）、スレッド２ によって next_start が 文字列２ に対するアドレスに上書きされているため、関数実行の結果、文字列１ ではなく、文字列２ に対して分離した結果が得られてしまうことになります。

これは、自作した my_strtok 関数だけでなく、本物の strtok 関数においても生じる現象になります。

こんな感じで結果に不整合が出る原因は、next_start が static 変数であることです。static でないローカル変数（static 指定せずに関数内で宣言された変数）は、関数が実行されるたびに別の変数として（別のアドレスに）生成されることになります。ですので、同時に関数が実行されたとしても、static でないローカル変数は、同じ変数名であったとしても実体は別の変数（別のメモリ）として扱われます。

そのため、static でないローカル変数だけを利用している関数では、複数のスレッドから同時に実行されたとしても、それぞれのスレッドでは全く独立した変数を利用して動作するため、上記のような不整合は発生しません。

その一方で、static 変数（グローバル変数も）は、関数実行時ではなく、プログラム起動時に生成される変数で、プログラム終了時までずっと同じ変数（同じアドレスのメモリ）として扱われます。

したがって、複数のスレッドから同時に関数が実行されてしまうと、関数内で全く同じ変数を利用している（同じアドレスのメモリを利用している）ため、上記のように意図せずに他のスレッドからデータが上書きされて結果に不整合が発生する可能性があります。

マルチスレッドを利用したことのない方には難しい解説だったかもしれませんが、”static 変数を利用する関数は、同時実行されてしまうと結果に不整合が発生する可能性がある” ということを是非覚えておいていただければと思います。

ちなみにですが、strtok 関数の場合、上記の不整合を解決した strtok_r という関数が存在します。

strtok_r 関数の宣言は下記のようになっています。

#include <string.h>

char *strtok_r(char *str, const char *sep, char **p_next_start);

strtok 関数と比較して第３引数 p_next_start が増えており、この第３引数で、次に分離を開始するアドレスを “関数” と “関数呼び出し側” とでやりとりできるようにしています。つまり、strtok_r 関数内では、次に分離を開始するアドレスを関数内で保持せずに、関数呼び出し側に渡す＆関数呼び出し側に指定してもらうようになっています。

要は、関数内で static 変数を使用しないように、関数呼び出し側で必要な情報を保持してもらうようになっているというわけです。

こんな感じで、同時実行を考慮した場合、関数内では static 変数を利用しないようにすることが解決手段の１つになることがあります。他には排他制御なども解決手段になりますが、どの解決手段を利用するべきかは、関数の作りによるので注意してください。

この解説の中で出てきた static・マルチスレッド・排他制御に関しては下記ページで解説していますので、詳しく知りたい方はぜひ読んでみてください。

【C言語】staticローカル変数の使い方・メリットを解説

入門者向け！C言語でのマルチスレッドをわかりやすく解説

【C言語】排他制御について解説【Mutex】