字符串：SDS 简单动态字符串

type string struct {
    data uintptr  // 指向字符数组
    len  int      // 长度
}

s := "Hello"
s = s + " World"  // 创建新字符串，旧的被 GC 回收

// V1: 基础 SDS
type SDS struct {
    len  int      // 已使用长度
    free int      // 剩余空间
    buf  []byte   // 字符数组
}

// 创建 SDS
func NewSDS(initStr string) *SDS {
    data := []byte(initStr)
    length := len(data)

    return &SDS{
        len:  length,
        free: 0,
        buf:  data,
    }
}

// 追加字符串
func (s *SDS) Append(str string) {
    data := []byte(str)
    dataLen := len(data)
    totalLen := s.len + dataLen

    // 空间不足时扩容
    if s.free < dataLen {
        newCap := totalLen * 2
        newBuf := make([]byte, newCap)
        copy(newBuf, s.buf[:s.len])
        s.buf = newBuf
    }

    // 追加数据
    copy(s.buf[s.len:], data)
    s.len = totalLen
    s.free = len(s.buf) - s.len
}

// V2: 改进预分配
func (s *SDS) expand(newLen int) {
    var newCap int

    if newLen < 1024*1024 {  // 小于 1MB
        newCap = newLen * 2  // 翻倍分配
    } else {                  // 大于 1MB
        newCap = newLen + 1024*1024  // 多分配 1MB
    }

    // 确保最小容量
    if newCap < 16 {
        newCap = 16
    }

    newBuf := make([]byte, newCap)
    copy(newBuf, s.buf[:s.len])
    s.buf = newBuf
    s.free = newCap - s.len
}

// SDS 类型定义
type SDSType int

const (
    SDS_TYPE_5  SDSType = iota  // 长度 < 32 (2^5)
    SDS_TYPE_8                  // 长度 < 256 (2^8)
    SDS_TYPE_16                 // 长度 < 65536 (2^16)
    SDS_TYPE_32                 // 长度 < 4GB (2^32)
    SDS_TYPE_64                 // 长度 >= 4GB
)

// SDS 结构体
type SDS struct {
    len  int      // 字符串长度
    free int      // 剩余空间
    buf  []byte   // 字符数组
    typ  SDSType  // 类型标识
}

// 根据长度选择类型
func NewSDS(initStr string) *SDS {
    data := []byte(initStr)
    length := len(data)

    var typ SDSType
    if length < 32 {
        typ = SDS_TYPE_5
    } else if length < 256 {
        typ = SDS_TYPE_8
    } else if length < 65536 {
        typ = SDS_TYPE_16
    } else if length < 4294967296 {
        typ = SDS_TYPE_32
    } else {
        typ = SDS_TYPE_64
    }

    return &SDS{
        len:  length,
        free: 0,
        buf:  data,
        typ:  typ,
    }
}

// sds/sds.go
package sds

// SDS 类型
type SDSType int

const (
    SDS_TYPE_5  SDSType = iota
    SDS_TYPE_8
    SDS_TYPE_16
    SDS_TYPE_32
    SDS_TYPE_64
)

// SDS 结构体
type SDS struct {
    len  int      // 字符串长度
    free int      // 剩余空间
    buf  []byte   // 字符数组
    typ  SDSType  // 类型标识
}

// 创建 SDS
func NewSDS(initStr string) *SDS {
    data := []byte(initStr)
    length := len(data)

    // 根据长度选择类型
    var typ SDSType
    if length < 32 {
        typ = SDS_TYPE_5
    } else if length < 256 {
        typ = SDS_TYPE_8
    } else if length < 65536 {
        typ = SDS_TYPE_16
    } else if length < 4294967296 {
        typ = SDS_TYPE_32
    } else {
        typ = SDS_TYPE_64
    }

    return &SDS{
        len:  length,
        free: 0,
        buf:  data,
        typ:  typ,
    }
}

// 从字节数组创建
func NewSDSFromBytes(data []byte) *SDS {
    sds := NewSDS(string(data))
    return sds
}

// 创建空 SDS
func NewEmptySDS() *SDS {
    return &SDS{
        len:  0,
        free: 0,
        buf:  make([]byte, 0),
        typ:  SDS_TYPE_5,
    }
}

