C言語の標準関数を自作する：文字列処理 `strstr()`編

目次

はじめに
1. strstr()の仕様を確認する
2. 実装
🔗 関連記事・関連リンク

はじめに

C言語には、ある文字列の中から指定した別の文字列を検索し、最初に一致した位置を取得するための標準関数として strstr() が用意されています。

今回は、この strstr() を標準Cライブラリの strstr() を利用せずに自作します。

strchr() や strrchr() が1文字を検索するのに対して、 strstr() では文字列を検索します。

このプロジェクトでは、標準関数と同じインターフェースを提供するラッパー関数と、実際の処理を行うコア関数を分離する構成を採用しています。

今回作成する strstr() は、以下のような構成とします。

利用側
  ↓
my_strstr()
  ↓
core_strstr()

my_strstr() が利用側から呼び出され、実際の検索処理は core_strstr() が担当します。

なお、本プロジェクトでは、自作した標準関数模擬関数であるラッパー関数を、他の自作関数の実装から利用することを許容しています。

つまり、標準Cライブラリの関数を直接利用することは禁止しますが、自作した標準関数模擬関数については、必要に応じて他の自作関数から利用することができます。

これは、自作した標準関数群を組み合わせて利用できるようにするためのプロジェクト上の設計方針です。

1. `strstr()`の仕様を確認する

まず、標準関数としての strstr() の仕様を確認します。

Linux環境では、以下のコマンドでmanページを確認できます。

man strstr

オンラインでは、Linux man-pagesの strstr(3) — Linux manual page を参照できます。

Linux man-pages: strstr(3)

1.1 関数プロトタイプ

strstr()の関数プロトタイプは以下のとおりです。

char *strstr(const char *haystack, const char *needle);

strstr() は、2つの引数を持ちます。

第1引数で指定された文字列の中から、第2引数で指定された文字列を検索し、最初に一致した位置へのポインタを返します。

つまり、

haystack は、検索元となる文字列。

needle は、検索する部分文字列。

戻り値は、検索元の文字列の中で最初にneedleと一致した位置へのポインタです。

一致する文字列が見つからない場合は NULL を返します。

例えば、

char *lp_Result = strstr("Hello World", "World");

とした場合、"World" が "Hello World" の中で最初に出現する位置へのポインタが返されます。

返されたポインタから文字列を表示すると、

World

となります。

1.2 部分文字列を検索する

strstr()は、検索元の文字列から指定した部分文字列を検索します。

例えば、

haystack = "Hello World"
needle   = "World"

の場合、

Hello World
      ↑

このWの位置へのポインタが返されます。

返されたポインタから文字列として参照すると、

World

となります。

1.3 最初に一致した位置を返す

検索対象となる部分文字列が複数存在する場合、strstr()は最初に一致した位置を返します。

例えば、

haystack = "abcabcabc"
needle   = "abc"

の場合、

abcabcabc
^^^

最初のabcが一致するため、先頭へのポインタが返されます。

同様に、

haystack = "aaaaa"
needle   = "aaa"

の場合も、先頭のaaaが最初に一致するため、先頭へのポインタが返されます。

1.4 戻り値

検索結果によって戻り値が変わります。

部分文字列が見つかった場合

最初に一致した位置へのポインタを返します。

部分文字列が見つからなかった場合

NULLを返します。

例えば、

haystack = "Hello World"
needle   = "xxx"

では"xxx"が存在しないため、NULLが返されます。

1.5 空文字列を検索する場合

needleが空文字列の場合、strstr()は検索元の文字列の先頭を返します。

例えば、

strstr("Hello", "");

では、"Hello"の先頭へのポインタが返されます。

これは、空文字列はどの位置でも一致すると考えられるためです。

1.6 検索元が空文字列の場合

検索元が空文字列で、検索する文字列が空文字列ではない場合、検索対象は存在しないためNULLが返ります。

例えば、

strstr("", "A");

では、NULLが返ります。

1.7 `NULL`ポインタについて

標準のstrstr()では、NULLポインタを渡した場合の動作は、未定義です。

