Redis-pqsort

1.pqsort原理分析

2.源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <sys/types.h>
#include <errno.h>
#include <stdlib.h>
static inline char *med3 (char *, char *, char *,
int (*)(const void *, const void *));
static inline void swapfunc (char *, char *, size_t, int);
#define min(a, b) (a) < (b) ? a : b
/*
* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
*/
#define swapcode(TYPE, parmi, parmj, n) { \
//i means es包含多少个TYPE \
size_t i = (n) / sizeof (TYPE); \
TYPE *pi = (TYPE *)(void *)(parmi); \
TYPE *pj = (TYPE *)(void *)(parmj); \
do { \
TYPE t = *pi; \
*pi++ = *pj; \
*pj++ = t; \
} while (--i > 0); \
}
/*
swaptype:
0: es == sizeof(long)
1: a或者es为sizeof(long)整数倍,但是es != sizeof(long)
2: a和es都不是sizeof(long)的整数倍
*/
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
//n = es, ie交换的a和b指向的元素的内存大小
static inline void
swapfunc(char *a, char *b, size_t n, int swaptype)
{
if (swaptype <= 1)
swapcode(long, a, b, n)
else
swapcode(char, a, b, n)
}
//交换a和b指向的内存
#define swap(a, b) \
if (swaptype == 0) { \
long t = *(long *)(void *)(a); \
*(long *)(void *)(a) = *(long *)(void *)(b); \
*(long *)(void *)(b) = t; \
} else \
swapfunc(a, b, es, swaptype) //swaptype =1或者2
#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
//找到a, b, c的中间值
static inline char *
med3(char *a, char *b, char *c,
int (*cmp) (const void *, const void *))
{
return cmp(a, b) < 0 ?
(cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
:(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
}
static void
_pqsort(void *a, size_t n, size_t es,
int (*cmp) (const void *, const void *), void *lrange, void *rrange)
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
size_t d, r;
int swaptype, cmp_result;
//init swaptype
loop: SWAPINIT(a, es);
if (n < 7) {
//采用插入排序
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
pm = (char *) a + (n / 2) * es;
if (n > 7) {
pl = (char *) a;
pn = (char *) a + (n - 1) * es;
if (n > 40) {
d = (n / 8) * es;
pl = med3(pl, pl + d, pl + 2 * d, cmp);
pm = med3(pm - d, pm, pm + d, cmp);
pn = med3(pn - 2 * d, pn - d, pn, cmp);
}
pm = med3(pl, pm, pn, cmp);
}
swap(a, pm);
pa = pb = (char *) a + es;
pc = pd = (char *) a + (n - 1) * es;
//快排
for (;;) {
//pa左边的都是等于a[0]的元素
while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
if (cmp_result == 0) {
swap(pa, pb);
pa += es;
}
pb += es;
}
//pd右边的都是等于a[0]的元素
while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
if (cmp_result == 0) {
swap(pc, pd);
pd -= es;
}
pc -= es;
}
if (pb > pc)
break;
swap(pb, pc);
pb += es;
pc -= es;
}
pn = (char *) a + n * es;
//pb-pa=小于a[0]的Bytes
r = min(pa - (char *) a, pb - pa);
vecswap(a, pb - r, r);
//
r = min((size_t)(pd - pc), pn - pd - es);
vecswap(pb, pn - r, r);
//left
if ((r = pb - pa) > es) {
void *_l = a, *_r = ((unsigned char*)a)+r-1;
if (!((lrange < _l && rrange < _l) ||
(lrange > _r && rrange > _r)))
_pqsort(a, r / es, es, cmp, lrange, rrange);
}
//right
if ((r = pd - pc) > es) {
void *_l, *_r;
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
_l = a;
_r = ((unsigned char*)a)+r-1;
if (!((lrange < _l && rrange < _l) ||
(lrange > _r && rrange > _r)))
goto loop;
}
/* qsort(pn - r, r / es, es, cmp);*/
}
/*
sort a[lrange, rrange]
es: ElementSize
a: array
n: 数组元素个数
cmp: CallBack Func
*/
void
pqsort(void *a, size_t n, size_t es,
int (*cmp) (const void *, const void *), size_t lrange, size_t rrange)
{
_pqsort(a,n,es,cmp,((unsigned char*)a)+(lrange*es),
((unsigned char*)a)+((rrange+1)*es)-1);
}

STL-目录

1.目录

C++对象模型-目录

