Re: Libft

Libft をもう一度書きたい

ft_isascii

manよりisasciiの定義

checks whether c is a 7-bit unsigned char value that fits into the ASCII character set.

つまり、0〜127であれば真、その他が偽となる。
この通りに条件式書いてもいいけど、まずis-系共通で

These functions check whether c, which must have the value of an unsigned char or EOF

とあって、前提として引数がunsigned char（0以上の値）だったら127以下の判定だけでいいのでは？と思ったけど、EOFが-1だからEOFを弾くために0以上という条件式も必要そう。

ft_strlcpy, ft_strlcat

strl-系いまだに理解が曖昧。

manより定義

The strlcpy() and strlcat() functions copy and concatenate strings respectively. They are designed to be safer, more consis‐tent, and less error prone replacements for strncpy(3) and strncat(3). Unlike those functions, strlcpy() and strlcat() take the full size of the buffer (not just the length) and guarantee to NUL-terminate the result (as long as size is larger than 0 or, in the case of strlcat(), as long as there is at least one byte free in dst). Note that a byte for the NUL should be in‐ cluded in size. Also note that strlcpy() and strlcat() only operate on true “C” strings. This means that for strlcpy() src must be NUL-terminated and for strlcat() both src and dst must be NUL-terminated.

引数のsizeは、dstのフルバッファサイズをとる。
そしてヌル終端を保証する。←ただし、前述のフルバッファサイズが0以上のとき。strlcatでは、dstに少なくとも1バイト（ヌル終端用）が残っているとき。だからフルバッファサイズにはヌル終端分の1バイトが含まれている必要がある。
また、strlcpyとstrlcatはヌル終端されている文字列に対してのみ動作するため、strlcpyのsrc, strlcatのsrcとdstはヌル終端文字列でなければならない。
こんな仕様だから、バッファオーバーフローの危険がなくヌル終端まであるってことで、strcpyやstrncpyより安全。

The strlcpy() and strlcat() functions return the total length of the string they tried to create. For strlcpy() that means the length of src.

strlcpyとstrlcatは作ろうとした文字列の全長を返す。
strlcpyの返り値はsrc文字列の長さ。dstにsrcをコピーするから、完成した文字列の長さはコピー元と同じ。

ft_strchr

公開されているテスターのどれかでint cに1024を渡したときに、比較時にcをcharにキャストしているかどうかで判定が変わることがあったのを思い出した。
manには

The strchr() function returns a pointer to the first occurrence of the character c in the string s.
Here "character" means "byte"; these functions do not work with wide or multibyte characters.

とあるから、キャストは必要ない気もするけどどうなんだろう。

まず、1024をprintfの%cで出力してみたら、

% ./a.out | cat -e 
^@

これは0を指定したときと同じ出力！

どうして同じになるのか知りたい。
+1して1025の場合。

% ./a.out | cat -e 
^A

これは1を指定した場合と同じ結果。

さらに+1して1026の場合。

% ./a.out | cat -e 
^B

これは2を指定した場合と同じ結果。

まとめると以下の通り。

#include <stdio.h>

int main(void)
{
	printf("---out of range---\n");
	printf("1024:%c\n", 1024);
	printf("1025:%c\n", 1025);
	printf("1026:%c\n", 1026);

	printf("---in range---\n");
	printf("0:%c\n", 0);
	printf("1:%c\n", 1);
	printf("2:%c\n", 2);

	return 0;
}

% ./a.out | cat -e
---out of range---$
1024:^@$
1025:^A$
1026:^B$
---in range---$
0:^@$
1:^A$
2:^B$

予想として、charの範囲外の値がcharに型変換されるすると一番下の桁のビットだけ残って他のビットは切り捨てられる、ってことだと思う。

https://www.jpcert.or.jp/sc-rules/c-int31-c.html#:~:text=通常、ある整数をより小さな型に変換すると、上位ビットが切り捨てられる。
新しい型が符号なしか符号つきかによっても違うらしいので、まず自分の環境でcharがどっちか調べる。

% getconf CHAR_MIN
-128

自分の環境では、char = signed charだとわかった。
となると、