そのため、

strstr(NULL, "A");

や、

strstr("Hello", NULL);

のような呼び出しは、標準関数の仕様として安全に扱えるものではありません。

2. 実装

ここまでで、標準 strstr() の基本的な仕様を確認しました。

では、先程確認した仕様を参考に、実際に strstr() を自作してみます。

今回のプロジェクトでは、利用側から呼び出されるラッパー関数と、実際の処理を行うコア関数を分離しています。

実装はこちらです。

2.1 コア関数のヘッダーファイル

まず、コア関数のインターフェースをヘッダーファイルに定義します。

core_strstr.h

#ifndef CORE_STRING_CORE_STRSTR_H
#define CORE_STRING_CORE_STRSTR_H

#include "myc/myc_define.h"

EXTERN char *core_strstr(
    const char *ap_Haystack,
    const char *ap_Needle);

#endif

core_strstr() は、検索対象となる ap_Haystack と、検索する文字列 ap_Needle を受け取ります。

戻り値は、検索に成功した場合は一致した位置へのポインタ、見つからなかった場合や NULL 入力の場合は NULL です。

ヘッダーファイルには、プロジェクトのコーディングルールに従い、インクルードガードを付けています。

インクルードガードは、同じヘッダーファイルが複数回インクルードされた場合に、定義が重複することを防ぐためのものです。

また、EXTERN はプロジェクト共通で使用するマクロです。

2.2 コア関数の実装

コア関数では、実際の文字列検索を行います。

core_strstr.c

#include <stddef.h>
#include "core/string/core_strstr.h"

char *core_strstr(
    const char *ap_Haystack,
    const char *ap_Needle)
{
    size_t lv_HaystackIndex = 0;
    size_t lv_NeedleIndex = 0;

    if (NULL == ap_Haystack) {
        return NULL;
    }

    if (NULL == ap_Needle) {
        return NULL;
    }

    if ('\0' == ap_Needle[0]) {
        return (char *)ap_Haystack;
    }

    while ('\0' != ap_Haystack[lv_HaystackIndex]) {
        lv_NeedleIndex = 0;

        while (('\0' != ap_Needle[lv_NeedleIndex]) &&
               (ap_Haystack[lv_HaystackIndex + lv_NeedleIndex] ==
                ap_Needle[lv_NeedleIndex])) {
            lv_NeedleIndex++;
        }

        if ('\0' == ap_Needle[lv_NeedleIndex]) {
            return (char *)&ap_Haystack[lv_HaystackIndex];
        }

        lv_HaystackIndex++;
    }

    return NULL;
}

まず、lv_HaystackIndex と lv_NeedleIndex の2つのインデックスを用意しています。

lv_HaystackIndex は検索対象である ap_Haystack の、現在検索している位置を表します。

一方、lv_NeedleIndex は検索する文字列 ap_Needle の何文字目を比較しているかを表します。

最初に ap_Haystack と ap_Needle が NULL ではないか確認しています。

if (NULL == ap_Haystack) {
    return NULL;
}

if (NULL == ap_Needle) {
    return NULL;
}

これは標準の strstr() の仕様ではなく、本プロジェクト独自の安全性対策です。

次に、検索する文字列が空文字列か確認します。

if ('\0' == ap_Needle[0]) {
    return (char *)ap_Haystack;
}

空文字列の場合は、ap_Haystack の先頭を返します。

その後、ap_Haystack の先頭から順番に検索を開始します。

