pipelinedb/freepage.go

// Package pipelinedb provides an integrated pipeline database system
// 集成了数据库存储和业务管道处理的一体化解决方案
package pipelinedb

import (
	"encoding/binary"
	"sync"
)

// FreePageManager 空闲页面管理器
//
// 核心职责：
// 1. 管理数据库文件中的空闲页面
// 2. 提供页面分配和回收功能
// 3. 维护空闲页面的持久化存储
// 4. 确保页面分配的线程安全性
//
// 设计思想：
// - 使用切片维护空闲页面列表，提供O(1)的分配性能
// - 支持空闲页面链表的持久化存储和恢复
// - 使用互斥锁保证并发安全
// - 防重复释放机制，避免空闲页面重复添加
//
// 适用场景：
// - 数据库页面空间管理
// - 文件系统空闲块管理
// - 任何需要页面级别资源管理的系统
//
// 性能特征：
// - 分配：O(1) - 从切片末尾取出
// - 释放：O(n) - 需要检查重复（n为空闲页数量）
// - 空间：O(n) - n为空闲页面数量
type FreePageManager struct {
	freePages []uint16   // 空闲页面编号列表（使用切片实现栈结构）
	mu        sync.Mutex // 互斥锁，保护空闲页面列表的并发访问
}

// NewFreePageManager 创建一个新的空闲页面管理器实例
//
// 初始化内容：
// 1. 创建空的空闲页面切片
// 2. 初始化互斥锁（自动完成）
//
// 返回值：
// - *FreePageManager: 初始化完成的空闲页面管理器
//
// 使用示例：
//
//	fpm := NewFreePageManager()
//	pageNo, ok := fpm.AllocPage()  // 分配页面
//	fpm.FreePage(pageNo)           // 释放页面
func NewFreePageManager() *FreePageManager {
	return &FreePageManager{
		freePages: make([]uint16, 0), // 初始化空的切片，容量为0
		// mu 会自动初始化为零值（未锁定状态）
	}
}

// AllocPage 从空闲页面池中分配一个页面
//
// 核心算法：栈式分配（LIFO - Last In First Out）
// 时间复杂度：O(1) - 直接从切片末尾取出
// 空间复杂度：O(1) - 只修改切片长度
//
// 返回值：
// - uint16: 分配的页面编号（如果成功）
// - bool: 是否分配成功（true=成功，false=无空闲页面）
//
// 执行流程：
// 1. 获取互斥锁（保证线程安全）
// 2. 检查是否有空闲页面可用
// 3. 如果有：从切片末尾取出页面编号，缩短切片
// 4. 如果没有：返回失败标志
//
// 设计考虑：
// - 使用LIFO策略提高缓存局部性
// - 最近释放的页面可能仍在缓存中
// - O(1)时间复杂度确保高性能分配
//
// 并发安全：使用互斥锁保护，支持多线程并发调用
func (fpm *FreePageManager) AllocPage() (uint16, bool) {
	fpm.mu.Lock()         // 获取互斥锁，保证线程安全
	defer fpm.mu.Unlock() // 确保函数退出时释放锁

	// 检查是否有空闲页面可用
	if len(fpm.freePages) == 0 {
		return 0, false // 无空闲页面，分配失败
	}

	// 从切片末尾取出最后一个空闲页面（LIFO策略）
	// 这样可以提高缓存局部性，最近释放的页面可能仍在内存中
	pageNo := fpm.freePages[len(fpm.freePages)-1]

	// 缩短切片，移除已分配的页面
	// 注意：这里使用切片操作，不会重新分配内存
	fpm.freePages = fpm.freePages[:len(fpm.freePages)-1]

	return pageNo, true // 返回分配的页面编号和成功标志
}

