# 機能設計書 48-ビットベクター

## 概要

SQLiteにおけるビットベクター（Bitvec）の設計書。固定長ビットマップを管理し、疎/密の両方のケースに適応する3種類の内部表現を提供する。

### 本機能の処理概要

SQLiteのビットベクター機能は、ページ番号の集合を効率的に管理するためのデータ構造である。

**業務上の目的・背景**：トランザクション中にジャーナルに記録されたページや「書き込み禁止」属性を持つページを追跡する必要がある。通常は少数のページのみが対象（疎）だが、大きなテーブルのDROP時には多数のページが対象（密）になる。両方のケースを効率的に処理するため、適応的なデータ表現を採用している。

**機能の利用シーン**：
- ジャーナルページの追跡（pInJournal）
- 変更ページの追跡（pDirty）
- ページの「dont-write」属性管理
- WALフレーム追跡

**主要な処理内容**：
1. 作成：sqlite3BitvecCreate()で指定サイズのビットベクター作成
2. テスト：sqlite3BitvecTest()でビットが設定されているか確認
3. 設定：sqlite3BitvecSet()でビットをセット
4. クリア：sqlite3BitvecClear()でビットをクリア
5. 破棄：sqlite3BitvecDestroy()でメモリ解放

**関連システム・外部連携**：
- Pagerサブシステム（ジャーナル管理）
- WALサブシステム（フレーム追跡）
- メモリアロケータ（sqlite3MallocZero, sqlite3_free）

**権限による制御**：特になし（内部データ構造）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | （内部機能） | - | Pager/WAL内部で使用 |

## 機能種別

汎用データ構造 / ビットマップ

## 入力仕様

### 入力パラメータ（sqlite3BitvecCreate）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| iSize | u32 | Yes | 最大ビットインデックス | 1〜4,294,967,296 |

### 入力パラメータ（sqlite3BitvecSet）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| p | Bitvec* | Yes | ビットベクター | NULL許容 |
| i | u32 | Yes | ビット番号（1起点） | 1〜iSize |

### 入力データソース

- PagerサブシステムからのAPI呼び出し

## 出力仕様

### 出力データ（sqlite3BitvecCreate）

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | Bitvec* | 作成されたビットベクター / NULL（失敗） |

### 出力データ（sqlite3BitvecTest）

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | int | 1=設定済み / 0=未設定 |

### 出力先

- 呼び出し元の戻り値

## 処理フロー

### 処理シーケンス

```
1. sqlite3BitvecCreate(iSize)
   └─ sqlite3MallocZero(512)でBitvec構造体確保
   └─ p->iSize = iSize

2. sqlite3BitvecTest(p, i)
   ├─ i-- （0起点に変換）
   ├─ while(p->iDivisor) サブビットマップ探索
   ├─ iSize<=BITVEC_NBIT: ビットマップ表現
   │   └─ aBitmap[i/8] & (1<<(i&7))
   └─ その他: ハッシュ表現
       └─ aHash[h]を線形探索

3. sqlite3BitvecSet(p, i)
   ├─ i-- （0起点に変換）
   ├─ while(iSize>BITVEC_NBIT && iDivisor) サブビットマップ作成
   ├─ iSize<=BITVEC_NBIT: ビットマップ表現
   │   └─ aBitmap[i/8] |= (1<<(i&7))
   └─ その他: ハッシュ表現
       ├─ 衝突なし かつ nSet<BITVEC_NINT-1: 直接挿入
       ├─ 衝突あり: 線形探索で空きスロット検索
       └─ nSet>=BITVEC_MXHASH: リハッシュ（サブビットマップ化）

4. sqlite3BitvecClear(p, i, pBuf)
   ├─ サブビットマップ探索
   ├─ iSize<=BITVEC_NBIT: ビットマップ表現
   │   └─ aBitmap[i/8] &= ~(1<<(i&7))
   └─ その他: ハッシュ表現を再構築
```

### フローチャート

