• Librdkafka用純C寫成,作者在C API基礎(chǔ)上作了C++的簡單封裝;
• 說到C, 自然里面離不開大量的指針操作, 內(nèi)存操作, 引用計(jì)數(shù)等等, 作者一一為我們作了實(shí)現(xiàn);
• 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)里面也說到了很多,比如 鏈表, 各種隊(duì)列, 二叉樹等等, 接下來我們會(huì)一一介紹.

Queue

• 所在文件: src/queue.h和src/rdsysqueue.h
• queue.h是個(gè)很古老的實(shí)現(xiàn)了, 作者這里用的是NetBsd里的實(shí)現(xiàn), 還有其他很多版本, 實(shí)現(xiàn)都大同小異, 里面指針的運(yùn)用真是值得我們好好學(xué)習(xí);
• 網(wǎng)上關(guān)于這個(gè)的講解有很多, 我們這里只是簡單過一下用得最多的Tail queue;
• 頭指針定義 #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,):

#define _TAILQ_HEAD(name, type, qual)                   \
struct name {                               \
    qual type *tqh_first;       /* first element */     \
    qual type *qual *tqh_last;  /* addr of last next element */ \
}

兩個(gè)元素:
tqh_first: 指向隊(duì)列的第一個(gè)成員;
tqh_last: 存的是隊(duì)列里的最后一個(gè)元素的 next指針的變量地址, 這個(gè)二級(jí)指針太有用了,我們后邊會(huì)再講到;

• 隊(duì)列的entry: #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,) 實(shí)際是用最少侵入式的方式實(shí)現(xiàn)了一個(gè)類似于C++的模板的機(jī)制, 定義中的type就是隊(duì)列里元素的類型, 可以是任意struct類型, 這個(gè)_TAILQ_ENTRY(type, qual)放在這個(gè)struct類型的定義里,是其的一個(gè)成員, 然后各個(gè)元素通過這個(gè)TAILQ_ENTRY成員彼此串聯(lián)起來, 松耦合在一起

#define _TAILQ_ENTRY(type, qual)                    \
struct {                                \
    qual type *tqe_next;        /* next element */      \
    qual type *qual *tqe_prev;  /* address of previous next element */\
}
#define TAILQ_ENTRY(type)   _TAILQ_ENTRY(struct type,)

兩個(gè)元素:
tqe_next: 指向隊(duì)列的下一個(gè)成員;
tqe_prev: 存的是前一個(gè)元素的 next指針的變量地址, 這個(gè)二級(jí)指針太有用了,我們后邊會(huì)再講到;

• 獲隊(duì)列的最后一個(gè)元素#define TAILQ_LAST(head, headname):

(*(((struct headname *)((head)->tqh_last))->tqh_last))

要理解這個(gè)其實(shí)關(guān)鍵一點(diǎn)是上面定義的TAILQ_HEAD和TAILQ_ENTRY在結(jié)構(gòu)和內(nèi)存布局上是一樣一樣的.
(head)->tqh_last)是最后一個(gè)元素的next指針的地址, 因?yàn)?code>TAILQ_ENTRY(type)這個(gè)定義是沒有類型名的,我們不能直接cast成 TAILQ_ENTRY(type)類型, 所有就只能cast成(struct headname *), 所有((struct headname *)((head)->tqh_last))也就是最后一個(gè)元素的地址,(((struct headname *)((head)->tqh_last))->tqh_last)就是最后一個(gè)元素的tqe_prev值, 這個(gè)tqe_prev指向的是它前一個(gè)元素的next的地址, 解引用后自然就指向隊(duì)列最后一個(gè)元素自己了, 有點(diǎn)繞~~~

• 獲取當(dāng)前元素的前一個(gè)元素 #define TAILQ_PREV(elm, headname, field)

