-
Notifications
You must be signed in to change notification settings - Fork 243
/
Copy patht_list.c
1699 lines (1415 loc) · 61.1 KB
/
t_list.c
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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Redis nor the names of its contributors may be used
* to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#include "server.h"
/*-----------------------------------------------------------------------------
* List API
*----------------------------------------------------------------------------*/
/* The function pushes an element to the specified list object 'subject',
* at head or tail position as specified by 'where'.
*
* There is no need for the caller to increment the refcount of 'value' as
* the function takes care of it if needed. */
/* 该函数将一个元素插入到指定的列表对象 'subject'，
* 插入位置由 'where' 决定是在列表头部还是尾部插入，
* 调用者不需要自己来增加 'value' 的 refcount， 因为该函数会负责处理 */
void listTypePush(robj *subject, robj *value, int where) {
/* 检查编码类型是否为 quicklist (快速列表) */
if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
/* 根据参数 where 选择插入位置，由 pos 保存插入位置信息 */
int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;
/* value 为整数编码 */
if (value->encoding == OBJ_ENCODING_INT) {
/* 将 value 先转换为字符串 */
char buf[32];
ll2string(buf, 32, (long)value->ptr);
/* 将元素插入列表 */
quicklistPush(subject->ptr, buf, strlen(buf), pos);
/* value 为字符串编码 */
} else {
quicklistPush(subject->ptr, value->ptr, sdslen(value->ptr), pos);
}
} else {
serverPanic("Unknown list encoding");
}
}
/* 用于给列表弹出的元素创建副本的函数 */
void *listPopSaver(unsigned char *data, size_t sz) {
return createStringObject((char*)data,sz);
}
/* 弹出列表元素的通用实现函数 */
robj *listTypePop(robj *subject, int where) {
long long vlong;
robj *value = NULL;
/* 根据参数 where 选择插入位置，由 ql_where 保存插入位置信息 */
int ql_where = where == LIST_HEAD ? QUICKLIST_HEAD : QUICKLIST_TAIL;
/* 检查编码类型是否为 quicklist (快速列表) */
if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
/* 从列表中弹出元素 */
if (quicklistPopCustom(subject->ptr, ql_where, (unsigned char **)&value,
NULL, &vlong, listPopSaver)) {
/* 如果 value 为 NULL ，则弹出元素被保存在 vlong 中（若不为 NULL 则说明保存在 value 中）
* 则用 vlong 创建一个字符串对象并让 value 对其引用 */
if (!value)
value = createStringObjectFromLongLong(vlong);
}
} else {
serverPanic("Unknown list encoding");
}
return value;
}
/* 获取列表长度（元素总数） */
unsigned long listTypeLength(const robj *subject) {
if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
return quicklistCount(subject->ptr);
} else {
serverPanic("Unknown list encoding");
}
}
/* Initialize an iterator at the specified index. */
/* 在指定的索引处初始化一个列表迭代器 */
listTypeIterator *listTypeInitIterator(robj *subject, long index,
unsigned char direction) {
/* 给列表迭代器分配内存空间 */
listTypeIterator *li = zmalloc(sizeof(listTypeIterator));
/* 初始化列表迭代器 */
li->subject = subject;
li->encoding = subject->encoding;
li->direction = direction;
li->iter = NULL;
/* LIST_HEAD means start at TAIL and move *towards* head.
* LIST_TAIL means start at HEAD and move *towards* tail. */
/* LIST_HEAD 意味着从列表尾部开始，并向头部移动。
* LIST_TAIL 表示从列表头部开始，并向尾部移动 */
int iter_direction =
direction == LIST_HEAD ? AL_START_TAIL : AL_START_HEAD;
/* 检查编码类型是否为 quicklist (快速列表) */
if (li->encoding == OBJ_ENCODING_QUICKLIST) {
/* 初始化一个 quicklist 节点的迭代器，并且该迭代器指向列表的第 index 个元素，
* 虽然用词是”指向“但是迭代器并不是一个指针，而是个结构体，它记录的元素信息是列表第 index 个元素 */
li->iter = quicklistGetIteratorAtIdx(li->subject->ptr,
iter_direction, index);
} else {
serverPanic("Unknown list encoding");
}
return li;
}
/* Sets the direction of an iterator. */
/* 设置迭代器的方向 */
void listTypeSetIteratorDirection(listTypeIterator *li, unsigned char direction) {
li->direction = direction;
int dir = direction == LIST_HEAD ? AL_START_TAIL : AL_START_HEAD;
quicklistSetDirection(li->iter, dir);
}
/* Clean up the iterator. */
/* 释放迭代器 */
void listTypeReleaseIterator(listTypeIterator *li) {
quicklistReleaseIterator(li->iter);
zfree(li);
}
/* Stores pointer to current the entry in the provided entry structure
* and advances the position of the iterator. Returns 1 when the current
* entry is in fact an entry, 0 otherwise. */
/* 获取迭代器指向元素的下一个元素，并推进迭代器的位置（推进方向由迭代器成员 direction 决定）。
* 如果 entry(下一个元素) 存在，返回1，否则返回0 */
int listTypeNext(listTypeIterator *li, listTypeEntry *entry) {
/* Protect from converting when iterating */
/* 保护迭代时编码不被转换，则需要迭代器记录的编码类型和迭代器指向的列表对象编码一致 */
serverAssert(li->subject->encoding == li->encoding);
/* 将参数 li 赋值给参数 entry 的迭代器成员 */
entry->li = li;
/* 检查编码类型是否为 quicklist (快速列表) */
if (li->encoding == OBJ_ENCODING_QUICKLIST) {
/* 调用 quicklistNext 函数获取下一个元素，
* 元素 (quicklistEntry) 保存在 entry->entry 中，并推进迭代器位置
* 如果 下一个元素存在，该函数返回1，否则返回0 */
return quicklistNext(li->iter, &entry->entry);
} else {
serverPanic("Unknown list encoding");
}
return 0;
}
/* Return entry or NULL at the current position of the iterator. */
/* 获取元素的值 */
robj *listTypeGet(listTypeEntry *entry) {
robj *value = NULL;
/* 检查编码类型是否为 quicklist (快速列表) */
if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) {
/* 元素的值保存在 value 中 */
if (entry->entry.value) {
/* value = 使用当前元素创建的字符串对象 */
value = createStringObject((char *)entry->entry.value,
entry->entry.sz);
/* 元素的值保存在 longval 中 */
} else {
/* value = 使用当前（整型）元素创建的字符串对象 */
value = createStringObjectFromLongLong(entry->entry.longval);
}
} else {
serverPanic("Unknown list encoding");
}
return value;
}
/* 在 entry 的位置前或后方插入元素 value */
void listTypeInsert(listTypeEntry *entry, robj *value, int where) {
/* 检查编码类型是否为 quicklist (快速列表) */
if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) {
/* 获取解码后的 value（实际上是让编码为INT的 value 转为字符串形式（raw 或 embstr））*/
value = getDecodedObject(value);
/* 令 str = value（字符串值），len = value 字符串长度 */
sds str = value->ptr;
size_t len = sdslen(str);
/* 在 entry 后方插入元素 */
if (where == LIST_TAIL) {
quicklistInsertAfter(entry->li->iter, &entry->entry, str, len);
/* 在 entry 前方插入元素 */
} else if (where == LIST_HEAD) {
quicklistInsertBefore(entry->li->iter, &entry->entry, str, len);
}
/* value 的被引用次数 -1 ，value 被引用次数为0时将被释放 */
decrRefCount(value);
} else {
serverPanic("Unknown list encoding");
}
}
/* Replaces entry at the current position of the iterator. */
/* 替换 entry 中的元素 */
void listTypeReplace(listTypeEntry *entry, robj *value) {
/* 检查编码类型是否为 quicklist (快速列表) */
if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) {
/* 获取解码后的 value（实际上是让编码为INT的 value 转为字符串形式（raw 或 embstr））*/
value = getDecodedObject(value);
/* 令 str = value（字符串值），len = value 字符串长度 */
sds str = value->ptr;
size_t len = sdslen(str);
/* 用 value 替换 entry 中的元素 */
quicklistReplaceEntry(entry->li->iter, &entry->entry, str, len);
/* value 的被引用次数 -1 ，value 被引用次数为0时将被释放 */
decrRefCount(value);
} else {
serverPanic("Unknown list encoding");
}
}
/* Compare the given object with the entry at the current position. */
/* 比较两个元素是否相同 */
int listTypeEqual(listTypeEntry *entry, robj *o) {
/* 检查编码类型是否为 quicklist (快速列表) */
if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) {
/* 使用断言确保 o 内部编码为字符串（raw 或 embstr） */
serverAssertWithInfo(NULL,o,sdsEncodedObject(o));
/* 调用比较函数进行比较，相同返回1，不相同返回0 */
return quicklistCompare(&entry->entry,o->ptr,sdslen(o->ptr));
} else {
serverPanic("Unknown list encoding");
}
}
/* Delete the element pointed to. */
/* 删除元素 */
void listTypeDelete(listTypeIterator *iter, listTypeEntry *entry) {
/* 检查编码类型是否为 quicklist (快速列表) */
if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) {
/* 调用删除函数将元素删除 */
quicklistDelEntry(iter->iter, &entry->entry);
} else {
serverPanic("Unknown list encoding");
}
}
/* This is a helper function for the COPY command.
* Duplicate a list object, with the guarantee that the returned object
* has the same encoding as the original one.
*
* The resulting object always has refcount set to 1 */
/* 这是一个用于 COPY 命令的辅助函数。
* 复制一个列表对象，并保证返回的对象具有与原始对象相同的编码。
* 返回的对象总是将 refcount 设置为1 */
robj *listTypeDup(robj *o) {
robj *lobj;
/* 使用断言确保 o 类型为列表 */
serverAssert(o->type == OBJ_LIST);
switch (o->encoding) {
/* 检查编码类型是否为 quicklist (快速列表) */
case OBJ_ENCODING_QUICKLIST:
/* 创建 o 的副本 lobj */
lobj = createObject(OBJ_LIST, quicklistDup(o->ptr));
lobj->encoding = o->encoding;
break;
default:
serverPanic("Unknown list encoding");
break;
}
return lobj;
}
/* Delete a range of elements from the list. */
/* 在列表中删除一个指定范围内的元素 */
int listTypeDelRange(robj *subject, long start, long count) {
/* 检查编码类型是否为 quicklist (快速列表) */
if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
/* 调用范围删除函数进行删除 */
return quicklistDelRange(subject->ptr, start, count);
} else {
serverPanic("Unknown list encoding");
}
}
/*-----------------------------------------------------------------------------
* List Commands
*----------------------------------------------------------------------------*/
/* Implements LPUSH/RPUSH/LPUSHX/RPUSHX.
* 'xx': push if key exists. */
/* push 命令通用实现函数
* 实现的命令：LPUSH/RPUSH/LPUSHX/RPUSHX
* 'xx': 如果 key 存在才能插入 */
void pushGenericCommand(client *c, int where, int xx) {
int j;
/* 获取 key 对应的 Redis 对象 */
robj *lobj = lookupKeyWrite(c->db, c->argv[1]);
/* 检查对象类型是否为 list，若不是 list 返回 true */
if (checkType(c,lobj,OBJ_LIST)) return;
/* 对象不存在 */
if (!lobj) {
/* 如果是 LPUSHX/RPUSHX 这类命令，key 不存在将不做操作 */
if (xx) {
/* 向客户端返回0并且退出函数 */
addReply(c, shared.czero);
return;
}
/* 创建 quicklist 对象 */
lobj = createQuicklistObject();
/* 初始设置 quicklist 对象（设置填充系数 fill 和压缩配置 compress） */
quicklistSetOptions(lobj->ptr, server.list_max_listpack_size,
server.list_compress_depth);
/* 将 quicklist 对象加入到数据库 */
dbAdd(c->db,c->argv[1],lobj);
}
/* 读取输入的元素，并向列表插入元素 */
for (j = 2; j < c->argc; j++) {
listTypePush(lobj,c->argv[j],where);
/* 脏数据 + 1，即缓存中未保存到本地的数据 */
server.dirty++;
}
/* 向客户端回复列表长度 */
addReplyLongLong(c, listTypeLength(lobj));
char *event = (where == LIST_HEAD) ? "lpush" : "rpush";
/* 发送 key 被修改信号 */
signalModifiedKey(c,c->db,c->argv[1]);
/* 发送事件通知（用于发布/订阅功能） */
notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
}
/* LPUSH <key> <element> [<element> ...] */
/* 处理 lpush 命令的函数 */
void lpushCommand(client *c) {
pushGenericCommand(c,LIST_HEAD,0);
}
/* RPUSH <key> <element> [<element> ...] */
/* 处理 rpush 命令的函数 */
void rpushCommand(client *c) {
pushGenericCommand(c,LIST_TAIL,0);
}
/* LPUSHX <key> <element> [<element> ...] */
/* 处理 lpushx 命令的函数 */
void lpushxCommand(client *c) {
pushGenericCommand(c,LIST_HEAD,1);
}
/* RPUSH <key> <element> [<element> ...] */
/* 处理 rpushx 命令的函数 */
void rpushxCommand(client *c) {
pushGenericCommand(c,LIST_TAIL,1);
}
/* LINSERT <key> (BEFORE|AFTER) <pivot> <element> */
/* 处理 linsert 命令的函数 */
void linsertCommand(client *c) {
int where;
robj *subject;
listTypeIterator *iter;
listTypeEntry entry;
int inserted = 0;
/* 解析插入方向参数，确定插入方向 */
if (strcasecmp(c->argv[2]->ptr,"after") == 0) {
where = LIST_TAIL;
} else if (strcasecmp(c->argv[2]->ptr,"before") == 0) {
where = LIST_HEAD;
} else {
/* 向客户端回复语法错误，并退出函数 */
addReplyErrorObject(c,shared.syntaxerr);
return;
}
/* 获取 key 对应的对象，之后检查对象类型 */
if ((subject = lookupKeyWriteOrReply(c,c->argv[1],shared.czero)) == NULL ||
checkType(c,subject,OBJ_LIST)) return;
/* Seek pivot from head to tail */
/* 从列表的头到尾部遍历寻找 pivot ，我们要插入在输入参数 pivot 所代表的元素的前或后方 */
/* 初始化列表迭代器 */
iter = listTypeInitIterator(subject,0,LIST_TAIL);
/* 遍历寻找 */
while (listTypeNext(iter,&entry)) {
/* 找到与 pivot 相等的元素 */
if (listTypeEqual(&entry,c->argv[3])) {
/* 插入元素 */
listTypeInsert(&entry,c->argv[4],where);
inserted = 1;
break;
}
}
/* 释放迭代器 */
listTypeReleaseIterator(iter);
/* 插入成功 */
if (inserted) {
signalModifiedKey(c,c->db,c->argv[1]);
notifyKeyspaceEvent(NOTIFY_LIST,"linsert",
c->argv[1],c->db->id);
server.dirty++;
} else {
/* Notify client of a failed insert */
/* 回复客户端插入失败，即回复 -1 */
addReplyLongLong(c,-1);
return;
}
addReplyLongLong(c,listTypeLength(subject));
}
/* LLEN <key> */
/* 处理 llen 命令的函数 */
void llenCommand(client *c) {
/* 获取 key 对应的对象 */
robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero);
/* 检查对象是否为空和对象类型 */
if (o == NULL || checkType(c,o,OBJ_LIST)) return;
/* 回复列表长度 */
addReplyLongLong(c,listTypeLength(o));
}
/* LINDEX <key> <index> */
/* 处理 lindex 命令的函数 */
void lindexCommand(client *c) {
/* 获取 key 对应的对象 */
robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.null[c->resp]);
/* 检查对象是否为空和对象类型 */
if (o == NULL || checkType(c,o,OBJ_LIST)) return;
long index;
/* 解析 index 参数 */
if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != C_OK))
return;
/* 对象内部编码为 quicklist */
if (o->encoding == OBJ_ENCODING_QUICKLIST) {
quicklistEntry entry;
/* 创建 index 位置的迭代器 */
quicklistIter *iter = quicklistGetIteratorEntryAtIdx(o->ptr, index, &entry);
/* 迭代器 iter 存在 */
if (iter) {
/* 元素的值为字符串类型，则保存在 value */
if (entry.value) {
addReplyBulkCBuffer(c, entry.value, entry.sz);
/* 元素的值为整数类型，则保存在 longval */
} else {
addReplyBulkLongLong(c, entry.longval);
}
/* 迭代器 iter 不存在 */
} else {
addReplyNull(c);
}
/* 释放迭代器 */
quicklistReleaseIterator(iter);
} else {
serverPanic("Unknown list encoding");
}
}
/* LSET <key> <index> <element> */
/* 处理 lset 命令的函数 */
void lsetCommand(client *c) {
robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.nokeyerr);
if (o == NULL || checkType(c,o,OBJ_LIST)) return;
long index;
/* 获取输入的元素 (element) */
robj *value = c->argv[3];
/* 获取输入的索引 (index) */
if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != C_OK))
return;
if (o->encoding == OBJ_ENCODING_QUICKLIST) {
/* 获取快速列表 */
quicklist *ql = o->ptr;
/* 调用 quicklistReplaceAtIndex 函数替换 index 上的元素 */
int replaced = quicklistReplaceAtIndex(ql, index,
value->ptr, sdslen(value->ptr));
/* 元素替换失败 */
if (!replaced) {
/* 向客户端回复错误信息（范围越界） */
addReplyErrorObject(c,shared.outofrangeerr);
} else {
/* 向客户端回复 "ok" */
addReply(c,shared.ok);
/* 发送 key 被修改信号，发送事件通知，脏数据 + 1*/
signalModifiedKey(c,c->db,c->argv[1]);
notifyKeyspaceEvent(NOTIFY_LIST,"lset",c->argv[1],c->db->id);
server.dirty++;
}
} else {
serverPanic("Unknown list encoding");
}
}
/* A helper function like addListRangeReply, more details see below.
* The difference is that here we are returning nested arrays, like:
* 1) keyname
* 2) 1) element1
* 2) element2
*
* And also actually pop out from the list by calling listElementsRemoved.
* We maintain the server.dirty and notifications there.
*
* 'deleted' is an optional output argument to get an indication
* if the key got deleted by this function. */
/* 一个辅助函数，如 addListRangeReply，更多细节见下文。
* 不同的是，这里我们返回的是嵌套数组，比如：
* 1) keyname
* 2) 1) element1
* 2) element2
*
* 通过调用 listElementsRemoved 从列表中弹出元素。
* 我们在 listElementsRemoved 函数中维护 server.dirty 和事件通知。
*
* 'deleted' 是一个可选的输出参数，含义为是否有 key 被删除（有为1，没有为0） */
void listPopRangeAndReplyWithKey(client *c, robj *o, robj *key, int where, long count, int *deleted) {
long llen = listTypeLength(o);
long rangelen = (count > llen) ? llen : count;
long rangestart = (where == LIST_HEAD) ? 0 : -rangelen;
long rangeend = (where == LIST_HEAD) ? rangelen - 1 : -1;
int reverse = (where == LIST_HEAD) ? 0 : 1;
/* We return key-name just once, and an array of elements */
/* 我们只返回一次 key 的名称，以及一个指定范围内的元素数组 */
addReplyArrayLen(c, 2);
addReplyBulk(c, key);
addListRangeReply(c, o, rangestart, rangeend, reverse);
/* Pop these elements. */
/* 弹出范围内的元素 */
listTypeDelRange(o, rangestart, rangelen);
/* Maintain the notifications and dirty. */
/* 维护事件通知和脏数据 */
listElementsRemoved(c, key, where, o, rangelen, deleted);
}
/* A helper for replying with a list's range between the inclusive start and end
* indexes as multi-bulk, with support for negative indexes. Note that start
* must be less than end or an empty array is returned. When the reverse
* argument is set to a non-zero value, the reply is reversed so that elements
* are returned from end to start. */
/* 一个帮助器，用于回复包含开始和结束之间的列表范围
* 多批量索引，支持负索引。 注意开始
* 必须小于 end 否则返回一个空数组。 反转的时候
* 参数设置为非零值，回复被颠倒以便元素
* 从头到尾返回 */
void addListRangeReply(client *c, robj *o, long start, long end, int reverse) {
long rangelen, llen = listTypeLength(o);
/* Convert negative indexes. */
/* 将负数索引转化为正数 */
if (start < 0) start = llen+start;
if (end < 0) end = llen+end;
if (start < 0) start = 0;
/* Invariant: start >= 0, so this test will be true when end < 0.
* The range is empty when start > end or start >= length. */
/* 经过上面转化后一定有 start >= 0，所以当 end < 0 时，该 if 总是为真
* 当 start > end 或 start >= llen 时，该范围是空的 */
if (start > end || start >= llen) {
/* 返回一个空数组并退出函数 */
addReply(c,shared.emptyarray);
return;
}
/* end 超出范围时强制令 end = llen - 1，防止越界 */
if (end >= llen) end = llen-1;
/* 计算范围长度 */
rangelen = (end-start)+1;
/* Return the result in form of a multi-bulk reply */
/* 以 multi-bulk （可以理解为结果数组）的形式向客户端返回结果 */
addReplyArrayLen(c,rangelen);
if (o->encoding == OBJ_ENCODING_QUICKLIST) {
/* 获取范围起点，迭代方向并初始化范围起点位置的迭代器 */
int from = reverse ? end : start;
int direction = reverse ? LIST_HEAD : LIST_TAIL;
listTypeIterator *iter = listTypeInitIterator(o,from,direction);
/* 循环获取范围内的元素并加入到回复中 */
while(rangelen--) {
listTypeEntry entry;
serverAssert(listTypeNext(iter, &entry)); /* 若出现数据损坏将会导致失败 */
quicklistEntry *qe = &entry.entry;
/* 元素为字符串编码，保存在 value 中 */
if (qe->value) {
addReplyBulkCBuffer(c,qe->value,qe->sz);
/* 元素为整数编码 */
} else {
addReplyBulkLongLong(c,qe->longval);
}
}
/* 释放迭代器 */
listTypeReleaseIterator(iter);
} else {
serverPanic("Unknown list encoding");
}
}
/* A housekeeping helper for list elements popping tasks.
*
* 'deleted' is an optional output argument to get an indication
* if the key got deleted by this function. */
/* 用于完成列表元素弹出后的后续步骤。
*
* 'deleted' 是一个可选的输出参数，含义为是否有 key 被删除（有为1，没有为0）*/
void listElementsRemoved(client *c, robj *key, int where, robj *o, long count, int *deleted) {
char *event = (where == LIST_HEAD) ? "lpop" : "rpop";
/* 发送事件通知 */
notifyKeyspaceEvent(NOTIFY_LIST, event, key, c->db->id);
/* 如果列表长度（在弹出元素后）为0，deleted 设置为 1，表示列表被删除 */
if (listTypeLength(o) == 0) {
if (deleted) *deleted = 1;
/* 将 key 从数据库中删除 */
dbDelete(c->db, key);
/* 发送事件通知 */
notifyKeyspaceEvent(NOTIFY_GENERIC, "del", key, c->db->id);
} else {
if (deleted) *deleted = 0;
}
/* 发送 key 被修改信号，以及脏数据加上 count（被删除元素的数量） */
signalModifiedKey(c, c->db, key);
server.dirty += count;
}
/* Implements the generic list pop operation for LPOP/RPOP.
* The where argument specifies which end of the list is operated on. An
* optional count may be provided as the third argument of the client's
* command. */
/* 实现 LPOP/RPOP 的通用列表弹出操作函数。
* where 参数指定了对列表的哪一端进行操作。
* 一个可选参数 count 被客户端命令的第三个参数提供。*/
void popGenericCommand(client *c, int where) {
int hascount = (c->argc == 3);
long count = 0;
robj *value;
/* 检查参数个数，超过3个则输入有误 */
if (c->argc > 3) {
addReplyErrorArity(c);
return;
/* 有输入可选参数 count */
} else if (hascount) {
/* Parse the optional count argument. */
/* 解析可选参数 count，并将输入参数 count 赋值到变量 count 中 */
if (getPositiveLongFromObjectOrReply(c,c->argv[2],&count,NULL) != C_OK)
return;
}
/* 获取 key 对应的对象 */
robj *o = lookupKeyWriteOrReply(c, c->argv[1], hascount ? shared.nullarray[c->resp]: shared.null[c->resp]);
if (o == NULL || checkType(c, o, OBJ_LIST))
return;
/* 如果输入的 count 为 0 */
if (hascount && !count) {
/* Fast exit path. */
/* 回复一个空数组并退出函数 */
addReply(c,shared.emptyarray);
return;
}
/* 如果没有输入可选参数 count */
if (!count) {
/* Pop a single element. This is POP's original behavior that replies
* with a bulk string. */
/* 弹出一个元素，这是 pop 的原始操作，会向客户端回复一个字符串 */
value = listTypePop(o,where);
serverAssert(value != NULL);
/* 回复客户端 */
addReplyBulk(c,value);
/* 减少 value 的被引用计数 */
decrRefCount(value);
/* 真正删除元素 */
listElementsRemoved(c,c->argv[1],where,o,1,NULL);
} else {
/* Pop a range of elements. An addition to the original POP command,
* which replies with a multi-bulk. */
/* 弹出一系列的元素。是原有 pop 命令的附加功能，回复形式是一个 multi-bulk （多返回值） */
long llen = listTypeLength(o);
long rangelen = (count > llen) ? llen : count;
long rangestart = (where == LIST_HEAD) ? 0 : -rangelen;
long rangeend = (where == LIST_HEAD) ? rangelen - 1 : -1;
int reverse = (where == LIST_HEAD) ? 0 : 1;
addListRangeReply(c,o,rangestart,rangeend,reverse);
listTypeDelRange(o,rangestart,rangelen);
listElementsRemoved(c,c->argv[1],where,o,rangelen,NULL);
}
}
/* Like popGenericCommand but work with multiple keys.
* Take multiple keys and return multiple elements from just one key.
*
* 'numkeys' the number of keys.
* 'count' is the number of elements requested to pop.
*
* Always reply with array. */
/* 基本就像 popGenericCommand 一样，但支持多个 key 输入。
* 取多个 key 中输入顺序从左到右的第一个不为空的 key ，返回多个元素。
*
* 'numkeys'是 key 的数量。
* 'count'是要求弹出的元素的数量。
*
* 总是用数组来向客户端回复。*/
void mpopGenericCommand(client *c, robj **keys, int numkeys, int where, long count) {
int j;
robj *o;
robj *key;
for (j = 0; j < numkeys; j++) {
key = keys[j];
o = lookupKeyWrite(c->db, key);
/* Non-existing key, move to next key. */
/* key 不存在，跳过到下一个 key */
if (o == NULL) continue;
/* 检查对象类型 */
if (checkType(c, o, OBJ_LIST)) return;
long llen = listTypeLength(o);
/* Empty list, move to next key. */
/* 空列表，跳过到下一个 key */
if (llen == 0) continue;
/* Pop a range of elements in a nested arrays way. */
/* 弹出一系列元素，并以嵌套数组的方式回复给客户端 */
listPopRangeAndReplyWithKey(c, o, key, where, count, NULL);
/* Replicate it as [LR]POP COUNT. */
/* 将其重写为 [LR]POP COUNT 的形式传播给AOF与从服务器 */
robj *count_obj = createStringObjectFromLongLong((count > llen) ? llen : count);
rewriteClientCommandVector(c, 3,
(where == LIST_HEAD) ? shared.lpop : shared.rpop,
key, count_obj);
decrRefCount(count_obj);
return;
}
/* Look like we are not able to pop up any elements. */
/* 我们没有能够弹出任何元素，回复空数组 */
addReplyNullArray(c);
}
/* LPOP <key> [count] */
/* 处理 LPOP 命令的函数 */
void lpopCommand(client *c) {
popGenericCommand(c,LIST_HEAD);
}
/* RPOP <key> [count] */
/* 处理 RPOP 命令的函数 */
void rpopCommand(client *c) {
popGenericCommand(c,LIST_TAIL);
}
/* LRANGE <key> <start> <stop> */
/* 处理 LRANGE 命令的函数 */
void lrangeCommand(client *c) {
robj *o;
long start, end;
/* 获取输入的 start 和 end 参数 */
if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != C_OK) ||
(getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != C_OK)) return;
/* 获取 key 对应的对象 */
if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptyarray)) == NULL
|| checkType(c,o,OBJ_LIST)) return;
addListRangeReply(c,o,start,end,0);
}
/* LTRIM <key> <start> <stop> */
/* 处理 LTRIM 命令的函数 */
void ltrimCommand(client *c) {
robj *o;
long start, end, llen, ltrim, rtrim;
/* 获取输入的 start 和 end 参数 */
if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != C_OK) ||
(getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != C_OK)) return;
/* 获取 key 对应的对象 */
if ((o = lookupKeyWriteOrReply(c,c->argv[1],shared.ok)) == NULL ||
checkType(c,o,OBJ_LIST)) return;
llen = listTypeLength(o);
/* convert negative indexes */
/* 将负数索引转化为正数 */
if (start < 0) start = llen+start;
if (end < 0) end = llen+end;
if (start < 0) start = 0;
/* Invariant: start >= 0, so this test will be true when end < 0.
* The range is empty when start > end or start >= length. */
/* 经过上面转化后一定有 start >= 0，所以当 end < 0 时，该 if 总是为真
* 当 start > end 或 start >= llen 时，该范围是空的 */
if (start > end || start >= llen) {
/* Out of range start or start > end result in empty list */
/* start 越界或 start > end 则该范围是空的 */
ltrim = llen;
rtrim = 0;
} else {
if (end >= llen) end = llen-1;
ltrim = start;
rtrim = llen-end-1;
}
/* Remove list elements to perform the trim */
/* 通过弹出指定范围外的列表元素来修剪列表 */
if (o->encoding == OBJ_ENCODING_QUICKLIST) {
quicklistDelRange(o->ptr,0,ltrim);
quicklistDelRange(o->ptr,-rtrim,rtrim);
} else {
serverPanic("Unknown list encoding");
}
/* 发送事件通知 */
notifyKeyspaceEvent(NOTIFY_LIST,"ltrim",c->argv[1],c->db->id);
/* 列表长度为0，则将它从数据库中删除 */
if (listTypeLength(o) == 0) {
dbDelete(c->db,c->argv[1]);
notifyKeyspaceEvent(NOTIFY_GENERIC,"del",c->argv[1],c->db->id);
}
/* 发送 key 被修改信号 */
signalModifiedKey(c,c->db,c->argv[1]);
/* 脏数据加上被弹出的元素个数 */
server.dirty += (ltrim + rtrim);
/* 回复客户端 */
addReply(c,shared.ok);
}
/* LPOS key element [RANK rank] [COUNT num-matches] [MAXLEN len]
*
* The "rank" is the position of the match, so if it is 1, the first match
* is returned, if it is 2 the second match is returned and so forth.
* It is 1 by default. If negative has the same meaning but the search is
* performed starting from the end of the list.
*
* If COUNT is given, instead of returning the single element, a list of
* all the matching elements up to "num-matches" are returned. COUNT can
* be combined with RANK in order to returning only the element starting
* from the Nth. If COUNT is zero, all the matching elements are returned.
*
* MAXLEN tells the command to scan a max of len elements. If zero (the
* default), all the elements in the list are scanned if needed.
*
* The returned elements indexes are always referring to what LINDEX
* would return. So first element from head is 0, and so forth. */
/* 命令用法：LPOS key element [RANK rank] [COUNT num-matches] [MAXLEN len]
*
* rank "是匹配的位置，所以如果它是1，则返回第一个匹配。
* 如果是2，则返回第二个匹配，以此类推。
* 它默认为1。如果是负数，含义为倒数第 rank 个元素。
*
* 如果给出 count，不是返回单个元素，而是返回一个列表，其中包括
* 所有匹配的元素（匹配个数由 num-matches 决定）。
* count 可以可以与 rank 结合，以便只返回从第 rank 个开始的元素。
* 如果 count 为 0，则返回所有的匹配元素。
*
* maxlen 告诉命令要扫描的最大长度。如果是0（默认值）
* 将扫描列表中的所有元素。
*
* 返回的元素索引和使用 lindex 命令会返回的索引一致，
* 所以从头开始的第一个元素是0，以此类推。*/
void lposCommand(client *c) {
robj *o, *ele;
ele = c->argv[2];