Redisソース学習--双方向チェーンテーブルadlist

にほうこうチェーンテーブル
定義＃テイギ＃
チェーンテーブル接点
チェーンテーブルのノードには、前後を指す2つのポインタと、保存されたデータを指すvoid*ポインタがあります.

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

チェーンテーブル
チェーンテーブル.2つのチェーンテーブルノードポインタ、1つはheadを指し、1つはtailを指し、dup関数ポインタは2つのチェーンテーブルコピー時のチェーンテーブルノードvalueのコピー方法を指す.matchはチェーンテーブルとkeyが同じvalueを探す場合の比較方法である.

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;

チェーンテーブル反復器
もう1つのチェーンテーブル反復器は、関数にアクセスし、チェーンテーブルを反復器で完了します.Directionは、前方反復器か逆反復器かを示す.

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
#define AL_START_HEAD 0//  
#define AL_START_TAIL 1//  

マクロを定義することによって、チェーンテーブル内の関数ポインタの割り当てといくつかの情報を完了します.

#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

操作
チェーンテーブルの作成

list *listCreate(void);

すべてのメンバーが空です
チェーンテーブルをクリア
チェーンテーブル内のすべてのチェーンテーブルノードを解放します.チェーンテーブル自体は解放されません

void listEmpty(list *list);

チェーンテーブルを削除して空にし、それ自体も解放します.

void listRelease(list *list)
{
    listEmpty(list);
    zfree(list);
}

ノードを最初から追加

list *listAddNodeHead(list *list, void *value);

末尾からノードを追加

list *listAddNodeTail(list *list, void *value);

挿入ノードafterは、所与のノードの前に挿入するか、後ろに挿入するかを示す

list *listInsertNode(list *list, listNode *old_node, void *value, int after);

順方向反復の取得

void listRewind(list *list, listIter *li) {//  
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

関数の内部にチェーンテーブルを反復する

listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next;
        else
            iter->next = current->prev;
    }
    return current;
}

インデックスによって要素にアクセスし、indexが0でhead、-1でtailを表します.

listNode *listIndex(list *list, long index) {
    listNode *n;

    if (index < 0) {
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    } else {
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
}

キー値に基づいて検索

listNode *listSearchKey(list *list, void *key)
{
    listIter iter;
    listNode *node;

    listRewind(list, &iter);
    while((node = listNext(&iter)) != NULL) {
        if (list->match) {
            if (list->match(node->value, key)) {
                return node;
            }
        } else {
            if (key == node->value) {
                return node;
            }
        }
    }
    return NULL;
}