go源码解读-sync.Mutex

发表于 2020-05-13 | 分类于 go ，源码解读

Mutex

sync包提供了互斥量，Once, WaitGroup来保证多线程并发安全
比较简单的同步通过sync包，比较复杂的同步建议通过channel来实现

Mutex结构体

Mutex实际上是互斥锁
Mutex的初始化状态就是一个没加锁的互斥锁
Mutex在被加锁之后不允许被复制，也就是带有状态的Mutex不能被复制，否则会给原来的临界数据复制出一把锁
Mutex包含两个字段
- state
- sema
Mutex现在有两种状态，normal和starvation
- normal状态下，goroutine是在一个FIFO的队列中排队等待锁的，也就是按照锁的请求时间依次获取锁。但是被唤醒的goroutine并不会立刻拥有mutex，而是需要与新到达的goroutine进行竞争，由于新到达的goroutine已经加载在内存中，所以被唤醒的goroutine大概率会竞争失败，竞争失败之后被唤醒的goroutine会被防止到FIFO的队首。如果一个被唤醒的goroutine在1ms内获取mutex失败，则mutex状态设置为starvation
- starvation状态下，mutex在被当前持有的线程解锁之后，FIFO队列首的goroutine被唤醒并直接拥有改mutex，新到达的goroutine不再尝试获取mutex,也不再自选等待获取锁，而是直接排到队列的队尾
- 如果一个goroutine获取到mutex，如果这个goroutine是队列中的最后一个goroutine或者goroutine等待时间小于1ms，则mutex状态变为noraml状态
- normal状态下性能更好，starvation状态下更加公平，不存在插队和多次获取的情况

type Mutex struct {
	state int32
	sema  uint32
}
const (
	mutexLocked = 1 << iota      // 锁定状态 001
	mutexWoken                   // 唤醒状态 010
	mutexStarving                // 饥饿状态 100
	mutexWaiterShift = iota      // 向右偏移3位之后的值记录等待该mutex的goroutine数量
	starvationThresholdNs = 1e6  // normal到starvation状态的阈值 1ms
)

Mutex实现了Locker接口

type Locker interface {
	Lock()
	Unlock()
}

lock方法对mutex加锁
如果mutex已经被加锁，尝试加锁的goroutine将会被阻塞直到获取到该锁

func (m *Mutex) Lock() {
  // 如果mutex没有被加过锁,则用原子方法CAS修改mutex的状态为mutexLocked，直接返回结果即可
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		if race.Enabled {
			race.Acquire(unsafe.Pointer(m))
		}
		return
	}
	var waitStartTime int64
	starving := false
	awoke := false
	iter := 0
	old := m.state
	for {
    // 如果当前mutex的状态为starvation，则当前线程不再自旋等待mutex
		if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
			// Active spinning makes sense.
			// Try to set mutexWoken flag to inform Unlock
			// to not wake other blocked goroutines.
      // awork为false,mutex为非awoke状态，有等待状态的goroutine且CAS更改awoke位成功，则将awoke设置为true
			if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
				atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
				awoke = true
			}
      // 实际的自旋等待操作，更新iter和old的值
			runtime_doSpin()
			iter++
			old = m.state
			continue
		}
		new := old
    // 如果mutex为starvation状态的话，当前的goroutine需要去队列中排队
		if old&mutexStarving == 0 {
			new |= mutexLocked
		}
		if old&(mutexLocked|mutexStarving) != 0 {
			new += 1 << mutexWaiterShift
		}
    // 当前goroutine为starvation状态并且为非锁定状态，设置mutex状态为starvation
		if starving && old&mutexLocked != 0 {
			new |= mutexStarving
		}
    // awoke为true,在等待队列中唤醒一个goroutine
		if awoke {
			if new&mutexWoken == 0 {
				throw("sync: inconsistent mutex state")
			}
			new &^= mutexWoken
		}
    // 将新的mutex状态值通过CAS复制给state
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
      // 如果old的状态为000，则直接退出，已经完成了上锁操作
			if old&(mutexLocked|mutexStarving) == 0 {
				break // locked the mutex with CAS
			}
			// If we were already waiting before, queue at the front of the queue.
			queueLifo := waitStartTime != 0
			if waitStartTime == 0 {
				waitStartTime = runtime_nanotime()
			}
      // 阻塞获取mutex，这个地方会一直阻塞，直到获取到mutex锁
			runtime_SemacquireMutex(&m.sema, queueLifo)
      // 获取到锁之后，根据获取锁的等待时间，设置mutex的运行状态是否为starvation
			starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
			old = m.state
      // 设置mutex的starvation状态
			if old&mutexStarving != 0 {
				if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
					throw("sync: inconsistent mutex state")
				}
				delta := int32(mutexLocked - 1<<mutexWaiterShift)
				if !starving || old>>mutexWaiterShift == 1 {
					delta -= mutexStarving
				}
				atomic.AddInt32(&m.state, delta)
				break
			}
			awoke = true
			iter = 0
		} else {
			old = m.state
		}
	}
	if race.Enabled {
		race.Acquire(unsafe.Pointer(m))
	}
}
// runtime包中的，返回当前时刻自旋等待是否有意义
func runtime_canSpin(i int) bool

Unlock完成解锁

func (m *Mutex) Unlock() {
  // 快速解锁
	if race.Enabled {
		_ = m.state
		race.Release(unsafe.Pointer(m))
	}
  // 快速重置mutexLocked位置为0，完成之后很可能被其他goroutine抢走锁
	new := atomic.AddInt32(&m.state, -mutexLocked)
	if (new+mutexLocked)&mutexLocked == 0 {
		throw("sync: unlock of unlocked mutex")
	}
  // 如果mutex为normal状态，走stravtion分支即可
	if new&mutexStarving == 0 {
		old := new
		for {
      // 如果没有等待的goroutine，直接返回即可
			if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
				return
			}
			// 有等待的goroutine，则会减少等待数量并且唤醒一个goroutine进行竞争mutex
			new = (old - 1<<mutexWaiterShift) | mutexWoken
			if atomic.CompareAndSwapInt32(&m.state, old, new) {
				runtime_Semrelease(&m.sema, false)
				return
			}
			old = m.state
		}
	} else {
    // starvation分支直接将mutex交给FIFO队列首部的goroutine
    // 通过runtime_Semrelease唤醒等待的goroutine
		runtime_Semrelease(&m.sema, true)
	}
}

goroutine&channel学习

发表于 2020-05-12 | 分类于 go

goroutine & channel

不需要共享内存来通信，而是通过通信来共享内存。

1. channel关键的概念总结

通道（channel），就像一个可以用于发送类型化数据的管道，由其负责协程之间的通信，从而避开所有由共享内存导致的陷阱；这种通过通道进行通信的方式保证了同步性。数据在通道中进行传递：在任何给定时间，一个数据被设计为只有一个协程可以对其访问，所以不会发生数据竞争。数据的所有权（可以读写数据的能力）也因此被传递。
channel零值nil
channel只能传递一种类型的数据
channel实际上是类型化消息的队列，使数据得以传输。它是先进先出（FIFO）的结构所以可以保证发送给他们的元素的顺序
channel是引用类型，make来初始化 ch1 := make(chan string)
通信操作符<-
- ch <-int1 写入
- int2 := <- ch 写出
- <-ch 写出
channel的收发都是原子操作

channel默认是同步且无缓冲的：接收者接收数据之前，发送不会结束。channel的发送和接收操作都是在对方准备好之前是阻塞的

package main
import "fmt"
func main() {
    ch1 := make(chan int)
    go pump(ch1)       // pump hangs
    fmt.Println(<-ch1) // prints only 0
}
func pump(ch chan int) {
    for i := 0; ; i++ {
        ch <- i
    }
}
// 0

2. 通过channel进行协程同步

1
2
3
4
5
6
7
8 func f1(in chan int) {
    fmt.Println(<-in)
}
func main() {
    out := make(chan int)
    out <- 2
    go f1(out)
}

3. channel可以用来完成协程间的通信

ch1 := make(chan string, buf) buf为个数
在缓冲满载之前，给通道发送数据是不会被阻塞的
在缓冲空之前，读取是不会阻塞的
协程通过在channel中放置一个值来发出处理结束的信号

信号量是实现互斥锁常见的同步机制

带缓冲通道的容量和要同步的资源容量相同
通道的长度（当前存放的元素个数）与当前资源被使用的数量相同

容量减去通道的长度就是未处理的资源个数（标准信号量的整数值）

func main() {
    stream := pump()
    go suck(stream)
    time.Sleep(1e9)
}
func pump() chan int {
    ch := make(chan int)
    go func() {
        for i := 0; ; i++ {
            ch <- i
        }
    }()
    return ch
}
func suck(ch chan int) {
    for {
        fmt.Println(<-ch)
    }
}

channel可以用for关键字循环

func main() {
    suck(pump())
    time.Sleep(1e9)
}
func pump() chan int {
    ch := make(chan int)
    go func() {
        for i := 0; ; i++ {
            ch <- i
        }
    }()
    return ch
}
func suck(ch chan int) {
    go func() {
        for v := range ch {
            fmt.Println(v)
        }
    }()
}

channel可以指定数据流动方向
- 只接收：var recv_noly <-chan int
- 只发送：var send_only chan<- int
channel关闭 defer close(ch)

使用select切换协程,select 被称为通信开关,select可以处理多个通信中的一个

func main() {
    ch1 := make(chan int)
    ch2 := make(chan int)
    go pump1(ch1)
    go pump2(ch2)
    go suck(ch1, ch2)
    time.Sleep(1e9)
}
func pump1(ch chan int) {
    for i := 0; ; i++ {
        ch <- i * 2
    }
}
func pump2(ch chan int) {
    for i := 0; ; i++ {
        ch <- i + 5
    }
}
func suck(ch1, ch2 chan int) {
    for {
        select {
        case v := <-ch1:
            fmt.Printf("Received on channel 1: %d\n", v)
        case v := <-ch2:
            fmt.Printf("Received on channel 2: %d\n", v)
        }
    }
}

goroutine recover机制，保证一个协程出错会继续执行其他的协程

func server(workChan <-chan *Work) {
    for work := range workChan {
        go safelyDo(work)
    }
}
func safelyDo(work *Work) {
    defer func() {
        if err := revocer(); err != nil {
            log.Printf("")
        }
    }()
    do(work)
}

4. channel通信方式和传统共享内存方式的对比

使用共享内存来进行同步：
- 首先定义一个结构体处理一个任务
- 各个任务组成任务池来共享内存，引入锁机制
- 任务数量巨大，则锁机制的开销会导致效率急剧下降
channel方式
- 使用一个通道接受需要处理的任务，一个通道接受处理完成的任务及其结果。worker在协程中启动，数量N可以调整
- 不使用锁的机制，因为从通道获取到新任务不存在竞争关系
- 我理解实际上锁机制是实现在了channel中，一个channel的获取是原子性的，从而提高性能
  1
  2
  3
  4
  5
  6
  7
  8
  //Worker的写法, Master -> Workers
  func Worker(in, out chan *Task) {
  for {
  t := <- in
  process(t)
  out <- t
  }
  }
使用锁的情景：
- 访问共享数据结构中的缓存信息
- 保存应用程序上下文和状态信息数据
使用通道的情景
- 与异步操作的结果进行交互
- 分发任务
- 传递数据所有权