```mermaid
flowchart TD
    A[sqlite3BitvecSet] --> B{p==NULL?}
    B -->|Yes| C[SQLITE_OK]
    B -->|No| D[i--]
    D --> E{iSize>BITVEC_NBIT && iDivisor?}
    E -->|Yes| F[サブビットマップ探索/作成]
    F --> E
    E -->|No| G{iSize<=BITVEC_NBIT?}
    G -->|Yes| H[ビットマップにセット]
    H --> I[SQLITE_OK]
    G -->|No| J[ハッシュ計算]
    J --> K{aHash[h]==0?}
    K -->|Yes| L{nSet<BITVEC_NINT-1?}
    L -->|Yes| M[直接挿入]
    L -->|No| N[リハッシュ]
    K -->|No| O{既存?}
    O -->|Yes| P[SQLITE_OK]
    O -->|No| Q[線形探索]
    Q --> R{nSet>=BITVEC_MXHASH?}
    R -->|Yes| N
    R -->|No| M
    N --> S[サブビットマップに変換]
    S --> A
    M --> T[nSet++]
    T --> U[SQLITE_OK]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-48-01 | 1起点インデックス | ビット番号は1から開始 | 全操作 |
| BR-48-02 | 3種類の表現 | ビットマップ/ハッシュ/サブビットマップ | iSizeによる |
| BR-48-03 | リハッシュ条件 | nSet>=BITVEC_MXHASH | ハッシュ表現時 |
| BR-48-04 | 固定サイズ | Bitvec構造体は常に512バイト | コンパイル時 |

### 内部表現の選択

| 条件 | 表現 | 説明 |
|------|------|------|
| iSize<=BITVEC_NBIT | ビットマップ | 直接ビットマップ（約4000ビット） |
| iSize>BITVEC_NBIT かつ iDivisor==0 | ハッシュ | 最大BITVEC_MXHASH個のエントリ |
| iSize>BITVEC_NBIT かつ iDivisor>0 | サブビットマップ | 再帰的構造 |

### コンパイル時定数

| 定数 | 値 | 説明 |
|------|-----|------|
| BITVEC_SZ | 512 | Bitvec構造体のサイズ（バイト） |
| BITVEC_NBIT | 約4000 | ビットマップ表現の最大ビット数 |
| BITVEC_NINT | 約125 | ハッシュテーブルのスロット数 |
| BITVEC_MXHASH | 約62 | ハッシュテーブルの最大エントリ数 |
| BITVEC_NPTR | 約62 | サブビットマップポインタ数 |

### Bitvec構造体

| フィールド | 型 | 説明 |
|-----------|-----|------|
| iSize | u32 | 最大ビットインデックス |
| nSet | u32 | ハッシュテーブル内のエントリ数 |
| iDivisor | u32 | サブビットマップの分割単位 |
| u.aBitmap | BITVEC_TELEM[] | ビットマップ表現 |
| u.aHash | u32[] | ハッシュテーブル表現 |
| u.apSub | Bitvec*[] | サブビットマップポインタ配列 |

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

### 操作別データベース影響一覧

本機能はデータベーステーブルを直接操作しない（メモリ内データ構造）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| SQLITE_NOMEM | メモリ不足 | Bitvec作成失敗 | NULLを返却 |
| SQLITE_NOMEM | メモリ不足 | サブビットマップ作成失敗 | エラーコード返却 |
| SQLITE_NOMEM | メモリ不足 | リハッシュ用一時領域確保失敗 | エラーコード返却 |

### リトライ仕様

ビットベクター操作はリトライ不要（同期処理）

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

ビットベクターはトランザクションの対象外（メモリ内データ構造、ただしトランザクション管理に使用される）

## パフォーマンス要件

- テスト操作は設定操作の約100倍の頻度
- クリア操作は稀
- 疎/密の両方に対応する適応的表現

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

- 特になし（内部データ構造）

## 備考

- ハッシュ関数の乗数*37は*1と同等（コメントによる）
- SQLITE_DEBUG時にshowBitvec()でデバッグ出力可能
- sqlite3BitvecBuiltinTest()でテスト可能

---

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

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

### 推奨読解順序

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

ビットベクターの3種類の内部表現を理解。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | bitvec.c | `src/bitvec.c` | BITVEC_*定数（40-70行目）：サイズ・容量定数 |
| 1-2 | bitvec.c | `src/bitvec.c` | Bitvec構造体（94-108行目）：3種類のunion表現 |

**読解のコツ**: u.aBitmap、u.aHash、u.apSubは排他的に使用される。iSizeとiDivisorの値で表現が決定される。

#### Step 2: 基本操作を理解する

作成とテスト操作の実装。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | bitvec.c | `src/bitvec.c` | sqlite3BitvecCreate（116-124行目）：作成 |
| 2-2 | bitvec.c | `src/bitvec.c` | sqlite3BitvecTestNotNull（131-153行目）：テスト |
| 2-3 | bitvec.c | `src/bitvec.c` | sqlite3BitvecTest（154-156行目）：NULL安全テスト |

**主要処理フロー**:
- **133行目**: i-- で0起点に変換
- **135-142行目**: サブビットマップの探索
- **143-144行目**: ビットマップ表現のテスト
- **146-152行目**: ハッシュ表現のテスト

#### Step 3: 設定操作を理解する

ビットセットとリハッシュの実装。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | bitvec.c | `src/bitvec.c` | sqlite3BitvecSet（170-235行目）：設定 |

**主要処理フロー**:
- **176-184行目**: サブビットマップの探索/作成
- **185-188行目**: ビットマップ表現への設定
- **189-206行目**: ハッシュ表現への設定（衝突処理）
- **210-230行目**: リハッシュ（サブビットマップへの変換）

#### Step 4: クリアと破棄を理解する

ビットクリアとメモリ解放の実装。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | bitvec.c | `src/bitvec.c` | sqlite3BitvecClear（243-275行目）：クリア |
| 4-2 | bitvec.c | `src/bitvec.c` | sqlite3BitvecDestroy（280-289行目）：破棄 |

**主要処理フロー**:
- **255-256行目**: ビットマップ表現のクリア
- **258-273行目**: ハッシュ表現の再構築（削除要素を除外）
- **282-287行目**: サブビットマップの再帰的解放

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

```
sqlite3BitvecCreate(iSize)
    └─ sqlite3MallocZero(BITVEC_SZ)