// FreePage 将一个页面释放回空闲页面池
//
// 核心算法：防重复释放的页面回收
// 时间复杂度：O(n) - n为当前空闲页面数量（需要检查重复）
// 空间复杂度：O(1) - 只添加一个页面编号
//
// 参数说明：
// - pageNo: 要释放的页面编号
//
// 执行流程：
// 1. 获取互斥锁（保证线程安全）
// 2. 遍历现有空闲页面列表，检查是否重复
// 3. 如果不重复：将页面编号添加到列表末尾
// 4. 如果重复：静默忽略（幂等操作）
//
// 设计考虑：
// - 防重复机制避免空闲页面列表污染
// - 幂等操作确保多次释放同一页面不会出错
// - 添加到末尾保持LIFO分配顺序
//
// 性能权衡：
// - 检查重复需要O(n)时间，但保证了数据一致性
// - 对于大量空闲页面的场景，可考虑使用Set数据结构优化
//
// 并发安全：使用互斥锁保护，支持多线程并发调用
func (fpm *FreePageManager) FreePage(pageNo uint16) {
	fpm.mu.Lock()         // 获取互斥锁，保证线程安全
	defer fpm.mu.Unlock() // 确保函数退出时释放锁

	// 检查页面是否已经在空闲列表中（防重复释放）
	for _, p := range fpm.freePages {
		if p == pageNo {
			return // 页面已存在，静默忽略（幂等操作）
		}
	}

	// 将页面添加到空闲列表末尾
	// 这样下次分配时会优先使用（LIFO策略）
	fpm.freePages = append(fpm.freePages, pageNo)
}

// FreeCount 获取当前空闲页面的数量
//
// 用途：
// - 监控数据库空间使用情况
// - 评估是否需要扩展数据库文件
// - 性能调优和容量规划
//
// 核心算法：直接返回切片长度
// 时间复杂度：O(1) - 直接读取切片长度
// 空间复杂度：O(1) - 不创建额外数据
//
// 返回值：
// - int: 当前空闲页面数量（>=0）
//
// 使用示例：
//
//	count := fpm.FreeCount()
//	if count < 100 {
//	    // 空闲页面不足，考虑扩展数据库
//	}
//
// 并发安全：使用互斥锁保护，支持多线程并发调用
func (fpm *FreePageManager) FreeCount() int {
	fpm.mu.Lock()         // 获取互斥锁，保证读取一致性
	defer fpm.mu.Unlock() // 确保函数退出时释放锁

	// 返回空闲页面列表的长度
	return len(fpm.freePages)
}

// LoadFromHeader 从数据库文件头加载空闲页面信息
//
// 核心功能：将持久化存储的空闲页面链表加载到内存中
// 时间复杂度：O(n) - n为空闲页面数量（需要遍历链表）
// 空间复杂度：O(n) - 需要存储所有空闲页面编号
//
// 参数说明：
//   - freeHead: 空闲页面链表的头页面编号（0表示无空闲页面）
//   - readPage: 页面读取函数，用于从磁盘读取页面数据
//     函数签名：func(pageNo uint16) ([]byte, error)
//
// 返回值：
// - error: 加载过程中的错误（nil表示成功）
//
// 执行流程：
//  1. 获取互斥锁（保证线程安全）
//  2. 清空当前内存中的空闲页面列表
//  3. 从链表头开始遍历空闲页面链表：
//     a. 读取当前页面数据
//     b. 解析下一页面指针（存储在页面偏移4-6字节）
//     c. 将当前页面添加到空闲列表
//     d. 移动到下一页面
//  4. 遍历完成后返回结果
//
// 链表结构：
// - 每个空闲页面的4-6字节存储下一个空闲页面的编号
// - 链表末尾页面的下一页面指针为0
// - 支持最多65535个空闲页面
//
// 错误处理：
// - 页面读取失败时立即返回错误
// - 防止无限循环（限制最大页面数）
//
// 并发安全：使用互斥锁保护，确保加载过程的原子性
func (fpm *FreePageManager) LoadFromHeader(freeHead uint16, readPage func(uint16) ([]byte, error)) error {
	fpm.mu.Lock()         // 获取互斥锁，保证线程安全
	defer fpm.mu.Unlock() // 确保函数退出时释放锁

	// 清空现有的空闲页面列表，准备重新加载
	fpm.freePages = fpm.freePages[:0]

	// 从链表头开始遍历空闲页面链表
	current := freeHead
	for current != 0 {
		// 读取当前页面的数据
		p, err := readPage(current)
		if err != nil {
			return err // 页面读取失败，返回错误
		}

		// 从页面数据中解析下一页面指针
		// 空闲页面的4-6字节存储下一个空闲页面的编号
		nextPage := binary.LittleEndian.Uint16(p[4:6])

		// 将当前页面添加到空闲列表中
		fpm.freePages = append(fpm.freePages, current)

		// 移动到链表中的下一个页面
		current = nextPage

		// 防止无限循环的安全检查
		// 理论上最多支持65535个页面（uint16的最大值）
		if len(fpm.freePages) > 65535 {
			break // 超出合理范围，停止遍历
		}
	}

	return nil // 加载成功
}