// sds/basic_operations.go
package sds

// 获取长度 O(1)
func (s *SDS) Len() int {
    return s.len
}

// 获取容量
func (s *SDS) Cap() int {
    return len(s.buf)
}

// 获取剩余空间
func (s *SDS) Free() int {
    return s.free
}

// 获取字符串内容
func (s *SDS) String() string {
    return string(s.buf[:s.len])
}

// 获取字节数组
func (s *SDS) Bytes() []byte {
    return s.buf[:s.len]
}

// 获取 C 字符串（以 \0 结尾）
func (s *SDS) CString() string {
    return string(s.buf[:s.len]) + "\x00"
}

// 检查是否为空
func (s *SDS) IsEmpty() bool {
    return s.len == 0
}

// 清空 SDS
func (s *SDS) Clear() {
    s.len = 0
    s.free = len(s.buf)
    s.buf = s.buf[:0]
}

// sds/memory_management.go
package sds

// 扩容策略
func (s *SDS) expand(newLen int) {
    currentCap := len(s.buf)

    // 计算新容量
    var newCap int
    if newLen < 1024*1024 { // 小于 1MB，翻倍
        newCap = newLen * 2
    } else { // 大于 1MB，每次增加 1MB
        newCap = newLen + 1024*1024
    }

    // 确保最小容量
    if newCap < 16 {
        newCap = 16
    }

    // 分配新空间
    newBuf := make([]byte, newCap)
    copy(newBuf, s.buf[:s.len])

    s.buf = newBuf
    s.free = newCap - s.len

    // 更新类型
    s.updateType()
}

// 更新 SDS 类型
func (s *SDS) updateType() {
    length := s.len
    if length < 32 {
        s.typ = SDS_TYPE_5
    } else if length < 256 {
        s.typ = SDS_TYPE_8
    } else if length < 65536 {
        s.typ = SDS_TYPE_16
    } else if length < 4294967296 {
        s.typ = SDS_TYPE_32
    } else {
        s.typ = SDS_TYPE_64
    }
}

// 惰性空间释放
func (s *SDS) Trim() {
    if s.free > s.len {
        newBuf := make([]byte, s.len)
        copy(newBuf, s.buf[:s.len])
        s.buf = newBuf
        s.free = 0
    }
}

// 预分配空间
func (s *SDS) Reserve(additional int) {
    if s.free < additional {
        s.expand(s.len + additional)
    }
}

// sds/string_operations.go
package sds

import "fmt"

// 追加字符串
func (s *SDS) Append(str string) {
    s.AppendBytes([]byte(str))
}

// 追加字节数组
func (s *SDS) AppendBytes(data []byte) {
    dataLen := len(data)
    totalLen := s.len + dataLen

    // 空间不足时扩容
    if s.free < dataLen {
        s.expand(totalLen)
    }

    // 追加数据
    copy(s.buf[s.len:], data)
    s.len = totalLen
    s.free = len(s.buf) - s.len
}

// 追加单个字符
func (s *SDS) AppendChar(c byte) {
    s.AppendBytes([]byte{c})
}

// 插入字符串
func (s *SDS) Insert(index int, str string) error {
    if index < 0 || index > s.len {
        return fmt.Errorf("index out of range")
    }

    data := []byte(str)
    dataLen := len(data)
    totalLen := s.len + dataLen

    // 空间不足时扩容
    if s.free < dataLen {
        s.expand(totalLen)
    }

    // 移动现有数据
    copy(s.buf[index+dataLen:], s.buf[index:s.len])

    // 插入新数据
    copy(s.buf[index:], data)
    s.len = totalLen
    s.free = len(s.buf) - s.len

    return nil
}

// 删除指定范围的字符
func (s *SDS) Delete(start, end int) error {
    if start < 0 || end > s.len || start > end {
        return fmt.Errorf("invalid range")
    }

    // 移动数据
    copy(s.buf[start:], s.buf[end:s.len])
    s.len -= (end - start)
    s.free = len(s.buf) - s.len

    return nil
}

