adlist는 Redis의 이중 종료 연결 목록으로 느린 로그 저장소, 마스터-슬레이브 복제의 오류 보고 클라이언트, 목록 데이터 구조 구현 등 Redis의 여러 곳에서 널리 사용됩니다. 그래서 이것 역시 매우 중요한 데이터 구조입니다.
1), Redis의 이중 끝 연결 목록의 데이터 구조
(권장: redis 비디오 자습서)
이중 끝 연결 목록(다음 코드는 src/adlist.h에 정의되어 있음):
typedef struct list { listNode *head; //指向链表的第一个节点 listNode *tail; //指向链表的最后一个节点 //复制链表节点时候的回调函数,由于链表节点可以任意类型的数据,不同类型操作不同,故而用回调函数去特殊处理 void *(*dup)(void *ptr); void (*free)(void *ptr); //释放链表节点内存时候的回调函数,理由同上 int (*match)(void *ptr, void *key); //比较链表节点值的回调函数,用于自定义比较,理由同上 unsigned long len; //当前列表节点数量 } list;
이중 종료 연결 목록의 노드(다음 코드는 src/adlist.h에 정의되어 있습니다):
typedef struct listNode { struct listNode *prev; //当前节点的上一个节点 struct listNode *next; //当前节点的下一个节点 void *value; //当前节点存储的值,可以任意类型 } listNode;
list는 각각 두 개의 포인터인 head와 tail을 통해 연결 목록의 머리와 꼬리 끝을 가리킵니다. 연결된 목록을 양수 및 음수 순서로 탐색할 수 있도록 하고 listNode의 void *값을 사용하면 모든 데이터를 저장할 수 있고 dup, free 및 match를 통해 listNode의 값을 처리하는 방법을 사용자 지정할 수 있습니다.
2. 이중 종료 연결 목록의 간단한 작업
연결 목록 만들기(다음 코드는 src/adlist.c에 정의되어 있음):
list *listCreate(void) { struct list *list; //初始化链表 //为链表分配内存 if ((list = zmalloc(sizeof(*list))) == NULL) return NULL; //为空链表设置初始值 list->head = list->tail = NULL; list->len = 0; list->dup = NULL; list->free = NULL; list->match = NULL; return list; }
연결 목록 끝에 추가(다음 코드가 정의됨) src/adlist.c):
list *listAddNodeTail(list *list, void *value) { listNode *node; //初始化node节点 //为新的node节点分配内存 if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; //为node节点设置值 node->value = value; if (list->len == 0) { //如果空链表则 将头尾指向 新节点 并后继前驱节点设置为NULL list->head = list->tail = node; node->prev = node->next = NULL; } else { //否则将节点的前驱节点设置为原来的尾部节点 node->prev = list->tail; //由于追加到尾部,后继节点为NULL node->next = NULL; //之前的尾部节点的后继节点设置为新增的节点 list->tail->next = node; //将列表的尾部节点指针指向新增的节点 list->tail = node; } //增加链表长度 list->len++; return list; }
Traverse 연결 목록:
연결 목록을 순회하는 데 일반적으로 사용되는 두 가지 방법이 있습니다. 하나는 연결 목록의 길이에 따라 while 루프를 수동으로 순회하는 것이고, 다른 하나는 Redis 이중 종료 연결 목록에서 제공하는 반복자를 사용하는 것입니다.
수동 탐색(다음 코드는 src/adlist.c의 메모리 해제 함수에 정의되어 있습니다):
void listRelease(list *list) { unsigned long len; //current表示当前遍历的游标指针,next表示下次遍历的游标指针(next作为临时变量用于保存下一个节点) listNode *current, *next; //将current指向头部节点 current = list->head; //计算长度(其实就是 listLength(list)) len = list->len; //通过长度递减的方式进行遍历,便利到长度为0的时候,遍历结束 while(len--) { //保存下次循环的节点指针 next = current->next; //释放掉当前节点,如果设置释放节点的回调函数,则执行用户自定义的函数 if (list->free) list->free(current->value); zfree(current); //将游标指向下个节点 current = next; } zfree(list); }
반복자 모드 탐색은 아래를 참조하세요.
3) 이중 종료 연결 목록의 반복자
Redis 연결 목록의 반복을 용이하게 하기 위해 연결 목록이 반복자에 캡슐화됩니다. 반복자 구조는 다음과 같습니다(다음 코드는 src/adlist에 정의되어 있습니다). .h):
typedef struct listIter { listNode *next; //迭代器指向的下一个节点 //迭代方向,由于双端链表保存了head和tail的值,所以可以进行两个方向的迭代 //AL_START_HEAD表示从头向后遍历,AL_START_TAIL表示从尾部向前遍历 int direction; } listIter;
Iteration Server 사용 예:
//l表示list结构,n表示listNode结构,listNode的值保存的是sds字符串 //创建迭代器对象 iter = listGetIterator(l, AL_START_HEAD); //循环获取下一个需要遍历的节点 while ((n = listNext(iter))) { //输出返回的节点n的value值 printf("Node Value: %s\n", listNodeValue(n)); }
더 많은 Redis 지식을 보려면 redis 소개 튜토리얼 칼럼을 주목하세요.
위 내용은 Redis에서 양방향 연결 목록 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!