pipelinedb/freepage_test.go

package pipelinedb

import (
	"encoding/binary"
	"errors"
	"sync"
	"testing"
)

// TestNewFreePageManager 测试空闲页面管理器的创建
func TestNewFreePageManager(t *testing.T) {
	fpm := NewFreePageManager()

	if fpm == nil {
		t.Fatal("NewFreePageManager returned nil")
	}

	if fpm.FreeCount() != 0 {
		t.Errorf("initial free count = %d, want 0", fpm.FreeCount())
	}

	// 验证初始状态下没有空闲页面
	freePages := fpm.GetFreePages()
	if len(freePages) != 0 {
		t.Errorf("initial free pages length = %d, want 0", len(freePages))
	}
}

// TestFreePageManagerAllocPage 测试页面分配
func TestFreePageManagerAllocPage(t *testing.T) {
	fpm := NewFreePageManager()

	// 测试空管理器分配页面
	pageNo, ok := fpm.AllocPage()
	if ok {
		t.Error("AllocPage should return false when no free pages available")
	}
	if pageNo != 0 {
		t.Errorf("AllocPage returned pageNo = %d, want 0", pageNo)
	}

	// 添加一些空闲页面
	testPages := []uint16{10, 20, 30}
	for _, page := range testPages {
		fpm.FreePage(page)
	}

	// 验证页面数量
	if fpm.FreeCount() != len(testPages) {
		t.Errorf("free count = %d, want %d", fpm.FreeCount(), len(testPages))
	}

	// 测试LIFO分配（后进先出）
	expectedOrder := []uint16{30, 20, 10} // 反向顺序
	for i, expected := range expectedOrder {
		pageNo, ok := fpm.AllocPage()
		if !ok {
			t.Errorf("AllocPage[%d] should return true", i)
		}
		if pageNo != expected {
			t.Errorf("AllocPage[%d] = %d, want %d", i, pageNo, expected)
		}
	}

	// 验证所有页面都被分配完
	if fpm.FreeCount() != 0 {
		t.Errorf("free count after allocation = %d, want 0", fpm.FreeCount())
	}

	// 再次尝试分配应该失败
	_, ok = fpm.AllocPage()
	if ok {
		t.Error("AllocPage should return false when all pages allocated")
	}
}

// TestFreePageManagerFreePage 测试页面释放
func TestFreePageManagerFreePage(t *testing.T) {
	fpm := NewFreePageManager()

	// 释放一个页面
	fpm.FreePage(100)

	if fpm.FreeCount() != 1 {
		t.Errorf("free count after FreePage = %d, want 1", fpm.FreeCount())
	}

	// 验证页面可以被分配
	pageNo, ok := fpm.AllocPage()
	if !ok || pageNo != 100 {
		t.Errorf("AllocPage = (%d, %t), want (100, true)", pageNo, ok)
	}

	// 测试重复释放同一页面（应该是幂等操作）
	fpm.FreePage(200)
	fpm.FreePage(200) // 重复释放

	if fpm.FreeCount() != 1 {
		t.Errorf("free count after duplicate FreePage = %d, want 1", fpm.FreeCount())
	}

	// 验证只有一个页面200
	pageNo, ok = fpm.AllocPage()
	if !ok || pageNo != 200 {
		t.Errorf("AllocPage after duplicate free = (%d, %t), want (200, true)", pageNo, ok)
	}

	// 验证没有更多页面
	_, ok = fpm.AllocPage()
	if ok {
		t.Error("should have no more pages after allocating the only one")
	}
}

// TestFreePageManagerGetFreePages 测试获取空闲页面列表
func TestFreePageManagerGetFreePages(t *testing.T) {
	fpm := NewFreePageManager()

	// 添加一些页面
	testPages := []uint16{5, 15, 25, 35}
	for _, page := range testPages {
		fpm.FreePage(page)
	}

	// 获取空闲页面列表
	freePages := fpm.GetFreePages()

	if len(freePages) != len(testPages) {
		t.Errorf("free pages length = %d, want %d", len(freePages), len(testPages))
	}

	// 验证返回的是副本（修改不影响原始数据）
	originalCount := fpm.FreeCount()
	freePages[0] = 999 // 修改副本

	if fpm.FreeCount() != originalCount {
		t.Error("modifying returned slice affected original data")
	}

	// 验证原始数据未被修改
	newFreePages := fpm.GetFreePages()
	if newFreePages[0] == 999 {
		t.Error("original data was modified when returned slice was changed")
	}
}