while ('\0' != ap_Haystack[lv_HaystackIndex]) {

検索対象の文字列の終端に到達するまで、検索開始位置を1文字ずつ移動していきます。

各検索開始位置では、まず lv_NeedleIndex を 0 に戻します。

lv_NeedleIndex = 0;

そして、ap_Needle の先頭から1文字ずつ比較します。

while (('\0' != ap_Needle[lv_NeedleIndex]) && 
        (ap_Haystack[lv_HaystackIndex + lv_NeedleIndex]
         == ap_Needle[lv_NeedleIndex])) {
    lv_NeedleIndex++;
}

ここでは、次の2つを同時に確認しています。

ap_Needle の終端に到達していないこと.
ap_Haystack と ap_Needle の文字が一致していること.

文字が一致している間は lv_NeedleIndex を進め、次の文字を比較します。

そして、ap_Needle の終端まで到達していれば、検索文字列全体が一致したことになります。

if ('\0' == ap_Needle[lv_NeedleIndex]) {
    return (char *)&ap_Haystack[lv_HaystackIndex];
}

この時点で lv_HaystackIndex は一致した部分文字列の先頭位置を示しているため、その位置へのポインタを返します。

一方、途中で文字が一致しなかった場合は、検索開始位置を1文字進めます。

lv_HaystackIndex++;

例えば、

ap_Haystack = "ababc"
ap_Needle   = "abac"

の場合、最初の位置から "aba" までは一致しますが、次の文字で一致しません。

この場合は検索をそこで終了するのではなく、検索開始位置を1文字進めて、次の位置から再び ap_Needle の先頭との比較を開始します。

この処理を ap_Haystack の終端まで繰り返します。

最後まで一致する位置が見つからなかった場合は、NULL を返します。

return NULL;

このように、今回の実装では検索対象の各位置を順番に調べ、その位置から ap_Needle 全体が一致するかを確認する、シンプルな方法を採用しています。

2.3 ラッパー関数のヘッダーファイル

次に、利用側から呼び出されるラッパー関数のインターフェースを定義します。

my_strstr.h

#ifndef WRAPPER_STRING_MY_STRSTR_H
#define WRAPPER_STRING_MY_STRSTR_H

#include "myc/myc_define.h"

/*
 * 標準関数: strstr.
 *
 * 文字列から指定した部分文字列を検索し、
 * 最初に一致した位置を返します.
 *
 * 引数:
 *   ap_Haystack : 検索元の文字列.
 *   ap_Needle   : 検索する文字列.
 *
 * 戻り値:
 *   文字列発見   : 最初に一致した位置へのポインタ.
 *   文字列未発見 : NULL.
 *   NULL入力     : NULL.
 *
 * 標準strstrとの相違点:
 *   標準strstrではNULLポインタを渡した場合の動作は保証されません.
 *   本関数ではNULLを独自に処理し、NULLを返します.
 */
EXTERN char *my_strstr(
    const char *ap_Haystack,
    const char *ap_Needle);

#endif

こちらのヘッダーファイルにもインクルードガードを付けています。

また、利用側に対して標準 strstr() と同じ引数の型を提供します。

こちらは利用側に公開するインターフェースです。

2.4 ラッパー関数の実装

ラッパー関数では、利用側から呼び出される my_strstr() を実装します。

my_strstr.c

#include "core/string/core_strstr.h"
#include "wrapper/string/my_strstr.h"

char *my_strstr(
    const char *ap_Haystack,
    const char *ap_Needle)
{
    return core_strstr(ap_Haystack, ap_Needle);
}

ラッパー自身は連結処理を行わず、コア関数へ処理を委譲しています。

今回の実装では、

my_strstr()
    ↓
core_strstr()
    ↓
文字列探索

という役割分担になります。

ここまでで、実際に動作する strstr() の実装を確認しました。

ただし、このコードには、本プロジェクト独自の仕様やコーディング規約が反映されています。

🔗 関連記事・関連リンク

この記事の最新アップデートや、このシリーズの関連記事は以下のリンクからご覧いただけます。

内容は基本的に同じですので、お好みのサイトでお読みください。

🟢 Zenn

この記事の最新版はこちら。
https://zenn.dev/malloc/articles/13_string_strstr
「標準関数自作」Topicの関連記事はこちら。
https://zenn.dev/topics/標準関数自作

🔵 Qiita

「標準関数自作」タグの関連記事はこちら。
https://qiita.com/tags/標準関数自作

🧡 note

このシリーズの記事はこちら。
要件定義以降は、有料パートとしてこちらで公開。
https://note.com/lofty_lilac5806/m/m5d52012f476d