YYCache源码阅读笔记之_YYLinkedMap的链表操作

最近为了更深入学习缓存，决定阅读下YYCache这个高性能的的缓存框架，刚开始阅读的时候各种蒙圈（什么c语言知识啊，链表知识啊都是比较少接触的），庆幸的是这些薄弱的知识在网上都有比较多资源可以学习到。

首先去学习了下双向链表，简单点说就是这种链表的每个节点都有两个指针域，分别指向前驱和后继，通过这俩个指针可以访问节点的上一个节点或下一个节点。

然后根据双向链表知识阅读了_YYLinkedMap是怎么对链表进行操作的

把节点移到链表头节点

- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
 if (_head == node) return;
 if (_tail == node) { // node等于链表尾节点时，把_tail往前移一个节点并重新设置为链表尾节点
 _tail = node->_prev; // _tail指向链表尾节点上一个节点
 _tail->_next = nil; // _tail的后继节点（链表尾节点）置空，使_tail重新成为链表尾节点
 } else { // node不等于链表尾节点时，把node前向节点的下一个节点设置为node后继节点
  node->_next->_prev = node->_prev; // 把node前向节点赋值给后继节点的前驱指针
 node->_prev->_next = node->_next; // 把node后继节点赋值给前向节点的后驱指针
 }
 // 把node设置成头节点
 node->_next = _head; //_head赋值给node的后继指针
 node->_prev = nil; //node的前驱指针置空
 _head->_prev = node; //node赋值给_head的前驱指针
 _head = node; //_head指向node
}

把节点插入链表头节点

- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
    CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node)); // 字典保存链表节点node
    _totalCost += node->_cost; // 叠加该缓存开销到总内存开销
    _totalCount++;  // 总缓存数+1
    if (_head) {
        // 存在链表头，取代当前表头
        node->_next = _head;
        _head->_prev = node;
        // 重新赋值链表表头临时变量_head
        _head = node;
    } else {
        // 不存在链表头
        _head = _tail = node;
    }
}

移除节点

- (void)removeNode:(_YYLinkedMapNode *)node {

 CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key)); // 从字典中移除node
 _totalCost -= node->_cost; // 减掉总内存消耗
_totalCount--; // 总缓存数-1
 //移除node节点
 if (node->_next) node->_next->_prev = node->_prev; // 如果node存在下一个节点，则把上一个节点赋值给下一个节点的前驱指针
 if (node->_prev) node->_prev->_next = node->_next; // 如果node存在上一个节点，则把下一个节点赋值给上一个节点的后继指针
 if (_head == node) _head = node->_next; // 如果链表头节点等于node，则node的下一个节点赋值给链表头节点
 if (_tail == node) _tail = node->_prev; // 如果链表尾节点等于node，则把node的上一个节点赋值给链表尾节点
}

移除尾节点

- (_YYLinkedMapNode *)removeTailNode {
 if (!_tail) return nil;
 _YYLinkedMapNode *tail = _tail;// 保留一份要删除的尾节点指针
 CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));// 移除链表尾节点
 _totalCost -= _tail->_cost;// 减掉总内存消耗
 _totalCount--;// 总缓存数-1
 if (_head == _tail) {
 _head = _tail = nil;// 清除节点，链表上已无节点了
 } else {
 // 设倒数第二个节点为链表尾节点
 _tail = _tail->_prev;
 _tail->_next = nil;
 }
 // 返回完tail后_tail将会释放
 return tail;
}

移除所有缓存

- (void)removeAll {

 // 清空内存开销与缓存数量
 _totalCost = 0;
 _totalCount = 0;
 // 清空头尾节点
 _head = nil;
 _tail = nil;

 if (CFDictionaryGetCount(_dic) > 0) {
 CFMutableDictionaryRef holder = _dic;// 拷贝一份字典 
 _dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);// 重新分配新的空间

 if (_releaseAsynchronously) {
 // 异步释放缓存
 dispatch_queue_t queue = _releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
 dispatch_async(queue, ^{
 CFRelease(holder); // hold and release in specified queue
 });
 } else if (_releaseOnMainThread && !pthread_main_np()) {
 // 主线程上释放缓存
 dispatch_async(dispatch_get_main_queue(), ^{
 CFRelease(holder); // hold and release in specified queue
 });
 } else {
 // 同步释放缓存
 CFRelease(holder);
     }
  }
}