此文章为学习 《Go语言标准库》的总结性文章
对于程序员而言,标准库与语言本身同样重要,它好比一个百宝箱,能为各种常见的任务提供完美的解决方案。
输入输出 (Input/Output)
一般的计算机程序都是输入(input)内容 -> 算法处理 -> 输出 (Output)
Go语言中,为了方便开发者使用,将IO操作封装在了如下几个包中:
- io 为 IO 原语(I/O primitives)提供基本的接口
- io/ioutil 封装了一些实用的 I/O 函数
- fmt 实现格式化 I/O,类似 C 语言中的 printf 和 scanf
- bufio 实现带缓冲I/O
IO 库
ReaderFrom 和 WriterTo 接口
用于一次性从某个地方读或写到某个地方去,ioutil.ReadFile其实底层用的也是ReaderFrom方法实现
Seeker 接口
Seek 方法是用于设置偏移量的,这样可以从某个特定位置开始操作数据流。听起来和 ReaderAt/WriteAt 接口有些类似,不过 Seeker 接口更灵活,可以更好的控制读写数据流的位置。
|
|
whence 的值,在 io 包中定义了相应的常量,应该使用这些常量
|
|
而原先 os 包中的常量已经被标注为Deprecated
|
|
SectionReader 类型
SectionReader 是一个 struct(没有任何导出的字段),实现了 Read, Seek 和 ReadAt,同时,内嵌了 ReaderAt 接口。结构定义如下:
|
|
从名称我们可以猜到,该类型读取数据流中部分数据。
|
|
LimitedReader 类型
|
|
从 R 读取数据但将返回的数据总量限制为 N 字节。每调用一次 Read 都将更新 N 来反应新的剩余数量,每读取m字节,n就等于n-m。
也就是说,你可以读取很多次,但是最多总共只能返回 N 字节数据。
|
|
可见,通过该类型可以达到 只允许读取一定长度数据 的目的。
在 io 包中,LimitReader 函数的实现其实就是调用 LimitedReader:
|
|
PipeReader 和 PipeWrite 类型
PipeReader(一个没有任何导出字段[字段全小写]的 struct)是管道的读取端。从管道中读取数据。该方法会堵塞,直到管道写入端开始写入数据或写入端被关闭。如果写入端关闭时带有 error(即调用 CloseWithError 关闭),该Read返回的 err 就是写入端传递的error;否则 err 为 EOF。
PipeWriter(一个没有任何导出字段的 struct)是管道的写入端。写数据到管道中。该方法会堵塞,直到管道读取端读完所有数据或读取端被关闭。如果读取端关闭时带有 error(即调用 CloseWithError 关闭),该Write返回的 err 就是读取端传递的error;否则 err 为 ErrClosedPipe。
|
|
有点类似于无缓冲channel
它将 io.Reader 连接到 io.Writer。一端的读取匹配另一端的写入,直接在这两端之间复制数据;它没有内部缓存。它对于并行调用 Read 和 Write 以及其它函数或 Close 来说都是安全的(一方调用close,另一方就无法再写入或读取)。
一旦等待的 I/O 结束,Close 就会完成。并行调用 Read 或并行调用 Write 也同样安全:同种类的调用将按顺序进行控制。
正因为是同步的,因此不能在一个 goroutine 中进行读和写(会死锁,就像channel一样)。
另外,对于管道的 close 方法(非 CloseWithError 时),err 会被置为 EOF。
ReadAtLeast 和 ReadFull 函数
ReadAtLeast 函数的签名:
|
|
ReadAtLeast 将 r 读取到 buf 中,直到读了最少 min 个字节为止。
它返回复制的字节数,如果读取的字节较少,还会返回一个错误。若没有读取到字节,错误就只是 EOF。如果一个 EOF 发生在读取了少于 min 个字节之后,ReadAtLeast 就会返回 ErrUnexpectedEOF。若 min 大于 buf 的长度,ReadAtLeast 就会返回 ErrShortBuffer。对于返回值,当且仅当 err == nil 时,才有 n >= min。
ReadFull 函数的签名:
|
|
ReadFull 精确地从 r 中将 len(buf) 个字节读取到 buf 中。
它返回复制的字节数,如果读取的字节较少,还会返回一个错误。若没有读取到字节,错误就只是 EOF。如果一个 EOF 发生在读取了一些但不是所有的字节后,ReadFull 就会返回 ErrUnexpectedEOF。对于返回值,当且仅当 err == nil 时,才有 n == len(buf)。
注意该函数和 ReadAtLeast 的区别:ReadFull 将 buf 读满;而 ReadAtLeast 是最少读取 min 个字节。
MultiReader 和 MultiWriter 函数
这两个函数的定义分别是:
|
|
它们接收多个 Reader 或 Writer,返回一个 Reader 或 Writer。我们可以猜想到这两个函数就是操作多个 Reader 或 Writer 就像操作一个。
MultiReader 的使用:
|
|
输出:
|
|
代码中首先构造了一个 io.Reader 的 slice,由 strings.Reader 和 bytes.Buffer 两个实例组成,然后通过 MultiReader 得到新的 Reader,循环读取新 Reader 中的内容。从输出结果可以看到,第一次调用 Reader 的 Read 方法获取到的是 slice 中第一个元素的内容(第一个元素读完后才会读第二个元素)……也就是说,MultiReader 只是逻辑上将多个 Reader 组合起来,并不能通过调用一次 Read 方法获取所有 Reader 的内容,而是顺序读取Reader切片中的所有Reader。在所有的 Reader 内容都被读完后,Reader 会返回 EOF。
MultiWriter 的使用:
|
|
这段程序执行后先生成 tmp.txt 文件,然后同时在文件和屏幕中都输出:Go语言中文网。这和 Unix 中的 tee 命令类似。
MultiWriter 可以通过调用一次Write同时向多个I/O写入内容,因为写入可以通过句柄直接从尾部写入;MultiReader 只能顺序读取切片中的每一个元素数据,只有上一个元素读取完后才能读取下一个元素。
TeeReader函数
函数签名如下:
|
|
TeeReader 返回一个 Reader,它将从 r 中读到的数据写入 w 中。所有经由它处理的从 r 的读取都匹配于对应的对 w 的写入。它没有内部缓存,当读取 r 中的内容时,会无缓冲的将读取内容写入到 Writer 中。任何在写入时遇到的错误都将作为读取错误返回。
这种功能的实现其实挺简单,无非是在 Read 完后执行 Write。
|
|
可以使用TeeReader来计算文件hash值,通过 TeeReader 和 io.ReadAll() 读取文件后再 sha256 占用的内存来看, TeeReader 占用的内存更少
|
|
还可以用此方法实现简易的下载进度条,只需要定义一个结构体struct,并让它实现io.Writer,然后在自己的Write()方法中实现每次读多少字节就增加多少字节数即可。
|
|
ioutil
ioutil这个包在go1.16就被废弃了,它的大部分方法都是直接去调用io或os包,比如 ioutil.ReadAll() 点开源码就会发现它的实现逻辑就是直接调用 io.ReadAll()
|
|
NopCloser 函数
有时候我们需要传递一个 io.ReadCloser 的实例,而我们现在只有一个 io.Reader 的实例,比如:strings.Reader ,这个时候 NopCloser 就派上用场了。它包装一个io.Reader,返回一个 io.ReadCloser ,而相应的 Close 方法啥也不做,只是返回 nil。
比如,在标准库 net/http 包中的 NewRequest,接收一个 io.Reader 的 body,而实际上,Request 的 Body 的类型是 io.ReadCloser,因此,代码内部进行了判断,如果传递的 io.Reader 也实现了 io.ReadCloser 接口,则转换,否则通过ioutil.NopCloser 包装转换一下。
ReadFile 和 WriteFile 函数
ReadFile 的实现和ReadAll 类似,不过,ReadFile 会先判断文件的大小,给 bytes.Buffer 一个预定义容量,避免额外分配内存。
按源码中注释的说法是 FileInfo 不会很精确地得到文件大小。
WriteFile 将data写入filename文件中,当文件不存在时会根据perm指定的权限进行创建一个,文件存在时会先清空文件内容。
Discard 变量
Discard 是一个 io.Writer,对它进行的任何 Write 调用都将无条件成功。
是一个用于丢弃数据的地方。同时,为了优化 io.Copy 到 Discard,避免不必要的工作,实现了 io.ReaderFrom 接口(在io.Copy源码中会尝试将dst转换为io.ReaderForm)。
fmt
对数值而言,宽度为该数值占用区域的最小宽度,不足的话会用空格进行填充;精度为小数点之后的位数。对字符串而言,精度为输出的最大字符数,如果必要的话会直接截断。
Scan、Scanf、Scanln的区别
Scan和Scanln基本相同,唯一区别是当读取多个变量当时候,遇到换行符Scanln会直接结束,未读到输入值的变量为零值;Scan会等待,将换行符视为一个空格,等待下一个输入,直到输入的值满足参数的个数后再遇到换行符后才会结束。
Scanf适用于完全了解输入格式的场景,可以直接把不需要的部分过滤掉。但是如果输入时格式和设置时不同就无法扫描到。
|
|
Println和Print拼接字符串
Println输出时会将两个不定参数之间加上一个空格,如 fmt.Println("sa", "111")
输出的结果为 sa 111
,而Print输出时不会加空格,即它的结果为 sa111
。
因此Print有拼接字符串的作用,而且参数有int类型时都不需要通过 strconv.Itoa()
转换。
Sprint/Fprint同理。
Stringer 接口
Stringer接口的定义如下:
|
|
根据 Go 语言中实现接口的定义,一个类型只要有 String() string
方法,我们就说它实现了 Stringer 接口。如果格式化输出某种类型的值,只要它实现了 String() 方法,那么就会调用 String() 方法进行处理。因此为了避免无限递归循环,在自己实现的String()方法中只要涉及到fmt包输出的代码,一定不要直接输出方法接收者,因为当打印方法接收者时,它又会去调用String(),然后在String()中又出现了打印,就这样子无限递归下去直到爆栈。
|
|
Formatter 接口
Formatter 接口的定义如下:
|
|
官方文档中关于该接口方法的说明:
Formatter 接口由带有定制的格式化器的值所实现。 Format 的实现可调用 Sprintf、Printf 或 Fprintf(f) 等函数来生成其输出。
也就是说,通过实现 Formatter 接口可以做到自定义输出格式(自定义占位符)。
接着上面的例子,我们为 people增加一个方法:
|
|
这样,people便实现了Formatter接口。这时再运行:
|
|
输出为:
|
|
这里需要解释以下几点:
- fmt.State 是一个接口。由于 Format 方法是被 fmt 包调用的,它内部自己会实例化好一个 fmt.State 接口的实例,我们不需要关心该接口;
- 可以实现自定义占位符,
同时 fmt 包中和类型相对应的预定义占位符都会无效。而且其他占位符都会走else路线,去掉else就会发现只要不符合if条件就都会不再输出内容。
- 实现了 Formatter 接口后,
相应的 Stringer 接口就不再起作用了。
但实现了 Formatter 接口的类型应该实现 Stringer 接口,这样方便在 Format 方法中调用 String() 方法。 - Format 方法的第二个参数是占位符中%后的字母(有精度和宽度会被忽略,只保留字母);
一般地,我们不需要实现 Formatter 接口。通常可以将其作为一个中间件使用,比如我们有一个结构体,需要序列化后打印,如果不需要打印就不需要进行序列化,这种情况就可以实现Formatter接口,在方法内部进行序列化,这样子就可以实现只在打印时才进行序列化的需求。
State接口相关说明:
|
|
GoStringer 接口
该接口定义了类型的Go语法格式。专门用于打印(Printf)格式化占位符为 %#v 时的值 (%+v %v 都不适配)。
|
|
这个时候再执行
|
|
输出:
|
|
一般的,我们不需要实现该接口。
bufio
bufio 包实现了缓存IO。它包装了 io.Reader 和 io.Writer 对象,创建了另外的Reader和Writer对象,它们也实现了 io.Reader 和 io.Writer 接口,不过它们是有缓存的。
Reader 类型和方法
bufio.Reader 结构包装了一个 io.Reader 对象,提供缓存功能,同时实现了 io.Reader 接口。
Reader 结构没有任何导出的字段,结构定义如下:
|
|
bufio 包提供了两个实例化 bufio.Reader 对象的函数:NewReader 和 NewReaderSize。其中,NewReader 函数是调用 NewReaderSize 函数实现的:
|
|
ReadSlice、ReadBytes、ReadString 和 ReadLine 方法
ReadSlice方法签名如下:
|
|
ReadSlice 从输入中读取内容,直到遇到第一个界定符(delim)为止,返回一个指向缓存中字节的 slice 指针,在下次调用读操作(read)时,slice内容会发生变化。举例说明:
|
|
输出:
|
|
从结果可以看出,第一次ReadSlice的结果(line),在第二次调用读操作后,内容发生了变化。也就是说,ReadSlice 返回的 []byte 是指向 Reader 中的 buffer ,而不是 copy 一份返回。
正因为ReadSlice 返回的数据会被下次的 I/O 操作重写,因此许多的客户端会选择使用 ReadBytes 或者 ReadString 来代替。这两个方法就不会出现第二次读取会覆盖第一次的结果。
注意,这里的界定符可以是任意的字符,可以将上面代码中的’\n’改为’m’试试。同时,返回的结果是包含界定符本身的,上例中,输出结果有一空行就是’\n’本身(line携带一个’\n’,printf又追加了一个’\n’)。
如果 ReadSlice 在找到界定符之前遇到了 error ,它就会返回缓存中所读到的数据和错误本身(经常是 io.EOF)。
如果在找到界定符之前缓存已经满了,ReadSlice 会返回 bufio.ErrBufferFull 错误。
当且仅当返回的结果(line)没有以界定符结束的时候,ReadSlice 返回err != nil,也就是说,如果ReadSlice 返回的结果 line 不是以界定符 delim 结尾,那么返回的 err 就一定 不等于 nil(可能是bufio.ErrBufferFull或io.EOF)。
上面关于错误的逻辑 ReadBytes ReadSting也是同理。
通过源码可以发现,ReadSlice() 中返回的是b.buf切片的某一段,即返回的 []byte 和 Reader 中的 buffer共用同一个底层数组;而ReadBytes() 是 copy 一份返回,它和buf已经没关系了;ReadString()则是通过string强转了b.buf,它会在内存开辟新空间。也正因为如此,通常我们会使用 ReadBytes 或 ReadString,它们不会影响到buf的内容。
ReadLine
ReadLine 是一个底层的原始行读取命令。效果和 ReadBytes(’\n’) 或者 ReadString(’\n’) 相当,但是它会去掉换行符,而这两个方法会将换行符保留。
ReadLine 尝试返回单独的行,但不包括行尾的换行符。如果一行大于缓存,isPrefix 会被设置为 true,同时返回该行已经读取的内容(等于缓存大小的部分)。该行剩余的部分就会在下次调用的时候返回。当下次调用返回该行剩余部分时,isPrefix 将会是 false 。由于它底层调用的是 ReadSlice(),因此返回的 line 只是 buffer 的引用,每次读取line的值都会发生改变。
注意,返回值中,要么 line 不是 nil,要么 err 非 nil,两者不会同时非 nil。
ReadLine 返回的文本不会包含行结尾("\r\n"或者"\n")。如果输入中没有行尾标识符,它也不会返回任何指示或者错误。
从上面的讲解中,我们知道,读取一行,通常会选择 ReadBytes 或 ReadString。不过,正常人的思维,应该用 ReadLine,只是不明白为啥 ReadLine 的实现不是通过 ReadBytes,然后清除掉行尾的\n(或\r\n),它现在的实现,用不好会出现意想不到的问题 (底层使用ReadSlice导致buf改变时,获取的值也会发生改变),比如丢数据。建议可以这么实现读取一行:
|
|
这样既读取了一行,也去掉了行尾结束符。
Peek 方法
该方法只是“窥探”一下 Reader 中没有读取的 n 个字节。好比栈数据结构中的取栈顶元素,但不出栈。意思就是它会读取Reader中尚未被读取的n个字节但并不会导致偏移量发生移动。
|
|
观察源码可以发现,它返回的 []byte 只是 buffer 中的引用,在下次IO操作后结果会发生改变,可见该方法对多 goroutine 是不安全的,也就是在多并发环境下,不能依赖其结果。
Peek 方法如果返回的 []byte 长度小于 n,这时返回的
err != nil ,用于解释为啥会小于 n。如果 Peek 的 n 大于 reader 设定的 buffer 长度,err 会是 ErrBufferFull。
Scanner 类型
对于简单的读取一行,在 Reader 类型中,感觉没有让人特别满意的方法。于是,Go1.1增加了一个类型:Scanner。
|
|
SplitFunc 类型
|
|
SplitFunc 定义了 用于对输入进行分词的 split 函数的签名。参数 data 是还未处理的数据,atEOF 标识 Reader 是否还有更多数据,有则为true(是否到了EOF)。返回值 advance 表示从输入中读取的字节数,token 表示下一个结果数据,err 则代表可能的错误。
|
|
如果 data 中没有一个完整的 token,例如,在扫描行(scanning lines)时没有换行符,SplitFunc 会返回(0,nil,nil)通知 Scanner 读取更多数据到 slice 中,然后在这个更大的 slice 中 同样的读取点处,从输入中重试读取。
如果 err != nil
,扫描停止,同时该错误会返回。
如果参数 data 为空的 slice,除非 atEOF 为 true,否则该函数永远不会被调用。如果 atEOF 为 true,这时 data 可以非空,这时的数据是没有处理的。
在 bufio 包中预定义了一些 split 函数,也就是说,在 Scanner 结构中的 split 字段,可以通过这些预定义的 split 进行赋值,同时 Scanner 类型的 Split 方法也可以接收这些预定义函数作为参数。可以说,这些预定义 split 函数都是 SplitFunc 类型的实例。这些函数包括:ScanBytes、ScanRunes、ScanWords 和 ScanLines。
- ScanBytes 返回单个字节作为一个 token。
- ScanRunes 返回单个 UTF-8 编码的 rune 作为一个 token。返回的 rune 序列(token)和 range string类型 返回的序列是等价的,也就是说,对于无效的 UTF-8 编码会解释为 U+FFFD = “\xef\xbf\xbd”。
- ScanWords 返回通过“空格”分词的单词。如:study golang,调用会返回study。注意,这里的“空格”是
unicode.IsSpace()
,即包括:’\t’, ‘\n’, ‘\v’, ‘\f’, ‘\r’, ’ ‘, U+0085 (NEL), U+00A0 (NBSP)。 - ScanLines 返回一行文本,不包括行尾的换行符。这里的换行包括了Windows下的"\r\n"和Unix下的"\n"。
(默认实例化Scanner用的就是这个策略)
一般地,我们不会单独使用这些函数,而是提供给 Scanner 实例使用。可以使用上面介绍的预定义 SplitFunc 实例赋值,也可以自定义 SplitFunc 实例。(要给 split 字段赋值,必须调用 Scanner 的 Split 方法)
Scan 方法
该方法好比 iterator 中的 Next 方法,它用于让 Scanner 获取下一个 token,以便 Bytes 和 Text 方法可用。当扫描停止时,它返回false,这时候,要么是到了输入的末尾要么是遇到了一个错误。注意,当 Scan 返回 false 时,通过 Err 方法可以获取第一个遇到的错误 (但如果错误是 io.EOF,Err 方法会返回 nil)。
用法
我们经常会有这样的需求:读取文件中的数据,一次读取一行(或者其他读取策略)。在学习了 Reader 类型,我们可以使用它的 ReadBytes 或 ReadString来实现,甚至使用 ReadLine 来实现。但是Scanner比这些方法更简单好用。
|
|
Writer 类型和方法
相比 bufio.Reader, bufio.Writer 结构定义简单很多。
|
|
如果在写数据到 Writer 的时候出现了一个错误,就不会再允许有数据被写进来了,并且所有随后的写操作都会返回该错误。
和 Reader 类型一样,bufio 包提供了两个实例化 bufio.Writer 对象的函数:NewWriter 和 NewWriterSize。其中,NewWriter 函数是调用 NewWriterSize 函数实现的。
方法
Available 方法获取缓存中还未使用的字节数(缓存大小 - 字段 n 的值)
Buffered 方法获取写入当前缓存中的字节数(字段 n 的值)
Flush 方法将缓存中的所有数据写入底层的 io.Writer 对象中。使用 bufio.Writer 时,在所有的 Write 操作完成之后,应该调用 Flush 方法使得缓存都写入 io.Writer 对象中。
Writer 类型其他方法是一些实际的写方法,这些写方法在缓存满时都会调用Flush() 方法,但是defer buf.Flush() 不能省略,因为需要在业务函数结束时将buffer中残留且未存满的缓存写入io.Writer中。
另外,这些写方法源码开始处,都有这样的代码:
|
|
也就是说,只要是在写的过程中遇到了错误,再次调用任何写操作都会直接返回该错误。
数据结构与算法
sort 排序算法
该包实现了四种基本排序算法:插入排序、归并排序、堆排序和快速排序。 但是这四种排序方法是不公开的,它们只被用于 sort 包内部使用。所以在对数据集合排序时不必考虑应当选择哪一种排序方法,只要实现了 sort.Interface 定义的三个方法:获取数据集合长度的 Len() 方法、比较两个元素大小的 Less() 方法和交换两个元素位置的 Swap() 方法,就可以顺利对数据集合进行排序。
sort 包会根据实际数据自动选择高效的排序算法。 除此之外,为了方便对常用数据类型的操作,sort 包提供了对[]int 切片、[]float64 切片和[]string 切片完整支持
|
|
此外,如果临时想进行降序操作时,sort 包提供了 Reverse() 方法,可以允许将数据按 Less() 定义的排序方式逆序排序,而不必修改 Less() 代码。方法定义如下:
|
|
整个 Reverse() 的内部实现比较有趣:
|
|
如果想要查询数组中符合条件的第一个元素时,可以使用Search() 方法:
|
|
该方法会使用“二分查找”算法来找出能使 f(x) 在(0<=x<n) 索引返回 ture 的最小值 i。 前提条件 : f(x)(0<=x<i) 均返回 false, f(x)(i<=x<n) 均返回 ture。 如果不存在 i 可以使 f(i) 返回 ture, 则返回 n。
它会返回符合条件的第一个元素的索引。大于等于时会找到和条件相等的元素,即等于91的那个元素,没有比这个元素排在更前面了;大于时则会找到升序数组中第一个大于91这个值的元素,返回其索引。
当排序为升序,则Search的条件必须为 大于,这是因为升序由小到大,如果是小于的话,那么第一个就会小于设置的值,第一个都不小于,数组就没有小于的了(因为升序排序第一个值最小)。当数组是降序时,Search就必须为 小于
[]interface 排序与查找
只要实现了 sort.Interface
接口,即可通过 sort 包内的函数完成排序,但是这种用法对于其它数据类型的 slice 不友好,可能我们需要为大量的 struct 定义一个单独的 []struct 类型,再为其实现 sort.Interface
接口。
|
|
sort.Slice
|
|
sort.SliceStable
该函数完成 []interface 的稳定排序,其性能会比sort.Slice略低,通常情况下用Slice() 即可
|
|
sort.SliceIsSorted
该函数判断 []interface 是否为有序
|
|
判断有序的前提是已经按对应逻辑排好序了,如排序方式为降序,那么上面的返回值则是false,需要将大于变为小于符号,因为SliceIsSorted中是判断该slice是否是升序排序。
sort.Search
该函数判断 []interface 是否存在指定元素 (或返回最接近的元素),其只能用于已经排好序的数组切片。
|
|
container 容器数据类型:heap、list 和 ring
该包实现了三个复杂的数据结构:堆、链表和环,使用这个包就意味着你使用这三个数据结构的时候不需要再费心从头开始写算法了。
堆
这里的堆使用的数据结构是最小二叉树,即根节点比左边子树和右边子树的所有值都小。
|
|
可以看出,这个堆结构继承自 sort.Interface。需要实现五个方法。
|
|
使用堆时就需要使用 container/heap
包
|
|
具体说下内部实现,是使用最小堆,索引排序从根节点开始,然后左子树,右子树的顺序方式。索引布局如下:
1 2 3 4
0 1 2 3 4 5 6 7 8 9 10 11
假设 (heap[1]== 小明 ) 它的左子树 (heap[3]== 小黑 ) 和右子树 (heap[4]== 大黄 ) 且小明 > 小黑 > 大黄 ;
堆内部实现了 down 和 up 函数 : down 函数用于将索引 i 处存储的值 ( 设 i=1, 即小明 ) 与它的左子树 ( 小黑 ) 和右子树 ( 大黄 ) 相比 , 将三者最小的值 (小明大于小黄) 大黄与小明的位置交换,交换后小明继续与交换后的子树 (heap[9]和 heap[10]) 相比,重复以上步骤,直到小明位置不再发生改变。
up 函数用于将索引 i 处的值 ( 设 i=3, 即小黑 ) 与他的父节点 ( 小明 ) 比较,将两者较小的值放到父节点上,本例中即交换小黑和小明的位置,之后小黑继续与其父节点比较,重复以上步骤,直到小黑位置不再发生改变。
从堆中pop时,每次pop的都是堆顶元素,即最小或最大的那个元素,假设 heap[11]== 阿花,当从堆中 Pop 一个元素的时候,会先把堆顶元素和最后一个节点的值 ( 阿花 ) 交换,然后弹出最后一个元素 (交换后的堆顶元素),这样可以保证堆的性质不被破坏。然后对堆顶的阿花调用 down,将新的堆顶元素下沉,直到满足最小堆的性质。
当往堆中 Push 一个元素的时候,这个元素插入到最后一个节点,本例中为 heap[12],即作为 heap[5]的右子树,然后调用 up 函数向上比较。
链表
链表就是一个有 prev 和 next 指针的数组了。
|
|
基本使用是先创建 list,然后往 list 中插入值,list 就内部创建一个 Element,并内部设置好 Element 的 next,prev 等。
|
|
list 对应的方法有:
|
|
环 (循环链表)
环的结构有点特殊,环的尾部就是头部,所以每个元素实际上就可以代表自身的这个环。 它不需要像 list 一样保持 list 和 element 两个结构,只需要保持一个结构就行。
|
|
我们初始化环的时候,需要定义好环的大小,然后对环的每个元素进行赋值。环还提供一个 Do 方法,能遍历一遍环,对每个元素执行一个 function。
|
|
ring 提供的方法有:
|
|
进程、线程和goroutine
创建进程
os
包及其子包 os/exec
提供了创建进程的方法。
一般应该优先使用 os/exec
包。因为 os/exec
包依赖 os
包中关键创建进程的 API
在 Unix 中,创建一个进程,通过系统调用 fork
实现(及其一些变种,如 vfork、clone)。在 Go 语言中,Linux 下创建进程使用的系统调用是 clone
。
很多时候,系统调用 fork
、execve
、wait
和 exit
会在一起出现
- fork:允许某一进程(父进程)创建一个新进程(子进程)。具体做法是,新的子进程几近于对父进程的翻版:子进程获得父进程的栈、数据段、堆和执行文本段的拷贝。可将此视为把父进程一分为二。
- exit(status):终止一进程,将进程占用的所有资源(内存、文件描述符等)归还内核,交其进行再次分配。**参数
status
为一整型变量,表示进程的退出状态。**父进程可使用系统调用wait()
来获取该状态。 - wait(&status) 目的有二:其一,如果子进程尚未调用
exit()
终止,那么wait
会挂起父进程(阻塞)直至子进程终止,这样可以确保父进程在子进程完成后再继续执行后续的操作;其二,子进程的终止状态通过wait
的status
参数返回。status
参数是一个整数指针,通过传入wait
函数的地址,父进程可以在子进程终止后获取到子进程的终止状态。 - execve(pathname, argv, envp) 加载一个新程序(路径名为 pathname,参数列表为 argv,环境变量列表为 envp)到当前进程的内存。这将丢弃现存的程序文本段,并为新程序重新创建栈、数据段以及堆。通常将这一动作称为执行一个新程序(舍弃旧程序),它是实现进程间切换和程序替换的重要系统调用函数。
在 Go 语言中,没有直接提供 fork
系统调用的封装,而是将 fork
和 execve
合二为一,提供了 syscall.ForkExec
。如果想只调用 fork
,得自己通过 syscall.Syscall(syscall.SYS_FORK, 0, 0, 0)
实现。
Process 及其相关方法
os.Process
存储了通过 StartProcess
创建的进程的相关信息。
一般通过 StartProcess
创建 Process
的实例,函数声明如下:
func StartProcess(name string, argv []string, attr *ProcAttr) (*Process, error)
它使用提供的程序名、命令行参数、属性开始一个新进程。StartProcess
是一个低级别的接口。os/exec
包提供了高级别的接口,一般应该尽量使用 os/exec
包。如果出错,错误的类型会是 *PathError
。
其中的参数 attr
,类型是 ProcAttr
的指针,用于为 StartProcess
创建新进程提供一些属性。定义如下:
|
|
FindProcess
可以通过 pid
查找一个运行中的进程。该函数返回的 Process
对象可以用于获取关于底层操作系统进程的信息。在 Unix 系统中,此函数总是成功,即使 pid
对应的进程不存在。
func FindProcess(pid int) (*Process, error)
Process
提供了四个方法:Kill
、Signal
、Wait
和 Release
。其中 Kill
和 Signal
跟信号相关,而 Kill
实际上就是调用 Signal
,发送了 SIGKILL
信号,强制进程退出
Release
方法用于释放 Process
对象相关的资源,以便将来可以被再使用(释放资源给其他程序使用)。该方法只有在确定没有调用 Wait
时才需要调用。Unix 中,该方法的内部实现只是将 Process
的 pid
置为 -1。
func (p *Process) Wait() (*ProcessState, error)
在多进程应用程序的设计中,父进程需要知道某个子进程何时改变了状态 —— 子进程终止或因收到信号而停止。Wait
方法就是一种用于监控子进程的技术。
Wait
方法阻塞父进程直到子进程退出,然后返回一个 ProcessState
描述子进程的状态和可能的错误。Wait
方法会释放绑定到 Process
的所有资源。在大多数操作系统中,Process
必须是当前进程的子进程,否则会返回错误。
|
|
ProcessState
保存了 Wait
函数报告的某个进程的信息。status
记录了状态原因,通过 syscal.WaitStatus
类型定义的方法可以判断:
- Exited():是否正常退出,如调用
os.Exit
; - Signaled():是否收到未处理信号而终止;
- CoreDump():是否收到未处理信号而终止,同时生成 coredump 文件,如 SIGABRT;
- Stopped():是否因信号而停止(SIGSTOP);
- Continued():是否因收到信号 SIGCONT 而恢复;
syscal.WaitStatus
还提供了其他一些方法,比如获取退出状态、信号、停止信号和中断(Trap)原因。
因为 Linux 下 Wait
的内部实现使用的是 wait4
系统调用,因此,ProcessState
中包含了 rusage
,用于统计进程的各类资源信息。一般情况下,syscall.Rusage
中定义的信息都用不到,如果实际中需要使用,可以查阅 Linux 系统调用 getrusage
获得相关说明 (getrusage(2)
)。
ProcessState
结构体内部字段都是私有的,我们可以通过它提供的方法来获得一些基本信息,比如:进程是否退出、Pid、进程是否是正常退出、进程 CPU 时间、用户时间等等。
运行外部命令
通过 os
包可以做到运行外部命令 (os.StartProcess) 。不过,Go 标准库为我们封装了更好用的包: os/exec
,运行外部命令,应该优先使用它,它包装了 os.StartProcess
函数以便更容易的重定向标准输入和输出,使用管道连接 I/O,以及作其它的一些调整。
查找可执行程序
exec.LookPath
函数在 PATH
指定的多个目录中搜索可执行程序。该函数返回完整路径或相对于当前路径的一个相对路径。
func LookPath(file string) (string, error)
如果在 $PATH
中没有找到可执行文件,则返回 exec.ErrNotFound
。
Cmd 及其相关方法
Cmd
结构代表一个正在准备或者在执行中的外部命令,调用了 Run
、Output
或 CombinedOutput
后,Cmd
实例不能被重用(已经执行无法重用)。
|
|
Command
一般应该通过 exec.Command
函数产生 Cmd
实例:
func Command(name string, arg ...string) *Cmd
该函数返回一个 *Cmd
,用于使用给出的参数执行 name
指定的程序。返回的 *Cmd
只设定了 Path
和 Args
两个字段。
**如果 name
不含路径分隔符,将使用 LookPath
获取完整路径;否则直接使用 name
。**参数 arg
不应包含命令名。
得到 *Cmd
实例后,接下来一般有两种写法:
- 调用
Start()
,接着调用Wait()
,然后会阻塞父进程直到命令执行完成 (这种方式主要用在需要在start和wait之间需要处理其他逻辑的情况); - 调用
Run()
,它内部会先调用Start()
,接着调用Wait()
;
Start
func (c *Cmd) Start() error
开始执行 c
包含的命令,但并不会等待该命令完成后再返回。Start() 内部调用 os.StartProcess
,执行 forkExec
。
Wait
func (c *Cmd) Wait() error
Wait
会阻塞当前进程直到该命令执行完成,该命令必须是先通过 Start
执行。
如果命令成功执行,stdin、stdout、stderr 数据传递没有问题,并且返回状态码为 0,方法的返回值为 nil;如果命令没有执行或者执行失败,会返回 *ExitError
类型的错误;否则返回的 error 可能是表示 I/O 问题。
如果 c.Stdin
不是 *os.File
类型,Wait
会等待,直到数据从 c.Stdin
拷贝到进程的标准输入中。
Wait
方法会返回命令的退出状态码并在命令执行完后释放相关的资源。
Output
除了 Run()
是 Start
+Wait
的简便写法,Output()
更是 Run()
的简便写法,外加获取外部命令的输出。
func (c *Cmd) Output() ([]byte, error)
它要求 c.Stdout
必须是 nil
(内部第一步就是c.Stdout != nil返回错误),内部会将 bytes.Buffer
赋值给 c.Stdout
,在 Run()
成功返回后,会将 Buffer
的结果返回(stdout.Bytes()
)。
CombinedOutput
Output()
只返回 Stdout
的结果,而 CombinedOutput
组合了 Stdout
和 Stderr
的输出,即 Stdout
和 Stderr
都赋值为同一个 bytes.Buffer
。
StdoutPipe、StderrPipe 和 StdinPipe
除了上面介绍的 Output
和 CombinedOutput
直接获取命令输出结果外,还可以通过 StdoutPipe
返回的 io.ReadCloser
来获取输出;相应的 StderrPipe
得到错误信息;而 StdinPipe
则可以往命令写入数据。
func (c *Cmd) StdoutPipe() (io.ReadCloser, error)
StdoutPipe
方法返回一个在命令 Start
执行后与命令标准输出关联的管道。Wait
方法会在命令结束后会自动关闭这个管道,所以一般不需要手动关闭该管道。但是如果在从管道读取完全部数据之前调用 Wait
出错了,则必须手动关闭。因此建议获取后直接defer close,即使已经关闭了再次关闭也没事,只是会因为已经关闭返回失败而已。
func (c *Cmd) StderrPipe() (io.ReadCloser, error)
逻辑和 StdoutPipe
类似,只是关联的是标准错误输出。而 StdinPipe
关联的是标准输入,Wait也会自动关闭这个管道,必要时调用者可以直接通过调用 Close
方法来强行关闭管道。例如,有时候标准输入必须要关闭后,命令执行才能完成,此时调用者需要显式地关闭管道。
因为这些管道虽然在Start之前定义,但是结果要在 Start
之后 Wait
之前才能获取(Wait会关闭管道),所以,要使用这些方法,一般只能使用 Start
+Wait
组合,使用 Run
就必须需要为管道开一个新的goroutine。
|
|
进程终止
os.Exit()
函数会终止当前进程,对应的系统调用不是 _exit
,而是 exit_group
。
func Exit(code int)
Exit
让当前进程以给出的状态码 code
退出。一般来说,状态码 0 表示成功,非 0 表示出错。Exit 会让进程立刻终止,defer 函数都不会被执行。因此如果需要执行defer函数最好使用return来结束函数。
进程属性和控制
每个进程都有一些属性,os
包提供了一些函数可以获取进程属性。
每个进程都会有一个进程 ID,可以通过 os.Getpid
获得。同时,每个进程都有创建自己的父进程,通过 os.Getppid
获得。
进程凭证
Unix 中进程都有一套数字表示用户 ID(UID) 和组 ID(GID),有时也将这些 ID 称之为进程凭证。Windows 下总是 -1。
实际用户 ID 和实际组 ID
实际用户 ID(real user ID)和实际组 ID(real group ID)确定了进程所属的用户和组。可以从 /etc/passwd
文件读取用户 ID 和组 ID。当创建新进程时(如 shell 执行程序),将从其父进程中继承这些 ID。
可通过 os.Getuid()
和 os.Getgid()
获取当前进程的实际用户 ID 和实际组 ID;
有效用户 ID 和有效组 ID
大多数 Unix 实现中,当进程尝试执行各种操作(即系统调用)时,将结合有效用户 ID、有效组 ID,连同辅助组 ID 一起来确定授予进程哪些权限。内核还会使用有效用户 ID 来决定一个进程是否能向另一个进程发送信号。
有效用户 ID 为 0(root 的用户 ID)的进程拥有超级用户的所有权限。这样的进程又称为特权级进程(privileged process)。某些系统调用只能由特权级进程执行。
可通过 os.Geteuid()
和 os.Getegid()
获取当前进程的有效用户 ID(effective user ID)和有效组 ID(effectvie group ID)。
**通常情况下,有效用户 ID 及组 ID 与其相应的实际 ID 相等,**但有两种方法能够致使二者不同。一是使用相关系统调用;二是执行 set-user-ID 和 set-group-ID 程序,这就会导致实际用户id为运行程序的用户id,而有效用户id为程序本身所属的用户id。
Set-User-ID 和 Set-Group-ID 程序
set-user-ID
程序会将进程的有效用户 ID 设置为可执行文件所属的用户 ID(实际id和有效id在正常情况下相同,均为执行当前程序的用户,但是set-user-id可以将其改为以文件本身用户权限运行),从而获得常规情况下并不具有的权限。set-group-ID
程序对进程有效组 ID 实现类似任务。(有时也将这程序简称为 set-UID 程序和 set-GID 程序。)
与其他文件一样,可执行文件的用户 ID 和组 ID 决定了该文件的所有权。文件还拥有两个特别的权限位 set-user-ID 位和 set-group-ID 位,可以使用 os.Chmod
修改这些权限位(非特权用户进程只能修改其自身文件,而特权用户进程能修改任何文件)。
chmod u+s filename
文件设置了 set-user-ID 位后,ls -l
显示文件会在属主用户执行权限字段上看到字母 s(有执行权限时) 或 S(无执行权限时);相应的 set-group-ID 则是在组用户执行位上看到 s 或 S。
当运行 set-user-ID 程序时,内核会将进程的有效用户 ID 设置为可执行文件自身的用户 ID。set-group-ID 程序对进程有效组 ID 的操作与之类似。通过这种方法修改进程的有效用户 ID 或组 ID,能够使进程(换言之,执行该程序的用户)获得常规情况下所不具有的权限。例如,如果一个可执行文件的属主为 root,且为此程序设置了 set-user-ID 权限位,那么当运行该程序时,进程会取得超级用户权限。
也可以利用程序的 set-user-ID 和 set-group-ID 机制,将进程的有效 ID 修改为 root 之外的其他用户。例如,为提供一个受保护文件的访问,可采用如下方案:创建一个具有对该文件访问权限的专有用户(组)ID,然后再创建一个 set-user-ID(set-group-ID)程序,将进程有效用户(组)ID 变更为这个专用 ID (即修改文件属主为专有用户)。这样,无需拥有超级用户的所有权限,程序就能访问该文件,避免使用root权限时进行其他非法操作。
此外,os
还提供了获取辅助组 ID 的函数:os.Getgroups()
操作系统用户
包 os/user
允许通过名称或 ID 查询用户账号。用户结构定义如下:
|
|
User
结构体代表一个用户帐户。
在 POSIX 系统中 Uid 和 Gid 字段分别包含代表 uid 和 gid 的十进制数字。在 Windows 系统中 Uid 和 Gid 包含字符串格式的安全标识符(SID)。在 Plan 9 系统中,Uid、Gid、Username 和 Name 字段是 /dev/user 的内容。
Current
函数可以获取当前用户账号。而 Lookup
和 LookupId
则分别根据用户名和用户 ID 查询用户。如果对应的用户不存在,则返回 user.UnknownUserError
或 user.UnknownUserIdError
。
|
|
进程的当前工作目录
一个进程的当前工作目录(current working directory)定义了该进程解析相对路径名的起点。新进程的当前工作目录继承自其父进程。
func Getwd() (dir string, err error)
Getwd
返回一个对应当前工作目录的根路径(即绝对路径)。如果当前目录可以经过多条路径抵达(比如符号链接),Getwd
会返回其中一个。对应系统调用:getcwd
。
func Chdir(dir string) error
相应的,Chdir
将当前工作目录修改为 dir
指定的目录。如果出错,会返回 *PathError
类型的错误。对应系统调用 chdir
。
另外,os.File
有一个方法:Chdir
,对应系统调用 fchidr
(以文件描述符为参数),也可以改变当前工作目录。
改变进程的根目录
每个进程都有一个根目录,该目录是解释绝对路径(即那些以 / 开始的目录)时的起点。默认情况下,这是文件系统的真实根目录。新进程从其父进程处继承根目录。有时可能需要改变一个进程的根目录(比如 ftp 服务就是一个典型的例子,ftp一进入,其根就是某个文件夹内容,而不是真实的根)。系统调用 chroot
能改变一个进程的根目录。
在go的高版本中已经无法通过标准库修改进程的根目录了,可以直接通过syscall去调用系统调用来修改。
进程环境列表
每个进程都有与其相关的称之为环境列表(environment list)的字符串数组,或简称环境(environment)。其中每个字符串都以 名称 = 值(name=value)形式定义。因此,环境是“名称 - 值”的成对集合,可存储任何信息。常将列表中的名称称为环境变量(environment variables)。
新进程在创建之时,会继承其父进程的环境副本。这是一种原始的进程间通信方式,却颇为常用。环境(environment)提供了将信息从父进程传递给子进程的方法。创建后,父子进程的环境相互独立,互不影响。
环境变量的常见用途之一是在 shell 中,通过在自身环境中放置变量值,shell 就可确保把这些值传递给其所创建的进程,并以此来执行用户命令。
在程序中,可以通过 os.Environ
获取环境列表:
func Environ() []string
返回的 []string
中每个元素是 key=value
的形式。
func Getenv(key string) string
Getenv
检索并返回名为 key
的环境变量的值。如果不存在该环境变量会返回空字符串。有时候,可能环境变量存在,只是值刚好是空。为了区分这种情况,提供了另外一个函数 LookupEnv()
:
func LookupEnv(key string) (string, bool)
如果变量名存在,第二个参数返回 true
,否则返回 false
。
func Setenv(key, value string) error
Setenv
设置名为 key
的环境变量,值为 value
。如果出错会返回错误。(如果值之前存在,会覆盖)
func Unsetenv(key string) error
Unsetenv
删除名为 key
的环境变量。
func Clearenv()
Clearenv
删除所有环境变量。
这些函数都是获取和修改当前程序的环境变量,并不会对全局或其他进程的环境变量造成影响,它们都是独立的副本。如果想修改全局的环境变量肯定需要修改文件 /etc/profile,这会由第一个进程执行,其他进程都是从该进程延申出来的,因此会得到其环境变量的副本。
另外,ExpandEnv
和 Getenv
功能类似,不过,前者使用变量方式,如:
os.ExpandEnv("$GODEBUG") 和 os.Getenv(“GODEBUG”) 是一样的。
实际上,os.ExpandEnv
调用的是 os.Expand(s, os.Getenv)
。
func Expand(s string, mapping func(string) string) string
Expand
能够将${var} 或 $var 形式的变量,经过 mapping 处理,得到结果。
实际开发中使用 os.GetEnv
就行了,ExpandEnv基本不会使用,其本质上也是用的os.GetEnv。
线程
与进程类似,线程是允许应用程序并发执行多个任务的一种机制。一个进程可以包含多个线程。同一个程序中的所有线程均会独立执行相同程序,且共享同一份全局内存区域。
同一进程中的多个线程可以并发执行。在多处理器环境下,多个线程可以同时并行(不是并发)。如果一个线程因等待 I/O 操作而遭阻塞,其他线程依然可以继续运行。
在 Linux 中,通过系统调用 clone()
来实现线程的。从前面的介绍,我们知道,该系统调用也可以用来创建进程。实际上,从内核的角度来说,它并没有线程这个概念。Linux 把所有的线程都当作进程来实现。内核并没有准备特别的调度算法或是定义特别的数据结构来表示线程。相反,线程仅仅被内核视为一个使用某些共享资源的进程。所以,在内核中,它看起来就是一个普通的进程(只是该进程和其他一些进程共享某些资源,如地址空间)。
在 Go 中,通过 clone()
系统调用来创建线程,其中的 clone_flags
为:
|
|
也就是说,父子俩共享了地址空间 (_CLONE_VM)、文件系统资源 (_CLONE_FS)、文件描述符 (_CLONE_FILES) 和信号处理程序 (_CLONE_SIGHAND)。而 _CLONE_THREAD
则会将父子进程放入相同的线程组。这样一来,新建的进程和父进程都叫做线程。
需要注意的是,直接使用 clone()
系统调用创建线程相对于使用 Go 语言提供的 goroutine 来说较为底层,并且需要手动处理线程的等待和退出。**因此,在一般情况下,推荐使用 goroutine 来实现并发操作。**只有在特定的需求下,才需要使用 clone()
系统调用来创建线程。