链表-go语言实现

最近复习数据结构与算法，正好也顺带练习下go语言。

结构体定义

type node struct {
	value int
	next  *node
}

func (node *node) setValue(value int) {
	node.value = value
}

func (node *node) getValue(value int) int {
	return node.value
}

首先定义链表的结点并定义与其关联的getset方法用来操作结点的值。此处和java等面向对象的语言有些不同，go语言方法接收一个定义的结点类型的变量，并修改其值，由于go本身是值传递，此处接收者定义为指针。

	方法名	声明
	创建新链表	newList()
	增加链表值	add()
	删除链表值	delete(index int)
	修改链表值	update(index int,value int)
	查找链表值	find(value int) int

完整代码


type node struct {
	value int
	next  *node
}

func (node *node) setValue(value int) {
	node.value = value
}

func (node *node) getValue(value int) int {
	return node.value
}

func newList() node {
	return node{
		value: -1,
		next:  nil,
	}
}

func (list *node) add(value int) {

	var temp *node = nil

	newNode := new(node)
	newNode.value = value
	newNode.next = nil

	temp = list.next
	list.next = newNode
	newNode.next = temp
}

func (list *node) delete(index int) error {

	for i := 1; i <= index; i++ {
		if (i == index && list.next != nil) {
			list.next = list.next.next;
			return nil

		} else {
			list = list.next
		}

	}
	return errors.New("删除失败")
}

func (list *node) update(index int, value int) error {

	for i := 1; i <= index; i++ {
		if (i == index && list.next != nil) {
			list.next.value = value;
			return nil

		} else {
			list = list.next
		}

	}
	return errors.New("更新失败")
}

func (list *node) find(value int) (index int) {

	list = list.next
	for i := 1; list != nil; i++ {
		if list.value == value {
			index = i
			return
		}
		list = list.next
	}
	index = -1
	return
}

以上就是这次所定义的链表，以及对其所定义的一系列操作，下面运行看看我们的程序是否可以正常运行。


func main() {
	var list Node
	list = NewList()
	list.add(1)
	list.add(2)
	list.add(3)
	println(list.find(1), list.find(2), list.find(3))
	err := list.delete(1)
	if err != nil {
		println(err)
	}
	println(list.find(3))

	err = list.update(2, 9)
	if err != nil {
		println(err)
	}

	println(list.find(9))

}

运行结果：
image.png-9.2kB

可以看到结果正如我们所期待的那样，先给链表中插入三个值，1，2，3.由于是按照头插法插入的，所以输出顺序为逆序。紧接着删除掉第一个位置的元素3，然后3不存在结果输出-1。然后再更新第二个位置的元素为9，输出9确实在第二个位置。

最后

链表其本质上就是一组离散结构的顺序表，使用任何语言都可以实现，其类型包括单向链表，双向链表，单向循环链表，双向循环链表等。在日常编程中具有相当广的应用范围，本次我们仅仅是用其完成了一个具有简单增删改查功能的列表容器结构，算是简单的小回顾复习了下吧。

8月
01

调度算法

操作系统

调度层次

高级调度（作业调度）
- 作业
  包含通常的程序和数据，而且还应配有一份作业说明书。
低级调度（进程调度）
- 调度方式
  - 非抢占方式
  - 抢占方式
    - 优先权原则
    - 短作业优先原则
    - 时间片原则
中级调度
- 中级调度(Intermediate Level Scheduling)又称中程调度(Medium-Term Scheduling)。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。

调度算法

1.先来先服务调度算法（FCFS）
2.短作业优先调度算法（SJF）
3.高响应比优先调度算法
4.时间片轮转
5.多级反馈队列调度

##死锁的原因和必要条件

原因
（1）竞争资源
（2）进程间推进顺序非法。
必要条件
1.互斥条件
2.请求和保持条件
3.不可剥夺条件
4.环路等待条件
解决死锁的方法
1. 预防死锁
  - 摒弃“请求和保持”条件
  - 摒弃“不剥夺”条件
  - 摒弃“环路等待”条件
2. 避免死锁
  - 安全状态
3. 检测死锁
4. 解除死锁

8月
01

进程相关

操作系统

试说明进程在三个基本状态之间转换的典型原因
- 就绪状态->执行状态：进程分配到CPU资源
- 执行状态->就绪状态：时间片用完
- 执行状态->阻塞状态: I/O请求；
- 阻塞状态->就绪状态: I/O完成。
PV操作
- 概念:PV操作与信号量的处理相关，P表示通过的意思，V表示释放的意思。
- 所谓信号灯，实际上就是用来控制进程状态的一个代表某一资源的存储单元。例如，p1和p2是分别将数据送入缓冲B和从缓冲B读出数据的两个进程，为了防止这两个进程并发时产生错误，Dijkstra设计了一种同步机制叫“PV操作”，P操作和V操作是执行时不被打断的两个操作系统原语。
- PV原语:PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生