1.目录

  1. 大端法/小端法
  2. 基础类型的内存表示, 24 bits解析为有符号整数
  3. 数组内存布局
  4. 函数调用过程
  5. 函数调用过程:Class Object作为函数参数
  6. Class Objec
  7. Virtual Base Class
  8. 引用
  9. ObjectSlice
  10. Default Constructor
  11. Non-Staitc成员函数
  12. Operator Delete异常分析
  13. switch/if-else实现机制

2.参考文献

《深度探索C++对象模型》
《CSAPP中文第二版》
《程序员的自我修养》
《C++反汇编与逆向分析技术揭秘》
《老码识途》

Round up to the next highest power of 2

version1

1
2
3
4
5
6
static unsigned int power2gt(unsigned int size) {
while (1) {
if (i >= size) return i;
i *= 2;
}
}

version2

1
2
3
4
5
6
7
8
9
static unsigned int power2gt(unsigned int size) {
--size;
size |= size >> 1;
size |= size >> 2;
size |= size >> 4;
size |= size >> 8;
size |= size >> 16;
return size + 1;
}

参考资料

  1. the explanation of version2:here
  2. Reidis#issue4776

Atoi&Itoa函数

  • atoi函数实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*************************************************************************
> File Name: Atoi.c
> Author: qinchao
> Mail: 1187620726@qq.com
> Created Date:2018-01-28 Time:04:36:18.
************************************************************************/
// 32bits无符号整数表示范围[0, 2^32-1]
#define UINTEGER32_MAX (4294967295)
// 32bits有符号整数表示范围为[-2^31, 2^31-1]
#define INTEGER32_MAX (2147483647)
#define INTEGER32_MIN (-2147483648)
int Atoi(const char *str) {
unsigned int value = 0;
// 1表示负数,0表示整数
int negative = 0;
//判断str指针非NULL
if (str != NULL) {
//判断是否为负数
if (str[0] == '-') {
negative = 1;
str++;
}
else if (str[0] == '+') {
str++;
}
// str指向的字符串以0结尾
while (str[0] != '\0') {
if (str[0] >= '0' && str[0] <= '9') {
//判断value是否会溢出
if (value > UINTEGER32_MAX / 10) return 0;
value *= 10;
//判断value是否会溢出
if (value > UINTEGER32_MAX - (str[0] - '0')) return 0;
value += (str[0] - '0');
str++;
} else {
//含有非法字符,value的值返回0
value = 0;
break;
}
}
if (str[0] == '\0') {
if (negative) //负数
{
// INT32_MINI = -(INT32_MAX+1)
if (value > (unsigned int)(INTEGER32_MAX + 1)) return 0;
return -value;
} else { //正数
if (value > INTEGER32_MAX) return 0;
return value;
}
}
}
return value;
}

redis4.0_输入/输出缓冲区处理

之前读了一下redis事件处理器的代码点我,今天无所事事,看了下redis对输入缓冲区(querybuf)和输出缓冲区(buf/replylist)的代码,记录一下学习过程。

1. 读缓冲区处理

读取fd数据,然后放入client的输入缓冲区(querybuf)的整个调用栈如下:

1
2
3
4
5
6
7
8
9
10
1211 int processMultibulkBuffer(client *c) {
(gdb) bt
#0 processMultibulkBuffer (c=c@entry=0x7ffff6f15e00) at networking.c:1211
#1 0x000000000043c736 in processInputBuffer (c=0x7ffff6f15e00)
at networking.c:1408
#2 0x00000000004262de in aeProcessEvents (
eventLoop=eventLoop@entry=0x7ffff6e340a0, flags=flags@entry=11) at ae.c:452
#3 0x000000000042670b in aeMain (eventLoop=0x7ffff6e340a0) at ae.c:495
#4 0x00000000004232d6 in main (argc=<optimized out>, argv=0x7fffffffe3e8)
at server.c:3897

redis4.0_发布/订阅

1. channel的订阅与退订

  • UBSCRIBE, UNSUBSCRIBE and PUBLISH implement the Publish/Subscribe messaging paradigm where senders (publishers) are not programmed to send their messages to specific receivers (subscribers). Rather, published messages are characterized into channels, without knowledge of what (if any) subscribers there may be. Subscribers express interest in one or more channels, and only receive messages that are of interest, without knowledge of what (if any) publishers there are.

  • Messages sent by other clients to these channels will be pushed by Redis to all the subscribed clients.

  • A client subscribed to one or more channels should not issue commands, although it can subscribe and unsubscribe to and from other channels. The replies to subscription and unsubscription operations are sent in the form of messages, so that the client can just read a coherent stream of messages where the first element indicates the type of message. The commands that are allowed in the context of a subscribed client are SUBSCRIBE, PSUBSCRIBE, UNSUBSCRIBE, PUNSUBSCRIBE, PING and QUIT.

    • Please note that redis-cli will not accept any commands once in subscribed mode and can only quit the mode with Ctrl-C.
  • channel订阅实现:在客户端结构体的pubsub_channels(为dict)添加key为订阅的channel的entry,在server结构体的pubsub_chanels(dict)添加key为channel的entry,该entry为所有订阅该channel的list