5. int channel实现惰性生成器

var resume chan int
func integers() chan int {
    yield := make(chan int)
    count := 0
    go func() {
        for {
            yield <- count
            count++
        }
    }()
    return yield
}
func generateInteger() int {
    resume = integers()
    return <- resume
}

使用空接口，闭包和高阶函数可以实现一个通用的惰性生产期的工厂函数

type Any interface{}
type EvalFunc func(Any) (Any, Any)
func BuildLazyEvaluator(evalFunc, initState Any) func() Any {
    retValChan := make(chan Any)
    loopFunc := func(){
        var actState Any = initState
        var retVal
        for {
            retVal, actState = evalFunc(actState)
            retValChan <- retVal
        }
    }
    retFunc := func() Any {
        return <- retValChan
    }
    go loopFunc()
    return retFunc
}
func BuildLazyIntEvaluator(evalFunc EvalFunc, initState Any) func() int {
    ef := BuildLazyIntEvaluator(evalFunc, initState)
    return func() int {
        return ef().(int)
    }
}
func main() {
    evenFunc := func(state Any) (Any, Any) {
        os := state.(int)
        ns := os + 2
        return os, ns
    }
    even := BuildLazyIntEvaluator(evenFunc, 0)
    for i := 0; i < 10; i++ {
        fmt.
    }
}

6. 带缓冲的channel可以用于降频

const MAXREQS = 50
var sem = make(chan int, MAXREQS)
type Request struct {
    a, b int
    replyc chan int
}
func process(r *Request) {
//    ...
}
func handle(r *Request) {
    sem <- 1
    process(r)
    <- sem
}
func server(service chan *Request) {
    for {
        request := <- service
        go handler(request)
    }
}
func main() {
    service := make(chan *Request)
    go server(service)
}

链式协程，海量协程的创建和运行

var ngoroutine = flag.Int("n", 100000, "how many goroutines")
func f(left, right chan int) {
    left <- 1 + <- right
}
func main() {
    flag.Parse()
    leftmost := make(chan int)
    var left, right chan int = nil, leftmost
    for i := 0; i < *ngoroutine; i++ {
        left, right = right, make(chan int)
        go f(left, right)
    }
    right <- 0
    x := <-leftmost
    fmt.Println(x)
}

并行化大量数据的计算

串行处理流水线

func SerialProcessData(in <- chan *Data, out chan <- *Data) {
    for data := range in {
        tmpA := PreproceeData(data)
        tmpB := ProcessStepA(tmpA)
        tmpC := ProcessStepB(tmpB)
        out <- PostProcessData(tmpC)
    }
}

并行计算

func ParallelProcessData(in <-chan *Data, out chan<- *Data) {
    // make channels:
    preOut := make(chan *Data, 100)
    stepAOut := make(chan *Data, 100)
    stepBOut := make(chan *Data, 100)
    stepCOut := make(chan *Data, 100)
    // start parallel computations:
    go PreprocessData(in, preOut)
    go ProcessStepA(preOut,StepAOut)
    go ProcessStepB(StepAOut,StepBOut)
    go ProcessStepC(StepBOut,StepCOut)
    go PostProcessData(StepCOut,out)
}

8. 使用channel并发访问对象

type Person struct {
	Name   string
	salary float64
	chF    chan func()
}
func NewPerson(name string, salary float64) *Person {
	p := &Person{name, salary, make(chan func())}
	go p.backend()
	return p
}
func (p *Person) backend() {
	for f := range p.chF {
		f()
	}
}
// Set salary.
func (p *Person) SetSalary(sal float64) {
	p.chF <- func() { p.salary = sal }
}
// Retrieve salary.
func (p *Person) Salary() float64 {
	fChan := make(chan float64)
	p.chF <- func() { fChan <- p.salary }
	return <-fChan
}
func (p *Person) String() string {
	return "Person - name is: " + p.Name + " - salary is: " + strconv.FormatFloat(p.Salary(), 'f', 2, 64)
}
func main() {
	bs := NewPerson("Smith Bill", 2500.5)
	fmt.Println(bs)
	bs.SetSalary(4000.25)
	fmt.Println("Salary changed:")
	fmt.Println(bs)
}

golang interface学习

发表于 2020-05-12 | 分类于 go

interface

概念

go中的接口使用隐式实现的
LSP里式替换-一个类型可以自由的使用另一个满足相同接口的类型来进行替换
接口类型具体描述了一系列方法的集合，一个实现了这些方法的具体类型时这个接口类型的实例

go标准库存在大量的单方法接口的命名习惯

package io
type Reader interface {
    Read(p []byte) (n int, err error)
}
type Closer interface {
    Close() error
}

接口内嵌，关注的是内嵌的方法，和组合的设计模式思想类似

type ReadWriterCloser interface {
    Reader
    Writer
    Closer
}

一个类型持有一个方法，对于一个具体类型T，其一些方法的接收者可以是T也可以是T的指针，是因为比那一起隐式的获取了变量的地址。但是实际上T类型的值是不拥有所有*T指针的方法，这样就可能其实现更少的接口
- IntSet类型的String方法的接收者是一个指针类型，则不能在一个不能寻址的IntSet值上调用这个方法
  1
  2
  3
  type IntSet struct {/* ... */}
  func (*IntSet) String() string
  var _ = IntSet{}.String() // compile error : String requires *IntSet receiver
- 但是可以在一个IntSet值上调用这个方法
  1
  2
  var s IntSet
  var _ = s.String() // ok
- 同时只有IntSet类型有String类型，也只有IntSet类型实现了fmt.Stringer接口
接口类型封装和隐藏了具体类型和它的值，及时具体类型有其他方法也只有接口类型暴露出来的方法会被调用，也就是说一个具体的类型可以实现很多的接口，在调用的时候看持有这个变量的类型时哪个接口，就可以调用该接口的方法，而其他接口在该类型中实现的方法是被隐藏的。
空接口interface{}可以承接任意的值

每一个具体类型的组基于他们相同的行为可以表示成一个接口类型，不需要修改具体类型的定义，这个地方感觉还是组合的思想

// 出售数字文化产品如音乐，书籍，电影等
type Artifact interface {
    Title() string
    Creator() []string
    Created() time.Time
}
type Text interface {
    Pages() int
    Words() int
    PageSize() int
}
type Audio interface {
    Stream() (io.Readerclose, error)
    RunningTime() time.Duration
    Format() string
}
type Video interface {
    Stream() (io.ReadCloser, error)
    RunningTime() time.Duration
    Format() string
    Resolution() (x, y int)
}

flag.Value接口

flag.Duration方法

flag可以为程序预设命令行参数，会有一个参数缺省默认值
flag.Duration函数创建一个time.Duration类型的标记变量并且允许用户通过多种用户友好的方式来设置这个值的大小

var period = flag.Duration("period", 1 * time.Second, "Sleep duration")
func main() {
	flag.Parse()
	fmt.Printf("Sleeping for %v...", *period)
	time.Sleep(*period)
	fmt.Println("end")
}

首先看flag.Duration方法，返回的是一个地址指着

1
2
3

func Duration(name string, value time.Duration, usage string) *time.Duration {
	return CommandLine.Duration(name, value, usage)
}

然后看CommandLine的结构体和其Duration方法

var CommandLine = NewFlagSet(os.Args[0], ExitOnError)
func NewFlagSet(name string, errorHandling ErrorHandling) *FlagSet {
	f := &FlagSet{
		name:          name,
		errorHandling: errorHandling,
	}
	f.Usage = f.defaultUsage
	return f
}
func (f *FlagSet) Duration(name string, value time.Duration, usage string) *time.Duration {
	p := new(time.Duration)
	f.DurationVar(p, name, value, usage)
	return p
}
func (f *FlagSet) DurationVar(p *time.Duration, name string, value time.Duration, usage string) {
	f.Var(newDurationValue(value, p), name, usage)
}
// 真正实现值注入的地方
func (f *FlagSet) Var(value Value, name string, usage string) {
	// Remember the default value as a string; it won't change.
	flag := &Flag{name, usage, value, value.String()}
	_, alreadythere := f.formal[name]
	if alreadythere {
		var msg string
		if f.name == "" {
			msg = fmt.Sprintf("flag redefined: %s", name)
		} else {
			msg = fmt.Sprintf("%s flag redefined: %s", f.name, name)
		}
		fmt.Fprintln(f.Output(), msg)
		panic(msg) // Happens only if flags are declared with identical names
	}
	if f.formal == nil {
		f.formal = make(map[string]*Flag)
	}
	f.formal[name] = flag
}

实际上所有的Flag值保存在FlagSet结构体中的formal（map[string] *Flag）中

type FlagSet struct {
	// Usage is the function called when an error occurs while parsing flags.
	Usage func()
	name          string
	parsed        bool
	actual        map[string]*Flag
	formal        map[string]*Flag
	args          []string // arguments after flags
	errorHandling ErrorHandling
	output        io.Writer // nil means stderr; use out() accessor
}
// A Flag represents the state of a flag.
type Flag struct {
	Name     string // name as it appears on command line
	Usage    string // help message
	Value    Value  // value as set
	DefValue string // default value (as text); for usage message
}
// Value is the interface to the dynamic value stored in a flag.
type Value interface {
	String() string
	Set(string) error
}

flag.Parse()方法

首先看Parse()方法的实现