经典进程同步问题

生产者-消费者问题

概念:假设有两个共享固定大小缓冲区的线程–即所谓的”生产者”和”消费者”—在实际运行时会发生问题。
问题:生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
解决方法：令生产者在缓冲区满时休眠，等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。

信号量实现:

多生产者-多消费者问题
Process Pi(1...m);//生产者
.....
Repeat
//生产一个产品
wait(buffer);
wait(S);
//送产品到Buffer(in)
in=(int+1)mod n;
singal(s);
singal(prod);
Process Pi(1...m);//消费者
.....
Repeat
//生产一个产品
wait(prod);
wait(S);
//送产品到Buffer(in)
out=(out+1)mod N;
singal(s);
singal(buf);

进程控制块

作用
使一个在多道程序环境下不能独立运行的程序，称为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

结构

进程标识符

1
2
3
进程标识符用于唯一地标识一个进程。
（1）内部标识符。（方便系统）
 (2) 外部标识符。（方便用户）

处理机状态

进程调度信息

(1)进程状态
(2)进程优先级
(3)进程调度所需的其它信息
(4)事件

+ 进程控制信息

    1
2
3
4
(1)程序和数据的地址
(2)进程同步和通信 机制
(3)资源清单
(4)链接指针

组织方式
- 链接方式
- 索引方式

进程同步

两种制约关系

间接相互制约关系（共享资源）
直接相互制约关系（合作）

同步机制应遵循的规则

空闲让进
忙则等待
有限等待
让权等待

进程同步机制

信号量机制
- 整型信号量
- 记录型信号量
- AND型信号量
- 信号量集
管程机制
一个管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。
- 管程的名称
- 局部于管程内部的共享数据结构说明
- 对该数据结构进行操作的一组过程
- 对局部于管程内部的共享数据设置初始值的语句

进程通信

共享存储器系统
消息传递系统
管道通信

线程

属性
- 轻型实体
  不拥有系统资源，独立tcb，用于指示被执行指令序列的程序计数器，保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈
- 可独立调度和分派的基本单位
- 可并发执行
- 共享进程资源
实现方式
1.内核支持线程
2.用户级线程

7月
31

redis源码阅读-整数集合

redis源码阅读

redis中整数集合（intset）用于有序、无重复地保存多个整数值，根据元素的值，自动选择该用什么长度的整数类型来保存元素。

intset的结构体

typedef struct intset{
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
}intset;

在这个结构体中encoding用来保存元素所使用的类型的长度，length用来保存元素个数，contents保存实际的数据。有意思的是，对于int8_t，实际上contents保存的类型根据实际需要为数据中最大的类型，int8_t在此仅仅作为占位符。

intset的函数

intset的主要运行

创建一个新的整数集合

intset *is = intsetNew()

当创建一个新的整数集合时，其默认将encoding赋值为_int16的大小，length设置为0。

添加新元素到 intset

当将元素添加到整数集合中时，其需要考虑以下情形：

元素已存在于集合，不做动作；
元素不存在于集合，并且添加新元素并不需要升级；
元素不存在于集合，但是要在升级之后，才能添加新元素；
而且，intsetAdd 需要维持元素内容的以下性质：
确保数组中没有重复元素；
确保数组中的元素按由小到大排序；

所以添加元素函数intsetAdd的主要流程步骤可以如下：

添加新元素到 intset(需要升级)

接下来详细，看下当需要对contens进行升级时intsetAdd函数进行的操作。
该操作主要由intsetUpgradeAndAdd函数进行。

该函数的主要任务为：
1.对新元素进行检测，看保存的新元素需要什么类型编码；
2.将集合encoding属性的值设置为新编码类型，并根据新编码类型，对整个contetns数组进行内存重分配；
3.调整contents数组内原有元素在内存中的排列方式，从旧编码调整为新编码。
4.将新元素添加到集合中。

此处重点考虑下理解将旧的编码更改为新的编码。

假设有个intset，有三个用int16_t方式保存的数值，分别是1、2和3，结构如下：

1	intset->contents = [1,2,3];

内存排列如下：

1 2	bit 0 15 31 47 value 1 2 3

将一个长度为int32_t的值 65535加入到集合中。
1.将encoding设置。
2.根据encoding属性的值，对contents数组进行内存重分配。
重分配后，contents在内存中的排列如下：

1 2	bit 0 15 31 47 63 95 127 value 1 2 3

contens数组现在有4个int32_t值的空间。
3.因为原来的3个int16_t值还“挤在”contents前面的48个位里，所以程序需要移动它们并转换类型，让它们适应集合的新编码方式。
4.移除后，将新值65535添加到数组。

###升级有两个原则

