C言語で文字列を簡単にかつ少し高速に操作する

C言語では文字列を連結していくと、メモリの再確保とかしなくてはならないのでとても面倒です。

さらに、strcatを利用すると、
以下のように文字列連結をした場合。

strcat(str1, str2);

char *strcat(char *s1, const char *s2) {
    int len = strlen(s1);

    strcpy(s1 + len, s2);

    return s1;
}

となっている(はず)ため、連結を行う度に線形探索による文字数カウントが行われる。よって、連結を行う操作が多いと処理速度が大幅に低下する。特にオーダーがO(n)になるため、s1の文字数が多くなるとパフォーマンスは最悪だ。
そこで、常に文字数を保持しておくことでstrlenを省くことができ、連結のコストを抑えることができるのだ。

ソース

MyString.h

#ifndef __MY_STRING_H__
#define __MY_STRING_H__

#include <stdlib.h>
#include <string.h>

#define STRING_ALLOC_SIZE (1024)

typedef unsigned int unichar;

typedef struct MyString {
	char *str;
	size_t length;
	size_t buff_length;
} MyString;

MyString *new_string();
void free_string(MyString *mstr);
size_t my_strlen(MyString *mstr);
void resize_string(MyString *mstr, size_t size);
char *my_strcat(MyString *mstr, const char *str);
char *my_strncat(MyString *mstr, const char *str, size_t n);
char *my_chrcat(MyString *mstr, const char c);
char *my_strcat2str(MyString *mstr, const char *str, const char *end_str);
char *my_strcat2chr(MyString *mstr, const char *str, const char endc);
char *my_strcat2ptr(MyString *mstr, const char *str, const char *endp);

#endif

MyString.c

#include "MyString.h"

MyString *new_string() {
	MyString *mstr = (MyString *)malloc(sizeof(MyString));
	
	mstr->str = (char *)malloc(STRING_ALLOC_SIZE);
	mstr->str[0] = '\0';
	mstr->length = 0;
	mstr->buff_length = STRING_ALLOC_SIZE;

	return mstr;
}

void free_string(MyString *mstr) {
	if (mstr) {
		free(mstr->str);
		free(mstr);
	}
}

size_t my_strlen(MyString *mstr) {
	return mstr->length;
}

void resize_string(MyString *mstr, size_t size) {
	if (size > mstr->buff_length) {
		mstr->buff_length = (size / STRING_ALLOC_SIZE + 1) * STRING_ALLOC_SIZE * 2;
		mstr->str = (char *)realloc(mstr->str, mstr->buff_length);
	}
}

char *my_strcat(MyString *mstr, const char *str) {
	size_t len = mstr->length + strlen(str);
	resize_string(mstr, len + 1);
	strcpy(mstr->str + mstr->length, str);
	mstr->length = len;

	return mstr->str;
}

char *my_strncat(MyString *mstr, const char *str, size_t n) {
	size_t len = mstr->length + n;
	resize_string(mstr, len + 1);
	strncpy(mstr->str + mstr->length, str, n);
	mstr->length = len;

	return mstr->str;
}

char *my_chrcat(MyString *mstr, const char c) {
	resize_string(mstr, mstr->length + 2);
	mstr->str[mstr->length++] = c;
	mstr->str[mstr->length] = '\0';

	return mstr->str;
}

char *my_strcat2str(MyString *mstr, const char *str, const char *end_str) {
	char *end = strstr(str, end_str);

	if (end != NULL) {
//		end += strlen(end_str);
		return my_strcat2ptr(mstr, str, end);
	}

	return (char *)mstr->str;
}

char *my_strcat2chr(MyString *mstr, const char *str, const char endc) {
	char *end = strchr(str, endc);

	if (end != NULL) {
//		end++;
		return my_strcat2ptr(mstr, str, end);
	}

	return (char *)mstr->str;
}

char *my_strcat2ptr(MyString *mstr, const char *str, const char *endp) {
	size_t cat_len = endp - str - 1;

	if (cat_len > 0) {
		my_strncat(mstr, str, cat_len);
	}

	return (char *)mstr->str;
}

使い方

関数名	用途	引数
MyString *new_string()	MyStringを作成	なし
void free_string(MyString *mstr)	MyStringの解放	解放するMyString
size_t my_strlen(MyString *mstr)	MyStringの文字長	文字長をカウントするMyString
char *my_strcat(MyString *mstr, const char *str)	文字列の連結	mstr:MyString str:連結する文字列
char *my_strncat(MyString *mstr, const char *str, size_t n)	n文字連結	n:連結する文字数
char *my_chrcat(MyString *mstr, const char c)	1文字連結	c連結する文字
char *my_strcat2str(MyString *mstr, const char *str, const char *end_str)	指定文字列前まで連結	end_str:指定文字列
char *my_strcat2chr(MyString *mstr, const char *str, const char endc)	指定文字前まで連結	endc:指定文字
char *my_strcat2ptr(MyString *mstr, const char *str, const char *endp)	指定ポインタ前まで連結	endp:指定ポインタ

※各連結関数はchar*を返すようになっており、連結後の文字列の先頭ポインタを返している。
※文字列の連結で確保しているメモリより大きくなる場合は、動的にメモリの再確保を行っているため、メモリの大きさを気にする必要が無い。
※内部的に文字列の長さを計算しているため、外部で文字列を操作することは望ましくない！

使用例

#include <stdio.h>
#include "MyString.h"

int main(int argc, char **argv) {
	MyString *str = new_string();

	printf("str = %s\n", my_strcat(str, "test"));
	printf("str = %s\n", my_strncat(str, "1234567890", 4));
	printf("str = %s\n", my_chrcat(str, ':'));
	printf("str = %s\n", my_strcat2str(str, "abcd<br />", "<br />"));
	printf("str = %s\n", my_strcat2chr(str, "wxyz<br />", '<'));

	free_string(str);

	return 0;
}

出力

str = test
str = test1234
str = test1234:
str = test1234:abc
str = test1234:abcwxy

まとめ

本来なら、既存の連結と比較し速度向上率を算出すべきですが、今日のところは勘弁を。。
JSONのパーサを作った時に利用したが、本ソースを利用することで格段に処理速度が上がった。
JSONパーサも後ほど紹介します。