func Parse() {
	// Ignore errors; CommandLine is set for ExitOnError.
	CommandLine.Parse(os.Args[1:])
}
// flags初始化默认值之后，flag值使用之前，实际上是从命令行读取参数值对默认值进行覆盖操作
func (f *FlagSet) Parse(arguments []string) error {
	f.parsed = true
	f.args = arguments
	for {
		seen, err := f.parseOne()
		if seen {
			continue
		}
		if err == nil {
			break
		}
		switch f.errorHandling {
		case ContinueOnError:
			return err
		case ExitOnError:
			os.Exit(2)
		case PanicOnError:
			panic(err)
		}
	}
	return nil
}
//
func (f *FlagSet) parseOne() (bool, error) {
	if len(f.args) == 0 {
		return false, nil
	}
	s := f.args[0]
	if len(s) < 2 || s[0] != '-' {
		return false, nil
	}
	numMinuses := 1
	if s[1] == '-' {
		numMinuses++
		if len(s) == 2 { // "--" terminates the flags
			f.args = f.args[1:]
			return false, nil
		}
	}
	name := s[numMinuses:]
	if len(name) == 0 || name[0] == '-' || name[0] == '=' {
		return false, f.failf("bad flag syntax: %s", s)
	}
	// it's a flag. does it have an argument?
	f.args = f.args[1:]
	hasValue := false
	value := ""
	for i := 1; i < len(name); i++ { // equals cannot be first
		if name[i] == '=' {
			value = name[i+1:]
			hasValue = true
			name = name[0:i]
			break
		}
	}
	m := f.formal
	flag, alreadythere := m[name] // BUG
	if !alreadythere {
		if name == "help" || name == "h" { // special case for nice help message.
			f.usage()
			return false, ErrHelp
		}
		return false, f.failf("flag provided but not defined: -%s", name)
	}
	if fv, ok := flag.Value.(boolFlag); ok && fv.IsBoolFlag() { // special case: doesn't need an arg
		if hasValue {
			if err := fv.Set(value); err != nil {
				return false, f.failf("invalid boolean value %q for -%s: %v", value, name, err)
			}
		} else {
			if err := fv.Set("true"); err != nil {
				return false, f.failf("invalid boolean flag %s: %v", name, err)
			}
		}
	} else {
		// It must have a value, which might be the next argument.
		// 在这里进行解析替换
		if !hasValue && len(f.args) > 0 {
			// value is the next arg
			hasValue = true
			value, f.args = f.args[0], f.args[1:]
		}
		if !hasValue {
			return false, f.failf("flag needs an argument: -%s", name)
		}
		// set设置
		if err := flag.Value.Set(value); err != nil {
			return false, f.failf("invalid value %q for flag -%s: %v", value, name, err)
		}
	}
	if f.actual == nil {
		f.actual = make(map[string]*Flag)
	}
	f.actual[name] = flag
	return true, nil
}
// Duration的Set方法
func (d *durationValue) Set(s string) error {
	v, err := time.ParseDuration(s)
	if err != nil {
		err = errParse
	}
	*d = durationValue(v)
	return err
}
func ParseDuration(s string) (Duration, error) {
	// [-+]?([0-9]*(\.[0-9]*)?[a-z]+)+
	orig := s
	var d int64
	neg := false
	// Consume [-+]?
	if s != "" {
		c := s[0]
		if c == '-' || c == '+' {
			neg = c == '-'
			s = s[1:]
		}
	}
	// Special case: if all that is left is "0", this is zero.
	if s == "0" {
		return 0, nil
	}
	if s == "" {
		return 0, errors.New("time: invalid duration " + orig)
	}
	for s != "" {
		var (
			v, f  int64       // integers before, after decimal point
			scale float64 = 1 // value = v + f/scale
		)
		var err error
		// The next character must be [0-9.]
		if !(s[0] == '.' || '0' <= s[0] && s[0] <= '9') {
			return 0, errors.New("time: invalid duration " + orig)
		}
		// Consume [0-9]*
		pl := len(s)
		v, s, err = leadingInt(s)
		if err != nil {
			return 0, errors.New("time: invalid duration " + orig)
		}
		pre := pl != len(s) // whether we consumed anything before a period
		// Consume (\.[0-9]*)?
		post := false
		if s != "" && s[0] == '.' {
			s = s[1:]
			pl := len(s)
			f, scale, s = leadingFraction(s)
			post = pl != len(s)
		}
		if !pre && !post {
			// no digits (e.g. ".s" or "-.s")
			return 0, errors.New("time: invalid duration " + orig)
		}
		// Consume unit.
		i := 0
		for ; i < len(s); i++ {
			c := s[i]
			if c == '.' || '0' <= c && c <= '9' {
				break
			}
		}
		if i == 0 {
			return 0, errors.New("time: missing unit in duration " + orig)
		}
		u := s[:i]
		s = s[i:]
		unit, ok := unitMap[u]
		if !ok {
			return 0, errors.New("time: unknown unit " + u + " in duration " + orig)
		}
		if v > (1<<63-1)/unit {
			// overflow
			return 0, errors.New("time: invalid duration " + orig)
		}
		v *= unit
		if f > 0 {
			// float64 is needed to be nanosecond accurate for fractions of hours.
			// v >= 0 && (f*unit/scale) <= 3.6e+12 (ns/h, h is the largest unit)
			v += int64(float64(f) * (float64(unit) / scale))
			if v < 0 {
				// overflow
				return 0, errors.New("time: invalid duration " + orig)
			}
		}
		d += v
		if d < 0 {
			// overflow
			return 0, errors.New("time: invalid duration " + orig)
		}
	}
	if neg {
		d = -d
	}
	return Duration(d), nil
}

接口值

接口值指一个具体的类型和那个类型的值，也称为接口的动态类型和动态值
go中提供类型信息的值实际上是类型描述符，类型时编译期的概念
接口的零值指的是期类型和值的部分都是nil
不包含任何值的nil接口和一个刚好包含nil指针的接口值是不同的

go中排序算法的实现

sort接口

package sort
// 排序接口只规定了三个方法，序列长度，两个元素的比较结果，交换两个元素的方式
type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

go中排序函数的实现

// 实现了前面Interface的结构体都可以进行排序，go中排序使用的是改进后的快排
func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}
// 堆排序最大深度
func maxDepth(n int) int {
	var depth int
	for i := n; i > 0; i >>= 1 {
		depth++
	}
	return depth * 2
}
func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
		    // 进行堆排序
			heapSort(data, a, b)
			return
		}
		maxDepth--
		// 获取pivot，进行快排
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		// 希尔排序
		// It could be written in this simplified form cause b-a <= 12
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}

总结

interface是一种类型
interfacde{}是空接口，和Java中Object类似，所有的结构体都实现了空接口
如果一个类型实现了一个interface的所有方法，则该类型实现了该接口
interface变量存储的是实现结构体的值，并且只会暴露接口公开的值和方法
判断interface存储的类型可以使用断言来实现。value, ok := interfaceObject.(assertType)

interface的接收者是类型值还是指针在定义的时候没有严格规定，但是go语言实际上是只支持值传递。golang的语法糖会将函数里调用的指针进行隐式的转换成值，但是反过来是不行的。函数调用优先使用指针就OK了。

type I interface {
	Get() int
	Set(int)
}
type SS struct {
	Age int
}
func (s SS) Get() int {
	return s.Age
}
func (s SS) Set(age int) {
	s.Age = age
}
func f(i I) {
	i.Set(10)
	fmt.Println(i.Get())
}
func main() {
	ss := SS{}
	f(&ss) //指针参数，无论函数的接收者是值还是指针都不会保存
	f(ss)  //值参数，函数的接收者是值不会报错，是指针会编译报错
}

go源码解读-io包

发表于 2020-05-12 | 分类于 go ，源码解读

io包中的接口定义

io包中提供了IO操作相关的一系列接口
io包可以理解对os包中底层操作的封装
由于是对底层进行封装，除非特殊提及，否则io包下的函数是线程不安全的

Reader接口

Reader接口只包含一个Read方法
Read方法最多读取len(p)个字节到p中，返回读取到p中的字节数及过程中的错误
Read方法读取过程中出错，会返回已经读取到的字节数
Read出错的时候可以返回已经读取到的字节数和nil错误或者返回遇到的错误，而再下次调用Read方法的时候返回0, err即可
Read方法的调用者需要先处理n>0的情况下的数据，而后考虑err的值，防止读取的数据丢失
Read方法不鼓励返回0，nil样式的返回值，除非len(p) == 0
p不能作为实现Reader接口的结构体的成员变量

1
2
3

type Reader interface {
	Read(p []byte) (n int, err error)
}

Writer接口

Writer接口只包含Write方法
Write方法完成从p中写入len(p)个字节到数据流中，返回的是写入的字节数及遇到的错误
Write方法如果返回的n<len(p)，则必须返回个非空的错误
Write方法不允许调整p中的数据，临时调整也不可以
p不能作为实现Writer接口的结构体的成员变量

1
2
3

type Writer interface {
	Write(p []byte) (n int, err error)
}

Closer接口

Closer接口只包含Close方法
Closer接口返回关闭对象中遇到的错误

1
2
3

type Closer interface {
	Close() error
}

Seeker接口

Seeker接口只含有一个Seek方法
Seek方法根据whence的值计算出下一个读取或者写入的偏移量
- SeekStart对起始文件的偏移量
- SeekCurrent对当前索引的偏移量
- SeekEnd对结尾的偏移量
Seek方法返回相对于起始位置的偏移量，和遇到的错误
实际上返回的偏移量小于文件的起始索引会产生错误

const (
	SeekStart   = 0 // seek relative to the origin of the file
	SeekCurrent = 1 // seek relative to the current offset
	SeekEnd     = 2 // seek relative to the end
)
type Seeker interface {
	Seek(offset int64, whence int) (int64, error)
}

组合接口

对于上述的接口进行组合会产生一系列新的接口

// ReadWriter is the interface that groups the basic Read and Write methods.
type ReadWriter interface {
	Reader
	Writer
}
// ReadCloser is the interface that groups the basic Read and Close methods.
type ReadCloser interface {
	Reader
	Closer
}
// WriteCloser is the interface that groups the basic Write and Close methods.
type WriteCloser interface {
	Writer
	Closer
}
// ReadWriteCloser is the interface that groups the basic Read, Write and Close methods.
type ReadWriteCloser interface {
	Reader
	Writer
	Closer
}
// ReadSeeker is the interface that groups the basic Read and Seek methods.
type ReadSeeker interface {
	Reader
	Seeker
}
// WriteSeeker is the interface that groups the basic Write and Seek methods.
type WriteSeeker interface {
	Writer
	Seeker
}
// ReadWriteSeeker is the interface that groups the basic Read, Write and Seek methods.
type ReadWriteSeeker interface {
	Reader
	Writer
	Seeker
}

ReaderFrom接口

ReaderFrom接口只包含ReadFrom方法
ReadFrom方法从r中读取数据直到遇到EOF或者error
ReadFrom方法返回读取到的字节数和遇到的错误
io.Copy函数会优先使用

1
2
3

type ReaderFrom interface {
	ReadFrom(r Reader) (n int64, err error)
}

WriteTo接口

WriteTo接口只包含WriteTo方法
WriteTo方法向w中写入数据，直到没有数据可以写入或者遇到了错误
WriteTo方法返回写入的字节数和遇到的问题
io.Copy函数会优先使用

1
2
3

type WriterTo interface {
	WriteTo(w Writer) (n int64, err error)
}

ReaderAt接口

ReaderAt接口只包含ReadAt方法
ReadAt方法在实现的结构体的输入流中，在偏移量offset的位置读取len(p)个字节数据导p中
ReadAt方法在读取到的字节小于len(p)时会返回一个非空错误来解释为什么没有读取完全，这个地方的要求比Reader接口更加严格
ReadAt方法在调用过程中会占据p的全部内存空间，即使读取到的n小于p的长度
ReadAt如果读取到的数据小于len(p),则ReadAt方法会等待更多的数据到来或者返回一个错误，这个地方要求也是比Reader更加严格
ReadAt如果读取完最后一个数据之后，刚好读取了len(p)个字节，则可以返回的err为nil或者EOF
ReadAt方法如果读取的是一个实现了Seek接口的结构体，那么ReadAt的offset和seek的offset不应该相互影响
读取的数据流可以支持多个ReadAt方法并发读取，也就是ReadAt是线程安全的

1
2
3

type ReaderAt interface {
	ReadAt(p []byte, off int64) (n int, err error)
}

WriteAt接口

WriterAt接口只包含WriteAt方法
WriteAt方法完成向数据流的写入，写入的起点为输入流的offset位置
WriteAt方法返回向数据流写入的数据和遇到的错误
WriteAt方法当写入的数据小于len(p)时，返回的错误不能为nil
WriteAt方法写入的数据流实现了Seek方法，则Seek方法的offset和WriteAt方法的offset互不影响
在数据流不溢出的情况下，WriteAt方法可以并发写入，是线程安全的
-

1
2
3