从较短整数到较长整数的转换，并不会更改元素里面的值
集合编码元素的方式，由元素中长度最大的那个值来决定

##总结

Intset 用于有序、无重复地保存多个整数值，会根据元素的值，自动选择该用什么长度的整数类型来保存元素。
当一个位长度更长的整数值添加到 intset 时，需要对 intset 进行升级，新 intset 中每个元素的位长度，会等于新添加值的位长度，但原有元素的值不变。
升级会引起整个 intset 进行内存重分配，并移动集合中的所有元素，这个操作的复杂度为 O(N) 。
Intset 只支持升级，不支持降级。
Intset 是有序的，程序使用二分查找算法来实现查找操作，复杂度为 O(lgN)
st=>start: 开始 cond1=>condition: 实际值长度大于intset的值长度 op1=>operation: 对contents进行类型升级后插入值 cond2=>condition: 判断元素是否重复 op2=>operation: 为新元素分配内存，并对contents数组中现有的元素进行移动，确保新元素会被放到有序数组正确的位置 op3=>operation: 将新元素的值保存到contents数组中更新lenght计数器 op4=>operation: 添加失败 ed=>end: 结束 st->cond1 cond1(yes)->op1->ed cond1(no)->cond2 cond2(yes)->op4->ed cond2(no)->op2->op3->ed{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}

6月
02

redis源码阅读--跳跃表

redis源码阅读

对于跳跃表之前已经简单说明了下，那么redis的跳跃表又是如何实现应用的呢？这次就来看看。

redis跳跃表的实现

数据结构定义：(server.h/zskiplist)

typedef struct zskiplist {
    //头节点，尾节点
    struct zskiplistNode *header, *tail;
    //节点数量
    unsigned long length;
    //目前表内节点的最大层数
    int level;
} zskiplist;

节点定义如下：

