Welcome to MDGSF's Blog!

This is my github blog

[Head First Design Pattern] Decorator Pattern

2017-08-14

mdgsf

DesignPattern

Decorator

装饰者模式：被装饰的和装饰要继承自同一个基类。

#include <iostream>
#include <string>
using namespace std;

class Beverge
{
public:
    virtual double Cost() = 0;

    virtual string GetDescription()
    {
        return m_description;
    }

    string m_description;
};

class CondimentDecorator : public Beverge
{
public:
    virtual string GetDescription() = 0;
};

class Espresso : public Beverge
{
public:
    Espresso() { m_description = "Espresso"; }
    double Cost() { return 1.99; }
};

class DarkRoast : public Beverge
{
public:
    DarkRoast() { m_description = "DarkRoast coffee"; }
    double Cost() { return 1.00; }
};

class HouseBlend : public Beverge
{
public:
    HouseBlend() { m_description = "HouseBlend coffee"; }
    double Cost() { return 0.89; }
};

class Mocha : public CondimentDecorator
{
public:
    Mocha(Beverge * pBeverge)
    {
        m_pBeverge = pBeverge;
    }

    string GetDescription()
    {
        return m_pBeverge->GetDescription() + ", Mocha ";
    }

    double Cost()
    {
        return 0.10 + m_pBeverge->Cost();
    }

private:
    Beverge * m_pBeverge;
};

class Whip : public CondimentDecorator
{
public:
    Whip(Beverge * pBeverge)
    {
        m_pBeverge = pBeverge;
    }

    string GetDescription()
    {
        return m_pBeverge->GetDescription() + ", Whip ";
    }

    double Cost()
    {
        return 0.20 + m_pBeverge->Cost();
    }

private:
    Beverge * m_pBeverge;
};

class Soy : public CondimentDecorator
{
public:
    Soy(Beverge * pBeverge)
    {
        m_pBeverge = pBeverge;
    }

    string GetDescription()
    {
        return m_pBeverge->GetDescription() + ", Soy ";
    }

    double Cost()
    {
        return 0.30 + m_pBeverge->Cost();
    }

private:
    Beverge * m_pBeverge;
};


int main()
{
    Beverge * pBeverge = new Espresso;
    cout << pBeverge->GetDescription() << " $" << pBeverge->Cost() << endl;

    Beverge * pBeverge2 = new Espresso;
    pBeverge2 = new Mocha(pBeverge2);
    pBeverge2 = new Whip(pBeverge2);
    pBeverge2 = new Soy(pBeverge2);
    cout << pBeverge2->GetDescription() << " $" << pBeverge2->Cost() << endl;

    Beverge * pBeverge3 = new Espresso;
    pBeverge3 = new Mocha(pBeverge3);
    pBeverge3 = new Whip(pBeverge3);
    pBeverge3 = new Whip(pBeverge3);
    cout << pBeverge3->GetDescription() << " $" << pBeverge3->Cost() << endl;
    return 0;
}

Read All

[Lua-love2d] 打包发布

2017-08-12

mdgsf

lua

Lua
1. 进入game目录，game目录就是游戏的代码目录。
2. 全选，右键压缩成 game.zip
3. 将 game.zip 重命名为 game.love
4. 将 game.love 复制到 love游戏引擎的安装目录下。
5. copy /b love.exe+game.love game.exe
6. 然后会生成 game.exe
7. 把game.exe和love游戏引擎目录下的dll一起打包发布就好了。
Read All

[Nginx] queue队列

2017-08-09

mdgsf

nginx

Nginx

源文件如下：

nginx-1.13.1\src\core\ngx_queue.h

nginx-1.13.1\src\core\ngx_queue.c

两种不同的链表类型

0901

我发现很多比较底层的代码都是使用第二种方式，而且喜欢用宏定义。

nginx_queue这里也是用第二种方式。

数据结构

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

ngx_queue_init

初始化一个节点