type WriterAt interface {
	WriteAt(p []byte, off int64) (n int, err error)
}

ByteReader接口

ByteReader接口只包含ReadByte方法
ReadByte方法读取一个字节，返回从input数据流中读取到的下一个字节或者遇到的错误
如果返回了一个错误，则input数据流没有字节被读取消费掉，并且返回的字节值为undefined

1
2
3

type ByteReader interface {
	ReadByte() (byte, error)
}

ByteScanner接口

ByteScanner接口封装了ByteReader接口和UnreadByte方法
UnreadByte方法在ReadByte方法之后调用，会重置ReadByte方法的操作
如果在没调用ReadByte方法时，调用UnreadByte方法会报错

type ByteScanner interface {
	ByteReader
	UnreadByte() error
}

ByteWriter接口

ByteWriter接口只包含WriteByte方法
WriteByte方法完成对数据流的字节写入

1
2
3

type ByteWriter interface {
	WriteByte(c byte) error
}

RuneReader接口

RuneReader接口包含ReadRune方法
Readrune方法从数据流中读取一个UTF-8编码的Unicode字符，返回读取到的字符，字符的大小和遇到的错误

1
2
3

type RuneReader interface {
	ReadRune() (r rune, size int, err error)
}

RuneScanner接口

RuneScanner接口封装了RuneReader接口和UnreadRune方法
UnreadRune方法实际上是重置ReadRune方法的操作，需要在ReadRune方法之后调用

type RuneScanner interface {
	RuneReader
	UnreadRune() error
}

StringWriter接口

1
2
3

type StringWriter interface {
	WriteString(s string) (n int, err error)
}

io包中的错误定义

var ErrShortWrite = errors.New("short write")
var ErrShortBuffer = errors.New("short buffer")
var EOF = errors.New("EOF")
var ErrUnexpectedEOF = errors.New("unexpected EOF")
var ErrNoProgress = errors.New("multiple Read calls return no data or error")

io包中定义的结构体

LimitedReader

LimitedReader读入数据到R中，限制读入的字节数为N

type LimitedReader struct {
	R Reader // underlying reader
	N int64  // max bytes remaining
}
// 初始化方法
func LimitReader(r Reader, n int64) Reader { return &LimitedReader{r, n} }
// 实现Reader接口
func (l *LimitedReader) Read(p []byte) (n int, err error) {
	if l.N <= 0 {
		return 0, EOF
	}
	if int64(len(p)) > l.N {
		p = p[0:l.N]
	}
	n, err = l.R.Read(p)
	l.N -= int64(n)
	return
}

SectionReader

SectionReader完成数据的部分读取

type SectionReader struct {
	r     ReaderAt
	base  int64
	off   int64
	limit int64
}
// 初始化
func NewSectionReader(r ReaderAt, off int64, n int64) *SectionReader {
	return &SectionReader{r, off, off, off + n}
}
// 实现Reader接口
func (s *SectionReader) Read(p []byte) (n int, err error) {
	if s.off >= s.limit {
		return 0, EOF
	}
	if max := s.limit - s.off; int64(len(p)) > max {
		p = p[0:max]
	}
	n, err = s.r.ReadAt(p, s.off)
	s.off += int64(n)
	return
}
// 实现Seeker接口
func (s *SectionReader) Seek(offset int64, whence int) (int64, error) {
	switch whence {
	default:
		return 0, errWhence
	case SeekStart:
		offset += s.base
	case SeekCurrent:
		offset += s.off
	case SeekEnd:
		offset += s.limit
	}
	if offset < s.base {
		return 0, errOffset
	}
	s.off = offset
	return offset - s.base, nil
}
// 实现ReaderAt接口
func (s *SectionReader) ReadAt(p []byte, off int64) (n int, err error) {
	if off < 0 || off >= s.limit-s.base {
		return 0, EOF
	}
	off += s.base
	if max := s.limit - off; int64(len(p)) > max {
		p = p[0:max]
		n, err = s.r.ReadAt(p, off)
		if err == nil {
			err = EOF
		}
		return n, err
	}
	return s.r.ReadAt(p, off)
}
// 返回section的字节尺寸
func (s *SectionReader) Size() int64 { return s.limit - s.base }

常用工具类方法

WriteString函数将字符串s写入到w中

func WriteString(w Writer, s string) (n int, err error) {
	if sw, ok := w.(StringWriter); ok {
		return sw.WriteString(s)
	}
	return w.Write([]byte(s))
}

ReadAtLeast函数从r中读取数据导buf中，同时规定了最少读取的字节数

func (r Reader, buf []byte, min int) (n int, err error) {
	if len(buf) < min {
		return 0, ErrShortBuffer
	}
	for n < min && err == nil {
		var nn int
		nn, err = r.Read(buf[n:])
		n += nn
	}
	if n >= min {
		err = nil
	} else if n > 0 && err == EOF {
		err = ErrUnexpectedEOF
	}
	return
}

ReadFull一次性读取len(buf)个数到buf中，实际上是对ReadAtLeast的封装

1
2
3

func ReadFull(r Reader, buf []byte) (n int, err error) {
	return ReadAtLeast(r, buf, len(buf))
}

Copy方法完成将src的数据复制到dst中，直到遇到EOF或者错误
Copy成功的话会返回nil，而不是EOF
如果src实现了WriteTo方法，则会优先调用，否则会调用dst的ReadFrom方法

1
2
3

func Copy(dst Writer, src Reader) (written int64, err error) {
	return copyBuffer(dst, src, nil)
}

CopyBuffer和Copy是一致的，只是增加了缓冲区

func CopyBuffer(dst Writer, src Reader, buf []byte) (written int64, err error) {
	if buf != nil && len(buf) == 0 {
		panic("empty buffer in io.CopyBuffer")
	}
	return copyBuffer(dst, src, buf)
}

copyBuffer是实际上的Copy和CopyBuffer的实现

func copyBuffer(dst Writer, src Reader, buf []byte) (written int64, err error) {
  // 如果src实现了WriteTo接口，则调用其WroteTo方法完成写入
	if wt, ok := src.(WriterTo); ok {
		return wt.WriteTo(dst)
	}
  // 如果dst实现了ReaderFrom接口，则调用ReadFrom方法完成写入
	if rt, ok := dst.(ReaderFrom); ok {
		return rt.ReadFrom(src)
	}
  // 缓冲区大小确定
	if buf == nil {
		size := 32 * 1024
		if l, ok := src.(*LimitedReader); ok && int64(size) > l.N {
			if l.N < 1 {
				size = 1
			} else {
				size = int(l.N)
			}
		}
		buf = make([]byte, size)
	}
	for {
    // 读取到buf中
		nr, er := src.Read(buf)
		if nr > 0 {
      // 写入操作
			nw, ew := dst.Write(buf[0:nr])
			if nw > 0 {
				written += int64(nw)
			}
			if ew != nil {
				err = ew
				break
			}
			if nr != nw {
				err = ErrShortWrite
				break
			}
		}
		if er != nil {
			if er != EOF {
				err = er
			}
			break
		}
	}
	return written, err
}

CopyN完成从src复制N个字节数据到dst

func CopyN(dst Writer, src Reader, n int64) (written int64, err error) {
	written, err = Copy(dst, LimitReader(src, n))
	if written == n {
		return n, nil
	}
	if written < n && err == nil {
		err = EOF
	}
	return
}

ioutil中的工具类

ReadAll函数

ReadAll函数将r中的数据读取出来并返回
成功读取返回的err为nil
readAll函数实际上是利用bytes.Buffer完成数据的读取的

func ReadAll(r io.Reader) ([]byte, error) {
	return readAll(r, bytes.MinRead)
}
func readAll(r io.Reader, capacity int64) (b []byte, err error) {
	var buf bytes.Buffer
	defer func() {
		e := recover()
		if e == nil {
			return
		}
		if panicErr, ok := e.(error); ok && panicErr == bytes.ErrTooLarge {
			err = panicErr
		} else {
			panic(e)
		}
	}()
  // 防止capacity溢出
	if int64(int(capacity)) == capacity {
		buf.Grow(int(capacity))
	}
	_, err = buf.ReadFrom(r)
	return buf.Bytes(), err
}

ReadFile函数

ReadFile完成对指定文件的读取并且返回其数据

func ReadFile(filename string) ([]byte, error) {
  // 打开文件
	f, err := os.Open(filename)
	if err != nil {
		return nil, err
	}
	defer f.Close()
	var n int64 = bytes.MinRead
	if fi, err := f.Stat(); err == nil {
    // 确定读取的size，比文件的大小稍微多一些
		if size := fi.Size() + bytes.MinRead; size > n {
			n = size
		}
	}
  // 调用readAll方法来完成数据的读取
	return readAll(f, n)
}

WriteFile函数

WriteFile将数据写入到名称为filename的文件中

func WriteFile(filename string, data []byte, perm os.FileMode) error {
  // 打开文件，如果不存在，则创建
	f, err := os.OpenFile(filename, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, perm)
	if err != nil {
		return err
	}
  // 数据的追加写入
	n, err := f.Write(data)
	if err == nil && n < len(data) {
		err = io.ErrShortWrite
	}
  // 关闭文件
	if err1 := f.Close(); err == nil {
		err = err1
	}
	return err
}

ReadDir函数

ReadDir函数读取dirname下的文件或者路径并返回

func ReadDir(dirname string) ([]os.FileInfo, error) {
	f, err := os.Open(dirname)
	if err != nil {
		return nil, err
	}
	list, err := f.Readdir(-1)
	f.Close()
	if err != nil {
		return nil, err
	}
	sort.Slice(list, func(i, j int) bool { return list[i].Name() < list[j].Name() })
	return list, nil
}

NopCloser

NopCloser返回带Close方法的Reader

func NopCloser(r io.Reader) io.ReadCloser {
	return nopCloser{r}
}
type nopCloser struct {
	io.Reader
}
func (nopCloser) Close() error { return nil }

Discard

Discard的写入操作都会被忽略

// Discard实际上是通过devNull来构建的
var Discard io.Writer = devNull(0)
// devNull结构体本身是个int数据
type devNull int
// 实现了Writer接口
func (devNull) Write(p []byte) (int, error) {
	return len(p), nil
}
// 实现了StringWriter接口
func (devNull) WriteString(s string) (int, error) {
	return len(s), nil
}
// 实现了ReaderFrom接口
func (devNull) ReadFrom(r io.Reader) (n int64, err error) {
	bufp := blackHolePool.Get().(*[]byte)
	readSize := 0
	for {
		readSize, err = r.Read(*bufp)
		n += int64(readSize)
		if err != nil {
			blackHolePool.Put(bufp)
			if err == io.EOF {
				return n, nil
			}
			return
		}
	}
}
var blackHolePool = sync.Pool{
	New: func() interface{} {
		b := make([]byte, 8192)
		return &b
	},
}

Pipe函数

Pipe在内存中创建了个管道，可以用于连接需要io.Reader和io.Writer的代码
读写会相互阻塞，除非一个写入被多次读取的场景存在
Pipe是并发安全的

func Pipe() (*PipeReader, *PipeWriter) {
	p := &pipe{
		wrCh: make(chan []byte),
		rdCh: make(chan int),
		done: make(chan struct{}),
	}
	return &PipeReader{p}, &PipeWriter{p}
}