typedef struct zskiplistNode {
    sds ele;
    //分值
    double score;
    //后退指针，用于从表尾方向向表头方向迭代：当需要逆序处理有序集的命令时，就会用到这个属性
    struct zskiplistNode *backward;
    //层
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

redis跳跃表的应用

跳跃表在redis中的唯一作用，就是实现有序集数据类型。跳跃表将指向有续集的score值和meber域的指针作为元素，并且以score值作为索引，对有序元素进行排序。
举例子来说：

1
2
3

redis> ZADD s 6 x 10 y 15 z
(integer) 3
redisZRANGE s 0-1 WITHSCORES

在redis的底层实现中，其为x、yh和z三个member分别创建了三个字符串，值分别为double类型的6，10，和15，然后用跳跃表将这些指针有序地保存起来，形成这样一个跳跃表：
image.png-35.8kB

总结

redis的跳跃表是一种随机化的数据结构，查找、添加、删除操作都可以在对数期望时间下完成。
跳跃表目前在redis的唯一作用，就是作为有序集类型的底层数据结构（另一个是字典）。
为了满足自身需要，redis基于william pugh 论文中的描述的跳跃表进行了修改，包括:
1.score值可重复。
2.对比一个元素与同时需要检查它的score和member。
3.每个节点带有高度为1层的后退指针，用于从表尾方向向表头方向迭代。

5月
21

理解跳跃表

数据结构与算法

好久没碰过数据结构了，在看redis源码时看到跳跃表的结构，不禁又回想起大学毕业面试被问到跳表的一脸尴尬，于是这次就好好的将对跳表的理解整理下吧。

概念

跳跃表是一种数据结构。其允许快速查询一个有序连续元素的数据链表。而且跳跃列表的平均查找和插入时间复杂度都是O(log n)，比常用的线性结构链表，数组这类的时间复杂度O(n)要优秀很多。
其结构如图所示：
image.png-61kB
每个带有箭头的框表示一个指针, 而每行是一个稀疏子序列的链表；底部的编号框（黄色）表示有序的数据序列。查找从顶部最稀疏的子序列向下进行, 直至需要查找的元素在该层两个相邻的元素中间。

##增加元素
对于跳跃表来说，当向表中增加一个元素时其会通过最顶层的索引一层层往下找，由于建立索引的关键节点几乎是下一层的一半，所以在查找索引的过程需要比较的元素数目相比于直接去查找源链表一次会减少一半的查询次数，即总的时间复杂度会为O(log n)。
具体过程是这样的：

##删除元素
跳跃表删除元素的操作是这样的，自上而下，查找第一次出现节点的索引，并逐层找到每一层对应的节点。删除每一层查找到的节点，如果该层只剩下1个节点，删除整个一层（原链表除外）。总体上，跳跃表删除操作的时间复杂度是O（logN）。
![image.png-79.1kB][2]

5为需要删除的节点。

##总结
跳表的结构定义：

ype head struct {
	length int
	next   *skipNode
}

type skipNode struct {
	value int
	next  *skipNode
	high  *skipNode
}

type skipTable struct {
	table []*head
}

对于跳表其实可以使用一个指针数组保存每一级别的头节点，每个元素节点存在两个指针一个指向链表的下一个元素一个指向上级索引这种方式来实现。查找和修改的操作基本步骤和上面的删除添加差不多。我们日常熟悉的redis中也有对其使用，相比于平衡树其具有易于维护的特点。

[2]: http://static.zybuluo.com/yiranblade/rrgrlex0unc20o563pgdmhki/image.pngst=>start: 开始 input=>inputoutput: 待增加节点 op1=>operation: 查找第一层索引 op2=>operation: 查找到后继续下一层索引 op3=>operation: 直到找到相应位置 op4=>operation: 插入该节点，抛硬币决定该节点是否要提升一层索引 ed=>end: 结束 st->input->op1->op2->op3->op4->ed{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}

5月
11

redis源码阅读--字典

redis源码阅读

字典又叫映射或者说关联数组，是一种抽象的数据结构。本节主要来分析下它的源码。关于map应该说都是挺熟悉的数据结构了。

redis中字典的应用

redis字典的用途有以下两个：
1.实现数据库键空间；
2.用作hash类型键的底层实现之一；

字典的实现

实现字典的方法有很多种：

使用链表和数组
使用哈希表
平衡树

在redis种使用哈希表作为字典的底层实现。
其结构如下:

 typedef struct dict {
    dictType *type;
    void *privdata;
    //哈希表
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

0号哈希表是字典主要使用的哈希表，1号哈希表则只有在程序对0号哈希表rehash时使用。

哈希表实现

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    //哈希表节点指针数组
    dictEntry **table;
    //指针数组大小
    unsigned long size;
    //指针数组长度的掩码
    unsigned long sizemask;
    //哈希表现有的节点数量
    unsigned long used;
} dictht;

table 属性是个数组，数组的每个元素都是个指向 dictEntry 结构的指针。

每个 dictEntry 都保存着一个键值对，以及一个指向另一个 dictEntry 结构的指针：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

next属性指向另一个dictEntry结构，多个dictEntry可以通过next指针串连成链表，所以dictht使用链地址法来处理键碰撞：当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。结构如下：
image.png-43kB

所以整个字典结构如下：
image.png-69.6kB

哈希算法

redis目前使用两种不同的哈希算法：

MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好
基于 djb 算法实现的一个大小写无关散列算法

dictCreate函数

dictCreate函数创建并返回一个新字典：

1	dict *d = dictCreate(&hash_type, NULL);

image.png-37.4kB
新创建的哈希表都没有为table属性分配任何空间:

ht[0]->table 的空间分配将在第一次往字典添加键值对时进行；
ht1->table 的空间分配将在rehash开始时进行;

添加键值对到字典

根据字典所处的状态，将给定的键值对添加到字典会引起一系列复杂的操作:

如果字典未初始化（即字典的0号哈希表的table属性为空），则程序需要对0号哈希表进行初始化；
如果在插入时发生了键碰撞，则程序需要处理碰撞；
如果插入新元素，使得字典满足了rehash条件，则需要启动rehash程序

当程序处理完以上三种情况之后，新的键值对才会被真正地添加到字典上。
整个添加流程如下：
image.png-140.7kB

添加新元素到空白字典

当第一次往空字典里添加键值对时，程序会根据dict.h/DICT_HT_INITIAL_SIZE里指定的大小为d->ht[0]->table分配空间（目前这个值是4）

字典空白
往字典添加了第一个键值对之后

添加新键值对时发生碰撞处理

在哈希表实现中，当两个不同的键拥有相同的哈希值时，称这两个键发生碰撞，而哈希表必须要对碰撞进行处理。字典哈希表所使用的碰撞解决方法被称之为链地址法：这种方法使用链表将多个哈希值相同的节点串连在一起，从而解决冲突问题。

添加新键值对时触发了rehash操作

对于使用链地址法来解决碰撞问题的哈希表dictht来说，哈希表的性能取决于大小（size属性）与保存节点数量（used属性）之间的比率：

哈希表的大小与节点数量，比率在1:1时，哈希表的性能最好；
如果节点数量比哈希表的大小要大很多的话，哈希表就会退化称多个链表，哈希表本身的性能优势便不复存在；

所以为了在字典的键值对不断增多的情况下保持良好的性能，字典需要对所使用的哈希表（ht[0]）进行rehash操作:在不修改任何键值对的情况下，对哈希表进行扩容，将比率维持在1:1左右。
dictAdd在每次向字典添加新键值对之前，都会对哈希表ht[0]进行检查，对于ht[0]的size和used属性，如果它们之间的比率ratio=used/size满足以下任何一个条件的话，rehash过程就会被激活：

自然 rehash ： ratio >= 1 ，且变量 dict_can_resize 为真。
强制 rehash ： ratio 大于变量 dict_force_resize_ratio（目前版本中， dict_force_resize_ratio的值为 5 ）。

Rehash执行过程

字典的rehash操作实际上就是执行以下任务:

创建一个比ht[0]->table更大的ht1->table；
将ht[0]->table中的所有键值对迁移到ht1->table;
将原有ht[0]的数据清空，并将ht1替换为新的ht[0]；

经过以上步骤，程序就在不改变原有键值对数据的基础上，增大了哈希表的大小。

渐进式rehash

rehash程序并不是在激活之后，就马上执行直到完成的，而是多次、渐进式地完成。
redis完成渐进式rehash主要由_dictRehashStep和dictRehashMilliseconds两个函数进行：

_dictRehashStep用于对数据库字典、以及哈希键的字典进行被动rehash；
dictRehashMilliseconds则由Redis服务器常规任务程序执行，用于对数据库字典进行主动rehash；

_dictRehashStep
每次执行_dictRehahshStep，ht[0]->table哈希表第一个不为空的索引上的所有节点就会全部迁移到ht1->table。
dictRehashMilliseconds
dictRehashMilliseconds可以在指定的毫秒数内，对字典进行rehash。
当Redis的服务器常规任务执行时，dictRehashMilliseconds就会被执行，在规定的时间内，尽可能对数据库字典中那些需要rehash的字典进行rehash，从而加速数据库字典的rehash进程。

因为在rehash时，字典会同时使用两个哈希表，所以在这期间的所有查找、删除等操作，除了在ht[0]进行，还会在ht1进行。在执行添加操作时，新的节点会直接添加到ht1而不是ht[0]，这样保证ht[0]的节点数量在整个rehash过程中都只减不增。

字典的收缩

对hash表进行收缩的过程与增加几乎一样；

创建一个比ht[0]->table小的ht1->table;
将ht[0]->table中的所有键值对迁移到ht1->table；
将原有ht[0]数据清空，并将ht1替换为新的ht[0];

字典的迭代

字典拥有其自己的迭代器实现—对字典进行迭代实际上就是对字典所使用的哈希表进行迭代：

迭代器首先迭代字典的第一个哈希表，然后，如果rehash正在进行的话，就继续对第二个哈希表进行迭代。
当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
当这个索引迭代完了，继续查找下一个不为空的索引，如此反覆，直到整个哈希表都迭代完为止。

字典的迭代器有两种：

安全迭代器：在迭代过程中，可以对字典进行修改。
不安全迭代器：在迭代过程中，不可以对字典进行修改。

总结

字典是由键值对构成的抽象数据结构
Redis中的数据库和哈希键都基于字典来实现
Redis字典的底层实现为哈希表，每个字典使用两个哈希表，一般情况下只使用0号哈希表，只有在rehash进行时，才会使用0号和1号哈希表。
哈希表使用链地址法来解决键冲突的问题。
Rehash可以用于扩展或收缩哈希表。
对哈希表的rehash是分多次、渐进式地进行的

4月
27

redis源码阅读--双端链表

redis源码阅读

em….链表是一种常用的数据结构。双端链表也是比较熟悉的了，redis的实现还是有必要研究一下的。

redis中双端链表的应用

redis的列表类型

双端lian链表是redis列表类型的底层实现之一，当对列表类型的键进行操作–例如rpush、lpop或者llen等命令，程序在底层操作的可能就是双端链表。

//这里之所以使用“可能”，是因为redis的列表其实使用两种数据结构作为底层实现：
//1. 双端链表
//2. 压缩列表
//因为双端链表占用的内存比压缩列表要多，所以当创建新的列表键时，列表会优先考虑使用压缩列表作为底层实现，并且在有需要的时候，才会从压缩列表实现转换到双端列表的实现。

redis自身功能

除了实现列表类型，双端链表还被redis内部模块所应用：

事务模块使用双端列表依序保存输入的命令
服务器模块使用双端链表来保存多个客户端
订阅/发送模块使用双端列表来保存订阅模式的多个客户端
事件模块使用双端链表来保存时间事件

双端链表的实现

双端链表的实现由list和listNode这两个数据结构构成。

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list {
    listNode *head; //表头指针
    listNode *tail; //表尾指针
    void *(*dup)(void *ptr); //复制函数
    void (*free)(void *ptr); //释放函数
    int (*match)(void *ptr, void *key);//比对函数
    unsigned long len; //节点数量
}

这里的void表示双端列表对于节点保存的值的类型不做限制。
从数据结构的定义中可以看出：

1
2
3

+ list的遍历可以双向进行
+ list对链表头和表尾进行插入的复杂度都为0(1)---从而可以做到高效实现lpush，rpop，rpoplpush等命令
+ list带有保存节点数量的len属性，所以计算链表长度的复杂度仅为0（1），和之前sds一样读取长度不会成为性能瓶颈。

操作双端链表的函数如下：

list *listCreate(void);
void listRelease(list *list);
void listEmpty(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
void listJoin(list *l, list *o);

迭代器

redis还为双端链表实现了一个迭代器，这个迭代器可以从两个方向对双端列表进行迭代：

沿着next指针前进，从表头到表尾
沿着节点的prev指针前进，从表尾向表头

定义如下：

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

#define AL_START_HEAD 0
#define AL_START_TAIL 1

其中，direction记录迭代从哪里开始，AL_START_HEA表示从表头开始，AL_START_TAIL 1表示从表尾开始。

总结

redis实现了自己的双端链表，其主要的作用用来作为redis列表类型的底层实现以及作为通用数据结构，被其他功能模块所使用。总体来说，这部分的代码不是很复杂，基本的实现都是当初学习c语言实现过的一些类似的东西，但是redis的设计者为其加上一点点额外的东西感觉就可以使得这些熟悉的东西变得灵活又作用强大，比如那个len字段的设计，看起来好像挺理所应当，但是在开始设计时，确实很难意识到这一点，往往看到别人的代码这样用才恍然大悟，所以学习的道路还很漫长。

4月
20

redis源码阅读--动态字符串

redis源码阅读

由于char类型的功能单一，抽象层次比较低，且无法高效支持一些Redis常用的操作（追加操作和长度计算操作），所以redis内部程序大多数时候会使用sds动态字符串类型而并不是char表示。

Redis中的字符串

c语言中，字符串本质为一个使用\0结尾的char数组来表示。
但是这种形式无法支持长度计算和追加操作：

每次计算字符串长度的复杂度为O(N)
对字符串进行N次追加，必定需要对字符串进行N次内存重分配

但是在redis内部，字符串的追加长度和长度计算很常见，而APPEND和STRLEN更是这两种操作，在Redis命令中的直接映射，这两个简单的操作不应该成为性能的瓶颈。而且，Redis除了处理C字符串之外，还需要处理单纯的字节数组，以及服务器协议等，所以为了方便与安全，Redis的字符串表示应该是二进制安全的：程序不应该对字符串里面保存的数据做任何假设，即数据可以是以\0结尾的C字符串，也可以是单纯的字节数组，或者其他格式的数据。
基于此，Redis使用sds类型替换了C语言的默认字符串表示：sds既可以高效地追加和长度计算，同时也是二进制安全的。

sds实现

sds实现主要由两部分构成，第一部分是单纯的c中的char*:

1	typedef char *sds;

第二部分则为其涉及的具体sds数据类型，一共有5种：

结构体类型	作用
sdshdr5	保存5位长度字符串（不再使用）
sdshdr8	保存8位长度字符串
sdshdr16	保存16位长度字符串
sdshdr32	保存32位长度字符串
sdshdr64	保存64位长度字符串

在这些结构中整体都可以提取为以下几个字段：

struct sdshdr{
    len ; 
    alloc ;
    buf[] ;
    flags ;
}

这三个字段所表示的含义为：len代表buf的字符串长度，alloc代表整体的分配空间，buf为实际保存字符串数据的地方，flags保存了字符串的具体数据类型。
整体来看，我们就可以这样去理解整个sds的结构，类型sds是char*的别名，而结构sdshdr则保存了len、alloc、buf、flags四个属性。
使用这个结构来保存helloworld：

struct sdshdr{
    len = 11;
    alloc = 11;
    buf = {'h','e','l','l','o','w','o','r','l','d','\0'};
}

由此我们就可以理解，redis是怎么优化读取len的速度了。直接读取sdslen属性就可以实现时间复杂度为θ(1) 的长度计算操作。另一点，通过对buf分配一些额外的空间，sdshdr 可以让执行追加操作所需的内存重分配次数大大减少。

字符串追加操作的优化

其实由前面的结构已经可以看出来了，这里实际上是redis在执行append操作时会进行一个内存预先分配的策略，如果内存足够就无需再次分配内存从而提高效率，减少重新分配内存的策略。这个套路好多编程语言软件在其动态数组或者说线性表的结构都会使用，java中的List,Go中的切片等等都有使用。
redis这里sds的分配策略实际是通过sdsMakeRoomFor这个函数来实现的。

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

总体整理下该函数所作的操作为，首先获取剩余内存空间长度，如果剩余内存足够使用，则返回无需进行分配。需要新分配空间时计算新字符串所需的总长度，如果其长度小于SDS_MAX_PREALLOC那么为字符串分配2倍于所需长度的空间，否则就分配所需长度加上SDS_MAX_PREALLOC数量的空间。最后的一系列操作就是确认新的sds类型重新分配空间。
在目前版本的 Redis 中， SDS_MAX_PREALLOC 的值为 1024 * 1024 ，也就是说，当大小小于 1MB 的字符串执行追加操作时， sdsMakeRoomFor 就为它们分配多于所需大小一倍的空间；当字符串的大小大于 1MB ，那么 sdsMakeRoomFor 就为它们额外多分配 1MB 的空间。

最后

对于redis来说，其内部字符串的实现采用sds来实现。我们从sds这一内部结构开始阅读redis的源代码，其数据类型结构部分与其余地方耦合度比较少，阅读起来还是比较容易的。
总结一下，sds大概的特点如下：

Redis 的字符串表示为 sds ，而不是 C 字符串（以 \0 结尾的 char*）。
对比 C 字符串， sds 有以下特性：
- 可以高效地执行长度计算（strlen）；
- 可以高效地执行追加操作（append）；
- 二进制安全；
sds 会为追加操作进行优化：加快追加操作的速度，并降低内存分配的次数，代价是多占用了一些内存，而且这些内存不会被主动释放。

4月
14

垃圾代码重构-《代码整洁之道》-读后感

《代码整洁之道》读书笔记

根据作者的说法，该书大致上分为3个部分。第一部分主要介绍编写整洁代码的原则、模式和实践。第二部分结合实际的例子教导我们如何使用这些原则。第三部分则重点介绍得到的启示与灵感。目前的话我应该是读完了第一部分以及第二部分的一半左右，但是仅仅这部分的内容感觉就已经获益匪浅，在此记录一下。

有意义的命名

这一点，在我不长的编程生涯中，体会不可谓不深。截取一段自己在大学阶段项目里的代码：

public class LoginServiceImpl implements LoginService{

	@Autowired
	private UserMapper userDao;
	
	@Autowired
	private UserInfoMapper userInfoDao;
	
	public UserDto login(String username, String password) {
		// TODO Auto-generated method stub
		UserDto userDto=new UserDto();
		User user=userDao.LoginService(username, password);
		UserInfo userInfo=null;
		if(user!=null){
			userInfo=userInfoDao.selectByUserName(user.getUserName());
			userDto.setUserName(user.getUserName());
			userDto.setRole(user.getRole());
			userDto.setDepartment(userInfo.getDepartment());
			userDto.setEmail(userInfo.getEmail());
			userDto.setName(userInfo.getName());
			userDto.setCreateTime(userInfo.getCreateTime());
			userDto.setUserId(userInfo.getUserId());
			return userDto;
		}else{
			return null;
		}
		
		
	}
}

这是自己当年上学时某个项目中的一个实现用户登录的逻辑，以现在的眼光或者说现在的经验来看，感觉命名糟糕的一踏糊涂。首先是类的命名，类的命名应该是一个名词，因为一个对象其方法才是具体的行为，在这里我用login作为命名一眼看过去就好像这整个类都在做登录这个动作，但实际上类代表的不是一个动作，这很不面向对象。其次是对象UserDto和userDao也意义不明，一眼看去根本不知道这个类到底是用来干嘛的。所以正如书中说的那样变量、函数或类的名称应该已经答复了所有的大问题。它应该告诉你，它为什么会存在，它做什么事情，应该怎么用。
还有一点避免使用编码，没有理由要求每位新人都在弄清楚要应付的代码之外，还要再搞懂另一种编码“语言”。感觉自己刚刚进公司就常常犯这种错误，比如xxxList，xxxSet之类的带有鲜明语言特色的东西，其实对阅读代码的人毫无帮助反而徒增了很多负担。在看看下面的一个排序代码：

int main(void){
    int array[5] ={4,2,1,4,5};
    selectSort(array,5);
    for(int i=0;i<5;j++){
        printf("%d",array[i]);
    }
    return 0;
}

初学编程我们每个人应该都写过这样的排序代码，那在命名层面其有什么不妥呢？首先在代码开头定义的array变量就很意义不明，数组这一单词带有明显的编码色彩。其次是selectSort的函数命名，看起来是要排序，但是select是什么鬼，取出排序？对于函数命名应该言简意赅，意义明确，使用动词表达清其要做的事情，所以这里单纯用sort其实更好。最后是for循环的终止条件5，5这个数字在这段代码中表示什么？它在循环中表示什么的终止？显然这些问题仅仅靠单纯一个数字是没办法回答的。虽然这个程序现在很短小我们结合上下文阅读立马就可以反应过来，这个5是需要排序数组的大小，是待排数据的极值。但是如果程序变得很长很长呢，想象一下，你已经读了100来行代码了，现在又要求你回过头去结合上下文理解这个5的含义，任谁都会吐槽诅咒写的人吧。所以在编码中我们需要将这类意义不明的数字“5”换作一个具有意义的变量来表示其作用职责。
对于命名书中还涉及到了很多原则，在此就不做过多展开了，有兴趣可以去翻翻原作。由此看以看出，就单纯一项命名已经很考验编程功底了，所以千万不要胡乱命名给自己他人造成麻烦。

函数

短小，只做好一件事情。这是我对书中关于函数部分的最大印象。

短小
即函数尽量要短，其实这个准则应该最大的好处就是读起来很很简单吧。按照作者的话说就是，每个函数都依序把你带到下一个函数。这就是函数应该达到的短小程度！！！即当我们面对一个长长的函数时，应该对其进行拆分将里面过长的内容拆分成一个个的小函数。这样不仅仅读的人赏心悦目，修改起来也很方便。
只做好一件事
个人感觉这条是最难以把握的，因为往往分不清这件事是不是应该这个函数做还是需要单独拆分。比如getStudentInfoById这个函数，根据名称来看应该是通过id获取学生信息，听起来貌似只需要从数据库中拿出学生信息并返回就可以了，但是学生信息还需要各种处理，比如需要有顺序的返回，或者说某些信息需要转换后返回，这些操作看起来与拿这个动作无关，但是确实是属于这个函数的附属品，不可能在函数名称中体现到这么多操作。其实，只要确保函数中的内容都在同一抽象级就好了，刚才说的各种对信息的处理其实可以拆分成使用formatXXX之类的函数完成，那么我们这个getStudentInfoById的函数就一共分为了两步，第一步从数据库拿出学生信息，第二部对其进行格式化。格式化与从数据库拿出这两个操作均在函数的同一抽象层，所以这两个操作都可以看作是为了完成拿出学生准确信息这一操作。

判断函数是否不止做了一件事，就是看是否能再拆岀一个函数，该函数不仅只是单纯地重新诠释其实现。

注释

这里我就记住一句话，唯一真正好的注释是你想办法不去写的注释
尽量用代码去解释函数、类的行为，带有少量注释的整洁而有表达力的代码，要比大量注释的零碎而复杂的代码像样的多。

格式

代码格式很重要，感觉作者再书中不断强调这一点。尤其是一个项目团队大家都应当按照相同的格式去编写代码，这样有利于维护代码。从上往下的垂直格式总是必要的，还有最外层的文件的抽象概念由外到里依次变得细节。
运算符之间加空格区分：

a = b + 2

不同的区块也应该分割下，函数开头一般都是变量声明初始化之类的，所以就应该在初始化变量完成后，多一个换行之类的与接下来的代码区分，以此利于阅读。总之不管用什么风格，同一个团队应该保持一致，这样在后续开发中项目整体才比较容易维护，不同人不同的风格就会造成巨大的混乱，最终导致源代码不可读，不可维护。

对象和数据结构

当功能点需要常常添加新的结构时使用面向对象，需要常常添加新的方法行为使用面向过程
所以说无论是面向对象或者是面向过程都是方法论，业务才是一切，没有永远适合的，只有当前适合的。
一切都是对象只是一个传说

错误处理

这个仁者见仁智者见智，我只想说书中关于只使用异常的做法以前我可能会很认同，但最近在使用了go语言之后，对于没有异常处理机制的语言来说只使用异常就不再可能了，所以说看待问题还是不能太死板，没有什么是一成不变的，也没有绝对的真理。

类

类应该短小，且遵循单一权责原则，即类或者模块应有且只有一条加以修改的理由。
类应该只有少量实体变量，类中的每个方法都应该操作一个或多个这种变量，即类要保持内聚性。
如果说有很多方法并没有黏聚到类上，又或者为了保持函数和参数列表短小的策略，有时会导致为一组子集方法所用的实体变量数量增加。出现这种情况，就要拆分岀新的类了。

结构体定义

相关操作方法定义

完整代码

最后

调度层次

调度算法

进程控制块

进程同步

两种制约关系

同步机制应遵循的规则

进程同步机制

进程通信

线程

intset的结构体

intset的函数

intset的主要运行

创建一个新的整数集合

添加新元素到 intset

添加新元素到 intset(需要升级)

redis跳跃表的实现

redis跳跃表的应用

总结

概念

redis中字典的应用

字典的实现

哈希表实现

哈希算法

dictCreate函数

添加键值对到字典

添加新元素到空白字典

添加新键值对时发生碰撞处理

添加新键值对时触发了rehash操作

Rehash执行过程

渐进式rehash

字典的收缩

字典的迭代

总结

redis中双端链表的应用

redis的列表类型

redis自身功能

双端链表的实现

迭代器

总结

Redis中的字符串

sds实现

字符串追加操作的优化

最后

有意义的命名

函数

注释

格式

对象和数据结构

错误处理

类