(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

有了上一個(gè)取最后元素的經(jīng)驗(yàn),這個(gè)理解起來就容易多啦, 這里就不講啦~~~

• 其他一些操作, 頭插,尾插, 前插,后插, 遍歷, 反向遍歷, 刪除都比較簡單了, 主要也都是指針操作;

rd_list_t

• 是一個(gè)append-only的輕量級(jí)數(shù)組鏈表, 支持固定大小和按需自動(dòng)增長兩種方式且支持sort;
• 所在文件: src/rdlist.h 和 src/rdlist.c
• 定義:

typedef struct rd_list_s {
        int    rl_size;  // 目前l(fā)ist的容易
        int    rl_cnt;  // 當(dāng)前l(fā)ist里已放入的元素個(gè)數(shù)
        void **rl_elems; // 存儲(chǔ)元素的內(nèi)存, 可以看成是一個(gè)void*類型的數(shù)組
        void (*rl_free_cb) (void *); // 存儲(chǔ)的元素的釋放函數(shù)
        int    rl_flags; 
        #define RD_LIST_F_ALLOCATED  0x1  /* The rd_list_t is allocated,
                   * will be free on destroy() */
        #define RD_LIST_F_SORTED     0x2  /* Set by sort(), cleared by any mutations.
                   * When this flag is set bsearch() is used
                   * by find(), otherwise a linear search. */
        #define RD_LIST_F_FIXED_SIZE 0x4  /* Assert on grow */
        #define RD_LIST_F_UNIQUE     0x8  /* Don't allow duplicates:
                                   * ONLY ENFORCED BY CALLER. */
} rd_list_t;

• 創(chuàng)建list: rd_list_t *rd_list_new (int initial_size, void (*free_cb) (void *))

rd_list_t *rd_list_new (int initial_size, void (*free_cb) (void *)) {
    rd_list_t *rl = malloc(sizeof(*rl));
    rd_list_init(rl, initial_size, free_cb);
    rl->rl_flags |= RD_LIST_F_ALLOCATED;
    return rl;
}

• 容量自增: void rd_list_grow (rd_list_t *rl, size_t size)
  主要是調(diào)用rd_realloc(realloc)

void rd_list_grow (rd_list_t *rl, size_t size) {
        rd_assert(!(rl->rl_flags & RD_LIST_F_FIXED_SIZE)); // 不適用于固定大小類型的list
        rl->rl_size += (int)size;
        if (unlikely(rl->rl_size == 0))
                return; /* avoid zero allocations */
        rl->rl_elems = rd_realloc(rl->rl_elems,
                                  sizeof(*rl->rl_elems) * rl->rl_size);
}

• 固定容量的list的創(chuàng)建: void rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t size)
  實(shí)際上連每個(gè)元素的大小也是固定的

oid rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t size) {
    size_t allocsize;
    char *p;
    size_t i;

    rd_assert(!rl->rl_elems);

    /* Allocation layout:
     *   void *ptrs[cnt];
     *   elems[elemsize][cnt];
     */

    allocsize = (sizeof(void *) * size) + (elemsize * size); //rl_elems數(shù)組本身的大小(元素類型是void*) + 所有元素的大小
    rl->rl_elems = rd_malloc(allocsize);

    /* p points to first element's memory. */
    p = (char *)&rl->rl_elems[size];

    /* Pointer -> elem mapping */
    for (i = 0 ; i < size ; i++, p += elemsize)
        rl->rl_elems[i] = p; //數(shù)組元素賦值

    rl->rl_size = (int)size;
    rl->rl_cnt = 0;
    rl->rl_flags |= RD_LIST_F_FIXED_SIZE; // 標(biāo)識(shí)為固定大小的list
}

• 添加新元素 void *rd_list_add (rd_list_t *rl, void *elem):

void *rd_list_add (rd_list_t *rl, void *elem) {
        if (rl->rl_cnt == rl->rl_size)
                rd_list_grow(rl, rl->rl_size ? rl->rl_size * 2 : 16); //容量不夠先自增
    rl->rl_flags &= ~RD_LIST_F_SORTED;  //新增后原有的排序失效
    if (elem)
        rl->rl_elems[rl->rl_cnt] = elem;
    return rl->rl_elems[rl->rl_cnt++];  //當(dāng)前已有元素?cái)?shù) + 1
}

• 按索引(相當(dāng)于數(shù)據(jù)的下標(biāo))移除元素:

static void rd_list_remove0 (rd_list_t *rl, int idx) {
        rd_assert(idx < rl->rl_cnt);

        if (idx + 1 < rl->rl_cnt) //如果idx指向的是最后一個(gè)元素,不用mm了, rl->rl_cnt--就好
                memmove(&rl->rl_elems[idx],
                        &rl->rl_elems[idx+1],
                        sizeof(*rl->rl_elems) * (rl->rl_cnt - (idx+1))); // 實(shí)際就是用memmove作內(nèi)存移動(dòng)
        rl->rl_cnt--;
}

• 排序用的qsort快排

void rd_list_sort (rd_list_t *rl, int (*cmp) (const void *, const void *)) {
    rd_list_cmp_curr = cmp;
        qsort(rl->rl_elems, rl->rl_cnt, sizeof(*rl->rl_elems),
          rd_list_cmp_trampoline);
    rl->rl_flags |= RD_LIST_F_SORTED;
}

• 查找:

void *rd_list_find (const rd_list_t *rl, const void *match,
                    int (*cmp) (const void *, const void *)) {
        int i;
        const void *elem;

       //如果排過序就用二分查找
    if (rl->rl_flags & RD_LIST_F_SORTED) {
        void **r;
        rd_list_cmp_curr = cmp;
        r = bsearch(&match/*ptrptr to match elems*/,
                rl->rl_elems, rl->rl_cnt,
                sizeof(*rl->rl_elems), rd_list_cmp_trampoline);
        return r ? *r : NULL;
    }

       沒排過就編歷, 是不是可以先qsort一下呢?
        RD_LIST_FOREACH(elem, rl, i) {
                if (!cmp(match, elem))
                        return (void *)elem;
        }

        return NULL;
}

Librdkafka源碼分析-Content Table