PipeReader和PipeWriter

PipeReader是管道读的半边

type PipeReader struct {
	p *pipe
}
// 实现了io.Reader接口
func (r *PipeReader) Read(data []byte) (n int, err error) {
	return r.p.Read(data)
}
// 实现了io.Closer接口
func (r *PipeReader) Close() error {
	return r.CloseWithError(nil)
}
func (r *PipeReader) CloseWithError(err error) error {
	return r.p.CloseRead(err)
}

PipeWriter是管道写的半边

type PipeWriter struct {
	p *pipe
}
// 实现了io.Writer接口
func (w *PipeWriter) Write(data []byte) (n int, err error) {
	return w.p.Write(data)
}
// 实现了io。Close方法
func (w *PipeWriter) Close() error {
	return w.CloseWithError(nil)
}
func (w *PipeWriter) CloseWithError(err error) error {
	return w.p.CloseWrite(err)
}

pipe结构体

实际上Pipe是对pipe的封装

type pipe struct {
	wrMu sync.Mutex // 保障写入的安全
	wrCh chan []byte // 写入的数据
	rdCh chan int // 读取到的数量的byte数
	once sync.Once // 保证pipe只被关闭一次
	done chan struct{} // pipe关闭通道信息
	rerr atomicError // 读错误
	werr atomicError // 写错误
}

pipe实现了io.Reader接口

func (p *pipe) Read(b []byte) (n int, err error) {
  // 判断要读取的通道是否已经关闭
  select {
	case <-p.done:
		return 0, p.readCloseError()
	default:
	}
  // 将数据写入b中，并将写入的字节数写入rdCh通道中
	select {
	case bw := <-p.wrCh:
		nr := copy(b, bw)
		p.rdCh <- nr
		return nr, nil
	case <-p.done:
		return 0, p.readCloseError()
	}
}

pipe实现了io.Writer接口

func (p *pipe) Write(b []byte) (n int, err error) {
  // 保证写入的时候安全，且pipe没有关闭
	select {
	case <-p.done:
		return 0, p.writeCloseError()
	default:
		p.wrMu.Lock()
		defer p.wrMu.Unlock()
	}
  // 写入数据
	for once := true; once || len(b) > 0; once = false {
		select {
		case p.wrCh <- b:
			nw := <-p.rdCh
			b = b[nw:]
			n += nw
		case <-p.done:
			return n, p.writeCloseError()
		}
	}
	return n, nil
}

pipe的Close方法

func (p *pipe) CloseRead(err error) error {
	if err == nil {
		err = ErrClosedPipe
	}
	p.rerr.Store(err)
	p.once.Do(func() { close(p.done) })
	return nil
}
func (p *pipe) CloseWrite(err error) error {
	if err == nil {
		err = EOF
	}
	p.werr.Store(err)
	p.once.Do(func() { close(p.done) })
	return nil
}

multi

MultiReader 将多个Reader的内容写入p

func MultiReader(readers ...Reader) Reader {
	r := make([]Reader, len(readers))
	copy(r, readers)
	return &multiReader{r}
}
type multiReader struct {
	readers []Reader
}
func (mr *multiReader) Read(p []byte) (n int, err error) {
	for len(mr.readers) > 0 {
    // flat嵌套
		if len(mr.readers) == 1 {
			if r, ok := mr.readers[0].(*multiReader); ok {
				mr.readers = r.readers
				continue
			}
		}
		n, err = mr.readers[0].Read(p)
		if err == EOF {
      // 避免nl panic
			mr.readers[0] = eofReader{} // permit earlier GC
			mr.readers = mr.readers[1:]
		}
		if n > 0 || err != EOF {
			if err == EOF && len(mr.readers) > 0 {
				// Don't return EOF yet. More readers remain.
				err = nil
			}
			return
		}
	}
	return 0, EOF
}
// 避免nil panic
type eofReader struct{}
func (eofReader) Read([]byte) (int, error) {
	return 0, EOF
}

MultiWriter 将p的内容写入多个数据流中

func MultiWriter(writers ...Writer) Writer {
	allWriters := make([]Writer, 0, len(writers))
	for _, w := range writers {
		if mw, ok := w.(*multiWriter); ok {
			allWriters = append(allWriters, mw.writers...)
		} else {
			allWriters = append(allWriters, w)
		}
	}
	return &multiWriter{allWriters}
}
type multiWriter struct {
	writers []Writer
}
func (t *multiWriter) Write(p []byte) (n int, err error) {
	for _, w := range t.writers {
		n, err = w.Write(p)
		if err != nil {
			return
		}
		if n != len(p) {
			err = ErrShortWrite
			return
		}
	}
	return len(p), nil
}
func (t *multiWriter) WriteString(s string) (n int, err error) {
	var p []byte // lazily initialized if/when needed
	for _, w := range t.writers {
		if sw, ok := w.(StringWriter); ok {
			n, err = sw.WriteString(s)
		} else {
			if p == nil {
				p = []byte(s)
			}
			n, err = w.Write(p)
		}
		if err != nil {
			return
		}
		if n != len(s) {
			err = ErrShortWrite
			return
		}
	}
	return len(s), nil
}

go源码解读-sort

发表于 2020-05-11 | 分类于 go ，源码解读

Interface接口

实现了Interface接口的结构体，可以调用sort.Sort进行排序

type Interface interface {
  // 长度获取方法
	Len() int
  // 大小比较方法
	Less(i, j int) bool
  // 元素交换方法
	Swap(i, j int)
}

Sort函数

Sort函数完成对传入的Interface类型数据data的排序
实际上调用的是quickSort方法来完成排序的
maxDepth函数返回数据的深度，用于确定排序算法是快排还是堆排列，分割值为2*ceil(lg(n+1))

func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}
func maxDepth(n int) int {
	var depth int
	for i := n; i > 0; i >>= 1 {
		depth++
	}
	return depth * 2
}

quickSort函数完成Interface的排序

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 {
		if maxDepth == 0 {
      // 堆排序
			heapSort(data, a, b)
			return
		}
		maxDepth--
    // 计算基准值，进行快速排序
		mlo, mhi := doPivot(data, a, b)
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
  // 排序长度小于12时用Shell排序
	if b-a > 1 {
    // Gap=6进行一次希尔排序
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
    // shell排序完之后用插入排序
		insertionSort(data, a, b)
	}
}
// 插入排序
func insertionSort(data Interface, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}

pivot函数


func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
	m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
	if hi-lo > 40 {
		// Tukey's ``Ninther,'' median of three medians of three.
		s := (hi - lo) / 8
		medianOfThree(data, lo, lo+s, lo+2*s)
		medianOfThree(data, m, m-s, m+s)
		medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
	}
	medianOfThree(data, lo, m, hi-1)
	// Invariants are:
	//	data[lo] = pivot (set up by ChoosePivot)
	//	data[lo < i < a] < pivot
	//	data[a <= i < b] <= pivot
	//	data[b <= i < c] unexamined
	//	data[c <= i < hi-1] > pivot
	//	data[hi-1] >= pivot
	pivot := lo
	a, c := lo+1, hi-1
	for ; a < c && data.Less(a, pivot); a++ {
	}
	b := a
	for {
		for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
		}
		for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
		}
		if b >= c {
			break
		}
		// data[b] > pivot; data[c-1] <= pivot
		data.Swap(b, c-1)
		b++
		c--
	}
	// If hi-c<3 then there are duplicates (by property of median of nine).
	// Let's be a bit more conservative, and set border to 5.
	protect := hi-c < 5
	if !protect && hi-c < (hi-lo)/4 {
		// Lets test some points for equality to pivot
		dups := 0
		if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
			data.Swap(c, hi-1)
			c++
			dups++
		}
		if !data.Less(b-1, pivot) { // data[b-1] = pivot
			b--
			dups++
		}
		// m-lo = (hi-lo)/2 > 6
		// b-lo > (hi-lo)*3/4-1 > 8
		// ==> m < b ==> data[m] <= pivot
		if !data.Less(m, pivot) { // data[m] = pivot
			data.Swap(m, b-1)
			b--
			dups++
		}
		// if at least 2 points are equal to pivot, assume skewed distribution
		protect = dups > 1
	}
	if protect {
		// Protect against a lot of duplicates
		// Add invariant:
		//	data[a <= i < b] unexamined
		//	data[b <= i < c] = pivot
		for {
			for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
			}
			for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
			}
			if a >= b {
				break
			}
			// data[a] == pivot; data[b-1] < pivot
			data.Swap(a, b-1)
			a++
			b--
		}
	}
	// Swap pivot into middle
	data.Swap(pivot, b-1)
	return b - 1, c
}
// medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
func medianOfThree(data Interface, m1, m0, m2 int) {
	// sort 3 elements
	if data.Less(m1, m0) {
		data.Swap(m1, m0)
	}
	// data[m0] <= data[m1]
	if data.Less(m2, m1) {
		data.Swap(m2, m1)
		// data[m0] <= data[m2] && data[m1] < data[m2]
		if data.Less(m1, m0) {
			data.Swap(m1, m0)
		}
	}
	// now data[m0] <= data[m1] <= data[m2]
}

堆排序