// 截取子字符串
func (s *SDS) Substr(start, end int) (*SDS, error) {
    if start < 0 || end > s.len || start > end {
        return nil, fmt.Errorf("invalid range")
    }

    // 处理负索引
    if start < 0 {
        start = s.len + start
    }
    if end < 0 {
        end = s.len + end
    }

    if start < 0 {
        start = 0
    }
    if end > s.len {
        end = s.len
    }

    if start >= end {
        return NewEmptySDS(), nil
    }

    data := s.buf[start:end]
    return NewSDSFromBytes(data), nil
}

// sds/compare_search.go
package sds

import (
    "bytes"
    "strings"
)

// 比较字符串
func (s *SDS) Compare(other *SDS) int {
    return bytes.Compare(s.buf[:s.len], other.buf[:other.len])
}

// 比较字符串（忽略大小写）
func (s *SDS) CompareIgnoreCase(other *SDS) int {
    return strings.Compare(strings.ToLower(s.String()), strings.ToLower(other.String()))
}

// 检查是否相等
func (s *SDS) Equals(other *SDS) bool {
    return s.Compare(other) == 0
}

// 检查是否以指定字符串开头
func (s *SDS) StartsWith(prefix string) bool {
    if len(prefix) > s.len {
        return false
    }
    return string(s.buf[:len(prefix)]) == prefix
}

// 检查是否以指定字符串结尾
func (s *SDS) EndsWith(suffix string) bool {
    if len(suffix) > s.len {
        return false
    }
    return string(s.buf[s.len-len(suffix):s.len]) == suffix
}

// 查找子字符串
func (s *SDS) Index(substr string) int {
    return strings.Index(s.String(), substr)
}

// 查找字符
func (s *SDS) IndexByte(c byte) int {
    for i := 0; i < s.len; i++ {
        if s.buf[i] == c {
            return i
        }
    }
    return -1
}

// sds/format_operations.go
package sds

import (
    "fmt"
    "strings"
)

// 格式化字符串
func (s *SDS) Format(format string, args ...interface{}) {
    formatted := fmt.Sprintf(format, args...)
    s.Clear()
    s.Append(formatted)
}

// 去除首尾空白字符
func (s *SDS) Strip() {
    s.LStrip()
    s.RStrip()
}

// 去除左侧空白字符
func (s *SDS) LStrip() {
    start := 0
    for start < s.len && isSpace(s.buf[start]) {
        start++
    }

    if start > 0 {
        s.Delete(0, start)
    }
}

// 去除右侧空白字符
func (s *SDS) RStrip() {
    end := s.len
    for end > 0 && isSpace(s.buf[end-1]) {
        end--
    }

    if end < s.len {
        s.Delete(end, s.len)
    }
}

// 检查是否为空白字符
func isSpace(c byte) bool {
    return c == ' ' || c == '\t' || c == '\n' || c == '\r'
}

// 分割字符串
func (s *SDS) Split(sep string) []*SDS {
    parts := strings.Split(s.String(), sep)
    result := make([]*SDS, len(parts))

    for i, part := range parts {
        result[i] = NewSDS(part)
    }

    return result
}

// 连接字符串
func JoinSDS(parts []*SDS, sep string) *SDS {
    if len(parts) == 0 {
        return NewEmptySDS()
    }

    result := NewSDS(parts[0].String())
    for i := 1; i < len(parts); i++ {
        result.Append(sep)
        result.Append(parts[i].String())
    }

    return result
}

package main

import (
    "fmt"
    "yourproject/sds"
)

func main() {
    // 1. 创建 SDS
    s := sds.NewSDS("Hello")
    fmt.Printf("s = %s, len = %d, free = %d\n", s.String(), s.Len(), s.Free())
    // 输出: s = Hello, len = 5, free = 0

    // 2. 追加字符串
    s.Append(" World")
    fmt.Printf("s = %s, len = %d, free = %d\n", s.String(), s.Len(), s.Free())
    // 输出: s = Hello World, len = 11, free = X

    // 3. 二进制安全
    binary := []byte{'R', 'e', 'd', 'i', 's', '\x00', 'D', 'B'}
    b := sds.NewSDSFromBytes(binary)
    fmt.Printf("Binary len = %d\n", b.Len())
    // 输出: Binary len = 8 (正确！)

    // 4. 子字符串
    sub, _ := s.Substr(0, 5)
    fmt.Printf("Substr = %s\n", sub.String())
    // 输出: Substr = Hello

    // 5. 分割
    csv := sds.NewSDS("a,b,c")
    parts := csv.Split(",")
    for i, part := range parts {
        fmt.Printf("Part %d: %s\n", i, part.String())
    }
}