sqlite3BitvecTest(p, i)
    └─ sqlite3BitvecTestNotNull(p, i)
           ├─ [サブビットマップ探索]
           ├─ [ビットマップ表現] aBitmap[i/8] & (1<<(i&7))
           └─ [ハッシュ表現] aHash[h]を検索

sqlite3BitvecSet(p, i)
    ├─ [サブビットマップ作成]
    │      └─ sqlite3BitvecCreate(iDivisor)
    ├─ [ビットマップ表現] aBitmap[i/8] |= (1<<(i&7))
    ├─ [ハッシュ表現] aHash[h] = i
    └─ [リハッシュ]
           ├─ sqlite3StackAllocRaw()
           ├─ iDivisor計算
           └─ sqlite3BitvecSet() 再帰呼び出し

sqlite3BitvecClear(p, i, pBuf)
    ├─ [サブビットマップ探索]
    ├─ [ビットマップ表現] aBitmap[i/8] &= ~(1<<(i&7))
    └─ [ハッシュ表現] ハッシュテーブル再構築

sqlite3BitvecDestroy(p)
    ├─ sqlite3BitvecDestroy(apSub[i]) 再帰
    └─ sqlite3_free(p)
```

### データフロー図

```
[入力]                    [処理]                           [出力]

ビット番号i(1起点) ────▶ i-- (0起点変換) ────────────▶ 内部インデックス
                         │
                         ▼
                  ┌─────────────────────────────────────┐
                  │ Bitvec構造体 (512バイト固定)          │
                  │                                     │
                  │ iSize ─────────▶ 表現選択            │
                  │                                     │
                  │ [iSize<=BITVEC_NBIT]                │
                  │   u.aBitmap[] ビットマップ           │
                  │                                     │
                  │ [iSize>BITVEC_NBIT && iDivisor==0]  │
                  │   u.aHash[] ハッシュテーブル          │
                  │   nSet エントリ数                    │
                  │                                     │
                  │ [iSize>BITVEC_NBIT && iDivisor>0]   │
                  │   u.apSub[] サブビットマップ配列      │
                  │   iDivisor 分割単位                  │
                  └─────────────────────────────────────┘
                         │
                         ▼
                  ┌─────────────────┐
                  │ 適応的ストレージ  │
                  │ 疎→ハッシュ       │
                  │ 密→ビットマップ   │
                  │ 巨大→サブ分割     │
                  └─────────────────┘
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| bitvec.c | `src/bitvec.c` | ソース | ビットベクター実装 |
| sqliteInt.h | `src/sqliteInt.h` | ヘッダ | Bitvec型の前方宣言 |
| pager.c | `src/pager.c` | ソース | 主要な使用箇所（pInJournal等） |
| wal.c | `src/wal.c` | ソース | WALフレーム追跡での使用 |