新しい型が符号付き整数型であって、値がその型で表現できない場合は、結果が 処理系定義の値 となるか、または処理系定義のシグナルを生成するかのいずれかとする。

処理系依存らしい...。

通常、ある整数をより小さな型に変換すると、上位ビットが切り捨てられる。

自分の環境でもこの処理がされてるっぽいので予想通りかも。

charに型変換したときにどうなるかはわかったけど、結局キャスト自体必要なのか？
本家の挙動を再現しないといけないため、本家の挙動を調べる。

#include <stdio.h>
#include <string.h>

int main(void)
{
	char *str = "42Tokyo";
	char *result = NULL;
	
	result = strchr(str, 1024);
	printf("strchr:%p\n", result);

	if (*result == '\0')
		printf("result is null character.\n");

	return 0;
}

% ./a.out
strchr:0x40200b
result is null character.

探す文字が文字列の中に存在しない場合はNULLが返るが、末尾のヌル文字へのポインタが返ってきている。つまり、1024が0として比較に用いられたことで、末尾のヌル文字と一致したと判定されて、末尾のヌル文字へのポインタが返ってきたことになる。
【結論】
strchrの挙動を再現するためには、比較時にcをcharにキャストする必要がある。

ft_memchr

文字列ではなくメモリ領域の比較だから、whileにヌル文字までみたいな条件式はいらない。
文字列が入っているとしても、ヌル終端に関係なくnバイト比較する。

ft_lstadd_back

newのnextにNULLを代入する必要はない。（条件にない。）

NULLガードを実装するかどうか

前回（課題提出時）は全ての関数でNULLガードをするように統一していて、今回は必要不可欠なもの以外はNULLガード実装しない方針で当初考えていたけど、

• 一貫したエラーハンドリングにより、関数ごとに異なる挙動を心配する必要がなくなってライブラリの使い勝手が良くなる
• 引数で予期しないNULLが渡された場合に予測不可能な動作をするリスクを軽減できる

あたりを考慮すると、やっぱり全部にNULLガード実装したい。
しかし、Part1は既存の関数の再実装なので、Part2とBonusの関数でNULLガードを行うことにする。

ft_lstmapの実装方法によっては、ft_lstadd_backに最初のノードが存在しない場合の処理を実装しないとSegmentation faultになる。
公開されているテスターのうち一部で上記の実装がないとKOになるのもft_lstmapの実装に関わることが理由だと思われる。

例えば、以下のような実装ではSegmentation faultになる。

t_list	*ft_lstmap(t_list *lst, void *(*f)(void *), void (*del)(void *))
{
	t_list	*start;
	t_list	*tmp;

	start = NULL;
	while (lst)
	{
		tmp = ft_lstnew(f(lst->content));
		if (!tmp)
		{
			ft_lstclear(&start, del);
			return (NULL);
		}
		ft_lstadd_back(&start, tmp);
		lst = lst->next;
	}
	return (start);
}

void	ft_lstadd_back(t_list **lst, t_list *new)
{
	t_list	*last;

	last = ft_lstlast(*lst);
	last->next = new;
}

このft_lstmapでは最初startにNULLをセットし、その後ft_lstnewでノードを一つ確保し、ft_lstadd_backでstartに足していくことで元のリストと同じサイズのリストを作っている。

問題は、最初startがNULLの状態でwhileループに入った場合である。
無事にtmpが確保されると、ft_lstadd_backに&startとtmpが渡されるはずである。しかし、startはNULLなので、&startでアドレスを参照しようとすると、Segmentation faultになってしまう。
よって、ft_lstadd_backには、リストの最初のノードが存在しない場合の処理が必要である。
例えば、以下のコードを追加する。

if (!*lst)
{
    *lst = new;
    return ;
}

NULLガード

基本的には引数のどれか（少なくとも一つに）NULLが渡されたときにガードするよう条件式を書く。

