# 機能設計書 50-containers

## 概要

本ドキュメントは、.NETランタイムにおけるcontainersコンポーネントの機能設計を記述したものである。containersは、ランタイム内部で使用される汎用データ構造（ベクター、リスト、ハッシュマップ等）を提供するネイティブライブラリである。

### 本機能の処理概要

containersライブラリは、.NETランタイムのネイティブコード部分で使用される効率的なデータ構造の実装を提供する。C言語で実装され、メモリ安全性と高パフォーマンスを両立する。

**業務上の目的・背景**：.NETランタイムのネイティブ部分（特にMono）では、標準Cライブラリだけでは不十分な高機能データ構造が必要である。containersライブラリは、ベクター（動的配列）、リスト（連結リスト）、ハッシュマップなどの汎用コンテナを提供し、ランタイム内部のデータ管理を効率化する。

**機能の利用シーン**：
- ランタイム内部でのコレクション操作
- eventpipeでのイベントバッファ管理
- JITコンパイラでのデータ管理
- GCでのオブジェクト追跡

**主要な処理内容**：
1. dn_vector: 動的配列の実装
2. dn_list: 双方向連結リストの実装
3. dn_fwd_list: 単方向連結リストの実装
4. dn_umap: ハッシュマップの実装
5. dn_queue: FIFOキューの実装
6. dn_simdhash: SIMD最適化ハッシュテーブル
7. カスタムアロケータのサポート

**関連システム・外部連携**：
- Monoランタイム
- eventpipe
- GCサブシステム

**権限による制御**：特になし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | 内部コンポーネント | 基盤 | ランタイム内部で使用 |

## 機能種別

ネイティブコンポーネント / データ構造ライブラリ

## 入力仕様

### 入力パラメータ（dn_vector作成時）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| params | dn_vector_custom_alloc_params_t* | No | カスタム割り当てパラメータ | - |
| element_size | uint32_t | Yes | 要素サイズ | 正の整数 |

### 入力データソース

- ランタイム内部からの呼び出し

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| dn_vector_t* | pointer | 作成されたベクターへのポインタ |

### 出力先

- メモリ（ヒープ）

## 処理フロー

### 処理シーケンス（dn_vector）

```
1. ベクターの割り当て
   └─ dn_vector_custom_alloc()
   └─ アロケータの設定

2. 初期化
   └─ dn_vector_custom_init()
   └─ 初期容量の確保

3. 要素の追加
   └─ _dn_vector_append_range()
   └─ 必要に応じて容量拡張

4. 要素のアクセス
   └─ dn_vector_at()
   └─ dn_vector_front() / dn_vector_back()

5. 解放
   └─ dn_vector_custom_free()
   └─ dn_vector_custom_dispose()
```

### フローチャート