// TestFreePageManagerLoadFromHeader 测试从文件头加载空闲页面
func TestFreePageManagerLoadFromHeader(t *testing.T) {
	fpm := NewFreePageManager()

	// 模拟页面数据
	const testPageSize = 4096
	pages := make(map[uint16][]byte)

	// 创建空闲页面链表：1 -> 2 -> 3 -> 0
	// 页面1
	page1 := make([]byte, testPageSize)
	binary.LittleEndian.PutUint16(page1[4:6], 2) // 下一页是2
	pages[1] = page1

	// 页面2
	page2 := make([]byte, testPageSize)
	binary.LittleEndian.PutUint16(page2[4:6], 3) // 下一页是3
	pages[2] = page2

	// 页面3
	page3 := make([]byte, testPageSize)
	binary.LittleEndian.PutUint16(page3[4:6], 0) // 链表结束
	pages[3] = page3

	// 模拟读取函数
	readPageFunc := func(pageNo uint16) ([]byte, error) {
		if page, exists := pages[pageNo]; exists {
			return page, nil
		}
		return nil, errors.New("page not found")
	}

	// 从头页面1开始加载
	err := fpm.LoadFromHeader(1, readPageFunc)
	if err != nil {
		t.Errorf("LoadFromHeader returned error: %v", err)
	}

	// 验证加载的页面数量
	if fpm.FreeCount() != 3 {
		t.Errorf("free count after load = %d, want 3", fpm.FreeCount())
	}

	// 验证页面顺序（应该按链表顺序加载）
	expectedPages := []uint16{1, 2, 3}
	freePages := fpm.GetFreePages()

	for i, expected := range expectedPages {
		if freePages[i] != expected {
			t.Errorf("loaded page[%d] = %d, want %d", i, freePages[i], expected)
		}
	}
}

// TestFreePageManagerLoadFromHeaderEmpty 测试加载空链表
func TestFreePageManagerLoadFromHeaderEmpty(t *testing.T) {
	fpm := NewFreePageManager()

	// 先添加一些页面
	fpm.FreePage(100)
	fpm.FreePage(200)

	// 模拟读取函数（不会被调用）
	readPageFunc := func(pageNo uint16) ([]byte, error) {
		t.Error("readPageFunc should not be called for empty list")
		return nil, errors.New("unexpected call")
	}

	// 从空链表加载（头页面为0）
	err := fpm.LoadFromHeader(0, readPageFunc)
	if err != nil {
		t.Errorf("LoadFromHeader with empty list returned error: %v", err)
	}

	// 验证原有页面被清空
	if fpm.FreeCount() != 0 {
		t.Errorf("free count after loading empty list = %d, want 0", fpm.FreeCount())
	}
}

// TestFreePageManagerLoadFromHeaderError 测试加载过程中的错误处理
func TestFreePageManagerLoadFromHeaderError(t *testing.T) {
	fpm := NewFreePageManager()

	// 模拟读取函数，第二次调用时返回错误
	callCount := 0
	readPageFunc := func(pageNo uint16) ([]byte, error) {
		callCount++
		if callCount == 2 {
			return nil, errors.New("simulated read error")
		}

		// 第一次调用返回指向页面2的数据
		page := make([]byte, 4096)
		binary.LittleEndian.PutUint16(page[4:6], 2)
		return page, nil
	}

	// 尝试加载，应该在第二次读取时失败
	err := fpm.LoadFromHeader(1, readPageFunc)
	if err == nil {
		t.Error("LoadFromHeader should return error when read fails")
	}

	if err.Error() != "simulated read error" {
		t.Errorf("error message = %s, want 'simulated read error'", err.Error())
	}
}