// sds/benchmark_test.go
package sds

import (
    "strings"
    "testing"
)

func BenchmarkSDSAppend(b *testing.B) {
    sds := NewSDS("")

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        sds.Append("test")
    }
}

func BenchmarkGoStringAppend(b *testing.B) {
    var str string

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        str += "test"
    }
}

func BenchmarkSDSSubstr(b *testing.B) {
    sds := NewSDS("Hello World")

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        sds.Substr(0, 5)
    }
}

func BenchmarkGoStringSubstr(b *testing.B) {
    str := "Hello World"

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = str[0:5]
    }
}

// sds/sds_test.go
package sds

import "testing"

func TestSDSBasic(t *testing.T) {
    sds := NewSDS("Hello")

    if sds.Len() != 5 {
        t.Errorf("Expected length 5, got %d", sds.Len())
    }

    if sds.String() != "Hello" {
        t.Errorf("Expected 'Hello', got '%s'", sds.String())
    }
}

func TestSDSBinarySafety(t *testing.T) {
    data := []byte{'H', 'i', '\x00', 'B', 'y', 'e'}
    sds := NewSDSFromBytes(data)

    if sds.Len() != 6 {
        t.Errorf("Expected length 6, got %d", sds.Len())
    }

    if !bytes.Equal(sds.Bytes(), data) {
        t.Error("Binary data corrupted")
    }
}

func TestSDSAppend(t *testing.T) {
    sds := NewSDS("Hello")
    sds.Append(" World")

    expected := "Hello World"
    if sds.String() != expected {
        t.Errorf("Expected '%s', got '%s'", expected, sds.String())
    }
}

type SDS struct {
    len  int      // 直接存储长度
    free int
    buf  []byte
}

func (s *SDS) Len() int {
    return s.len  // O(1) 直接返回
}

// 存储包含 '\0' 的数据
data := []byte{'R', 'e', 'd', 'i', 's', '\x00', 'D', 'B'}
sds := NewSDSFromBytes(data)

sds.Len()  // 返回 8（正确）

if newLen < 1024*1024 {  // 小于 1MB
    newCap = newLen * 2  // 翻倍
} else {                  // 大于 1MB
    newCap = newLen + 1024*1024  // 多分配 1MB
}

sds := NewSDS("Hello")

// 可以直接传给 C 函数
printf("%s\n", sds.buf)  // 正确输出
strcmp(sds.buf, "Hi")    // 正确比较

sds := NewSDS("Hello World")  // len=11, alloc=22
sds.Delete(5, 11)             // len=5, alloc=22 保留
sds.Append(" Redis")          // len=11, alloc=22 无需 realloc 

sds.Trim()  // len=5, alloc=5

// Go string 不可变
s := "Hello"
s = s + " World"  // 创建新字符串 

// SDS 可变
sds.Append(" World")  // 就地修改 

func TestBinarySafety(t *testing.T) {
    // 包含 '\0' 的数据
    data := []byte{'H', 'i', '\x00', 'B', 'y', 'e'}

    sds := NewSDSFromBytes(data)

    // 验证长度正确
    if sds.Len() != 6 {
        t.Error("Length should be 6")
    }

    // 验证数据完整
    if !bytes.Equal(sds.Bytes(), data) {
        t.Error("Data corrupted")
    }
}

func (s *SDS) Replace(old, new string) int {
    // TODO: 实现字符串替换
    // 提示：使用 Index 查找，Delete 删除，Insert 插入
    return 0
}

func BenchmarkComparison() {
    // TODO: 对比 SDS vs Go String
    // - 追加 10000 次
    // - 获取长度 100000 次
    // - 子字符串 100000 次
}

func TestBinaryData() {
    // TODO: 验证 SDS 能正确存储：
    // - PNG 图片数据
    // - Protocol Buffers 序列化数据
    // - 包含多个 '\0' 的数据
}