go语言实现b树 go实现二叉树

【原创】树莓派3B开发Go语言（四）-自写库实现pwm输出

在前一小节中介绍了点亮第一个LED灯，这里我们准备进阶尝试下，输出第一段PWM波形。（PWM也就是脉宽调制，一种可调占空比的技术，得到的效果就是：如果用示波器测量引脚会发现有方波输出，而且高电平、低电平的时间是可调的。）

成都创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都做网站、网站设计、外贸营销网站建设、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的新洲网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

这里爪爪熊准备写成一个golang的库，并开源到github上，后续更新将直接更新到github中，如果你有兴趣可以和我联系。 github.com/dpawsbear/bear_rpi_go

我在很多的教程中都看到说树莓派的PWM（硬件）只有一个GPIO能够输出，就是 GPIO1 。这可是不小的打击，因为我想使用至少四个 PWM ，还是不死心，想通过硬件手册上找寻蛛丝马迹，看看究竟怎么回事。

手册上找寻东西稍等下讲述，这里先提供一种方法测试 树莓派3B 的 PWM 方法：用指令控制硬件PWM。

这里通过指令的方式掌握了基本的pwm设置技巧，决定去翻一下手册看看到底PWM怎么回事，这里因为没有 BCM2837 的手册，根据之前文章引用官网所说， BCM2835 和 BCM2837 应该是一样的。这里我们直接翻阅 BCM2835 的手册，直接找到 PWM 章节。找到了如下图：

图中可以看到在博通的命名规则中 GPIO 12、13、18、19、40、41、45、52、53 均可以作为PWM输出。但是只有两路PWM0 PWM1。根据我之前所学知识，不出意外应该是PWM0 和 PWM1可以输出不一样的占空比，但是频率应该是一样的。因为没有示波器，暂时不好测试。先找到下面对应图：

根据以上两个图对比可以发现如下规律：

对照上面的表可以看出从 BCM2837 中印出来的能够使用在PWM上的就这几个了。

为了验证个人猜想是否正确，这里先直接使用指令的模式，模拟配置下是否能够正常输出。

通过上面一系列指令模拟发现，（GPIO1、GPIO26）、（GPIO23、GPIO24）是绑定在一起的，调节任意一个，另外一个也会发生变化。也即是PWM0、PWM1虽然输出了两路，可以理解成两路其实都是连在一个输出口上。这里由于没有示波器或者逻辑分析仪这类设备（仅有一个LED灯），所以测试很简陋，下一步是使用示波器这类东西对频率以及信号稳定性进行下测试。

小节：树莓派具有四路硬件输出PWM能力，但是四路中只能输出两个独立（占空比独立）的PWM，同时四路输出的频率均是恒定的。

上面大概了解清楚了树莓派3B的PWM结构，接下来就是探究如何使用Go语言进行设置。

因为拿到了手册，这里我想直接操作寄存器的方式进行设置，也是顺便学习下Go语言处理寄存器的过程。首先需要拿到pwm 系列寄存器的基地址，但是翻了一圈手册，发现只有偏移，没有找到基地址。

经过了一段时间的努力后，决定写一个 树莓派3B golang包开源放在github上，只需要写相关程序进行调用就可以了，以下是相关demo（pwm）（在GPIO.12 上输出PWM波，放上LED灯会有呼吸灯的效果，具体多少频率还没有进行测试）

以下是demo(pwm) 源码

Go语言基础语法（一）

本文介绍一些Go语言的基础语法。

先来看一个简单的go语言代码：

go语言的注释方法：

代码执行结果：

下面来进一步介绍go的基础语法。

go语言中格式化输出可以使用 fmt 和 log 这两个标准库，

常用方法：

示例代码：

执行结果：

更多格式化方法可以访问中的fmt包。

log包实现了简单的日志服务，也提供了一些格式化输出的方法。

执行结果：

下面来介绍一下go的数据类型

下表列出了go语言的数据类型：

int、float、bool、string、数组和struct属于值类型，这些类型的变量直接指向存在内存中的值；slice、map、chan、pointer等是引用类型，存储的是一个地址，这个地址存储最终的值。

常量是在程序编译时就确定下来的值，程序运行时无法改变。

执行结果：

执行结果：

Go 语言的运算符主要包括算术运算符、关系运算符、逻辑运算符、位运算符、赋值运算符以及指针相关运算符。

算术运算符：

关系运算符：

逻辑运算符：

位运算符：

赋值运算符：

指针相关运算符：

下面介绍一下go语言中的if语句和switch语句。另外还有一种控制语句叫select语句，通常与通道联用，这里不做介绍。

if语法格式如下：

if ... else ：

else if：

示例代码：

语法格式：

另外，添加 fallthrough 会强制执行后面的 case 语句，不管下一条case语句是否为true。

示例代码：

执行结果：