#define ngx_queue_init(q)                                                     \
    (q)->prev = q;                                                            \
    (q)->next = q

ngx_queue_empty

判断该队列是不是空。

#define ngx_queue_empty(h)                                                    \
    (h == (h)->prev)

ngx_queue_insert_head

往队列h的头部插入节点x，也就是插入到h的下一个节点。

h是队列的头部，是一个空节点，也就是哨兵节点。

#define ngx_queue_insert_head(h, x)                                           \
    (x)->next = (h)->next;                                                    \
    (x)->next->prev = x;                                                      \
    (x)->prev = h;                                                            \
    (h)->next = x

#define ngx_queue_insert_after   ngx_queue_insert_head

ngx_queue_insert_tail

往队列h的尾部插入节点x，因为是双向链表，所以尾部就是h的前一个节点。

#define ngx_queue_insert_tail(h, x)                                           \
    (x)->prev = (h)->prev;                                                    \
    (x)->prev->next = x;                                                      \
    (x)->next = h;                                                            \
    (h)->prev = x

//获取第一个节点
#define ngx_queue_head(h)                                                     \
    (h)->next


//获取最后一个节点
#define ngx_queue_last(h)                                                     \
    (h)->prev


//获取哨兵节点
#define ngx_queue_sentinel(h)                                                 \
    (h)


//获取该节点的下一个节点
#define ngx_queue_next(q)                                                     \
    (q)->next


//获取该节点的前一个节点
#define ngx_queue_prev(q)                                                     \
    (q)->prev

ngx_queue_remove

删除节点x

#define ngx_queue_remove(x)                                                   \
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next

ngx_queue_split

切割队列，h是队列的哨兵节点，q是该队列的内部节点，n是外部一个单独的节点，n不属于该队列。

#define ngx_queue_split(h, q, n)                                              \
    (n)->prev = (h)->prev;                                                    \
    (n)->prev->next = n;                                                      \
    (n)->next = q;                                                            \
    (h)->prev = (q)->prev;                                                    \
    (h)->prev->next = h;                                                      \
    (q)->prev = n;

ngx_queue_add

连接两个链表，把链表n连接到链表h的尾部。

#define ngx_queue_add(h, n)                                                   \
    (h)->prev->next = (n)->next;                                              \
    (n)->next->prev = (h)->prev;                                              \
    (h)->prev = (n)->prev;                                                    \
    (h)->prev->next = h;

ngx_queue_data

通过一个指向链表节点的指针，获取到该节点对应的结构体的指针。

#define ngx_queue_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))

#define offsetof(s,m) ((size_t)&(((s*)0)->m))

不理解的话，看下面的这个链接，在文章的最底部。

http://mdgsf.github.io/linux-kernel/2017/07/21/linux-kernel-list.html

ngx_queue_middle

/*
 * find the middle queue element if the queue has odd number of elements
 * or the first element of the queue's second part otherwise
 */

/*
@brief: 查找队列的中间节点。
就是用两个指针，第一个指针每次走两步，第二个每次走一步，当第一个指针走到尾部时，第二个指针就是中间节点。
*/
ngx_queue_t *
ngx_queue_middle(ngx_queue_t *queue)
{
    ngx_queue_t  *middle, *next;

    middle = ngx_queue_head(queue);

    if (middle == ngx_queue_last(queue)) {
        return middle;
    }

    next = ngx_queue_head(queue);

    for ( ;; ) {
        middle = ngx_queue_next(middle);

        next = ngx_queue_next(next);

        if (next == ngx_queue_last(queue)) {
            return middle;
        }

        next = ngx_queue_next(next);

        if (next == ngx_queue_last(queue)) {
            return middle;
        }
    }
}

ngx_queue_sort