func heapSort(data Interface, a, b int) {
	first := a
	lo := 0
	hi := b - a
	// Build heap with greatest element at top.
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown(data, i, hi, first)
	}
	// Pop elements, largest first, into end of data.
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown(data, lo, i, first)
	}
}
func siftDown(data Interface, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

字符串排序举例

func (p StringSlice) Len() int           { return len(p) }
func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
// Sort is a convenience method.
func (p StringSlice) Sort() { Sort(p) }

工具类函数

IsSorted判断data是否是有序的

func IsSorted(data Interface) bool {
	n := data.Len()
	for i := n - 1; i > 0; i-- {
		if data.Less(i, i-1) {
			return false
		}
	}
	return true
}

Reverse对data进行倒序排列

func Reverse(data Interface) Interface {
	return &reverse{data}
}
type reverse struct {
	Interface
}
// 重写Interface的Less方法
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

Stable函数在排序过程中保持相等数据的原始顺序

func Stable(data Interface) {
	stable(data, data.Len())
}
func stable(data Interface, n int) {
	blockSize := 20 // must be > 0
	a, b := 0, blockSize
	for b <= n {
		insertionSort(data, a, b)
		a = b
		b += blockSize
	}
	insertionSort(data, a, n)
	for blockSize < n {
		a, b = 0, 2*blockSize
		for b <= n {
			symMerge(data, a, a+blockSize, b)
			a = b
			b += 2 * blockSize
		}
		if m := a + blockSize; m < n {
			symMerge(data, a, m, n)
		}
		blockSize *= 2
	}
}

go源码解读-strings包的工具函数

发表于 2020-05-11 | 分类于 go ，源码解读

strings包中的常用函数

Contains类函数

Contains函数返回字符串s中是否存在substr，具体实现的Index方法和bytes包中的实现类似，也是用了Rabin-Karp search进行字符匹配查找
ContainsAny函数返回字符串s中是否存在chars中任意一个字符，实现中使用ASCiiSet的方法
ContainsRune函数返回字符串s中是否包含字符r,通过Index方法实现

// Contains reports whether substr is within s.
func Contains(s, substr string) bool {
	return Index(s, substr) >= 0
}
// ContainsAny reports whether any Unicode code points in chars are within s.
func ContainsAny(s, chars string) bool {
	return IndexAny(s, chars) >= 0
}
func IndexAny(s, chars string) int {
	if chars == "" {
		// Avoid scanning all of s.
		return -1
	}
	if len(s) > 8 {
		if as, isASCII := makeASCIISet(chars); isASCII {
			for i := 0; i < len(s); i++ {
				if as.contains(s[i]) {
					return i
				}
			}
			return -1
		}
	}
	for i, c := range s {
		for _, m := range chars {
			if c == m {
				return i
			}
		}
	}
	return -1
}
// makeASCIISet creates a set of ASCII characters and reports whether all
// characters in chars are ASCII.
func makeASCIISet(chars string) (as asciiSet, ok bool) {
	for i := 0; i < len(chars); i++ {
		c := chars[i]
		if c >= utf8.RuneSelf {
			return as, false
		}
		as[c>>5] |= 1 << uint(c&31)
	}
	return as, true
}
// ContainsRune reports whether the Unicode code point r is within s.
func ContainsRune(s string, r rune) bool {
	return IndexRune(s, r) >= 0
}

Fields

Fields函数将字符串按照空白字符进行切割，返回字符串数组

func Fields(s string) []string {
	n := 0
	wasSpace := 1
	// setBits is used to track which bits are set in the bytes of s.
	setBits := uint8(0)
	for i := 0; i < len(s); i++ {
		r := s[i]
		setBits |= r
		isSpace := int(asciiSpace[r])
		n += wasSpace & ^isSpace
		wasSpace = isSpace
	}
  // ASCII编码的快捷返回
	if setBits < utf8.RuneSelf { // ASCII fast path
		a := make([]string, n)
		na := 0
		fieldStart := 0
		i := 0
		// Skip spaces in the front of the input.
		for i < len(s) && asciiSpace[s[i]] != 0 {
			i++
		}
		fieldStart = i
		for i < len(s) {
			if asciiSpace[s[i]] == 0 {
				i++
				continue
			}
			a[na] = s[fieldStart:i]
			na++
			i++
			// Skip spaces in between fields.
			for i < len(s) && asciiSpace[s[i]] != 0 {
				i++
			}
			fieldStart = i
		}
		if fieldStart < len(s) { // Last field might end at EOF.
			a[na] = s[fieldStart:]
		}
		return a
	}
  // 调用FieldsFunc来完成字符串的分割操作
	return FieldsFunc(s, unicode.IsSpace)
}
func FieldsFunc(s string, f func(rune) bool) []string {
  // 分割起点终点索引值
	type span struct {
		start int
		end   int
	}
	spans := make([]span, 0, 32)
	// Find the field start and end indices.
	wasField := false
	fromIndex := 0
	for i, rune := range s {
		if f(rune) {
			if wasField {
				spans = append(spans, span{start: fromIndex, end: i})
				wasField = false
			}
		} else {
			if !wasField {
				fromIndex = i
				wasField = true
			}
		}
	}
	// Last field might end at EOF.
	if wasField {
		spans = append(spans, span{fromIndex, len(s)})
	}
  // 返回结果值
	a := make([]string, len(spans))
	for i, span := range spans {
		a[i] = s[span.start:span.end]
	}
	return a
}

Has函数

// HasPrefix tests whether the string s begins with prefix.
func HasPrefix(s, prefix string) bool {
	return len(s) >= len(prefix) && s[0:len(prefix)] == prefix
}
// HasSuffix tests whether the string s ends with suffix.
func HasSuffix(s, suffix string) bool {
	return len(s) >= len(suffix) && s[len(s)-len(suffix):] == suffix
}

Join函数

func Join(a []string, sep string) string {
	switch len(a) {
	case 0:
		return ""
	case 1:
		return a[0]
	}
  // 计算结果需要的内存大小
	n := len(sep) * (len(a) - 1)
	for i := 0; i < len(a); i++ {
		n += len(a[i])
	}
  // 构建strings.Builder并分配内存
	var b Builder
	b.Grow(n)
  // 将字符串数组s和sep逐个写入
	b.WriteString(a[0])
	for _, s := range a[1:] {
		b.WriteString(sep)
		b.WriteString(s)
	}
  // 返回结果
	return b.String()
}

Last类函数

LastIndex函数返回最后一个匹配的substr的索引值，使用了Rabin-Karp算法

func LastIndex(s, substr string) int {
	n := len(substr)
	switch {
	case n == 0:
		return len(s)
	case n == 1:
		return LastIndexByte(s, substr[0])
	case n == len(s):
		if substr == s {
			return 0
		}
		return -1
	case n > len(s):
		return -1
	}
	// Rabin-Karp search from the end of the string
	hashss, pow := hashStrRev(substr)
	last := len(s) - n
	var h uint32
	for i := len(s) - 1; i >= last; i-- {
		h = h*primeRK + uint32(s[i])
	}
	if h == hashss && s[last:] == substr {
		return last
	}
	for i := last - 1; i >= 0; i-- {
		h *= primeRK
		h += uint32(s[i])
		h -= pow * uint32(s[i+n])
		if h == hashss && s[i:i+n] == substr {
			return i
		}
	}
	return -1
}

LastIndexAny函数返回s中找到的最后一个chars中任意一个字符

func LastIndexAny(s, chars string) int {
	if chars == "" {
		return -1
	}
	if len(s) > 8 {
		if as, isASCII := makeASCIISet(chars); isASCII {
			for i := len(s) - 1; i >= 0; i-- {
				if as.contains(s[i]) {
					return i
				}
			}
			return -1
		}
	}
	for i := len(s); i > 0; {
		r, size := utf8.DecodeLastRuneInString(s[:i])
		i -= size
		for _, c := range chars {
			if r == c {
				return i
			}
		}
	}
	return -1
}

LastIndexByte返回s中匹配的最后一个字节c的索引值

func LastIndexByte(s string, c byte) int {
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == c {
			return i
		}
	}
	return -1
}

Map函数

Map函数根据映射规则函数mapping，完成对字符串s的字符替换

func Map(mapping func(rune) rune, s string) string {
	var b Builder
	for i, c := range s {
		r := mapping(c)
		if r == c && c != utf8.RuneError {
			continue
		}
		var width int
		if c == utf8.RuneError {
			c, width = utf8.DecodeRuneInString(s[i:])
			if width != 1 && r == c {
				continue
			}
		} else {
			width = utf8.RuneLen(c)
		}
		b.Grow(len(s) + utf8.UTFMax)
		b.WriteString(s[:i])
		if r >= 0 {
			b.WriteRune(r)
		}
		s = s[i+width:]
		break
	}
	if b.Cap() == 0 { // didn't call b.Grow above
		return s
	}
	for _, c := range s {
		r := mapping(c)
		if r >= 0 {
			if r < utf8.RuneSelf {
				b.WriteByte(byte(r))
			} else {
				// r is not a ASCII rune.
				b.WriteRune(r)
			}
		}
	}
	return b.String()
}

Repeat函数

Repeat函数将字符串s复制count遍并组合到一起

func Repeat(s string, count int) string {
	if count == 0 {
		return ""
	}
	if count < 0 {
		panic("strings: negative Repeat count")
	} else if len(s)*count/count != len(s) {
		panic("strings: Repeat count causes overflow")
	}
	n := len(s) * count
	var b Builder
	b.Grow(n)
	b.WriteString(s)
	for b.Len() < n {
		if b.Len() <= n/2 {
			b.WriteString(b.String())
		} else {
			b.WriteString(b.String()[:n-b.Len()])
			break
		}
	}
	return b.String()
}

Replace

Replace方法完成对字符串的替换并制定替换的个数

func Replace(s, old, new string, n int) string {
	if old == new || n == 0 {
		return s // avoid allocation
	}
	// Compute number of replacements.
	if m := Count(s, old); m == 0 {
		return s // avoid allocation
	} else if n < 0 || m < n {
		n = m
	}
	// Apply replacements to buffer.
	t := make([]byte, len(s)+n*(len(new)-len(old)))
	w := 0
	start := 0
	for i := 0; i < n; i++ {
		j := start
		if len(old) == 0 {
			if i > 0 {
				_, wid := utf8.DecodeRuneInString(s[start:])
				j += wid
			}
		} else {
			j += Index(s[start:], old)
		}
		w += copy(t[w:], s[start:j])
		w += copy(t[w:], new)
		start = j + len(old)
	}
	w += copy(t[w:], s[start:])
	return string(t[0:w])
}
func ReplaceAll(s, old, new string) string {
	return Replace(s, old, new, -1)
}

Split方法

func Split(s, sep string) []string { return genSplit(s, sep, 0, -1) }
func SplitAfter(s, sep string) []string {
	return genSplit(s, sep, len(sep), -1)
}
func SplitAfterN(s, sep string, n int) []string {
	return genSplit(s, sep, len(sep), n)
}
func SplitN(s, sep string, n int) []string { return genSplit(s, sep, 0, n) }

Split类函数实际上都是对genSplit函数的封装

func genSplit(s, sep string, sepSave, n int) []string {
	if n == 0 {
		return nil
	}
	if sep == "" {
		return explode(s, n)
	}
	if n < 0 {
		n = Count(s, sep) + 1
	}
	a := make([]string, n)
	n--
	i := 0
	for i < n {
		m := Index(s, sep)
		if m < 0 {
			break
		}
		a[i] = s[:m+sepSave]
		s = s[m+len(sep):]
		i++
	}
	a[i] = s
	return a[:i+1]
}

Title函数

Title对Map进行了封装，将空白字符的下一个字符进行大写处理

func Title(s string) string {
	prev := ' '
	return Map(
		func(r rune) rune {
			if isSeparator(prev) {
				prev = r
				return unicode.ToTitle(r)
			}
			prev = r
			return r
		},
		s)
}

To类方法和Trim类方法和bytes包中的类似，没有本质区别，不再赘述

go源码解读-strings.stringFinder

发表于 2020-05-11 | 分类于 go ，源码解读

stringFinder

stringFinder 结构体来完成在一个文本中查找指定的字符串
采用Boyer-Moore字符串查找算法，简单来说每次字符串后移的位数为坏字符规则和好后缀规则的较大值
参考 https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
stringFinder包含三个参数

type stringFinder struct {
  // 待查找的目标字符串
	pattern string
  // 坏字符对应的偏移量，索引为对应的字节
	badCharSkip [256]int
  // 好字符偏移量，索引表示有几个匹配的字符
	goodSuffixSkip []int
}

makeStringFinder函数

完成构建badCharSkip和goodSuffixSkip的值