// TestFreePageManagerSaveToHeader 测试保存空闲页面到文件头
func TestFreePageManagerSaveToHeader(t *testing.T) {
	fpm := NewFreePageManager()

	// 添加一些空闲页面
	testPages := []uint16{10, 20, 30}
	for _, page := range testPages {
		fpm.FreePage(page)
	}

	// 用于存储写入的页面数据
	writtenPages := make(map[uint16][]byte)

	// 模拟写入函数
	writePageFunc := func(pageNo uint16, data []byte) error {
		writtenPages[pageNo] = make([]byte, len(data))
		copy(writtenPages[pageNo], data)
		return nil
	}

	// 保存到文件头
	headPage, err := fpm.SaveToHeader(writePageFunc)
	if err != nil {
		t.Errorf("SaveToHeader returned error: %v", err)
	}

	// 验证返回的头页面
	if headPage != testPages[0] {
		t.Errorf("head page = %d, want %d", headPage, testPages[0])
	}

	// 验证写入的页面数量
	if len(writtenPages) != len(testPages) {
		t.Errorf("written pages count = %d, want %d", len(writtenPages), len(testPages))
	}

	// 验证链表结构
	for i, pageNo := range testPages {
		data, exists := writtenPages[pageNo]
		if !exists {
			t.Errorf("page %d was not written", pageNo)
			continue
		}

		// 检查下一页指针
		nextPage := binary.LittleEndian.Uint16(data[4:6])
		if i < len(testPages)-1 {
			// 不是最后一页，应该指向下一页
			expectedNext := testPages[i+1]
			if nextPage != expectedNext {
				t.Errorf("page %d next pointer = %d, want %d", pageNo, nextPage, expectedNext)
			}
		} else {
			// 最后一页，应该指向0
			if nextPage != 0 {
				t.Errorf("last page %d next pointer = %d, want 0", pageNo, nextPage)
			}
		}
	}
}

// TestFreePageManagerSaveToHeaderEmpty 测试保存空列表
func TestFreePageManagerSaveToHeaderEmpty(t *testing.T) {
	fpm := NewFreePageManager()

	// 模拟写入函数（不应该被调用）
	writePageFunc := func(pageNo uint16, data []byte) error {
		t.Error("writePageFunc should not be called for empty list")
		return errors.New("unexpected call")
	}

	// 保存空列表
	headPage, err := fpm.SaveToHeader(writePageFunc)
	if err != nil {
		t.Errorf("SaveToHeader with empty list returned error: %v", err)
	}

	// 验证返回的头页面为0
	if headPage != 0 {
		t.Errorf("head page for empty list = %d, want 0", headPage)
	}
}

// TestFreePageManagerSaveToHeaderError 测试保存过程中的错误处理
func TestFreePageManagerSaveToHeaderError(t *testing.T) {
	fpm := NewFreePageManager()

	// 添加一些页面
	fpm.FreePage(10)
	fpm.FreePage(20)

	// 模拟写入函数，第二次调用时返回错误
	callCount := 0
	writePageFunc := func(pageNo uint16, data []byte) error {
		callCount++
		if callCount == 2 {
			return errors.New("simulated write error")
		}
		return nil
	}

	// 尝试保存，应该在第二次写入时失败
	headPage, err := fpm.SaveToHeader(writePageFunc)
	if err == nil {
		t.Error("SaveToHeader should return error when write fails")
	}

	if err.Error() != "simulated write error" {
		t.Errorf("error message = %s, want 'simulated write error'", err.Error())
	}

	if headPage != 0 {
		t.Errorf("head page on error = %d, want 0", headPage)
	}
}

// TestFreePageManagerRoundTrip 测试保存和加载的往返操作
func TestFreePageManagerRoundTrip(t *testing.T) {
	// 创建第一个管理器并添加页面
	fpm1 := NewFreePageManager()
	originalPages := []uint16{100, 200, 300, 400}
	for _, page := range originalPages {
		fpm1.FreePage(page)
	}

	// 用于存储页面数据的映射
	pageStorage := make(map[uint16][]byte)

	// 保存到存储
	writePageFunc := func(pageNo uint16, data []byte) error {
		pageStorage[pageNo] = make([]byte, len(data))
		copy(pageStorage[pageNo], data)
		return nil
	}

	headPage, err := fpm1.SaveToHeader(writePageFunc)
	if err != nil {
		t.Errorf("SaveToHeader failed: %v", err)
	}

	// 创建第二个管理器并从存储加载
	fpm2 := NewFreePageManager()

	readPageFunc := func(pageNo uint16) ([]byte, error) {
		if data, exists := pageStorage[pageNo]; exists {
			return data, nil
		}
		return nil, errors.New("page not found")
	}

	err = fpm2.LoadFromHeader(headPage, readPageFunc)
	if err != nil {
		t.Errorf("LoadFromHeader failed: %v", err)
	}

	// 验证加载的页面与原始页面相同
	if fpm2.FreeCount() != len(originalPages) {
		t.Errorf("loaded free count = %d, want %d", fpm2.FreeCount(), len(originalPages))
	}

	loadedPages := fpm2.GetFreePages()
	for i, expected := range originalPages {
		if loadedPages[i] != expected {
			t.Errorf("loaded page[%d] = %d, want %d", i, loadedPages[i], expected)
		}
	}

	// 验证分配顺序相同（LIFO）
	for i := len(originalPages) - 1; i >= 0; i-- {
		expected := originalPages[i]
		pageNo, ok := fpm2.AllocPage()
		if !ok || pageNo != expected {
			t.Errorf("AllocPage[%d] = (%d, %t), want (%d, true)", i, pageNo, ok, expected)
		}
	}
}