下面介绍几种循环语句：

执行结果：

执行结果：

也可以通过标记退出循环：

--THE END--

go语言循环队列的实现

队列的概念在 顺序队列 中，而使用循环队列的目的主要是规避假溢出造成的空间浪费，在使用循环队列处理假溢出时，主要有三种解决方案

本文提供后两种解决方案。

顺序队和循环队列是一种特殊的线性表，与顺序栈类似，都是使用一组地址连续的存储单元依次存放自队头到队尾的数据元素，同时附设队头(front)和队尾(rear)两个指针，但我们要明白一点，这个指针并不是指针变量，而是用来表示数组当中元素下标的位置。

本文使用切片来完成的循环队列，由于一开始使用三个参数的make关键字创建切片，在输出的结果中不包含nil值(看起来很舒服)，而且在验证的过程中发现使用append()函数时切片内置的cap会发生变化，在消除了种种障碍后得到了一个四不像的循环队列，即设置的指针是顺序队列的指针，但实际上进行的操作是顺序队列的操作。最后是对make()函数和append()函数的一些使用体验和小结，队列的应用放在链队好了。

官方描述(片段)

即切片是一个抽象层，底层是对数组的引用。

当我们使用

构建出来的切片的每个位置的值都被赋为interface类型的初始值nil，但是nil值也是有大小的。

而使用

来进行初始化时，虽然生成的切片中不包含nil值，但是无法通过设置的指针变量来完成入队和出队的操作，只能使用append()函数来进行操作

在go语言中，切片是一片连续的内存空间加上长度与容量的标识，比数组更为常用。使用 append 关键字向切片中追加元素也是常见的切片操作

正是基于此，在使用go语言完成循环队列时，首先想到的就是使用make(type, len, cap)关键字方式完成切片初始化，然后使用append()函数来操作该切片，但这一方式出现了很多问题。在使用append()函数时，切片的cap可能会发生变化，用不好就会发生扩容或收缩。最终造成的结果是一个四不像的结果，入队和出队操作变得与指针变量无关，失去了作为循环队列的意义，用在顺序队列还算合适。

参考博客：

Go语言中的Nil

Golang之nil

Go 语言设计与实现

go语言string之Buffer与Builder

操作字符串离不开字符串的拼接，但是Go中string是只读类型，大量字符串的拼接会造成性能问题。

拼接字符串，无外乎四种方式，采用“+”，“fmt.Sprintf()”,"bytes.Buffer","strings.Builder"

上面我们创建10万字符串拼接的测试，可以发现"bytes.Buffer","strings.Builder"的性能最好，约是“+”的1000倍级别。

这是由于string是不可修改的，所以在使用“+”进行拼接字符串，每次都会产生申请空间，拼接，复制等操作，数据量大的情况下非常消耗资源和性能。而采用Buffer等方式，都是预先计算拼接字符串数组的总长度（如果可以知道长度），申请空间，底层是slice数组，可以以append的形式向后进行追加。最后在转换为字符串。这申请了不断申请空间的操作，也减少了空间的使用和拷贝的次数，自然性能也高不少。

bytes.buffer是一个缓冲byte类型的缓冲器存放着都是byte

是一个变长的 buffer，具有 Read 和Write 方法。 Buffer 的 零值 是一个 空的 buffer，但是可以使用，底层就是一个 []byte， 字节切片。

向Buffer中写数据，可以看出Buffer中有个Grow函数用于对切片进行扩容。

从Buffer中读取数据

strings.Builder的方法和bytes.Buffer的方法的命名几乎一致。

但实现并不一致，Builder的Write方法直接将字符拼接slice数组后。

其没有提供read方法，但提供了strings.Reader方式

Reader 结构:

Buffer:

Builder:

可以看出Buffer和Builder底层都是采用[]byte数组进行装载数据。

先来说说Buffer:

创建好Buffer是一个empty的，off 用于指向读写的尾部。

在写的时候，先判断当前写入字符串长度是否大于Buffer的容量，如果大于就调用grow进行扩容，扩容申请的长度为当前写入字符串的长度。如果当前写入字符串长度小于最小字节长度64，直接创建64长度的[]byte数组。如果申请的长度小于二分之一总容量减去当前字符总长度，说明存在很大一部分被使用但已读，可以将未读的数据滑动到数组头。如果容量不足，扩展2*c + n 。

其String()方法就是将字节数组强转为string

Builder是如何实现的。

Builder采用append的方式向字节数组后添加字符串。

从上面可以看出，[]byte的内存大小也是以倍数进行申请的，初始大小为 0，第一次为大于当前申请的最大 2 的指数，不够进行翻倍.

可以看出如果旧容量小于1024进行翻倍，否则扩展四分之一。（2048 byte 后，申请策略的调整）。