func makeStringFinder(pattern string) *stringFinder {
	f := &stringFinder{
		pattern:        pattern,
		goodSuffixSkip: make([]int, len(pattern)),
	}
	// last is the index of the last character in the pattern.
	last := len(pattern) - 1
	// Build bad character table.
	// Bytes not in the pattern can skip one pattern's length.
	for i := range f.badCharSkip {
		f.badCharSkip[i] = len(pattern)
	}
	// The loop condition is < instead of <= so that the last byte does not
	// have a zero distance to itself. Finding this byte out of place implies
	// that it is not in the last position.
	for i := 0; i < last; i++ {
		f.badCharSkip[pattern[i]] = last - i
	}
	// Build good suffix table.
	// First pass: set each value to the next index which starts a prefix of
	// pattern.
	lastPrefix := last
	for i := last; i >= 0; i-- {
		if HasPrefix(pattern, pattern[i+1:]) {
			lastPrefix = i + 1
		}
		// lastPrefix is the shift, and (last-i) is len(suffix).
		f.goodSuffixSkip[i] = lastPrefix + last - i
	}
	// Second pass: find repeats of pattern's suffix starting from the front.
	for i := 0; i < last; i++ {
		lenSuffix := longestCommonSuffix(pattern, pattern[1:i+1])
		if pattern[i-lenSuffix] != pattern[last-lenSuffix] {
			// (last-i) is the shift, and lenSuffix is len(suffix).
			f.goodSuffixSkip[last-lenSuffix] = lenSuffix + last - i
		}
	}
	return f
}
// 最长相同字符的数量，从后向前
func longestCommonSuffix(a, b string) (i int) {
	for ; i < len(a) && i < len(b); i++ {
		if a[len(a)-1-i] != b[len(b)-1-i] {
			break
		}
	}
	return
}

实际上移动的位数是从两个里面取最大值，next方法如下

func (f *stringFinder) next(text string) int {
	i := len(f.pattern) - 1
	for i < len(text) {
		// Compare backwards from the end until the first unmatching character.
		j := len(f.pattern) - 1
		for j >= 0 && text[i] == f.pattern[j] {
			i--
			j--
		}
		if j < 0 {
			return i + 1 // match
		}
		i += max(f.badCharSkip[text[i]], f.goodSuffixSkip[j])
	}
	return -1
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

go源码解读-strings.Compare、strings.Replace

发表于 2020-05-09 | 分类于 go ，源码解读

Compare

Compare只是提供一个方法，考虑性能的时候不建议调用
建议使用内建操作符== > <进行字符串的比较，效率更高，性能更好

func Compare(a, b string) int {
	if a == b {
		return 0
	}
	if a < b {
		return -1
	}
	return +1
}

Replace

replacer接口

抽象出来的所有replace方法都需要实现的接口
包含Replace方法和WriteString方法
Replace方法完成s中字符串的替换
WriteString方法在将s写入w中完成s字符串的替换操作

type replacer interface {
	Replace(s string) string
	WriteString(w io.Writer, s string) (n int, err error)
}

Replace结构体

Replacer结构体完成字符串切片的替换,第一个字符串是旧的，第二个是匹配到替换为新的字符串
Replacer是线程安全的，可以用于并发编程中，通过once参数来实现
NewReplacer完成Replacer结构体的初始化

type Replacer struct {
	once   sync.Once // guards buildOnce method
	r      replacer
	oldnew []string
}
func NewReplacer(oldnew ...string) *Replacer {
	if len(oldnew)%2 == 1 {
		panic("strings.NewReplacer: odd argument count")
	}
	return &Replacer{oldnew: append([]string(nil), oldnew...)}
}

Replace本身实现了replacer接口
实际上的替换操作是通过其参数r来完成的
r.once.Do保证参数函数只被执行一次
buildOnce函数完成对参数r的赋值，以及参数oldNew的置空操作

func (r *Replacer) Replace(s string) string {
	r.once.Do(r.buildOnce)
	return r.r.Replace(s)
}
func (r *Replacer) WriteString(w io.Writer, s string) (n int, err error) {
	r.once.Do(r.buildOnce)
	return r.r.WriteString(w, s)
}
func (r *Replacer) buildOnce() {
	r.r = r.build()
	r.oldnew = nil
}

build方法

build函数完成Replace中r的构造，根据oldnew内容的不通进行筛选
- 如果替换的新旧字符串长度为2，且被替换的字符串的长度>1，makeSingleStringReplacer完成替换
- 如果被替换的字符串不是单字节数据，则调用函数makeGenericReplacer构建通用的替换器
- 如果只是字节之间的替换，构造器为byteReplacer即可
- 如果是将单个字节替换为string字符串的情况，则byteStringReplacer可以完成替换能力

func (b *Replacer) build() replacer {
	oldnew := b.oldnew
  // 如果替换的新旧字符串长度为2，且被替换的字符串的长度>1，makeSingleStringReplacer完成替换
	if len(oldnew) == 2 && len(oldnew[0]) > 1 {
		return makeSingleStringReplacer(oldnew[0], oldnew[1])
	}
	allNewBytes := true
	for i := 0; i < len(oldnew); i += 2 {
    // 如果被替换的字符串不是单字节数据，则调用函数makeGenericReplacer构建通用的替换器
		if len(oldnew[i]) != 1 {
			return makeGenericReplacer(oldnew)
		}
		if len(oldnew[i+1]) != 1 {
			allNewBytes = false
		}
	}
  // 如果只是字节之间的替换，构造器为byteReplacer即可
	if allNewBytes {
		r := byteReplacer{}
		for i := range r {
			r[i] = byte(i)
		}
		for i := len(oldnew) - 2; i >= 0; i -= 2 {
			o := oldnew[i][0]
			n := oldnew[i+1][0]
			r[o] = n
		}
		return &r
	}
  // 如果是将单个字节替换为string字符串的情况，则byteStringReplacer可以完成替换能力
	r := byteStringReplacer{toReplace: make([]string, 0, len(oldnew)/2)}
	for i := len(oldnew) - 2; i >= 0; i -= 2 {
		o := oldnew[i][0]
		n := oldnew[i+1]
		if r.replacements[o] == nil {
      // 这个地方用string([]byte{o})是为了处理o为utf8编码的情况
			r.toReplace = append(r.toReplace, string([]byte{o}))
		}
		r.replacements[o] = []byte(n)
	}
	return &r
}

byteReplacer结构体

byteReplacer结构体完成单个ASCII编码字节的替换
Replace方法利用一个256大小的字节数组来完成字节的替换工作
WriteString完成替换，并将替换之后的数据写入到w中

type byteReplacer [256]byte
func (r *byteReplacer) Replace(s string) string {
	var buf []byte // 懒初始化
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r[b] != b {
			if buf == nil {
				buf = []byte(s)
			}
			buf[i] = r[b]
		}
	}
	if buf == nil {
		return s
	}
	return string(buf)
}
func (r *byteReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	// TODO(bradfitz): use io.WriteString with slices of s, avoiding allocation.
	bufsize := 32 << 10
	if len(s) < bufsize {
		bufsize = len(s)
	}
	buf := make([]byte, bufsize)
	for len(s) > 0 {
		ncopy := copy(buf, s)
		s = s[ncopy:]
    // 替换操作
		for i, b := range buf[:ncopy] {
			buf[i] = r[b]
		}
    // 写入操作
		wn, err := w.Write(buf[:ncopy])
		n += wn
		if err != nil {
			return n, err
		}
	}
	return n, nil
}

singleStringReplacer结构体

singleStringReplacer结构体包含两个参数
- finder结构体用于进行字符串的查找
- value是查找到的字符串替换为的值
makeSingleStringReplacer完成singleStringReplacer的构建

type singleStringReplacer struct {
	finder *stringFinder
	// value is the new string that replaces that pattern when it's found.
	value string
}
func makeSingleStringReplacer(pattern string, value string) *singleStringReplacer {
	return &singleStringReplacer{finder: makeStringFinder(pattern), value: value}
}

Replace方法完成字符串的匹配替换

func (r *singleStringReplacer) Replace(s string) string {
	var buf []byte
	i, matched := 0, false
	for {
    // 返回匹配到的起始位置
		match := r.finder.next(s[i:])
		if match == -1 {
			break
		}
		matched = true
    // 写入buf
		buf = append(buf, s[i:i+match]...)
		buf = append(buf, r.value...)
		i += match + len(r.finder.pattern)
	}
	if !matched {
		return s
	}
	buf = append(buf, s[i:]...)
	return string(buf)
}

WriteString将匹配之后的结果写入w中

func (r *singleStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	var i, wn int
	for {
		match := r.finder.next(s[i:])
		if match == -1 {
			break
		}
		wn, err = sw.WriteString(s[i : i+match])
		n += wn
		if err != nil {
			return
		}
		wn, err = sw.WriteString(r.value)
		n += wn
		if err != nil {
			return
		}
		i += match + len(r.finder.pattern)
	}
	wn, err = sw.WriteString(s[i:])
	n += wn
	return
}
func getStringWriter(w io.Writer) io.StringWriter {
	sw, ok := w.(io.StringWriter)
	if !ok {
		sw = stringWriter{w}
	}
	return sw
}
// stringWriter实现了io.Writer接口
type stringWriter struct {
	w io.Writer
}
func (w stringWriter) WriteString(s string) (int, error) {
	return w.w.Write([]byte(s))
}

byteStringReplacer 结构体

byteStringReplacer完成字节替换成字符串的操作的结构体
- replacements记录字符和字符串之间的替换映射关系
- toReplace记录待替换的字符数组，以[]string格式记录

type byteStringReplacer struct {
  // 替换规则
	replacements [256][]byte
  // 待替换的字符串数组，实际上记录的是单个字符的字符串数组
	toReplace []string
}
const countCutOff = 8

Replace方法替换中会根据字符串的长度采用效率更高的方法来确认替换后的字符串需要的空间
然后遍历完成替换操作

func (r *byteStringReplacer) Replace(s string) string {
	newSize := len(s)
	anyChanges := false
	// Is it faster to use Count?
	if len(r.toReplace)*countCutOff <= len(s) {
		for _, x := range r.toReplace {
			if c := Count(s, x); c != 0 {
				// The -1 is because we are replacing 1 byte with len(replacements[b]) bytes.
				newSize += c * (len(r.replacements[x[0]]) - 1)
				anyChanges = true
			}
		}
	} else {
		for i := 0; i < len(s); i++ {
			b := s[i]
			if r.replacements[b] != nil {
				// See above for explanation of -1
				newSize += len(r.replacements[b]) - 1
				anyChanges = true
			}
		}
	}
	if !anyChanges {
		return s
	}
	buf := make([]byte, newSize)
	j := 0
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r.replacements[b] != nil {
			j += copy(buf[j:], r.replacements[b])
		} else {
			buf[j] = b
			j++
		}
	}
	return string(buf)
}

WriteString则直接进行循环替换并写入w中

func (r *byteStringReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	last := 0
	for i := 0; i < len(s); i++ {
		b := s[i]
		if r.replacements[b] == nil {
			continue
		}
		if last != i {
			nw, err := sw.WriteString(s[last:i])
			n += nw
			if err != nil {
				return n, err
			}
		}
		last = i + 1
		nw, err := w.Write(r.replacements[b])
		n += nw
		if err != nil {
			return n, err
		}
	}
	if last != len(s) {
		var nw int
		nw, err = sw.WriteString(s[last:])
		n += nw
	}
	return
}

genericReplacer结构体

genericReplacer实际上是完整的通用算法，其余的各种分支是效率更高的快捷替换方法
genericReplacer包含三个参数
- root节点，，类型时trieNode，Trie树的根节点
- tableSize int类型 trie树的查找表大小
- mapping 完成字节到trie树索引的映射