/* the stable insertion sort */
//稳定的插入排序。
void
ngx_queue_sort(ngx_queue_t *queue,
    ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
{
    ngx_queue_t  *q, *prev, *next;

    q = ngx_queue_head(queue);

    if (q == ngx_queue_last(queue)) {
        return;
    }

    for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {

        prev = ngx_queue_prev(q);
        next = ngx_queue_next(q);

        ngx_queue_remove(q);

        do {
            if (cmp(prev, q) <= 0) {
                break;
            }

            prev = ngx_queue_prev(prev);

        } while (prev != ngx_queue_sentinel(queue));

        ngx_queue_insert_after(prev, q);
    }
}

Read All

[Nginx] list链表

2017-08-09

mdgsf

nginx

Nginx

源文件如下：

nginx-1.13.1\src\core\ngx_list.h

nginx-1.13.1\src\core\ngx_list.c

nginx中list和array感觉很像，还有内存池的结构。

结构体定义

typedef struct ngx_list_part_s  ngx_list_part_t;

struct ngx_list_part_s {
    void             *elts;
    ngx_uint_t        nelts;
    ngx_list_part_t  *next;
};

typedef struct {
    ngx_list_part_t  *last; //指向最后一块内存
    ngx_list_part_t   part; //指向第一块内存
    size_t            size; //保存每一块内存中，每个元素的大小
    ngx_uint_t        nalloc; //保存每一块内存中，可以有多少个元素
    ngx_pool_t       *pool; //内存池
} ngx_list_t;

这里的链表，是把多个像数组一样的空间链接起来，不是每一个元素链接的，估计是为了提高效率吧。

而且没有提供删除函数，有点神奇。

ngx_list_create

/*
@brief: 建立链表。
@param pool: 使用的内存池。
@param n[in]: 元素的数量
@param size[in]: 每个元素的大小，字节。
@return: 返回新创建的链表的指针。
*/
ngx_list_t *
ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    ngx_list_t  *list;

    list = ngx_palloc(pool, sizeof(ngx_list_t));
    if (list == NULL) {
        return NULL;
    }

    if (ngx_list_init(list, pool, n, size) != NGX_OK) {
        return NULL;
    }

    return list;
}

ngx_list_init

static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    list->part.elts = ngx_palloc(pool, n * size);
    if (list->part.elts == NULL) {
        return NGX_ERROR;
    }

    list->part.nelts = 0;
    list->part.next = NULL;
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;

    return NGX_OK;
}

ngx_list_push

/*
@brief: 从链表l中取出一个新的节点使用。
@param l[inout]: 链表。
@return: 返回指向新的节点的指针。
*/
void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;

    last = l->last;

    if (last->nelts == l->nalloc) {

        /* the last part is full, allocate a new list part */

        last = ngx_palloc(l->pool, sizeof(ngx_list_part_t));
        if (last == NULL) {
            return NULL;
        }

        //分配一块新的内存块，这块内存块的大小和之前的是一样的。应该说每一块内存块的大小都是一样的。
        last->elts = ngx_palloc(l->pool, l->nalloc * l->size);
        if (last->elts == NULL) {
            return NULL;
        }

        last->nelts = 0;
        last->next = NULL;

        l->last->next = last;
        l->last = last;
    }

    elt = (char *) last->elts + l->size * last->nelts;
    last->nelts++;

    return elt;
}

Read All

[Nginx] 定时器

2017-08-09

mdgsf

nginx

Nginx

源文件如下：

nginx-1.13.1\src\event\ngx_event_timer.h

nginx-1.13.1\src\event\ngx_event_timer.c

nginx这里的定时器是用红黑树实现的。

linux中是用时间轮实现的。

我记得还有用最小堆实现定时器的。

全局数据变量

#define NGX_TIMER_INFINITE  (ngx_msec_t) -1

#define NGX_TIMER_LAZY_DELAY  300

ngx_rbtree_t              ngx_event_timer_rbtree;

static ngx_rbtree_node_t  ngx_event_timer_sentinel;

ngx_event_timer_init

/*
 * the event timer rbtree may contain the duplicate keys, however,
 * it should not be a problem, because we use the rbtree to find
 * a minimum timer value only
 */