```mermaid
flowchart TD
    A[dn_vector_custom_alloc] --> B[メモリ割り当て]
    B --> C[dn_vector_custom_init]
    C --> D[初期容量確保]
    D --> E{操作}
    E -->|追加| F[_dn_vector_append_range]
    E -->|挿入| G[_dn_vector_insert_range]
    E -->|削除| H[_dn_vector_erase]
    E -->|検索| I[_dn_vector_custom_find]
    F --> J{容量不足?}
    J -->|Yes| K[_dn_vector_ensure_capacity]
    J -->|No| L[データコピー]
    K --> L
    G --> J
    H --> M[データ移動]
    I --> N[結果返却]
    E -->|解放| O[dn_vector_custom_free]
    O --> P[dispose_func呼び出し]
    P --> Q[メモリ解放]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-50-01 | 容量成長 | 新容量 = (現容量 + 現容量/2 + 63) & ~63 | 容量拡張時 |
| BR-50-02 | 初期容量 | デフォルト初期容量は64 | 指定なし時 |
| BR-50-03 | メモリ初期化 | DN_VECTOR_ATTRIBUTE_MEMORY_INIT属性で新領域をゼロ初期化 | 属性設定時 |
| BR-50-04 | オーバーフロー検査 | 容量/サイズ計算時にオーバーフロー検査 | 常時 |

### 計算ロジック

容量成長の計算:
```c
#define CALC_NEW_CAPACITY(capacity) ((capacity + (capacity >> 1) + 63) & ~63)
```

要素オフセットの計算:
```c
#define element_offset(p,i) ((p)->data + (i) * (p)->_internal._element_size)
#define element_length(p,i) ((i) * (p)->_internal._element_size)
```

## データベース操作仕様

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | メモリ不足 | reallocが失敗 | falseを返却 |
| - | オーバーフロー | UINT32_MAX超過 | falseを返却 |
| - | NULLポインタ | 無効な引数 | DN_ASSERTで検出 |

### リトライ仕様

リトライは行わない。

## トランザクション仕様

該当なし

## パフォーマンス要件

- O(1)での要素アクセス（ベクター）
- 効率的なメモリ再割り当て
- SIMD最適化ハッシュテーブル

## セキュリティ考慮事項

- オーバーフロー検査によるメモリ安全性
- 境界チェック

## 備考

- containersはeglib（Mono内部ライブラリ）の後継
- SIMD最適化によりハッシュテーブル性能を向上

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

まず、dn_vector_t構造体を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | dn-vector.c | `src/native/containers/dn-vector.c` | 26-37行目のマクロ定義 |

**読解のコツ**:
- element_offset: 要素へのポインタ計算
- element_length: 要素範囲のバイト長計算
- check_attribute: 属性チェック

#### Step 2: 容量管理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | dn-vector.c | `src/native/containers/dn-vector.c` | 39-75行目の_dn_vector_ensure_capacity() |

**主要処理フロー**:
- **45-46行目**: 現容量で十分か判定
- **48行目**: 新容量の計算
- **50-51行目**: UINT32_MAXオーバーフロー検査
- **53-55行目**: サイズ乗算のオーバーフロー検査
- **57行目**: realloc呼び出し
- **64-68行目**: MEMORY_INIT属性時のゼロ初期化

#### Step 3: 要素操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | dn-vector.c | `src/native/containers/dn-vector.c` | 77-138行目の挿入/追加関数 |

**主要API**:
- _dn_vector_insert_range: 指定位置への挿入
- _dn_vector_append_range: 末尾への追加

#### Step 4: 削除と検索を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | dn-vector.c | `src/native/containers/dn-vector.c` | 140-216行目の削除/検索関数 |

**主要API**:
- _dn_vector_erase: 要素削除（後続要素を移動）
- _dn_vector_erase_fast: 要素削除（末尾と交換）
- _dn_vector_custom_find: カスタム比較での検索

#### Step 5: ライフサイクル管理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | dn-vector.c | `src/native/containers/dn-vector.c` | 218-293行目のalloc/init/free/dispose関数 |

### プログラム呼び出し階層図

```
dn_vector_custom_alloc()
    │
    ├─ dn_allocator_alloc()
    │
    └─ dn_vector_custom_init()
           │
           └─ _dn_vector_ensure_capacity()
                  │
                  └─ dn_allocator_realloc()

dn_vector_push_back() [マクロ]
    │
    └─ _dn_vector_append_range()
           │
           └─ _dn_vector_ensure_capacity()

dn_vector_custom_free()
    │
    ├─ dn_vector_custom_dispose()
    │      │
    │      ├─ dispose_func() [各要素]
    │      │
    │      └─ dn_allocator_free() [データ]
    │
    └─ dn_allocator_free() [構造体]
```

### データフロー図

```
[呼び出し元]              [dn_vector]                    [アロケータ]

alloc() ──────────▶ dn_vector_custom_alloc()
                           │
                           ├──────────────────▶ dn_allocator_alloc()
                           │
                           ▼
push_back() ──────▶ _dn_vector_append_range()
                           │
                    ┌──────┴──────┐
                    ▼             ▼
               容量OK         容量不足
                    │             │
                    │             ▼
                    │      _dn_vector_ensure_capacity()
                    │             │
                    │             ▼
                    │      dn_allocator_realloc()
                    │             │
                    └──────┬──────┘
                           ▼
                    memmove(データコピー)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| dn-vector.c | `src/native/containers/dn-vector.c` | ソース | 動的配列実装 |
| dn-vector.h | `src/native/containers/dn-vector.h` | ヘッダー | 動的配列API |
| dn-list.c | `src/native/containers/dn-list.c` | ソース | 双方向リスト |
| dn-fwd-list.c | `src/native/containers/dn-fwd-list.c` | ソース | 単方向リスト |
| dn-umap.c | `src/native/containers/dn-umap.c` | ソース | ハッシュマップ |
| dn-queue.c | `src/native/containers/dn-queue.c` | ソース | FIFOキュー |
| dn-simdhash.c | `src/native/containers/dn-simdhash.c` | ソース | SIMDハッシュ |
| dn-allocator.c | `src/native/containers/dn-allocator.c` | ソース | メモリアロケータ |