type genericReplacer struct {
	root trieNode
	// tableSize is the size of a trie node's lookup table. It is the number
	// of unique key bytes.
	tableSize int
	// mapping maps from key bytes to a dense index for trieNode.table.
	mapping [256]byte
}

trieNode结构体

trieNode是trie树的一个节点，含有5个参数
- value为节点key/value对中的值，如果当前节点不是一个完整的key的话，value为空
- priority 优先值，当前节点为完整路径时大于0，否则优先级为0
- prefix,next，如果这两个非空，则当前节点有一个子节点
- table，如果table非空，则其中记录了所有的子节点

type trieNode struct {
	value string
	priority int
	prefix string
	next   *trieNode
	table []*trieNode
}

trieNode的add方法

func (t *trieNode) add(key, val string, priority int, r *genericReplacer) {
	if key == "" {
		if t.priority == 0 {
			t.value = val
			t.priority = priority
		}
		return
	}
	if t.prefix != "" {
		// n记录key和t.prefix的最大相同的前缀，也就是n之前是匹配的，n之后是不匹配的
		var n int
		for ; n < len(t.prefix) && n < len(key); n++ {
			if t.prefix[n] != key[n] {
				break
			}
		}
		if n == len(t.prefix) {
      // 如果n和t.prefix的长度相等，也就是说key之后的部分都是没有的索引值
			t.next.add(key[n:], val, priority, r)
		} else if n == 0 {
      // 首字母就不同，这时候需要在root节点创建个新的查找表
			var prefixNode *trieNode
			if len(t.prefix) == 1 {
				prefixNode = t.next
			} else {
				prefixNode = &trieNode{
					prefix: t.prefix[1:],
					next:   t.next,
				}
			}
			keyNode := new(trieNode)
			t.table = make([]*trieNode, r.tableSize)
			t.table[r.mapping[t.prefix[0]]] = prefixNode
			t.table[r.mapping[key[0]]] = keyNode
			t.prefix = ""
			t.next = nil
			keyNode.add(key[1:], val, priority, r)
		} else {
      // 插入节点数据
			next := &trieNode{
				prefix: t.prefix[n:],
				next:   t.next,
			}
			t.prefix = t.prefix[:n]
			t.next = next
			next.add(key[n:], val, priority, r)
		}
	} else if t.table != nil {
    // 插入已经存在table列表中心的节点
		m := r.mapping[key[0]]
		if t.table[m] == nil {
			t.table[m] = new(trieNode)
		}
		t.table[m].add(key[1:], val, priority, r)
	} else {
    // 创建根节点
		t.prefix = key
		t.next = new(trieNode)
		t.next.add("", val, priority, r)
	}
}

Replace方法

Replace方法实际上是对WriteString方法的调用，将s替换之后的结果写入到buf中
buf实际上是对io.Writer接口的实现

func (r *genericReplacer) Replace(s string) string {
	buf := make(appendSliceWriter, 0, len(s))
	r.WriteString(&buf, s)
	return string(buf)
}
type appendSliceWriter []byte
// Write writes to the buffer to satisfy io.Writer.
func (w *appendSliceWriter) Write(p []byte) (int, error) {
	*w = append(*w, p...)
	return len(p), nil
}
// WriteString writes to the buffer without string->[]byte->string allocations.
func (w *appendSliceWriter) WriteString(s string) (int, error) {
	*w = append(*w, s...)
	return len(s), nil
}

WriteString方法

func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error) {
	sw := getStringWriter(w)
	var last, wn int
	var prevMatchEmpty bool
	for i := 0; i <= len(s); {
		if i != len(s) && r.root.priority == 0 {
			index := int(r.mapping[s[i]])
			if index == r.tableSize || r.root.table[index] == nil {
				i++
				continue
			}
		}
		val, keylen, match := r.lookup(s[i:], prevMatchEmpty)
		prevMatchEmpty = match && keylen == 0
		if match {
			wn, err = sw.WriteString(s[last:i])
			n += wn
			if err != nil {
				return
			}
			wn, err = sw.WriteString(val)
			n += wn
			if err != nil {
				return
			}
			i += keylen
			last = i
			continue
		}
		i++
	}
	if last != len(s) {
		wn, err = sw.WriteString(s[last:])
		n += wn
	}
	return
}
// 查找方法
func (r *genericReplacer) lookup(s string, ignoreRoot bool) (val string, keylen int, found bool) {
	bestPriority := 0
	node := &r.root
	n := 0
	for node != nil {
		if node.priority > bestPriority && !(ignoreRoot && node == &r.root) {
			bestPriority = node.priority
			val = node.value
			keylen = n
			found = true
		}
		if s == "" {
			break
		}
		if node.table != nil {
			index := r.mapping[s[0]]
			if int(index) == r.tableSize {
				break
			}
			node = node.table[index]
			s = s[1:]
			n++
		} else if node.prefix != "" && HasPrefix(s, node.prefix) {
			n += len(node.prefix)
			s = s[len(node.prefix):]
			node = node.next
		} else {
			break
		}
	}
	return
}
// 创建通用的替换器，实际上是完成trie树的构建
func makeGenericReplacer(oldnew []string) *genericReplacer {
	r := new(genericReplacer)
	// Find each byte used, then assign them each an index.
	for i := 0; i < len(oldnew); i += 2 {
		key := oldnew[i]
		for j := 0; j < len(key); j++ {
			r.mapping[key[j]] = 1
		}
	}
	for _, b := range r.mapping {
		r.tableSize += int(b)
	}
	var index byte
	for i, b := range r.mapping {
		if b == 0 {
			r.mapping[i] = byte(r.tableSize)
		} else {
			r.mapping[i] = index
			index++
		}
	}
	// Ensure root node uses a lookup table (for performance).
	r.root.table = make([]*trieNode, r.tableSize)
	for i := 0; i < len(oldnew); i += 2 {
		r.root.add(oldnew[i], oldnew[i+1], len(oldnew)-i, r)
	}
	return r
}

go源码解读-strings.Reader

发表于 2020-05-09 | 分类于 go ，源码解读

Reader

strings.Reader结构体

Reader结构体包三个参数
- s,带读取的字符串
- i,当前读取到的字符索引值
- prevRune上一个读取到的字符索引值
- Reader结构体的零值和从空字符串读取创建Reader是等价的
- Reader结构体实现了io.Reader, io.ReaderAt, io.Seeker, io.WriterTo,io.ByteScanner, and io.RuneScanner等接口

type Reader struct {
	s        string
	i        int64 // current reading index
	prevRune int   // index of previous rune; or < 0
}
// 结构体初始化方法
func NewReader(s string) *Reader { return &Reader{s, 0, -1} }

结构体的方法

Len方法返回字符串s未读取部分的字节数
Size方法返回字符串s的字节数

func (r *Reader) Len() int {
	if r.i >= int64(len(r.s)) {
		return 0
	}
	return int(int64(len(r.s)) - r.i)
}
func (r *Reader) Size() int64 { return int64(len(r.s)) }

Read方法，从字符串s中读取数据到b中，读取到字节数为len(b)和len(s[s.r:])之间的较小值

func (r *Reader) Read(b []byte) (n int, err error) {
	if r.i >= int64(len(r.s)) {
		return 0, io.EOF
	}
	r.prevRune = -1
	n = copy(b, r.s[r.i:])
	r.i += int64(n)
	return
}

ReadAt方法读取s[off:]之后的字节切片到字符串到b中

func (r *Reader) ReadAt(b []byte, off int64) (n int, err error) {
	// cannot modify state - see io.ReaderAt
	if off < 0 {
		return 0, errors.New("strings.Reader.ReadAt: negative offset")
	}
	if off >= int64(len(r.s)) {
		return 0, io.EOF
	}
	n = copy(b, r.s[off:])
	if n < len(b) {
		err = io.EOF
	}
	return
}

ReadByte方法从s中读取i指向的字节
UnreadByte方法将reader的索引值i–，还原读取一个字节之前的状态

func (r *Reader) ReadByte() (byte, error) {
	r.prevRune = -1
	if r.i >= int64(len(r.s)) {
		return 0, io.EOF
	}
	b := r.s[r.i]
	r.i++
	return b, nil
}
func (r *Reader) UnreadByte() error {
	if r.i <= 0 {
		return errors.New("strings.Reader.UnreadByte: at beginning of string")
	}
	r.prevRune = -1
	r.i--
	return nil
}

ReadRune方法从s中读取i指向的字符
UnreadRune方法完成对ReadRune方法的重置

func (r *Reader) ReadRune() (ch rune, size int, err error) {
	if r.i >= int64(len(r.s)) {
		r.prevRune = -1
		return 0, 0, io.EOF
	}
	r.prevRune = int(r.i)
	if c := r.s[r.i]; c < utf8.RuneSelf {
		r.i++
		return rune(c), 1, nil
	}
	ch, size = utf8.DecodeRuneInString(r.s[r.i:])
	r.i += int64(size)
	return
}
func (r *Reader) UnreadRune() error {
	if r.i <= 0 {
		return errors.New("strings.Reader.UnreadRune: at beginning of string")
	}
	if r.prevRune < 0 {
		return errors.New("strings.Reader.UnreadRune: previous operation was not ReadRune")
	}
	r.i = int64(r.prevRune)
	r.prevRune = -1
	return nil
}

Seek方法根据whence设定下一个读取的字符的索引值

func (r *Reader) Seek(offset int64, whence int) (int64, error) {
	r.prevRune = -1
	var abs int64
	switch whence {
	case io.SeekStart:
		abs = offset
	case io.SeekCurrent:
		abs = r.i + offset
	case io.SeekEnd:
		abs = int64(len(r.s)) + offset
	default:
		return 0, errors.New("strings.Reader.Seek: invalid whence")
	}
	if abs < 0 {
		return 0, errors.New("strings.Reader.Seek: negative position")
	}
	r.i = abs
	return abs, nil
}

WriterTo方法将w中的数据写入到reader中

func (r *Reader) WriteTo(w io.Writer) (n int64, err error) {
	r.prevRune = -1
	if r.i >= int64(len(r.s)) {
		return 0, nil
	}
	s := r.s[r.i:]
	m, err := io.WriteString(w, s)
	if m > len(s) {
		panic("strings.Reader.WriteTo: invalid WriteString count")
	}
	r.i += int64(m)
	n = int64(m)
	if m != len(s) && err == nil {
		err = io.ErrShortWrite
	}
	return
}

Reset方法完成Reader的重置操作

1	func (r Reader) Reset(s string) { r = Reader{s, 0, -1} }

go源码解读-errors包

发表于 2020-05-09 | 分类于 go ，源码解读

errors

go语言的errors包比较简单，实际上就是基于内建函数的实现
内建接口error，该接口只含有一个Error方法

1
2
3

type error interface {
	Error() string
}

实际上可以根据需要实现error接口来封装自己的error

// MyError is an error implementation that includes a time and message.
type MyError struct {
	When time.Time
	What string
}
func (e MyError) Error() string {
	return fmt.Sprintf("%v: %v", e.When, e.What)
}

errors包中的实现也只是对一个内部结构体errorString的简单封装
包含初始化函数和Error方法

// New returns an error that formats as the given text.
func New(text string) error {
	return &errorString{text}
}
// errorString is a trivial implementation of error.
type errorString struct {
	s string
}
func (e *errorString) Error() string {
	return e.s
}