// TestFreePageManagerConcurrency 测试并发安全性
func TestFreePageManagerConcurrency(t *testing.T) {
	fpm := NewFreePageManager()

	const numGoroutines = 10
	const numOperations = 100

	var wg sync.WaitGroup

	// 启动多个goroutine进行并发操作
	for i := 0; i < numGoroutines; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()

			for j := 0; j < numOperations; j++ {
				pageNo := uint16(id*numOperations + j)

				// 释放页面
				fpm.FreePage(pageNo)

				// 尝试分配页面
				if allocPage, ok := fpm.AllocPage(); ok {
					// 再次释放分配到的页面
					fpm.FreePage(allocPage)
				}
			}
		}(i)
	}

	// 同时进行统计查询
	wg.Add(1)
	go func() {
		defer wg.Done()
		for i := 0; i < 50; i++ {
			fpm.FreeCount()
			fpm.GetFreePages()
		}
	}()

	// 等待所有goroutine完成
	wg.Wait()

	// 验证管理器仍然可用
	fpm.FreePage(9999)
	pageNo, ok := fpm.AllocPage()
	if !ok || pageNo != 9999 {
		t.Error("manager corrupted after concurrent operations")
	}
}

// TestFreePageManagerLargeList 测试大量页面的处理
func TestFreePageManagerLargeList(t *testing.T) {
	fpm := NewFreePageManager()

	// 添加大量页面
	const numPages = 1000
	for i := uint16(1); i <= numPages; i++ {
		fpm.FreePage(i)
	}

	// 验证数量
	if fpm.FreeCount() != numPages {
		t.Errorf("free count = %d, want %d", fpm.FreeCount(), numPages)
	}

	// 分配所有页面
	allocatedPages := make([]uint16, 0, numPages)
	for i := 0; i < numPages; i++ {
		pageNo, ok := fpm.AllocPage()
		if !ok {
			t.Errorf("AllocPage[%d] failed", i)
			break
		}
		allocatedPages = append(allocatedPages, pageNo)
	}

	// 验证分配完毕
	if fpm.FreeCount() != 0 {
		t.Errorf("free count after allocation = %d, want 0", fpm.FreeCount())
	}

	// 验证LIFO顺序（最后添加的最先分配）
	for i, pageNo := range allocatedPages {
		expected := uint16(numPages - i)
		if pageNo != expected {
			t.Errorf("allocated page[%d] = %d, want %d", i, pageNo, expected)
		}
	}
}

// BenchmarkFreePageManagerAllocPage 性能测试：页面分配
func BenchmarkFreePageManagerAllocPage(b *testing.B) {
	fpm := NewFreePageManager()

	// 预填充大量空闲页面
	for i := uint16(0); i < 10000; i++ {
		fpm.FreePage(i)
	}

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		fpm.AllocPage()
		if fpm.FreeCount() == 0 {
			// 重新填充
			for j := uint16(0); j < 10000; j++ {
				fpm.FreePage(j)
			}
		}
	}
}

// BenchmarkFreePageManagerFreePage 性能测试：页面释放
func BenchmarkFreePageManagerFreePage(b *testing.B) {
	fpm := NewFreePageManager()

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		fpm.FreePage(uint16(i % 10000))
	}
}

// BenchmarkFreePageManagerConcurrentAccess 性能测试：并发访问
func BenchmarkFreePageManagerConcurrentAccess(b *testing.B) {
	fpm := NewFreePageManager()

	// 预填充一些页面
	for i := uint16(0); i < 1000; i++ {
		fpm.FreePage(i)
	}

	b.ResetTimer()

	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			if i%2 == 0 {
				fpm.AllocPage()
			} else {
				fpm.FreePage(uint16(i % 1000))
			}
			i++
		}
	})
}