第5章：動的メモリ管理とプログラム設計の哲学
5.1 メモリアロケータの設計と実装
5.1.1 なぜmallocは必要だったのか - 動的メモリの歴史
コンピュータプログラミングの黎明期、メモリ管理は単純だった。1950年代のプログラムは固定されたメモリ領域で動作し、データサイズは事前に決定されていた。しかし、プログラムが複雑になるにつれ、この制限は深刻な問題となった。
初期のメモリ管理（1950年代）
block-beta
columns 1
block:os
OS["Operating System"]
end
block:code
Code["Program Code"]
end
block:data
Data["Static Data (Fixed Size)"]
end
block:unused
Unused["Unused Memory (Wasted)"]
end
style OS fill:#f9f,stroke:#333,stroke-width:2px
style Code fill:#bbf,stroke:#333,stroke-width:2px
style Data fill:#bfb,stroke:#333,stroke-width:2px
style Unused fill:#ddd,stroke:#333,stroke-width:2px,stroke-dasharray: 5 5
初期のFORTRANプログラムでは、配列サイズをコンパイル時に決定する必要があった：
C FORTRAN 77での固定サイズ配列
DIMENSION ARRAY(1000)
C 1000要素を超えるデータは処理不可能
C 小さなデータでもメモリを浪費
動的メモリの誕生
1960年代、LISPの開発者John McCarthyは、プログラム実行中にメモリを動的に割り当てる必要性を認識した。これは、LISPのリスト構造が事前にサイズを決定できないためだった。
McCarthyは「ガベージコレクション」の概念も導入したが、CとUNIXの設計者たちは異なるアプローチを選択した。Dennis RitchieとKen Thompsonは、プログラマに明示的なメモリ管理を委ねるmalloc/freeインターフェースを設計した。
/* 1970年代のUNIX V7におけるmalloc（簡略化） */
char *malloc(unsigned nbytes)
{
/* ヒープから連続したnbytesを割り当て */
/* 失敗時はNULLを返す */
}
void free(char *p)
{
/* 以前に割り当てたブロックを解放 */
}
設計上のトレードオフ
- 明示的 vs 自動管理
- 断片化 vs シンプルさ
- 速度 vs メモリ効率
5.1.2 メモリアロケータの内部構造
現代のmalloc実装を理解するため、基本的なアロケータを段階的に構築しよう。
最も単純なアロケータ：Bump Allocator
/*
* Bump Allocator（Arena Allocator）
*
* 最も単純で高速だが、個別解放が不可能
* 一括解放のみサポート
*/
typedef struct s_arena {
char *base; /* ヒープ領域の先頭 */
char *current; /* 次の割り当て位置 */
char *end; /* ヒープ領域の終端 */
} t_arena;
/* アリーナの初期化 */
t_arena *arena_create(size_t size)
{
t_arena *arena = mmap(NULL, sizeof(t_arena) + size,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (arena == MAP_FAILED)
return NULL;
arena->base = (char *)(arena + 1);
arena->current = arena->base;
arena->end = arena->base + size;
return arena;
}
/* O(1)の超高速割り当て */
void *arena_alloc(t_arena *arena, size_t size)
{
/* アライメント調整（8バイト境界） */
size = (size + 7) & ~7;
if (arena->current + size > arena->end)
return NULL; /* 領域不足 */
void *ptr = arena->current;
arena->current += size;
return ptr;
}
/* 個別解放はできない - 一括リセットのみ */
void arena_reset(t_arena *arena)
{
arena->current = arena->base;
}
void arena_destroy(t_arena *arena)
{
munmap(arena, arena->end - (char *)arena);
}
Free List Allocator
個別解放をサポートする基本的なアロケータ：
/*
* Free List Allocator
*
* 解放されたブロックをリンクリストで管理
* First-Fit戦略を使用
*/
/* ブロックヘッダ */
typedef struct s_block {
size_t size; /* ブロックサイズ（ヘッダ除く） */
int is_free; /* 使用中か解放済みか */
struct s_block *next; /* 次のブロックへのポインタ */
struct s_block *prev; /* 前のブロックへのポインタ */
} t_block;
#define BLOCK_HEADER_SIZE sizeof(t_block)
#define MIN_BLOCK_SIZE 16
static t_block *heap_start = NULL;
/*
* ヒープを拡張（sbrk呼び出し）
*/
static t_block *extend_heap(size_t size)
{
t_block *block = sbrk(0);
if (sbrk(BLOCK_HEADER_SIZE + size) == (void *)-1)
return NULL;
block->size = size;
block->is_free = 0;
block->next = NULL;
block->prev = NULL;
/* リストに追加 */
if (!heap_start) {
heap_start = block;
} else {
t_block *current = heap_start;
while (current->next)
current = current->next;
current->next = block;
block->prev = current;
}
return block;
}
/*
* First-Fit検索：最初の十分なサイズのブロックを返す
*/
static t_block *find_first_fit(size_t size)
{
t_block *current = heap_start;
while (current) {
if (current->is_free && current->size >= size)
return current;
current = current->next;
}
return NULL;
}
/*
* ブロックを分割（残りを新しい空きブロックに）
*/
static void split_block(t_block *block, size_t size)
{
size_t remaining = block->size - size - BLOCK_HEADER_SIZE;
/* 分割する価値があるか確認 */
if (remaining < MIN_BLOCK_SIZE)
return;
t_block *new_block = (t_block *)((char *)(block + 1) + size);
new_block->size = remaining;
new_block->is_free = 1;
new_block->next = block->next;
new_block->prev = block;
if (block->next)
block->next->prev = new_block;
block->next = new_block;
block->size = size;
}
/*
* malloc実装
*/
void *ft_malloc(size_t size)
{
if (size == 0)
return NULL;
/* アライメント調整 */
size = (size + 7) & ~7;
/* 既存の空きブロックを検索 */
t_block *block = find_first_fit(size);
if (block) {
/* 適切なサイズに分割 */
split_block(block, size);
block->is_free = 0;
return (block + 1); /* ヘッダの次のアドレスを返す */
}
/* 新しいブロックを割り当て */
block = extend_heap(size);
if (!block)
return NULL;
return (block + 1);
}
/*
* 隣接する空きブロックを結合（Coalescing）
*/
static void coalesce(t_block *block)
{
/* 次のブロックと結合 */
if (block->next && block->next->is_free) {
block->size += BLOCK_HEADER_SIZE + block->next->size;
block->next = block->next->next;
if (block->next)
block->next->prev = block;
}
/* 前のブロックと結合 */
if (block->prev && block->prev->is_free) {
block->prev->size += BLOCK_HEADER_SIZE + block->size;
block->prev->next = block->next;
if (block->next)
block->next->prev = block->prev;
}
}
/*
* free実装
*/
void ft_free(void *ptr)
{
if (!ptr)
return;
t_block *block = ((t_block *)ptr) - 1;
/* 二重解放チェック */
if (block->is_free) {
/* エラー：二重解放を検出 */
return;
}
block->is_free = 1;
/* 隣接ブロックと結合して断片化を軽減 */
coalesce(block);
}
ヒープの可視化
block-beta
columns 6
block:step1
H1["Header(16)"]
D1["Data(16)"]
H2["Header(8)"]
F1["FREE"]
H3["Header(64)"]
D2["Data(64)"]
end
space
Empty["Empty Heap..."]
style F1 fill:#faa,stroke:#333,stroke-width:2px
5.1.3 メモリ断片化の問題
外部断片化（External Fragmentation）
packet-beta
title External Fragmentation
0-19: "Used"
20-39: "Free (20)"
40-59: "Used"
60-89: "Free (30)"
90-109: "Used"
110-159: "Free (50)"
160-179: "Used"
内部断片化（Internal Fragmentation）
packet-beta
title Internal Fragmentation (16-byte alignment)
0-7: "Header (8)"
8-20: "Data (13)"
21-23: "Padding (3)"
24-31: "Next Block"
断片化対策
/*
* Best-Fit戦略：最も近いサイズのブロックを選択
* 外部断片化を軽減するが、検索が遅い
*/
static t_block *find_best_fit(size_t size)
{
t_block *current = heap_start;
t_block *best = NULL;
size_t best_diff = SIZE_MAX;
while (current) {
if (current->is_free && current->size >= size) {
size_t diff = current->size - size;
if (diff < best_diff) {
best = current;
best_diff = diff;
if (diff == 0)
break; /* 完璧な適合 */
}
}
current = current->next;
}
return best;
}
/*
* Buddy System：2のべき乗サイズのブロック管理
* 高速な結合が可能だが、内部断片化が増加
*/
#define MAX_ORDER 10 /* 最大ブロック = 2^10 = 1024 */
typedef struct s_buddy {
t_block *free_lists[MAX_ORDER + 1];
char *base;
size_t total_size;
} t_buddy;
size_t order_of_size(size_t size)
{
size_t order = 0;
size_t block_size = 1;
while (block_size < size) {
block_size <<= 1;
order++;
}
return order;
}
5.1.4 現代のアロケータ設計
dlmalloc（Doug Lea's malloc）
1987年にDoug Leaが設計したdlmallocは、多くのシステムの基礎となった：
/*
* dlmallocの主要な設計特徴：
*
* 1. 境界タグ：ブロックの前後にサイズ情報
* 2. ビニング：サイズクラスごとにフリーリストを分離
* 3. 即時結合：解放時に隣接ブロックを結合
*/
/* 境界タグ構造 */
typedef struct s_chunk {
size_t prev_size; /* 前のチャンクのサイズ（フリー時のみ有効） */
size_t size; /* このチャンクのサイズ + フラグ */
/* データ領域... */
/* 末尾にもサイズ情報（双方向走査のため） */
} t_chunk;
/* サイズの最下位ビットをフラグとして使用 */
#define PREV_INUSE 0x1 /* 前のチャンクが使用中 */
#define IS_MMAPPED 0x2 /* mmapで割り当て */
#define NON_MAIN 0x4 /* メインアリーナ以外 */
#define GET_SIZE(c) ((c)->size & ~0x7)
#define IS_FREE(c) (!((c)->size & PREV_INUSE))
jemalloc（Jason Evans malloc）
FreeBSDとFirefoxで使用される高性能アロケータ：
/*
* jemallocの革新的な特徴：
*
* 1. スレッドキャッシュ（tcache）
* 2. 複数アリーナによる競合削減
* 3. サイズクラスの最適化
*/
/* サイズクラス（概念図） */
/*
* Small: 8, 16, 32, 48, 64, 80, 96, 112, 128, ...
* Large: 4KB, 8KB, 16KB, ...
* Huge: 2MB, 4MB, ... (直接mmap)
*/
/* スレッドローカルキャッシュ */
typedef struct s_tcache {
void *small_bins[NBINS]; /* サイズクラスごとのキャッシュ */
size_t counts[NBINS]; /* 各ビンのエントリ数 */
} t_tcache;
/*
* 割り当てパス：
* 1. tcacheから割り当て（最速、ロックなし）
* 2. アリーナのbinから割り当て
* 3. 新しいページを取得
*/
メモリプールパターン
特定のオブジェクト用の効率的なアロケータ：
/*
* 固定サイズメモリプール
*
* 同一サイズのオブジェクトを高速に割り当て・解放
* ゲームやリアルタイムシステムで多用
*/
typedef struct s_pool_block {
struct s_pool_block *next;
} t_pool_block;
typedef struct s_pool {
t_pool_block *free_list;
char *memory;
size_t block_size;
size_t block_count;
size_t used_count;
} t_pool;
t_pool *pool_create(size_t block_size, size_t count)
{
t_pool *pool = malloc(sizeof(t_pool));
if (!pool)
return NULL;
/* ブロックサイズはポインタ以上 */
if (block_size < sizeof(t_pool_block))
block_size = sizeof(t_pool_block);
/* アライメント調整 */
block_size = (block_size + 7) & ~7;
pool->memory = malloc(block_size * count);
if (!pool->memory) {
free(pool);
return NULL;
}
pool->block_size = block_size;
pool->block_count = count;
pool->used_count = 0;
/* フリーリストを構築 */
pool->free_list = NULL;
for (size_t i = 0; i < count; i++) {
t_pool_block *block = (t_pool_block *)(pool->memory + i * block_size);
block->next = pool->free_list;
pool->free_list = block;
}
return pool;
}
/* O(1)の割り当て */
void *pool_alloc(t_pool *pool)
{
if (!pool->free_list)
return NULL; /* プール枯渇 */
t_pool_block *block = pool->free_list;
pool->free_list = block->next;
pool->used_count++;
return block;
}
/* O(1)の解放 */
void pool_free(t_pool *pool, void *ptr)
{
if (!ptr)
return;
t_pool_block *block = ptr;
block->next = pool->free_list;
pool->free_list = block;
pool->used_count--;
}
void pool_destroy(t_pool *pool)
{
if (!pool)
return;
free(pool->memory);
free(pool);
}
5.1.5 メモリデバッグの技術
アンダーフロー・オーバーフローの検出
/*
* デバッグアロケータ：カナリア値による境界チェック
*/
#define CANARY_VALUE 0xDEADBEEF
#define DEBUG_OVERHEAD (2 * sizeof(unsigned int) + sizeof(size_t))
typedef struct s_debug_header {
unsigned int front_canary;
size_t size;
} t_debug_header;
void *debug_malloc(size_t size)
{
char *ptr = malloc(size + DEBUG_OVERHEAD);
if (!ptr)
return NULL;
t_debug_header *header = (t_debug_header *)ptr;
header->front_canary = CANARY_VALUE;
header->size = size;
/* 末尾カナリアを設置 */
unsigned int *back_canary = (unsigned int *)(ptr + sizeof(t_debug_header) + size);
*back_canary = CANARY_VALUE;
return ptr + sizeof(t_debug_header);
}
void debug_free(void *ptr)
{
if (!ptr)
return;
t_debug_header *header = (t_debug_header *)((char *)ptr - sizeof(t_debug_header));
/* フロントカナリアチェック */
if (header->front_canary != CANARY_VALUE) {
fprintf(stderr, "Buffer underflow detected at %p!\n", ptr);
abort();
}
/* バックカナリアチェック */
unsigned int *back_canary = (unsigned int *)((char *)ptr + header->size);
if (*back_canary != CANARY_VALUE) {
fprintf(stderr, "Buffer overflow detected at %p!\n", ptr);
abort();
}
/* 解放後の使用を検出するため、ゴミで埋める */
memset(ptr, 0xDD, header->size);
free(header);
}
Use-After-Freeの検出
/*
* ポイズニング：解放後のメモリを特定パターンで埋める
*/
#define POISON_FREED 0xDD /* 解放済みメモリ */
#define POISON_ALLOC 0xCC /* 未初期化メモリ */
void poisoned_free(void *ptr)
{
if (!ptr)
return;
t_debug_header *header = GET_HEADER(ptr);
/* 解放済みパターンで埋める */
memset(ptr, POISON_FREED, header->size);
/* 即座には解放せず、遅延リストに追加 */
add_to_quarantine(ptr);
}
/*
* Valgrindと同様の技術：
* - メモリをすぐ再利用しない
* - アクセスパターンを監視
* - 問題発生時に詳細なスタックトレースを提供
*/
5.2 数体系と基数変換の数学
5.2.1 位取り記数法の歴史と理論
人類の数表記の歴史は、記数法の進化の歴史でもある。
古代の記数法
- エジプト数字（紀元前3000年頃）
- ローマ数字
- バビロニア数字（紀元前2000年頃）
インド・アラビア数字革命
7世紀インドで確立された十進位取り記数法は、数学史上最大の革新の一つ：
位取り記数法の本質：
数 = Σ(dᵢ × bⁱ) [i = 0 to n-1]
例：1234₁₀
= 1 × 10³ + 2 × 10² + 3 × 10¹ + 4 × 10⁰
= 1000 + 200 + 30 + 4
= 1234
なぜコンピュータは二進法を使うのか
物理的な理由：
- 電子回路は「ON/OFF」の2状態が最も安定
- ノイズ耐性が高い（2値なら判別が容易）
- 論理回路の設計がシンプル
数学的な理由：
- ブール代数との完璧な対応
- 算術演算が単純なビット操作で実現
/*
* 二進法の基本
*
* 1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰
* = 8 + 0 + 2 + 1
* = 11₁₀
*/
/* 二進数を理解するためのヘルパー */
void print_binary(unsigned int n)
{
for (int i = 31; i >= 0; i--) {
putchar((n & (1U << i)) ? '1' : '0');
if (i % 8 == 0)
putchar(' ');
}
putchar('\n');
}
/*
* 42 の二進表現：
* 00000000 00000000 00000000 00101010
*
* 32 + 8 + 2 = 42
*/
5.2.2 基数変換のアルゴリズム
任意の基数への変換
/*
* 除算と剰余による基数変換
*
* アルゴリズム：
* 1. nをbaseで割る
* 2. 余りが最下位桁
* 3. 商を新しいnとして1に戻る
* 4. n=0になるまで繰り返し
* 5. 結果を逆順に読む
*/
/* 例：42を二進数に変換 */
/*
* 42 ÷ 2 = 21 余り 0 (最下位)
* 21 ÷ 2 = 10 余り 1
* 10 ÷ 2 = 5 余り 0
* 5 ÷ 2 = 2 余り 1
* 2 ÷ 2 = 1 余り 0
* 1 ÷ 2 = 0 余り 1 (最上位)
*
* 結果: 101010₂
*/
char *convert_to_base(unsigned long n, unsigned int base)
{
static char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char buffer[65]; /* 最大64ビット + null */
char *ptr = &buffer[64];
if (base < 2 || base > 36)
return NULL;
*ptr = '\0';
if (n == 0)
*--ptr = '0';
while (n > 0) {
*--ptr = digits[n % base];
n /= base;
}
return strdup(ptr);
}
逆変換：文字列から数値へ
/*
* 任意基数の文字列を数値に変換
*
* アルゴリズム（Horner法）：
* result = 0
* for each digit d:
* result = result × base + value(d)
*/
/* 例："1A3" を16進数として解釈 */
/*
* result = 0
* '1': result = 0 × 16 + 1 = 1
* 'A': result = 1 × 16 + 10 = 26
* '3': result = 26 × 16 + 3 = 419
*/
int char_to_digit(char c)
{
if (c >= '0' && c <= '9')
return c - '0';
if (c >= 'A' && c <= 'Z')
return c - 'A' + 10;
if (c >= 'a' && c <= 'z')
return c - 'a' + 10;
return -1;
}
long parse_number(const char *str, int base)
{
long result = 0;
int sign = 1;
/* 符号処理 */
if (*str == '-') {
sign = -1;
str++;
} else if (*str == '+') {
str++;
}
while (*str) {
int digit = char_to_digit(*str);
if (digit < 0 || digit >= base)
break; /* 無効な文字 */
/* オーバーフローチェック */
if (result > (LONG_MAX - digit) / base)
return sign == 1 ? LONG_MAX : LONG_MIN;
result = result * base + digit;
str++;
}
return result * sign;
}
5.2.3 負の数の表現
コンピュータにおける負の数の表現は、ハードウェア設計に深く関わる。
符号・絶対値表現
+5 = 0 0000101
-5 = 1 0000101
↑
符号ビット
問題：
- 0が2つ存在（+0と-0）
- 加算器が複雑になる
1の補数表現
+5 = 0 0000101
-5 = 1 1111010 (全ビット反転)
問題：
- まだ0が2つ存在
- 加算時のキャリー処理が必要
2の補数表現（現代の標準）
/*
* 2の補数：1の補数 + 1
*
* +5 = 0 0000101
* -5 = 1 1111011 (反転して+1)
*
* 利点：
* - 0は1つだけ
* - 加算・減算が統一的に処理可能
* - 符号付き・符号なし演算が同じ回路で実行可能
*/
/* 2の補数の理解 */
void explain_twos_complement(void)
{
signed char pos = 5;
signed char neg = -5;
printf("+5 in binary: ");
print_binary((unsigned char)pos);
/* 00000101 */
printf("-5 in binary: ");
print_binary((unsigned char)neg);
/* 11111011 */
/* 加算が自然に動作することの証明 */
printf("+5 + (-5) = %d\n", pos + neg);
/* 00000101 + 11111011 = 100000000 */
/* 8ビットでは00000000 = 0 */
}
/*
* 2の補数の数学的解釈：
*
* 8ビットの場合、-xは256-xとして解釈される
* -5 = 256 - 5 = 251 = 11111011₂
*
* これにより：
* 5 + (-5) = 5 + 251 = 256 = 100000000₂
* 8ビットで切り捨てると0
*/
intの範囲とINT_MIN問題
/*
* 32ビット整数の範囲：
* INT_MAX = 2147483647 (2³¹ - 1)
* INT_MIN = -2147483648 (-2³¹)
*
* 非対称性：|INT_MIN| > INT_MAX
*
* これは ft_itoa で問題になる
*/
/* 危険な実装 */
char *dangerous_itoa(int n)
{
if (n < 0)
n = -n; /* INT_MINで未定義動作！ */
/* ... */
}
/* 安全な実装 */
char *safe_itoa(int n)
{
long num = n; /* 拡張して安全に処理 */
if (num < 0)
num = -num;
/* ... */
}
/*
* INT_MINの特殊ケース：
* -(-2147483648) はオーバーフロー
*
* 解決策：
* 1. long型を使用
* 2. 符号を分離してから処理
* 3. 特殊ケースとしてハードコード
*/
5.2.4 浮動小数点数の表現
IEEE 754規格は、浮動小数点数の事実上の標準：
/*
* IEEE 754単精度（float, 32ビット）：
*
* S EEEEEEEE MMMMMMMMMMMMMMMMMMMMMMM
* 1 8 23
*
* S: 符号（0=正, 1=負）
* E: 指数部（バイアス127）
* M: 仮数部（暗黙の1ビット）
*
* 値 = (-1)^S × 1.M × 2^(E-127)
*/
/* 例：3.14159の内部表現 */
void explain_float(float f)
{
union {
float f;
unsigned int bits;
} u;
u.f = f;
unsigned int sign = (u.bits >> 31) & 1;
unsigned int exp = (u.bits >> 23) & 0xFF;
unsigned int mantissa = u.bits & 0x7FFFFF;
printf("Float: %f\n", f);
printf("Binary: ");
print_binary(u.bits);
printf("Sign: %u\n", sign);
printf("Exponent: %u (actual: %d)\n", exp, (int)exp - 127);
printf("Mantissa: 0x%06X\n", mantissa);
}
/*
* 3.14159 ≈ 1.5707... × 2¹
*
* 符号: 0 (正)
* 指数: 128 (128-127=1)
* 仮数: 0.5707...の二進表現
*
* 0 10000000 10010010000111111011011
*/
浮動小数点数の落とし穴
/*
* 精度の問題
*/
void float_precision_demo(void)
{
float a = 0.1f;
float b = 0.2f;
float c = 0.3f;
/* 0.1 + 0.2 == 0.3 は偽になる可能性 */
if (a + b == c)
printf("Equal\n");
else
printf("Not equal: %.20f != %.20f\n", a + b, c);
/* 適切な比較方法 */
float epsilon = 1e-6f;
if (fabsf((a + b) - c) < epsilon)
printf("Approximately equal\n");
}
/*
* 0.1は二進数で無限小数：
* 0.1₁₀ = 0.000110011001100...₂
*
* 有限ビットでは近似値しか保存できない
*/
5.3 高階関数と関数型プログラミング
5.3.1 関数ポインタの理論と実践
関数型プログラミングの概念は、1930年代のラムダ計算にまで遡る。
ラムダ計算の基礎
アロンゾ・チャーチが1930年代に開発したラムダ計算は、計算の本質を関数の適用として捉える：
ラムダ計算の構文：
λx.M - 関数の定義（xを引数とする）
M N - 関数適用（MにNを適用）
x - 変数
例：
λx.x - 恒等関数
λx.λy.x - 第一引数を返す関数
(λx.x+1) 5 - 5+1 = 6
C言語における関数ポインタ
/*
* 関数ポインタはC言語における第一級関数の近似
*
* 関数はメモリ上のコードへのポインタとして扱える
*/
/* 関数ポインタの宣言 */
int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }
/* 関数ポインタ型の定義 */
typedef int (*t_binary_op)(int, int);
void demonstrate_function_pointers(void)
{
/* 関数ポインタ配列 */
t_binary_op operations[] = {add, sub, mul};
const char *names[] = {"add", "sub", "mul"};
for (int i = 0; i < 3; i++) {
printf("%s(10, 3) = %d\n", names[i], operations[i](10, 3));
}
/* 出力：
* add(10, 3) = 13
* sub(10, 3) = 7
* mul(10, 3) = 30
*/
}
/* 関数を返す関数（高階関数） */
t_binary_op get_operation(char op)
{
switch (op) {
case '+': return add;
case '-': return sub;
case '*': return mul;
default: return NULL;
}
}
関数ポインタのメモリモデル
テキストセグメント（コード領域）：
+------------------------+
| add: |
| push rbp |
| mov rbp, rsp |
| ... | ← add関数のアドレス
+------------------------+
| sub: |
| push rbp |
| mov rbp, rsp |
| ... | ← sub関数のアドレス
+------------------------+
関数ポインタ変数：
+------------------+
| ptr_to_add: 0x...| → addのアドレスを格納
+------------------+
5.3.2 コールバックパターン
コールバックの概念
コールバックは、ある関数に別の関数を渡し、特定の条件やイベント時に呼び出させるパターン：
/*
* 基本的なコールバックパターン
*/
/* コールバック型の定義 */
typedef void (*t_callback)(void *data, int event);
/* イベント処理関数 */
void on_click(void *data, int event)
{
const char *button_name = (const char *)data;
printf("Button '%s' clicked (event %d)\n", button_name, event);
}
void on_hover(void *data, int event)
{
const char *button_name = (const char *)data;
printf("Mouse over '%s' (event %d)\n", button_name, event);
}
/* イベントディスパッチャ */
typedef struct s_event_handler {
t_callback callback;
void *data;
} t_event_handler;
void dispatch_event(t_event_handler *handler, int event)
{
if (handler && handler->callback)
handler->callback(handler->data, event);
}
クロージャの模倣
本来のクロージャは関数と環境の組み合わせだが、Cでは構造体で近似：
/*
* クロージャ：関数 + 環境（キャプチャされた変数）
*
* Cにはクロージャがないため、構造体で環境を明示的に渡す
*/
/* カウンタークロージャの模倣 */
typedef struct s_counter {
int value;
int step;
} t_counter;
int counter_increment(t_counter *env)
{
env->value += env->step;
return env->value;
}
void demonstrate_closure(void)
{
t_counter counter1 = {.value = 0, .step = 1};
t_counter counter2 = {.value = 100, .step = 10};
printf("c1: %d\n", counter_increment(&counter1)); /* 1 */
printf("c1: %d\n", counter_increment(&counter1)); /* 2 */
printf("c2: %d\n", counter_increment(&counter2)); /* 110 */
printf("c1: %d\n", counter_increment(&counter1)); /* 3 */
printf("c2: %d\n", counter_increment(&counter2)); /* 120 */
}
/*
* 本来のクロージャ（JavaScript風）:
*
* function makeCounter(step) {
* let value = 0;
* return function() {
* value += step;
* return value;
* }
* }
*/
5.3.3 関数型プログラミングの三大操作
Map（写像）
/*
* Map: コレクションの各要素に関数を適用し、
* 結果の新しいコレクションを返す
*
* map :: (a -> b) -> [a] -> [b]
*/
/* 整数配列へのmap */
int *int_array_map(int *array, size_t len, int (*f)(int))
{
int *result = malloc(len * sizeof(int));
if (!result)
return NULL;
for (size_t i = 0; i < len; i++)
result[i] = f(array[i]);
return result;
}
/* 使用例 */
int square(int x) { return x * x; }
int increment(int x) { return x + 1; }
void map_demo(void)
{
int numbers[] = {1, 2, 3, 4, 5};
size_t len = 5;
int *squared = int_array_map(numbers, len, square);
/* {1, 4, 9, 16, 25} */
int *incremented = int_array_map(numbers, len, increment);
/* {2, 3, 4, 5, 6} */
free(squared);
free(incremented);
}
/*
* ft_strmapi は文字列に対するmap操作：
* 各文字にインデックス付きで関数を適用
*/
Filter（選択）
/*
* Filter: 条件を満たす要素だけを選択
*
* filter :: (a -> Bool) -> [a] -> [a]
*/
typedef struct s_int_list {
int *data;
size_t length;
} t_int_list;
t_int_list *int_array_filter(int *array, size_t len, int (*predicate)(int))
{
/* まず要素数をカウント */
size_t count = 0;
for (size_t i = 0; i < len; i++)
if (predicate(array[i]))
count++;
t_int_list *result = malloc(sizeof(t_int_list));
if (!result)
return NULL;
result->data = malloc(count * sizeof(int));
if (!result->data) {
free(result);
return NULL;
}
result->length = count;
/* 条件を満たす要素をコピー */
size_t j = 0;
for (size_t i = 0; i < len; i++)
if (predicate(array[i]))
result->data[j++] = array[i];
return result;
}
int is_even(int x) { return x % 2 == 0; }
int is_positive(int x) { return x > 0; }
void filter_demo(void)
{
int numbers[] = {-3, -1, 0, 2, 4, 5, 8};
size_t len = 7;
t_int_list *evens = int_array_filter(numbers, len, is_even);
/* {0, 2, 4, 8} */
t_int_list *positives = int_array_filter(numbers, len, is_positive);
/* {2, 4, 5, 8} */
}
Reduce/Fold（畳み込み）
/*
* Reduce/Fold: コレクションを単一の値に畳み込む
*
* foldl :: (b -> a -> b) -> b -> [a] -> b
* foldr :: (a -> b -> b) -> b -> [a] -> b
*/
/* 左畳み込み */
int int_array_foldl(int *array, size_t len,
int initial, int (*f)(int acc, int elem))
{
int accumulator = initial;
for (size_t i = 0; i < len; i++)
accumulator = f(accumulator, array[i]);
return accumulator;
}
/* 右畳み込み */
int int_array_foldr(int *array, size_t len,
int initial, int (*f)(int elem, int acc))
{
int accumulator = initial;
for (size_t i = len; i > 0; i--)
accumulator = f(array[i - 1], accumulator);
return accumulator;
}
int add_reducer(int acc, int elem) { return acc + elem; }
int mul_reducer(int acc, int elem) { return acc * elem; }
int max_reducer(int acc, int elem) { return acc > elem ? acc : elem; }
void reduce_demo(void)
{
int numbers[] = {1, 2, 3, 4, 5};
size_t len = 5;
int sum = int_array_foldl(numbers, len, 0, add_reducer);
/* 0 + 1 + 2 + 3 + 4 + 5 = 15 */
int product = int_array_foldl(numbers, len, 1, mul_reducer);
/* 1 * 1 * 2 * 3 * 4 * 5 = 120 */
int maximum = int_array_foldl(numbers, len, INT_MIN, max_reducer);
/* 5 */
}
5.3.4 関数合成とパイプライン
/*
* 関数合成: (f ∘ g)(x) = f(g(x))
*
* 2つの関数を組み合わせて新しい関数を作る
*/
typedef int (*t_int_func)(int);
/* 関数合成（動的に新しい関数を「作る」ことはCでは困難） */
/* 代わりに、合成を実行する関数を定義 */
int compose_and_apply(t_int_func f, t_int_func g, int x)
{
return f(g(x));
}
/* パイプライン処理 */
int pipeline(int x, t_int_func *funcs, size_t count)
{
for (size_t i = 0; i < count; i++)
x = funcs[i](x);
return x;
}
int double_it(int x) { return x * 2; }
int add_one(int x) { return x + 1; }
int negate(int x) { return -x; }
void pipeline_demo(void)
{
t_int_func funcs[] = {double_it, add_one, negate};
int result = pipeline(5, funcs, 3);
/* 5 -> 10 -> 11 -> -11 */
printf("Result: %d\n", result);
}
/*
* UNIXパイプとの類似性：
*
* cat file | grep pattern | sort | uniq
*
* 各コマンドは入力を受け取り、出力を生成
* 関数合成と同じ概念
*/
5.4 UNIX I/Oモデルとファイル抽象化
5.4.1 「全てはファイル」の哲学
UNIX設計の最も革命的な概念の一つが「Everything is a file」という抽象化：
ファイル抽象化の範囲
UNIXにおける「ファイル」：
┌─────────────────────────────────────────────────────┐
│ │
│ 通常ファイル ─ ディスク上のデータ │
│ ディレクトリ ─ ファイルの名前とinodeの対応表 │
│ デバイスファイル ─ ハードウェアへのインターフェース │
│ ├─ ブロックデバイス（/dev/sda） │
│ └─ キャラクタデバイス（/dev/tty） │
│ パイプ ─ プロセス間通信 │
│ ソケット ─ ネットワーク通信 │
│ シンボリックリンク ─ 別ファイルへの参照 │
│ │
│ 全てが同じインターフェースで操作可能： │
│ open(), read(), write(), close() │
│ │
└─────────────────────────────────────────────────────┘
この設計の利点
5.4.2 ファイルディスクリプタの仕組み
プロセスのファイルテーブル
プロセス構造：
┌─────────────────────────────────────────────────────┐
│ Process Control Block │
├─────────────────────────────────────────────────────┤
│ │
│ File Descriptor Table │
│ ┌─────┬──────────────────────────────────────┐ │
│ │ fd │ Pointer to File Table Entry │ │
│ ├─────┼──────────────────────────────────────┤ │
│ │ 0 │ ──→ stdin (keyboard/terminal) │ │
│ │ 1 │ ──→ stdout (terminal) │ │
│ │ 2 │ ──→ stderr (terminal) │ │
│ │ 3 │ ──→ opened file A │ │
│ │ 4 │ ──→ opened file B │ │
│ │ ... │ │ │
│ └─────┴──────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────┘
グローバルファイルテーブル（カーネル内）：
┌─────────────────────────────────────────────────────┐
│ System-wide Open File Table │
├─────────────────────────────────────────────────────┤
│ Entry │ Mode │ Offset │ Ref Count │ inode pointer │
├───────┼───────┼────────┼───────────┼────────────────┤
│ 0 │ R/W │ 1024 │ 2 │ ──→ inode X │
│ 1 │ R │ 0 │ 1 │ ──→ inode Y │
│ ... │ │ │ │ │
└───────┴───────┴────────┴───────────┴────────────────┘
標準ファイルディスクリプタ
/*
* 標準的なファイルディスクリプタ
*/
#define STDIN_FILENO 0 /* 標準入力 */
#define STDOUT_FILENO 1 /* 標準出力 */
#define STDERR_FILENO 2 /* 標準エラー出力 */
/*
* これらはプロセス起動時にシェルによって設定される
*
* 通常のプログラム実行：
* 0 → 端末（キーボード）
* 1 → 端末（画面）
* 2 → 端末（画面）
*
* リダイレクション：
* ./program < input.txt > output.txt 2> error.txt
* 0 → input.txt
* 1 → output.txt
* 2 → error.txt
*
* パイプ：
* cmd1 | cmd2
* cmd1の1 → パイプ書き込み端
* cmd2の0 → パイプ読み取り端
*/
5.4.3 システムコールの詳細
read()システムコール
/*
* ssize_t read(int fd, void *buf, size_t count);
*
* 戻り値：
* > 0: 読み取ったバイト数
* = 0: EOF（ファイル終端）
* < 0: エラー（errnoに詳細）
*/
/* readの動作詳細 */
void explain_read(void)
{
int fd = open("example.txt", O_RDONLY);
char buffer[100];
ssize_t bytes_read;
while ((bytes_read = read(fd, buffer, sizeof(buffer) - 1)) > 0) {
buffer[bytes_read] = '\0';
printf("Read %zd bytes: %s\n", bytes_read, buffer);
}
if (bytes_read < 0) {
perror("read error");
} else {
printf("EOF reached\n");
}
close(fd);
}
/*
* readの特性：
*
* 1. ブロッキング
* - データがなければ待機（端末やパイプの場合）
* - ファイルでは通常すぐ返る
*
* 2. 部分読み取り
* - 要求したバイト数未満を返すことがある
* - 特にネットワークソケットで頻発
*
* 3. アトミック性
* - 小さな読み取りは通常アトミック
* - PIPE_BUF以下のパイプ書き込みはアトミック
*/
write()システムコール
/*
* ssize_t write(int fd, const void *buf, size_t count);
*
* 戻り値：
* > 0: 書き込んだバイト数
* < 0: エラー
*
* 注意：0バイト書き込みは通常成功（ただし効果なし）
*/
/* 確実に全バイト書き込む関数 */
ssize_t write_all(int fd, const void *buf, size_t count)
{
const char *ptr = buf;
size_t remaining = count;
while (remaining > 0) {
ssize_t written = write(fd, ptr, remaining);
if (written < 0) {
if (errno == EINTR)
continue; /* シグナル割り込み、再試行 */
return -1; /* 本当のエラー */
}
ptr += written;
remaining -= written;
}
return count;
}
/*
* writeの特性：
*
* 1. バッファリング
* - カーネルがバッファリングする（遅延書き込み）
* - fsync()で強制的にディスクへ
*
* 2. 部分書き込み
* - ディスク満杯やパイプ容量超過で発生
* - ループで対処必要
*
* 3. シグナル
* - EINTRで中断される可能性
* - SA_RESTARTフラグで自動再試行可能
*/
5.4.4 バッファリング戦略
ユーザー空間バッファリング
/*
* stdio（printf, fwrite等）のバッファリング
*
* モード：
* - _IOFBF: フルバッファリング（ファイルのデフォルト）
* - _IOLBF: 行バッファリング（端末stdout）
* - _IONBF: バッファリングなし（stderrのデフォルト）
*/
void buffering_demo(void)
{
/* バッファリングの確認 */
printf("This may not appear immediately");
/* バッファに溜まったまま */
sleep(3);
printf("\n");
/* 改行でフラッシュ（端末の場合） */
/* 強制フラッシュ */
printf("Immediate output");
fflush(stdout);
/* バッファリングモードの変更 */
setvbuf(stdout, NULL, _IONBF, 0);
printf("This appears immediately");
}
/*
* バッファリングの層：
*
* アプリケーション
* ↓ printf()
* stdio バッファ (ユーザー空間)
* ↓ write()
* カーネルバッファ (ページキャッシュ)
* ↓ fsync() / 自動フラッシュ
* ディスク
*/
効率的なI/O
/*
* バッファサイズと性能
*
* 小さすぎるバッファ → システムコール多発
* 大きすぎるバッファ → メモリ浪費、レイテンシ増加
*/
/* 最適なバッファサイズの決定 */
size_t optimal_buffer_size(int fd)
{
struct stat st;
if (fstat(fd, &st) < 0)
return 4096; /* フォールバック */
/* ファイルシステムの推奨ブロックサイズ */
if (st.st_blksize > 0)
return st.st_blksize;
return 4096;
}
/*
* 典型的な値：
* - 通常ファイル: 4KB〜64KB
* - ネットワーク: 8KB〜64KB
* - パイプ: PIPE_BUF (通常4KB〜64KB)
*/
5.4.5 標準エラー出力の重要性
/*
* stderrが別ストリームである理由
*
* 1. 診断情報の分離
* - 正常出力とエラーを分けてリダイレクト可能
* - ./program > output.txt 2> errors.txt
*
* 2. パイプラインでの透過性
* - cmd1 | cmd2 でエラーは端末に表示
*
* 3. バッファリングの違い
* - stderrはデフォルトでバッファリングなし
* - エラーメッセージは即座に表示
*/
void proper_error_handling(void)
{
/* 正しいエラー報告 */
FILE *fp = fopen("important.dat", "r");
if (!fp) {
/* stderrに出力 */
fprintf(stderr, "Error: Cannot open file: %s\n",
strerror(errno));
exit(EXIT_FAILURE);
}
/* 正常出力はstdoutへ */
printf("File opened successfully\n");
/* プログレス情報もstderrが適切（パイプを乱さない） */
fprintf(stderr, "Processing... 50%%\n");
}
/*
* 使い分けの原則：
*
* stdout: プログラムの「結果」
* stderr: 診断情報、進捗、エラー
*
* これによりパイプラインが正常に機能：
* process_data < input | analyze > results 2> log.txt
*/
5.5 libft追加関数の実装
理論的基盤を踏まえ、各関数を実装していく。
5.5.1 ft_substr - 部分文字列の抽出
/*
* ft_substr - 文字列から部分文字列を抽出
*
* @s: 元の文字列
* @start: 開始位置
* @len: 最大長
* @return: 新しく割り当てられた部分文字列、失敗時NULL
*
* 設計上の決定：
* - startがsの長さを超える場合は空文字列を返す
* - 実際の長さはmin(len, strlen(s) - start)
* - メモリ割り当て失敗時はNULL
*/
char *ft_substr(char const *s, unsigned int start, size_t len)
{
char *substr;
size_t s_len;
size_t actual_len;
if (!s)
return (NULL);
s_len = ft_strlen(s);
/* 開始位置が文字列長を超える場合 */
if (start >= s_len)
return (ft_strdup(""));
/* 実際にコピーする長さを計算 */
actual_len = s_len - start;
if (actual_len > len)
actual_len = len;
/* メモリ割り当て（+1 for '\0'） */
substr = (char *)malloc(sizeof(char) * (actual_len + 1));
if (!substr)
return (NULL);
/* 部分文字列をコピー */
ft_memcpy(substr, s + start, actual_len);
substr[actual_len] = '\0';
return (substr);
}
/*
* 時間計算量: O(len) - コピー操作
* 空間計算量: O(len) - 新しい文字列
*
* エッジケース：
* - s == NULL → NULL
* - start >= strlen(s) → ""
* - len == 0 → ""
* - malloc失敗 → NULL
*/
5.5.2 ft_strjoin - 文字列の連結
/*
* ft_strjoin - 2つの文字列を連結
*
* @s1: 最初の文字列
* @s2: 2番目の文字列
* @return: 連結された新しい文字列、失敗時NULL
*
* 効率性の考慮：
* - 事前にサイズを計算し、一度のmallocで割り当て
* - memcpyによる効率的なコピー
*/
char *ft_strjoin(char const *s1, char const *s2)
{
char *joined;
size_t len1;
size_t len2;
if (!s1 || !s2)
return (NULL);
len1 = ft_strlen(s1);
len2 = ft_strlen(s2);
/* オーバーフローチェック */
if (len1 > SIZE_MAX - len2 - 1)
return (NULL);
joined = (char *)malloc(sizeof(char) * (len1 + len2 + 1));
if (!joined)
return (NULL);
ft_memcpy(joined, s1, len1);
ft_memcpy(joined + len1, s2, len2);
joined[len1 + len2] = '\0';
return (joined);
}
/*
* 時間計算量: O(len1 + len2) - 両文字列の走査
* 空間計算量: O(len1 + len2) - 新しい文字列
*
* 文字列結合のパフォーマンス問題：
*
* 悪い例（Schlemiel the Painter's algorithm）:
* result = strjoin(result, new_str); // ループ内で繰り返し
* → O(n²) の時間計算量
*
* 良い例：
* - StringBuilder パターンを使用
* - 事前にサイズを計算して一度に割り当て
*/
5.5.3 ft_strtrim - 文字列のトリミング
/*
* ft_strtrim - 文字列の両端から指定文字を削除
*
* @s1: トリムする文字列
* @set: 削除する文字の集合
* @return: トリムされた新しい文字列
*
* アルゴリズム：
* 1. 先頭からsetに含まれない最初の文字を探す
* 2. 末尾からsetに含まれない最初の文字を探す
* 3. その範囲を新しい文字列としてコピー
*/
char *ft_strtrim(char const *s1, char const *set)
{
size_t start;
size_t end;
if (!s1 || !set)
return (NULL);
/* 先頭のトリム位置を探す */
start = 0;
while (s1[start] && ft_strchr(set, s1[start]))
start++;
/* 末尾のトリム位置を探す */
end = ft_strlen(s1);
while (end > start && ft_strchr(set, s1[end - 1]))
end--;
return (ft_substr(s1, start, end - start));
}
/*
* 最適化版：ルックアップテーブルを使用
*
* ft_strchrの呼び出しは各文字でO(|set|)
* ルックアップテーブルならO(1)
*/
char *ft_strtrim_optimized(char const *s1, char const *set)
{
unsigned char charset[256] = {0};
size_t start;
size_t end;
if (!s1 || !set)
return (NULL);
/* ルックアップテーブルを構築 */
while (*set)
charset[(unsigned char)*set++] = 1;
/* 先頭のトリム */
start = 0;
while (s1[start] && charset[(unsigned char)s1[start]])
start++;
/* 末尾のトリム */
end = ft_strlen(s1);
while (end > start && charset[(unsigned char)s1[end - 1]])
end--;
return (ft_substr(s1, start, end - start));
}
5.5.4 ft_split - 文字列の分割
/*
* ft_split - 区切り文字で文字列を分割
*
* @s: 分割する文字列
* @c: 区切り文字
* @return: NULL終端の文字列配列
*
* 設計上の決定：
* - 連続する区切り文字は1つとして扱う
* - 空のトークンは生成しない
* - 結果配列はNULL終端
*/
/* 単語数をカウント */
static size_t count_words(char const *s, char c)
{
size_t count;
int in_word;
count = 0;
in_word = 0;
while (*s)
{
if (*s != c && !in_word)
{
in_word = 1;
count++;
}
else if (*s == c)
in_word = 0;
s++;
}
return (count);
}
/* 次の単語の長さを取得 */
static size_t word_len(char const *s, char c)
{
size_t len;
len = 0;
while (s[len] && s[len] != c)
len++;
return (len);
}
/* メモリ解放ヘルパー */
static void free_array(char **array, size_t count)
{
while (count > 0)
free(array[--count]);
free(array);
}
char **ft_split(char const *s, char c)
{
char **result;
size_t word_count;
size_t i;
size_t len;
if (!s)
return (NULL);
word_count = count_words(s, c);
result = (char **)malloc(sizeof(char *) * (word_count + 1));
if (!result)
return (NULL);
i = 0;
while (i < word_count)
{
/* 区切り文字をスキップ */
while (*s == c)
s++;
/* 単語を抽出 */
len = word_len(s, c);
result[i] = ft_substr(s, 0, len);
if (!result[i])
{
free_array(result, i);
return (NULL);
}
s += len;
i++;
}
result[word_count] = NULL;
return (result);
}
/*
* 時間計算量: O(n) - 文字列を2回走査
* 空間計算量: O(n) - 全ての単語をコピー
*
* 二段階アルゴリズムの理由：
* 1. カウントフェーズ: 配列サイズを決定
* 2. 分割フェーズ: 実際の分割とコピー
*
* 単一パス（動的配列）も可能だが、
* realloc のオーバーヘッドがある
*/
5.5.5 ft_itoa - 整数から文字列への変換
/*
* ft_itoa - 整数を文字列に変換
*
* @n: 変換する整数
* @return: 数値の文字列表現
*
* 注意点：
* - INT_MIN (-2147483648) を正しく処理
* - 負の数は先頭に'-'
*/
/* 桁数を計算 */
static int count_digits(int n)
{
int count;
if (n == 0)
return (1);
count = 0;
if (n < 0)
count++; /* 符号分 */
while (n != 0)
{
n /= 10;
count++;
}
return (count);
}
char *ft_itoa(int n)
{
char *str;
int digits;
long num;
digits = count_digits(n);
str = (char *)malloc(sizeof(char) * (digits + 1));
if (!str)
return (NULL);
str[digits] = '\0';
/* long型を使用してINT_MINを安全に処理 */
num = n;
if (num < 0)
{
str[0] = '-';
num = -num;
}
/* 0の特殊ケース */
if (num == 0)
str[0] = '0';
/* 逆順に数字を埋める */
while (num > 0)
{
str[--digits] = (num % 10) + '0';
num /= 10;
}
return (str);
}
/*
* INT_MIN問題の詳細：
*
* INT_MAX = 2147483647
* INT_MIN = -2147483648
*
* -INT_MIN はオーバーフロー（未定義動作）
*
* 解決策：
* 1. long型を使用（本実装）
* 2. 絶対値を取らずに処理
* 3. 特殊ケースとしてハードコード
*/
/* 代替実装：絶対値を取らない方法 */
char *ft_itoa_alternative(int n)
{
char buffer[12];
char *ptr;
int sign;
ptr = &buffer[11];
*ptr = '\0';
sign = (n < 0);
if (n == 0)
*--ptr = '0';
while (n != 0)
{
/* 負の数でも正の数でも動作 */
int digit = n % 10;
if (digit < 0)
digit = -digit;
*--ptr = digit + '0';
n /= 10;
}
if (sign)
*--ptr = '-';
return (ft_strdup(ptr));
}
5.5.6 ft_strmapi - 文字列へのマップ適用
/*
* ft_strmapi - 文字列の各文字に関数を適用
*
* @s: 入力文字列
* @f: 適用する関数（インデックスと文字を受け取り、文字を返す）
* @return: 変換された新しい文字列
*
* 関数型プログラミングのmap操作を文字列に適用
*/
char *ft_strmapi(char const *s, char (*f)(unsigned int, char))
{
char *result;
unsigned int i;
if (!s || !f)
return (NULL);
result = (char *)malloc(sizeof(char) * (ft_strlen(s) + 1));
if (!result)
return (NULL);
i = 0;
while (s[i])
{
result[i] = f(i, s[i]);
i++;
}
result[i] = '\0';
return (result);
}
/*
* 使用例：
*/
/* ROT13暗号化 */
char rot13(unsigned int i, char c)
{
(void)i;
if ((c >= 'a' && c <= 'm') || (c >= 'A' && c <= 'M'))
return (c + 13);
if ((c >= 'n' && c <= 'z') || (c >= 'N' && c <= 'Z'))
return (c - 13);
return (c);
}
/* 交互に大文字小文字 */
char alternate_case(unsigned int i, char c)
{
if (i % 2 == 0)
return (ft_toupper(c));
return (ft_tolower(c));
}
/* 位置ベースのシーザー暗号 */
char positional_cipher(unsigned int i, char c)
{
if (c >= 'a' && c <= 'z')
return ('a' + (c - 'a' + i) % 26);
if (c >= 'A' && c <= 'Z')
return ('A' + (c - 'A' + i) % 26);
return (c);
}
5.5.7 ft_striteri - 文字列のインプレース変換
/*
* ft_striteri - 文字列の各文字をインプレースで変換
*
* @s: 変換する文字列（変更される）
* @f: 適用する関数（インデックスと文字ポインタを受け取る）
*
* strmapi との違い：
* - 新しい文字列を作成しない
* - 元の文字列を直接変更
* - 戻り値がない（void）
*/
void ft_striteri(char *s, void (*f)(unsigned int, char*))
{
unsigned int i;
if (!s || !f)
return;
i = 0;
while (s[i])
{
f(i, &s[i]);
i++;
}
}
/*
* 使用例：
*/
/* 大文字に変換 */
void to_upper_in_place(unsigned int i, char *c)
{
(void)i;
if (*c >= 'a' && *c <= 'z')
*c = *c - 32;
}
/* 機密データのマスキング */
void mask_middle(unsigned int i, char *c)
{
/* 最初と最後の2文字以外をマスク */
static unsigned int len = 0;
if (i == 0) {
/* 長さを事前計算（やや非効率だが安全） */
len = 0;
char *p = c;
while (*p++)
len++;
}
if (i > 1 && i < len - 2)
*c = '*';
}
/* インデックスに基づくXOR暗号化 */
void xor_encrypt(unsigned int i, char *c)
{
*c = *c ^ (i % 256);
}
5.5.8 ファイルディスクリプタ出力関数
/*
* ft_putchar_fd - 1文字をファイルディスクリプタに出力
*
* @c: 出力する文字
* @fd: ファイルディスクリプタ
*/
void ft_putchar_fd(char c, int fd)
{
write(fd, &c, 1);
}
/*
* ft_putstr_fd - 文字列をファイルディスクリプタに出力
*
* @s: 出力する文字列
* @fd: ファイルディスクリプタ
*/
void ft_putstr_fd(char *s, int fd)
{
if (!s)
return;
write(fd, s, ft_strlen(s));
}
/*
* ft_putendl_fd - 文字列と改行をファイルディスクリプタに出力
*
* @s: 出力する文字列
* @fd: ファイルディスクリプタ
*/
void ft_putendl_fd(char *s, int fd)
{
ft_putstr_fd(s, fd);
ft_putchar_fd('\n', fd);
}
/*
* ft_putnbr_fd - 整数をファイルディスクリプタに出力
*
* @n: 出力する整数
* @fd: ファイルディスクリプタ
*
* 再帰を使用して桁を逆順に出力
*/
void ft_putnbr_fd(int n, int fd)
{
long num;
num = n;
if (num < 0)
{
ft_putchar_fd('-', fd);
num = -num;
}
if (num >= 10)
ft_putnbr_fd(num / 10, fd);
ft_putchar_fd((num % 10) + '0', fd);
}
/*
* 効率性の考慮：
*
* 現在の実装は各文字で write() を呼び出す
* 高頻度の出力では非効率
*
* 改善版：バッファリングを追加
*/
/* バッファリング版 */
void ft_putnbr_fd_buffered(int n, int fd)
{
char buffer[12]; /* INT_MIN用に十分なサイズ */
int i;
long num;
i = 11;
buffer[11] = '\0';
num = n;
if (num < 0)
num = -num;
if (num == 0)
buffer[--i] = '0';
while (num > 0)
{
buffer[--i] = (num % 10) + '0';
num /= 10;
}
if (n < 0)
buffer[--i] = '-';
write(fd, &buffer[i], 11 - i);
}
5.6 実践的なパターンとベストプラクティス
5.6.1 エラー処理パターン
/*
* 複数リソースの確保と解放
*
* 問題：複数のmalloc呼び出しがある場合、
* 途中で失敗したら既に割り当てた分を解放する必要がある
*/
/* 悪い例：エラー処理が散在 */
typedef struct s_config {
char *name;
char *value;
char **options;
} t_config;
t_config *create_config_bad(const char *name, const char *value)
{
t_config *cfg = malloc(sizeof(t_config));
if (!cfg)
return NULL;
cfg->name = ft_strdup(name);
if (!cfg->name) {
free(cfg); /* クリーンアップが必要 */
return NULL;
}
cfg->value = ft_strdup(value);
if (!cfg->value) {
free(cfg->name); /* 2つのリソースを解放 */
free(cfg);
return NULL;
}
/* エラー処理が複雑化していく... */
return cfg;
}
/* 良い例：gotoを使用した一元的なクリーンアップ */
t_config *create_config_good(const char *name, const char *value)
{
t_config *cfg = malloc(sizeof(t_config));
if (!cfg)
return NULL;
cfg->name = NULL;
cfg->value = NULL;
cfg->options = NULL;
cfg->name = ft_strdup(name);
if (!cfg->name)
goto error;
cfg->value = ft_strdup(value);
if (!cfg->value)
goto error;
return cfg;
error:
free(cfg->name);
free(cfg->value);
free(cfg);
return NULL;
}
/*
* gotoの正当な使用：
* - リソース解放パターン
* - 深いネストからの脱出
* - エラー処理の一元化
*/
5.6.2 文字列構築パターン
/*
* StringBuilder パターン
*
* 多数の連結を効率的に処理
*/
typedef struct s_strbuf {
char *data;
size_t length;
size_t capacity;
} t_strbuf;
t_strbuf *strbuf_new(size_t initial_capacity)
{
t_strbuf *sb = malloc(sizeof(t_strbuf));
if (!sb)
return NULL;
if (initial_capacity < 16)
initial_capacity = 16;
sb->data = malloc(initial_capacity);
if (!sb->data) {
free(sb);
return NULL;
}
sb->data[0] = '\0';
sb->length = 0;
sb->capacity = initial_capacity;
return sb;
}
int strbuf_append(t_strbuf *sb, const char *str)
{
size_t str_len = ft_strlen(str);
size_t required = sb->length + str_len + 1;
if (required > sb->capacity) {
/* 容量を倍にしながら必要量を確保 */
size_t new_cap = sb->capacity * 2;
while (new_cap < required)
new_cap *= 2;
char *new_data = realloc(sb->data, new_cap);
if (!new_data)
return -1;
sb->data = new_data;
sb->capacity = new_cap;
}
ft_memcpy(sb->data + sb->length, str, str_len + 1);
sb->length += str_len;
return 0;
}
char *strbuf_to_string(t_strbuf *sb)
{
char *result = sb->data;
free(sb);
return result; /* 所有権を移譲 */
}
void strbuf_free(t_strbuf *sb)
{
if (sb) {
free(sb->data);
free(sb);
}
}
/*
* 使用例：
*/
char *build_html_tag(const char *tag, const char *content,
const char **attrs, size_t attr_count)
{
t_strbuf *sb = strbuf_new(256);
if (!sb)
return NULL;
strbuf_append(sb, "<");
strbuf_append(sb, tag);
for (size_t i = 0; i < attr_count; i += 2) {
strbuf_append(sb, " ");
strbuf_append(sb, attrs[i]);
strbuf_append(sb, "=\"");
strbuf_append(sb, attrs[i + 1]);
strbuf_append(sb, "\"");
}
strbuf_append(sb, ">");
strbuf_append(sb, content);
strbuf_append(sb, "</");
strbuf_append(sb, tag);
strbuf_append(sb, ">");
return strbuf_to_string(sb);
}
5.6.3 メモリ所有権の明確化
/*
* 所有権の3つのパターン：
*
* 1. 所有権の移譲（Transfer）
* 2. 所有権の共有（Sharing/Borrowing）
* 3. 所有権のコピー（Copy）
*/
/* パターン1：所有権の移譲 */
/* 呼び出し元がfreeする責任を持つ */
char *create_greeting(const char *name)
{
return ft_strjoin("Hello, ", name);
/* 呼び出し元がfreeする */
}
/* パターン2：借用（参照のみ） */
/* 呼び出し元はfreeしてはいけない */
const char *get_first_word(const char *str)
{
static char buffer[256]; /* 静的バッファを使用 */
/* ... */
return buffer;
/* 呼び出し元はfreeしない */
}
/* パターン3：コピー */
/* 両者がそれぞれの所有権を持つ */
typedef struct s_user {
char *name; /* 所有するコピー */
} t_user;
t_user *user_create(const char *name)
{
t_user *user = malloc(sizeof(t_user));
if (!user)
return NULL;
user->name = ft_strdup(name); /* コピーを作成 */
if (!user->name) {
free(user);
return NULL;
}
return user;
}
void user_free(t_user *user)
{
if (user) {
free(user->name); /* 所有するコピーを解放 */
free(user);
}
}
/*
* 命名規則で所有権を示す：
*
* create_xxx() - 新しいオブジェクトを作成、呼び出し元が解放
* xxx_free() - オブジェクトを解放
* get_xxx() - 既存オブジェクトへの参照、解放不要
* dup_xxx() - コピーを作成、呼び出し元が解放
*/
5.7 テストとデバッグ
5.7.1 ユニットテストの設計
/*
* 追加関数のテストケース
*/
/* ft_substrのテスト */
void test_ft_substr(void)
{
char *result;
/* 正常ケース */
result = ft_substr("Hello, World!", 7, 5);
assert(strcmp(result, "World") == 0);
free(result);
/* 開始位置が文字列長を超える */
result = ft_substr("Hello", 10, 5);
assert(strcmp(result, "") == 0);
free(result);
/* 長さが残りより大きい */
result = ft_substr("Hello", 3, 100);
assert(strcmp(result, "lo") == 0);
free(result);
/* 空文字列 */
result = ft_substr("", 0, 10);
assert(strcmp(result, "") == 0);
free(result);
/* NULL入力 */
result = ft_substr(NULL, 0, 5);
assert(result == NULL);
printf("ft_substr: All tests passed!\n");
}
/* ft_splitのテスト */
void test_ft_split(void)
{
char **result;
/* 正常ケース */
result = ft_split("Hello World Test", ' ');
assert(strcmp(result[0], "Hello") == 0);
assert(strcmp(result[1], "World") == 0);
assert(strcmp(result[2], "Test") == 0);
assert(result[3] == NULL);
/* メモリ解放 */
for (int i = 0; result[i]; i++)
free(result[i]);
free(result);
/* 連続する区切り文字 */
result = ft_split("a b c", ' ');
assert(strcmp(result[0], "a") == 0);
assert(strcmp(result[1], "b") == 0);
assert(strcmp(result[2], "c") == 0);
assert(result[3] == NULL);
for (int i = 0; result[i]; i++)
free(result[i]);
free(result);
/* 区切り文字のみ */
result = ft_split(" ", ' ');
assert(result[0] == NULL);
free(result);
printf("ft_split: All tests passed!\n");
}
/* ft_itoaのテスト */
void test_ft_itoa(void)
{
char *result;
/* 正の数 */
result = ft_itoa(42);
assert(strcmp(result, "42") == 0);
free(result);
/* 負の数 */
result = ft_itoa(-42);
assert(strcmp(result, "-42") == 0);
free(result);
/* ゼロ */
result = ft_itoa(0);
assert(strcmp(result, "0") == 0);
free(result);
/* INT_MAX */
result = ft_itoa(2147483647);
assert(strcmp(result, "2147483647") == 0);
free(result);
/* INT_MIN（最重要テスト） */
result = ft_itoa(-2147483648);
assert(strcmp(result, "-2147483648") == 0);
free(result);
printf("ft_itoa: All tests passed!\n");
}
5.7.2 メモリリークの検出
/*
* Valgrindを使用したメモリリーク検出
*
* コンパイル：
* gcc -g -O0 test.c libft.a -o test
*
* 実行：
* valgrind --leak-check=full --show-leak-kinds=all ./test
*/
/* よくあるメモリリークパターン */
/* パターン1：エラーパスでの解放漏れ */
char **leaky_split(const char *str, char c)
{
char **result = malloc(sizeof(char *) * 10);
result[0] = ft_strdup("first");
result[1] = ft_strdup("second");
/* エラー発生 */
if (some_error_condition) {
return NULL; /* result[0], result[1], resultがリーク */
}
/* ... */
return result;
}
/* 修正版 */
char **fixed_split(const char *str, char c)
{
char **result = malloc(sizeof(char *) * 10);
if (!result)
return NULL;
result[0] = ft_strdup("first");
if (!result[0]) {
free(result);
return NULL;
}
result[1] = ft_strdup("second");
if (!result[1]) {
free(result[0]);
free(result);
return NULL;
}
if (some_error_condition) {
free(result[0]);
free(result[1]);
free(result);
return NULL;
}
return result;
}
/*
* Valgrindの出力例：
*
* ==12345== HEAP SUMMARY:
* ==12345== in use at exit: 48 bytes in 3 blocks
* ==12345== total heap usage: 10 allocs, 7 frees, 1,024 bytes allocated
* ==12345==
* ==12345== 48 (24 direct, 24 indirect) bytes in 1 blocks are definitely lost
* ==12345== at 0x4C2FB0F: malloc (...)
* ==12345== by 0x401234: leaky_split (test.c:42)
* ==12345== by 0x401567: main (test.c:100)
*/
5.8 本章のまとめ
5.8.1 学習した内容の総括
この章では、追加関数の実装を通じて以下の重要概念を学んだ：
1. メモリアロケータの設計
- ヒープメモリの構造と管理方法
- Free List、Buddy Systemなどの割り当て戦略
- 断片化の問題と対策
- メモリプールによる最適化
2. 数体系と基数変換
- 位取り記数法の歴史と理論
- 二進法と他の基数への変換アルゴリズム
- 2の補数表現とINT_MINの扱い
- 浮動小数点数の内部表現
3. 高階関数と関数型プログラミング
- 関数ポインタの仕組み
- コールバックパターン
- Map、Filter、Reduceの概念
- 関数合成とパイプライン
4. UNIX I/Oモデル
- ファイルディスクリプタの仕組み
- 標準入出力と標準エラー
- システムコールの動作
- バッファリング戦略
5.8.2 実装チェックリスト
libft追加関数の実装時に確認すべき項目：
□ すべての入力パラメータでNULLチェック
□ malloc失敗時のエラーハンドリング
□ 途中でエラーが発生した場合の部分的クリーンアップ
□ オーバーフロー対策（サイズ計算、INT_MIN）
□ エッジケースのテスト
□ 空文字列
□ 境界値（0, SIZE_MAX, INT_MIN, INT_MAX）
□ 特殊な入力（区切り文字のみ、等）
□ Valgrindでメモリリークなし
□ 正しい戻り値（失敗時NULL、成功時有効なポインタ）
5.8.3 次のステップ
追加関数をマスターしたら：
動的メモリ管理と関数型プログラミングの概念は、42のすべてのプロジェクトで活用される基盤となる。特に、メモリリークのない堅牢なコードを書く習慣は、プロフェッショナルな開発者への第一歩である。