/*
@brief: 定时器初始化，其实就是初始化一颗红黑树。
*/
ngx_int_t
ngx_event_timer_init(ngx_log_t *log)
{
    ngx_rbtree_init(&ngx_event_timer_rbtree, &ngx_event_timer_sentinel,
                    ngx_rbtree_insert_timer_value);

    return NGX_OK;
}

/*
@brief: 红黑树中的插入函数。
@param temp: 临时指针，指向红黑树中的节点。
@param node: 要插入的新节点。
@param sentinel: 哨兵节点。
*/
void
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t  **p;

    for ( ;; ) {

        /*
         * Timer values
         * 1) are spread in small range, usually several minutes,
         * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
         * The comparison takes into account that overflow.
         */

        /*  node->key < temp->key */

        p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
            ? &temp->left : &temp->right;

        if (*p == sentinel) {
            break;
        }

        temp = *p;
    }

    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}

ngx_event_add_timer

/*
@brief: 把时间ev添加到定时器中去，超时时间是timer，单位应该是毫秒。
可以看到这里定时器和事件是一起使用的。
@param ev: 事件。
@param timer: 超时时间，比如说100ms，就表示100ms后定时器促发，就会执行这个事件。
@tips:
//ngx_current_msec在源文件 nginx-1.13.1\src\core\ngx_times.c
volatile ngx_msec_t      ngx_current_msec;
我猜这个应该就是当前时间的意思。
*/
static ngx_inline void
ngx_event_add_timer(ngx_event_t *ev, ngx_msec_t timer)
{
    ngx_msec_t      key;
    ngx_msec_int_t  diff;

    //ngx_current_msec:当前时间， timer:超时时间， key:定时器促发的时间。
    key = ngx_current_msec + timer;

    if (ev->timer_set) {
        //如果定时器被设置过了

        /*
         * Use a previous timer value if difference between it and a new
         * value is less than NGX_TIMER_LAZY_DELAY milliseconds: this allows
         * to minimize the rbtree operations for fast connections.
         */

        diff = (ngx_msec_int_t) (key - ev->timer.key);

        if (ngx_abs(diff) < NGX_TIMER_LAZY_DELAY) { //如果之前的定时器的促发时间和现在的相距很近，那就用之前的定时器。
            ngx_log_debug3(NGX_LOG_DEBUG_EVENT, ev->log, 0,
                           "event timer: %d, old: %M, new: %M",
                            ngx_event_ident(ev->data), ev->timer.key, key);
            return;
        }

        ngx_del_timer(ev); //不然的话，先把之前的定时器删除掉。
    }

    ev->timer.key = key;

    ngx_log_debug3(NGX_LOG_DEBUG_EVENT, ev->log, 0,
                   "event timer add: %d: %M:%M",
                    ngx_event_ident(ev->data), timer, ev->timer.key);

    ngx_rbtree_insert(&ngx_event_timer_rbtree, &ev->timer); //把新的定时器插入红黑树中。

    ev->timer_set = 1;
}

ngx_event_del_timer

/*
@brief: 把事件ev从定时器中删除。
@param ev: 事件。
*/
static ngx_inline void
ngx_event_del_timer(ngx_event_t *ev)
{
    ngx_log_debug2(NGX_LOG_DEBUG_EVENT, ev->log, 0,
                   "event timer del: %d: %M",
                    ngx_event_ident(ev->data), ev->timer.key);

    ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer); //可以看到，其实就只是删除红黑树中的一个节点。

#if (NGX_DEBUG)
    ev->timer.left = NULL;
    ev->timer.right = NULL;
    ev->timer.parent = NULL;
#endif

    ev->timer_set = 0;
}

ngx_event_find_timer