2.Pattern-matching订阅与退订

  • The Redis Pub/Sub implementation supports pattern matching. Clients may subscribe to glob-style patterns in order to receive all the messages sent to channel names matching a given pattern.

  • pattern订阅实现:在客户端结构体的pubsub_patterns(为list)添加node,该node的value为订阅的pattern(robj),在server结构体的pubsub_patterns(为list)添加pubsubPattern Node,该node的client为订阅该pattern的客户端指针,该pattern为订阅pattern的robj.

1
2
3
4
5
//src/server.h
typedef struct pubsubPattern {
client *client;
robj *pattern;
} pubsubPattern;

3.源码分析

  • 订阅channel代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /* Subscribe a client to a channel. Returns 1 if the operation succeeded, or
    * 0 if the client was already subscribed to that channel. */
    int pubsubSubscribeChannel(client *c, robj *channel) {
    dictEntry *de;
    list *clients = NULL;
    int retval = 0;
    /* Add the channel to the client -> channels hash table */
    //将订阅的channel添加到client结构体的pubsub_channels字典
    //key为channel
    if (dictAdd(c->pubsub_channels,channel,NULL) == DICT_OK) {
    retval = 1;
    incrRefCount(channel);
    /* Add the client to the channel -> list of clients hash table */
    //将channel添加到server的pubsub_channels字典
    //首先在dict中查找是否该channel存在,如果存在,将c添加到entry的value链表中
    //如果不存在,在字典中添加entry,该entry的key为robj,value为client的链表
    de = dictFind(server.pubsub_channels,channel);
    if (de == NULL) {
    //den=NULL表示该channel在dict不存在
    clients = listCreate();
    dictAdd(server.pubsub_channels,channel,clients);
    //robj引用+1
    incrRefCount(channel);
    } else {
    //该channel在dict中已经存在
    clients = dictGetVal(de);
    }
    listAddNodeTail(clients,c);
    }
    /* Notify the client */
    addReply(c,shared.mbulkhdr[3]);
    addReply(c,shared.subscribebulk);
    addReplyBulk(c,channel);
    addReplyLongLong(c,clientSubscriptionsCount(c));
    return retval;
    }
  • 订阅pattern代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* Subscribe a client to a pattern. Returns 1 if the operation succeeded, or 0 if the client was already subscribed to that pattern. */
//订阅一个pattern
int pubsubSubscribePattern(client *c, robj *pattern) {
int retval = 0;
//首先查找链表中是否存在该pattern
if (listSearchKey(c->pubsub_patterns,pattern) == NULL) {
retval = 1;
pubsubPattern *pat;
//如果不存在,则添加到client的pubsub_patterns链表结尾
listAddNodeTail(c->pubsub_patterns,pattern);
//增加引用计数
incrRefCount(pattern);
//将该pattern添加到server的pubsub_patterns链表
pat = zmalloc(sizeof(*pat));
pat->pattern = getDecodedObject(pattern);
pat->client = c;
listAddNodeTail(server.pubsub_patterns,pat);
}
/* Notify the client */
addReply(c,shared.mbulkhdr[3]);
addReply(c,shared.psubscribebulk);
addReplyBulk(c,pattern);
addReplyLongLong(c,clientSubscriptionsCount(c));
return retval;
}

4.参考文献

redis.io

redis_reading

redis4.0_Transactions源码剖析

1.Transactions

  • MULTI, EXEC, DISCARD and WATCH are the foundation of transactions in Redis. They allow the execution of a group of commands in a single step, with two important guarantees:

    • All the commands in a transaction are serialized and executed sequentially. It can never happen that a request issued by another client is served in the middle of the execution of a Redis transaction. This guarantees that the commands are executed as a single isolated operation(隔离性).

    • Either all of the commands or none are processed, so a Redis transaction is also atomic(原子性).

  • WATCH命令

    • 在对应的db结构体中用dict保存WATCHed keys,其中dict的entry的key为WATCHed key robj,value为一个链表,链表的每个Node指向一个Client的指针(表示该client WATCHed该key)

    • 在每个client结构体中用链表保存了该客户端WATCHed的key的robj,和该key对应的db指针