Librdkafka的基础数据结构 1 --- 队列

2017-12-22 本文已影响357人扫帚的影子

Librdkafka用纯C写成,作者在C API基础上作了C++的简单封装;
说到C, 自然里面离不开大量的指针操作, 内存操作, 引用计数等等, 作者一一为我们作了实现;
基础数据结构里面也说到了很多,比如链表, 各种队列, 二叉树等等, 接下来我们会一一介绍.

Queue

所在文件: src/queue.h和src/rdsysqueue.h
queue.h是个很古老的实现了, 作者这里用的是NetBsd里的实现, 还有其他很多版本, 实现都大同小异, 里面指针的运用真是值得我们好好学习;
网上关于这个的讲解有很多, 我们这里只是简单过一下用得最多的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 */ \
}

两个元素:
tqh_first: 指向队列的第一个成员;
tqh_last: 存的是队列里的最后一个元素的 next指针的变量地址, 这个二级指针太有用了,我们后边会再讲到;

队列的entry: #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,) 实际是用最少侵入式的方式实现了一个类似于C++的模板的机制, 定义中的type就是队列里元素的类型, 可以是任意struct类型, 这个_TAILQ_ENTRY(type, qual)放在这个struct类型的定义里,是其的一个成员, 然后各个元素通过这个TAILQ_ENTRY成员彼此串联起来, 松耦合在一起

#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,)

两个元素:
tqe_next: 指向队列的下一个成员;
tqe_prev: 存的是前一个元素的 next指针的变量地址, 这个二级指针太有用了,我们后边会再讲到;

获队列的最后一个元素#define TAILQ_LAST(head, headname):

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

要理解这个其实关键一点是上面定义的TAILQ_HEAD和TAILQ_ENTRY在结构和内存布局上是一样一样的.
(head)->tqh_last)是最后一个元素的next指针的地址, 因为TAILQ_ENTRY(type)这个定义是没有类型名的,我们不能直接cast成 TAILQ_ENTRY(type)类型, 所有就只能cast成(struct headname *), 所有((struct headname *)((head)->tqh_last))也就是最后一个元素的地址,(((struct headname *)((head)->tqh_last))->tqh_last)就是最后一个元素的tqe_prev值, 这个tqe_prev指向的是它前一个元素的next的地址, 解引用后自然就指向队列最后一个元素自己了, 有点绕~~~

获取当前元素的前一个元素 #define TAILQ_PREV(elm, headname, field)

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

有了上一个取最后元素的经验,这个理解起来就容易多啦, 这里就不讲啦~~~

其他一些操作, 头插,尾插, 前插,后插, 遍历, 反向遍历, 删除都比较简单了, 主要也都是指针操作;

rd_list_t

是一个append-only的轻量级数组链表, 支持固定大小和按需自动增长两种方式且支持sort;
所在文件: src/rdlist.h 和 src/rdlist.c
定义:

typedef struct rd_list_s {
        int    rl_size;  // 目前list的容易
        int    rl_cnt;  // 当前list里已放入的元素个数
        void **rl_elems; // 存储元素的内存, 可以看成是一个void*类型的数组
        void (*rl_free_cb) (void *); // 存储的元素的释放函数
        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;

创建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)
主要是调用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的创建: void rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t size)
实际上连每个元素的大小也是固定的

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数组本身的大小(元素类型是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; //数组元素赋值

    rl->rl_size = (int)size;
    rl->rl_cnt = 0;
    rl->rl_flags |= RD_LIST_F_FIXED_SIZE; // 标识为固定大小的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++];  //当前已有元素数 + 1
}

按索引(相当于数据的下标)移除元素:

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

        if (idx + 1 < rl->rl_cnt) //如果idx指向的是最后一个元素,不用mm了, rl->rl_cnt--就好
                memmove(&rl->rl_elems[idx],
                        &rl->rl_elems[idx+1],
                        sizeof(*rl->rl_elems) * (rl->rl_cnt - (idx+1))); // 实际就是用memmove作内存移动
        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的基础数据结构 1 --- 队列

Queue

rd_list_t

Librdkafka源码分析-Content Table

猜你喜欢

热点阅读