/*
@brief:
如果没有一个定时器，那就返回NGX_TIMER_INFINITE。
如果最近的一个定时器还没有超时，那就返回这个定时器还有多久促发。
否则返回0.
*/
ngx_msec_t
ngx_event_find_timer(void)
{
    ngx_msec_int_t      timer;
    ngx_rbtree_node_t  *node, *root, *sentinel;

    if (ngx_event_timer_rbtree.root == &ngx_event_timer_sentinel) {
        return NGX_TIMER_INFINITE;
    }

    root = ngx_event_timer_rbtree.root;
    sentinel = ngx_event_timer_rbtree.sentinel;

    node = ngx_rbtree_min(root, sentinel);

    timer = (ngx_msec_int_t) (node->key - ngx_current_msec);

    return (ngx_msec_t) (timer > 0 ? timer : 0);
}

ngx_event_expire_timers

/*
@brief: 执行所有已经超时的定时器。
*/
void
ngx_event_expire_timers(void)
{
    ngx_event_t        *ev;
    ngx_rbtree_node_t  *node, *root, *sentinel;

    sentinel = ngx_event_timer_rbtree.sentinel;

    for ( ;; ) {
        root = ngx_event_timer_rbtree.root;

        if (root == sentinel) { //如果没有定时器
            return;
        }

        node = ngx_rbtree_min(root, sentinel);

        /* node->key > ngx_current_msec */

        if ((ngx_msec_int_t) (node->key - ngx_current_msec) > 0) { //如果最近的定时器都还没有超时，那就结束。
            return;
        }

        //通过node获取到对应的事件结构体的指针。
        ev = (ngx_event_t *) ((char *) node - offsetof(ngx_event_t, timer));

        ngx_log_debug2(NGX_LOG_DEBUG_EVENT, ev->log, 0,
                       "event timer del: %d: %M",
                       ngx_event_ident(ev->data), ev->timer.key);

        ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer); //先将该定时器删除。

#if (NGX_DEBUG)
        ev->timer.left = NULL;
        ev->timer.right = NULL;
        ev->timer.parent = NULL;
#endif

        ev->timer_set = 0;

        ev->timedout = 1;

        ev->handler(ev); //促发该事件。
    }
}

ngx_event_no_timers_left

/*
@brief:
*/
ngx_int_t
ngx_event_no_timers_left(void)
{
    ngx_event_t        *ev;
    ngx_rbtree_node_t  *node, *root, *sentinel;

    sentinel = ngx_event_timer_rbtree.sentinel;
    root = ngx_event_timer_rbtree.root;

    if (root == sentinel) {
        return NGX_OK;
    }

    for (node = ngx_rbtree_min(root, sentinel);
         node;
         node = ngx_rbtree_next(&ngx_event_timer_rbtree, node))
    {
        ev = (ngx_event_t *) ((char *) node - offsetof(ngx_event_t, timer));

        if (!ev->cancelable) { //不知道cancelable这个代表什么意思。
            return NGX_AGAIN;
        }
    }

    /* only cancelable timers left */

    return NGX_OK;
}

Read All

[Lua-love2d] 打开调试窗口

2017-08-09

mdgsf

lua

Lua

love –console Snake

equivalent to setting t.console=true in conf.lua

Read All

53/97

Welcome to MDGSF's Blog!

[Head First Design Pattern] Decorator Pattern

[Lua-love2d] 打包发布

[Nginx] queue队列

两种不同的链表类型

数据结构

ngx_queue_init

ngx_queue_empty

ngx_queue_insert_head

ngx_queue_insert_tail

ngx_queue_remove

ngx_queue_split

ngx_queue_add

ngx_queue_data

ngx_queue_middle

ngx_queue_sort

[Nginx] list链表

结构体定义

ngx_list_create

ngx_list_init

ngx_list_push

[Nginx] 定时器

全局数据变量

ngx_event_timer_init

ngx_event_add_timer

ngx_event_del_timer

ngx_event_find_timer

ngx_event_expire_timers

ngx_event_no_timers_left

[Lua-love2d] 打开调试窗口