// SaveToHeader 将空闲页面信息保存到数据库文件
//
// 核心功能：将内存中的空闲页面列表持久化为磁盘上的链表结构
// 时间复杂度：O(n) - n为空闲页面数量（需要写入所有页面）
// 空间复杂度：O(1) - 只创建单个页面的缓冲区
//
// 参数说明：
//   - writePage: 页面写入函数，用于将页面数据写入磁盘
//     函数签名：func(pageNo uint16, data []byte) error
//
// 返回值：
// - uint16: 空闲页面链表的头页面编号（0表示无空闲页面）
// - error: 保存过程中的错误（nil表示成功）
//
// 执行流程：
//  1. 获取互斥锁（保证线程安全）
//  2. 检查是否有空闲页面需要保存
//  3. 遍历所有空闲页面，构建链表结构：
//     a. 创建页面数据缓冲区
//     b. 设置下一页面指针（存储在4-6字节）
//     c. 写入页面数据到磁盘
//  4. 返回链表头页面编号
//
// 链表结构：
// - 每个页面的4-6字节存储下一页面编号
// - 最后一个页面的下一页面指针设为0
// - 链表头是第一个空闲页面的编号
//
// 错误处理：
// - 页面写入失败时立即返回错误
// - 部分写入成功的情况下，链表可能处于不一致状态
//
// 并发安全：使用互斥锁保护，确保保存过程的原子性
func (fpm *FreePageManager) SaveToHeader(writePage func(uint16, []byte) error) (uint16, error) {
	fpm.mu.Lock()         // 获取互斥锁，保证线程安全
	defer fpm.mu.Unlock() // 确保函数退出时释放锁

	// 检查是否有空闲页面需要保存
	if len(fpm.freePages) == 0 {
		return 0, nil // 无空闲页面，返回0作为链表头
	}

	// 遍历所有空闲页面，构建链表结构
	for i, pageNo := range fpm.freePages {
		// 创建页面大小的数据缓冲区
		p := make([]byte, PageSize)

		// 设置下一页面指针（存储在页面的4-6字节位置）
		if i < len(fpm.freePages)-1 {
			// 不是最后一个页面，设置指向下一个空闲页面
			nextPage := fpm.freePages[i+1]
			binary.LittleEndian.PutUint16(p[4:6], nextPage)
		} else {
			// 最后一个页面，设置下一页面指针为0（链表结束标志）
			binary.LittleEndian.PutUint16(p[4:6], 0)
		}

		// 将页面数据写入磁盘
		if err := writePage(pageNo, p); err != nil {
			return 0, err // 写入失败，返回错误
		}
	}

	// 返回链表头页面编号（第一个空闲页面）
	return fpm.freePages[0], nil
}

// GetFreePages 获取所有空闲页面编号的副本（主要用于调试和监控）
//
// 用途：
// - 调试空闲页面管理逻辑
// - 监控空闲页面分布情况
// - 数据库诊断和分析
//
// 核心算法：创建空闲页面列表的副本
// 时间复杂度：O(n) - n为空闲页面数量（需要复制所有元素）
// 空间复杂度：O(n) - 创建完整的副本
//
// 返回值：
// - []uint16: 所有空闲页面编号的副本切片
//
// 设计考虑：
// - 返回副本而不是原始切片，防止外部修改
// - 提供只读访问，不影响内部状态
// - 适用于调试、监控和诊断场景
//
// 使用示例：
//
//	freePages := fpm.GetFreePages()
//	fmt.Printf("空闲页面: %v\n", freePages)
//	fmt.Printf("空闲页面数量: %d\n", len(freePages))
//
// 并发安全：使用互斥锁保护，确保读取一致性
func (fpm *FreePageManager) GetFreePages() []uint16 {
	fpm.mu.Lock()         // 获取互斥锁，保证读取一致性
	defer fpm.mu.Unlock() // 确保函数退出时释放锁

	// 创建空闲页面列表的完整副本
	result := make([]uint16, len(fpm.freePages))
	copy(result, fpm.freePages)

	return result // 返回副本，防止外部修改原始数据
}