void	ft_lstdelone(t_list *lst, void (*del)(void *))
{
	if (!lst || !del)
		return ;

以下特殊なパターン。

ft_lstadd_back

上記の*lstがNULLの場合（つまり、最初のノードが存在しない場合）の他に、lstまたはnewがNULLの場合が存在するためガードする。

ft_lstadd_front

ft_lstadd_backに同じく3パターンあるが、*lstがNULLの場合はNULLだったところに新しくノードがセットされる動作をするため問題ない。lstまたはnewがNULLの場合のみガードすればよい。

ft_lstclear, ft_lstiter

私はwhile (*lst)やwhile (lst)という条件式を用いていて、while文に渡された変数がNULLでも条件式の評価が偽となってwhileに入らず関数の処理が終わるだけで、while文の外でも参照していないため先にNULLガードしなくても問題はない。そのため、別途用意したNULLガードはその他の引数がNULLの場合のみ。

ft_calloc

無効なnmemb, sizeが渡された場合のエラーハンドリングについて。

以下callocのman

The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either NULL, or a unique pointer value that can later be successfully passed to free(). If the multiplication of nmemb and size would result in integer overflow, then calloc() returns an er‐ror. By contrast, an integer overflow would not be detected in the following call to malloc(), with the result that an incorrectly sized block of memory would be allocated:
malloc(nmemb * size);

つまり、もしnmembまたはsizeが0の場合、callocはNULLを返すか、後でfreeに正常に渡すことができるポインタを返す。似た記述がmallocのmanにもある。
https://www.jpcert.or.jp/sc-rules/c-mem04-c.html
mallocもcallocも確保するサイズに0が渡されたときの動作は処理系定義らしい。

また、nmembとsizeの乗算がオーバーフローを引き起こす場合、callocはエラーを返す。対照的に、以下のmalloc呼び出しではオーバーフローが検出されることはなく、その結果として不正確なサイズのメモリブロックが割り当てられることになる：malloc(nmemb * size);

以上のことから、nmemb * sizeがオーバーフローを引き起こす（size_tの最大値 = SIZE_MAXを超える）場合本家callocはエラーを返すため無効とするべきで、少なくともどちらかに0が渡された場合はそのままmallocに渡すことで本家の挙動が保たれるため無効とする必要はない、と結論づけることができる。（ここでは、Part1の関数ということで本家の挙動が再現されるかに重点を置く。）

ft_atoi

オーバーフローの処理について。

atoiのmanより抜粋。

The atoi() function converts the initial portion of the string pointed to by nptr to int. The behav‐ ior is the same as
strtol(nptr, NULL, 10);
except that atoi() does not detect errors.

strtol(nptr, NULL, 10);とほぼ同じ挙動をするということで、strtolのmanを読むと、

The strtol() function returns the result of the conversion, unless the value would underflow or over‐flow. If an underflow occurs, strtol() returns LONG_MIN. If an overflow occurs, strtol() returns LONG_MAX.

strtolでは、アンダーフローが起きるとLONG_MINが返り、オーバーフローが起きるとLONG_MAXが返ると書いてある。
前述の通り、atoiがstrtol(nptr, NULL, 10);と同じ挙動をするなら、この挙動も再現する必要がある。

試行錯誤した結果、以下のコードになった。signは符号。
&&の右側の条件式はresult * 10 + (*nptr - '0') > INT_MAXを移項させたもの。（INT_MINのときも同じ感じ。）

if (sign == 1 && result > (INT_MAX - (*nptr - '0')) / 10)
    return ((int)LONG_MAX);
else if (sign == -1 && -(result) < (INT_MIN + (*nptr - '0')) / 10)
    return ((int)LONG_MIN);

条件式内ではオーバーフローの判定をしたいため、文字列の変換先の型であるintの範囲外かどうかを条件とする。つまり、INT_MAXとINT_MINを条件とする。だが、返り値はstrtolのmanに記載されている通りLONG_MINとLONG_MAXにしたい。（ただし、返り値はint型なのでキャストする。）

アンダーフローの定義は、マイナスの範囲外になることではなく、計算結果の絶対値が表現可能な最小値より小さくなってしまうことな気もするけど、本家のatoiの挙動を調べたら今回のft_atoiの実装で同じ挙動になるのでこれで問題ないことにしておく。