其次String()方法与Buffer的string方法也有明显区别。Buffer的string是一种强转，我们知道在强转的时候是需要进行申请空间，并拷贝的。而Builder只是指针的转换。

这里我们解析一下 *(*string)(unsafe.Pointer(b.buf)) 这个语句的意思。

先来了解下unsafe.Pointer 的用法。

也就是说，unsafe.Pointer 可以转换为任意类型，那么意味着，通过unsafe.Pointer媒介，程序绕过类型系统，进行地址转换而不是拷贝。

即*A = Pointer = *B

就像上面例子一样，将字节数组转为unsafe.Pointer类型，再转为string类型，s和b中内容一样，修改b,s也变了，说明b和s是同一个地址。但是对s重新赋值后，意味着s的地址指向了“WORLD”,它们所使用的内存空间不同了，所以s改变后，b并不会改变。

所以他们的区别就在于 bytes.Buffer 是重新申请了一块空间，存放生成的string变量， 而strings.Builder直接将底层的[]byte转换成了string类型返回了回来，去掉了申请空间的操作。

Go语言——goroutine并发模型

参考：

Goroutine并发调度模型深度解析手撸一个协程池

Golang 的 goroutine 是如何实现的？

Golang - 调度剖析【第二部分】

OS线程初始栈为2MB。Go语言中，每个goroutine采用动态扩容方式，初始2KB，按需增长，最大1G。此外GC会收缩栈空间。

BTW，增长扩容都是有代价的，需要copy数据到新的stack，所以初始2KB可能有些性能问题。

更多关于stack的内容，可以参见大佬的文章。 聊一聊goroutine stack

用户线程的调度以及生命周期管理都是用户层面，Go语言自己实现的，不借助OS系统调用，减少系统资源消耗。

Go语言采用两级线程模型，即用户线程与内核线程KSE（kernel scheduling entity）是M:N的。最终goroutine还是会交给OS线程执行，但是需要一个中介，提供上下文。这就是G-M-P模型

Go调度器有两个不同的运行队列：

go1.10\src\runtime\runtime2.go

Go调度器根据事件进行上下文切换。

调度的目的就是防止M堵塞，空闲，系统进程切换。

详见 Golang - 调度剖析【第二部分】

Linux可以通过epoll实现网络调用，统称网络轮询器N（Net Poller）。

文件IO操作

上面都是防止M堵塞，任务窃取是防止M空闲

每个M都有一个特殊的G，g0。用于执行调度，gc，栈管理等任务，所以g0的栈称为调度栈。g0的栈不会自动增长，不会被gc，来自os线程的栈。

go1.10\src\runtime\proc.go

G没办法自己运行，必须通过M运行

M通过通过调度，执行G

从M挂载P的runq中找到G，执行G

Go语言设计与实现（上）

基本设计思路：

类型转换、类型断言、动态派发。iface，eface。

反射对象具有的方法：

编译优化：

内部实现：

实现 Context 接口有以下几个类型（空实现就忽略了）：

互斥锁的控制逻辑：

设计思路：

（以上为写被读阻塞，下面是读被写阻塞）

总结，读写锁的设计还是非常巧妙的：

设计思路：

WaitGroup 有三个暴露的函数:

部件：

设计思路：

结构：

Once 只暴露了一个方法：

实现：

三个关键点：

细节：

让多协程任务的开始执行时间可控（按顺序或归一）。（Context 是控制结束时间）

设计思路： 通过一个锁和内置的 notifyList 队列实现，Wait() 会生成票据，并将等待协程信息加入链表中，等待控制协程中发送信号通知一个（Signal()）或所有（Boardcast()）等待者（内部实现是通过票据通知的）来控制协程解除阻塞。

暴露四个函数：

实现细节：

部件：

包： golang.org/x/sync/errgroup

作用：开启 func() error 函数签名的协程，在同 Group 下协程并发执行过程并收集首次 err 错误。通过 Context 的传入，还可以控制在首次 err 出现时就终止组内各协程。

设计思路：

结构：

暴露的方法：

实现细节：

注意问题：

包： "golang.org/x/sync/semaphore"

作用：排队借资源（如钱，有借有还）的一种场景。此包相当于对底层信号量的一种暴露。

设计思路：有一定数量的资源 Weight，每一个 waiter 携带一个 channel 和要借的数量 n。通过队列排队执行借贷。

结构：

暴露方法：

细节：

部件：

细节：

包： "golang.org/x/sync/singleflight"

作用：防击穿。瞬时的相同请求只调用一次，response 被所有相同请求共享。

设计思路：按请求的 key 分组（一个 *call 是一个组，用 map 映射存储组），每个组只进行一次访问，组内每个协程会获得对应结果的一个拷贝。

结构：

逻辑：

细节：

部件：

如有错误，请批评指正。

本文名称：go语言实现b树 go实现二叉树
本文网址：http://scjbc.cn/article/hphids.html