Welcome to MDGSF's Blog!

This is my github blog

[Lua-love2d] 检测两个2D平面上2个矩形是否重叠

2017-08-09

mdgsf

lua

Lua

function collisions.check_rectangles_overlap(a, b)
    local overlap = false
    if not(
        a.x + a.width < b.x or
        b.x + b.width < a.x or
        a.y + a.height < b.y or
        b.y + b.height < a.y
         ) then
        overlap = true
    end
    return overlap
end

Read All

[Nginx] 红黑树

2017-08-08

mdgsf

nginx

Nginx

源文件如下：

nginx-1.13.1\src\core\ngx_rbtree.h

nginx-1.13.1\src\core\ngx_rbtree.c

红黑树原理

http://blog.csdn.net/yang_yulei/article/details/26066409

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

红黑树的5条性质：

1）每个结点要么是红的，要么是黑的。

2）根结点是黑的。

3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。

4）如果一个结点是红的，那么它的俩个儿子都是黑的。

5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

2-3树和红黑树

2-3树是完美平衡，就是说从根节点到每一个叶子节点都有相同的高度。

用2-3树来理解红黑树很简单。

2节点: 1个key，2个儿子。

3节点: 2个key，3个儿子。

红色节点: 相当于3节点。红色表示指向该节点的连接是红色的，红色的连接永远是左儿子。

黑色节点: 相当于2节点。黑色表示指向该节点的连接是黑色的，黑色的连接可以是左儿子，也可以是右儿子。所有叶子节点到根节点的黑色连接数量是一样的。

2-3-4树和红黑树

不过nginx中的红黑树应该是相当于2-3-4树。

Perfect balance. Every path from root to leaf has same length.

2-node: one key, two children.

3-node: two keys, three children.

4-node: three keys, four children.

在2-3-4树中，3-node转为左斜杠为红色的红黑树。

在2-3-4树中，4-node转为左右斜杠为红色的红黑树。

基础数据结构

```c typedef ngx_uint_t ngx_rbtree_key_t; typedef ngx_int_t ngx_rbtree_key_int_t;

typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;

struct ngx_rbtree_node_s { ngx_rbtree_key_t key; ngx_rbtree_node_t *left; ngx_rbtree_node_t *right; ngx_rbtree_node_t *parent; u_char color; u_char data; };

typedef struct ngx_rbtree_s ngx_rbtree_t;

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

struct ngx_rbtree_s { ngx_rbtree_node_t *root; ngx_rbtree_node_t *sentinel; ngx_rbtree_insert_pt insert; };

#define ngx_rbtree_init(tree, s, i)
ngx_rbtree_sentinel_init(s);
(tree)->root = s;
(tree)->sentinel = s;
(tree)->insert = i

Read All

[Nginx] palloc 内存分配

2017-08-07

mdgsf

nginx

Nginx

用到的结构体定义

/*
 * NGX_MAX_ALLOC_FROM_POOL should be (ngx_pagesize - 1), i.e. 4095 on x86.
 * On Windows NT it decreases a number of locked pages in a kernel.
 */
#define NGX_MAX_ALLOC_FROM_POOL  (ngx_pagesize - 1)

#define NGX_DEFAULT_POOL_SIZE    (16 * 1024)

#define NGX_POOL_ALIGNMENT       16
#define NGX_MIN_POOL_SIZE                                                     \
    ngx_align((sizeof(ngx_pool_t) + 2 * sizeof(ngx_pool_large_t)),            \
              NGX_POOL_ALIGNMENT)


typedef void (*ngx_pool_cleanup_pt)(void *data);

typedef struct ngx_pool_cleanup_s  ngx_pool_cleanup_t;

struct ngx_pool_cleanup_s {
    ngx_pool_cleanup_pt   handler;
    void                 *data;
    ngx_pool_cleanup_t   *next;
};


typedef struct ngx_pool_large_s  ngx_pool_large_t;

struct ngx_pool_large_s {
    ngx_pool_large_t     *next;
    void                 *alloc;
};


typedef struct {
    u_char               *last;
    u_char               *end;
    ngx_pool_t           *next;
    ngx_uint_t            failed;
} ngx_pool_data_t;


struct ngx_pool_s {
    ngx_pool_data_t       d;
    size_t                max;
    ngx_pool_t           *current;
    ngx_chain_t          *chain;
    ngx_pool_large_t     *large;
    ngx_pool_cleanup_t   *cleanup;
    ngx_log_t            *log;
};


typedef struct {
    ngx_fd_t              fd;
    u_char               *name;
    ngx_log_t            *log;
} ngx_pool_cleanup_file_t;

先不管这些结构体什么意思。
ngx_log_t 是用来输出日志的，直接忽略它的存在。

ngx_align 内存对齐

#define ngx_align(d, a)     (((d) + (a - 1)) & ~(a - 1))
#define ngx_align_ptr(p, a)                                                   \
    (u_char *) (((uintptr_t) (p) + ((uintptr_t) a - 1)) & ~((uintptr_t) a - 1))

ngx_alloc

就只是对malloc的调用。

/*
@brief: 分配一块内存空间。
@param size[in]: 要分配的内存空间大小，单位：字节。
@param log: 日志输出。
@return : 返回值是指向分配好的内存空间首地址。
*/
void *
ngx_alloc(size_t size, ngx_log_t *log)
{
    void  *p;

    p = malloc(size);
    if (p == NULL) {
        ngx_log_error(NGX_LOG_EMERG, log, ngx_errno,
                      "malloc(%uz) failed", size);
    }

    ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, log, 0, "malloc: %p:%uz", p, size);

    return p;
}

ngx_calloc

#define ngx_memzero(buf, n)       (void) memset(buf, 0, n)

/*
@brief: 分配一块内存空间，并把分配好的空间清零。
@param size[in]: 要分配的内存空间大小，单位：字节。
@param log: 日志输出。
@return : 返回值是指向分配好的内存空间首地址。
*/
void *
ngx_calloc(size_t size, ngx_log_t *log)
{
    void  *p;

    p = ngx_alloc(size, log);

    if (p) {
        ngx_memzero(p, size);
    }

    return p;
}

ngx_create_pool

/*
@brief: 创建一个内存池对象。
@param size[in]: 要分配的内存大小。
@param log: 日志输出。
@return: 返回一个内存池对象的指针，失败返回NULL。
*/
ngx_pool_t *
ngx_create_pool(size_t size, ngx_log_t *log)
{
    ngx_pool_t  *p;

    //申请一块size大小的内存空间，以NGX_POOL_ALIGNMENT=16对齐。
    p = ngx_memalign(NGX_POOL_ALIGNMENT, size, log);
    if (p == NULL) {
        return NULL;
    }

    p->d.last = (u_char *) p + sizeof(ngx_pool_t);
    p->d.end = (u_char *) p + size;
    p->d.next = NULL;
    p->d.failed = 0;

    //这里p->max最大只能为NGX_MAX_ALLOC_FROM_POOL=4096 on x86
    size = size - sizeof(ngx_pool_t);
    p->max = (size < NGX_MAX_ALLOC_FROM_POOL) ? size : NGX_MAX_ALLOC_FROM_POOL;

    p->current = p;
    p->chain = NULL;
    p->large = NULL;
    p->cleanup = NULL;
    p->log = log;

    return p;
}

需要说明的是size的选择，size的大小必须小于等于NGX_MAX_ALLOC_FROM_POOL，且必须大于sizeof(ngx_pool_t)。

选择大于NGX_MAX_ALLOC_FROM_POOL的值会造成浪费，因为大于该限制的空间不会被用到。

选择小于sizeof(ngx_pool_t)的值会造成程序崩溃。由于初始大小的内存块中要用一部分来存储ngx_pool_t这个信息本身。

ngx_memalign

http://mdgsf.github.io/linux/2017/08/07/linux-memalign.html

/*
@brief: 如果memalign() 或者 posix_memalign() 可以只用，那就用这两个函数申请一块对齐的内存空间;
否则的话，就调用malloc()申请一块空间。
*/

/*
 * Linux has memalign() or posix_memalign()
 * Solaris has memalign()
 * FreeBSD 7.0 has posix_memalign(), besides, early version's malloc()
 * aligns allocations bigger than page size at the page boundary
 */

#if (NGX_HAVE_POSIX_MEMALIGN || NGX_HAVE_MEMALIGN)

void *ngx_memalign(size_t alignment, size_t size, ngx_log_t *log);

#else

#define ngx_memalign(alignment, size, log)  ngx_alloc(size, log)

#endif


/////////////////////////////////////////////////////////////////

#if (NGX_HAVE_POSIX_MEMALIGN)

void *
ngx_memalign(size_t alignment, size_t size, ngx_log_t *log)
{
    void  *p;
    int    err;

    err = posix_memalign(&p, alignment, size);

    if (err) {
        ngx_log_error(NGX_LOG_EMERG, log, err,
                      "posix_memalign(%uz, %uz) failed", alignment, size);
        p = NULL;
    }

    ngx_log_debug3(NGX_LOG_DEBUG_ALLOC, log, 0,
                   "posix_memalign: %p:%uz @%uz", p, size, alignment);

    return p;
}

#elif (NGX_HAVE_MEMALIGN)

void *
ngx_memalign(size_t alignment, size_t size, ngx_log_t *log)
{
    void  *p;

    p = memalign(alignment, size);
    if (p == NULL) {
        ngx_log_error(NGX_LOG_EMERG, log, ngx_errno,
                      "memalign(%uz, %uz) failed", alignment, size);
    }

    ngx_log_debug3(NGX_LOG_DEBUG_ALLOC, log, 0,
                   "memalign: %p:%uz @%uz", p, size, alignment);

    return p;
}

#endif

ngx_palloc 和 ngx_pnalloc

/*
@brief:从内存池pool中分配一块大小为size的内存，此函数分配的内存的起始地址按照NGX_ALIGNMENT进行了对齐。对齐操作会提高系统处理的速度，但会造成少量内存的浪费。
@param pool[in]: 内存池pool。
@param size[in]: 要分配的内存大小。
@return: 返回执行分配的内存空间的首地址。
*/
void *
ngx_palloc(ngx_pool_t *pool, size_t size)
{
#if !(NGX_DEBUG_PALLOC)
    if (size <= pool->max) {
        return ngx_palloc_small(pool, size, 1);
    }
#endif

    return ngx_palloc_large(pool, size);
}

/*
@brief:从内存池pool中分配一块大小为size的内存，没有进行内存对齐。
@param pool[in]: 内存池pool。
@param size[in]: 要分配的内存大小。
@return: 返回执行分配的内存空间的首地址。
*/
void *
ngx_pnalloc(ngx_pool_t *pool, size_t size)
{
#if !(NGX_DEBUG_PALLOC)
    if (size <= pool->max) {
        return ngx_palloc_small(pool, size, 0);
    }
#endif

    return ngx_palloc_large(pool, size);
}

可以看到，当size <= pool->max 时，调用ngx_palloc_small()。否则调用ngx_palloc_large()。

ngx_palloc_small

/*
@brief:从内存池pool中分配一块大小为size的内存。
@param pool[in]: 内存池pool。
@param size[in]: 要分配的内存大小。
@param align[in]: 1:内存对齐， 0:内存没有对齐。
@return: 返回执行分配的内存空间的首地址。
*/
static ngx_inline void *
ngx_palloc_small(ngx_pool_t *pool, size_t size, ngx_uint_t align)
{
    u_char      *m;
    ngx_pool_t  *p;

    p = pool->current;

    do {
        m = p->d.last;

        if (align) {
            m = ngx_align_ptr(m, NGX_ALIGNMENT); //对齐内存指针。
        }

        if ((size_t) (p->d.end - m) >= size) { //如果当前的ngx_pool_t对象中的内存空间足够，那就直接返回。
            p->d.last = m + size;

            return m;
        }

        p = p->d.next; //到下一个ngx_pool_t对象中去查找，这是一个链表结构。

    } while (p);

    return ngx_palloc_block(pool, size);
}

/*
@brief: 这个函数做了两件事：
1. 为ngx_pool_t对象分配一个新的内存节点，新的节点的大小和pool一样大，链表结构， pool.d.next = new ngx_pool_t。
2. 然后从这个新的节点上分配出size大小的内存来使用。
@param pool[inout]: 要增加新的节点的内存池。
@param size[in]: 要分配的内存大小。
@return: 返回size大小的内存空间的首地址。
*/
static void *
ngx_palloc_block(ngx_pool_t *pool, size_t size)
{
    u_char      *m;
    size_t       psize;
    ngx_pool_t  *p, *new;

    psize = (size_t) (pool->d.end - (u_char *) pool); //获取pool的大小

    m = ngx_memalign(NGX_POOL_ALIGNMENT, psize, pool->log); //分配一块新的节点
    if (m == NULL) {
        return NULL;
    }

    new = (ngx_pool_t *) m;

    new->d.end = m + psize;
    new->d.next = NULL;
    new->d.failed = 0;

    m += sizeof(ngx_pool_data_t); //这里做了优化，新的节点只使用了ngx_pool_data_t
    m = ngx_align_ptr(m, NGX_ALIGNMENT);
    new->d.last = m + size;

    for (p = pool->current; p->d.next; p = p->d.next) {
        if (p->d.failed++ > 4) {
            pool->current = p->d.next;
        }
    }

    p->d.next = new; //把新的节点链接到链表上去。

    return m;
}

ngx_palloc_large

/*
@brief: 分配一块size大小的内存，并把该内存链接到pool->large这个链表上去，在size > pool->max的时候才会调用这个函数。
@param pool[in]: 内存池对象。
@param size[in]: 要分配的内存空间大小。
@return: 返回指向改内存空间的首地址的指针。
*/
static void *
ngx_palloc_large(ngx_pool_t *pool, size_t size)
{
    void              *p;
    ngx_uint_t         n;
    ngx_pool_large_t  *large;

    p = ngx_alloc(size, pool->log);
    if (p == NULL) {
        return NULL;
    }

    n = 0;

    for (large = pool->large; large; large = large->next) {
        if (large->alloc == NULL) {
            large->alloc = p;
            return p;
        }

        if (n++ > 3) {
            break;
        }
    }

    large = ngx_palloc_small(pool, sizeof(ngx_pool_large_t), 1);
    if (large == NULL) {
        ngx_free(p);
        return NULL;
    }

    large->alloc = p;
    large->next = pool->large;
    pool->large = large;

    return p;
}

ngx_pmemalign

/*
@brief: 以内存对齐的方式，申请一块空间，并放在pool->large链表上。
@param pool[inout]: 内存池对象。
@param size[in]: 要分配的空间大小。
@param alignment[in]: 对齐的字节数，必须是2的倍数。
@return: 返回分配的内存空间的首地址的指针。
*/
void *
ngx_pmemalign(ngx_pool_t *pool, size_t size, size_t alignment)
{
    void              *p;
    ngx_pool_large_t  *large;

    p = ngx_memalign(alignment, size, pool->log);
    if (p == NULL) {
        return NULL;
    }

    large = ngx_palloc_small(pool, sizeof(ngx_pool_large_t), 1);
    if (large == NULL) {
        ngx_free(p);
        return NULL;
    }

    large->alloc = p;
    large->next = pool->large;
    pool->large = large;

    return p;
}

ngx_pfree

/*
@brief: 从pool->large链表中查找是否存在首地址为p的内存空间，如果存在则释放这块空间。
@param pool[inout]: 内存池对象。
@param p[in]: 要释放的内存空间。
@return:
NGX_OK: 释放成功。
NGX_DECLINED: 没有找到。
*/
ngx_int_t
ngx_pfree(ngx_pool_t *pool, void *p)
{
    ngx_pool_large_t  *l;

    for (l = pool->large; l; l = l->next) {
        if (p == l->alloc) {
            ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, pool->log, 0,
                           "free: %p", l->alloc);
            ngx_free(l->alloc);
            l->alloc = NULL;

            return NGX_OK;
        }
    }

    return NGX_DECLINED;
}

对于被置于大块内存链，也就是被large字段管理的一列内存中的某块进行释放。该函数的实现是顺序遍历large管理的大块内存链表。所以效率比较低下。如果在这个链表中找到了这块内存，则释放，并返回NGX_OK。否则返回NGX_DECLINED。

由于这个操作效率比较低下，除非必要，也就是说这块内存非常大，确应及时释放，否则一般不需要调用。反正内存在这个pool被销毁的时候，总归会都释放掉的嘛！

参考链接

http://tengine.taobao.org/book/chapter_02.html#ngx-pool-t-100

Read All

[Nginx] array数组

2017-08-07

mdgsf

nginx

Nginx

结构体定义

/*
elts: 指向数组的指针。
nelts: 数组中实际元素的个数。
size: 数组中每个元素的大小。
nalloc: 数组中最多存储的元素的个数。
pool: 数组就是从这个内存池中分配内存的。

size * nalloc 就是数组实际使用的字节数。
*/
typedef struct {
    void        *elts;
    ngx_uint_t   nelts;
    size_t       size;
    ngx_uint_t   nalloc;
    ngx_pool_t  *pool;
} ngx_array_t;

ngx_array_create

/*
@brief: 从内存池p中分配一个数组，数组的大小为 n * size 字节。
@param p[inout]: 内存池。
@param n[in]: 数组的元素个数。
@param size[in]: 每个元素的大小。
@return: 返回指向数组对象的指针。
*/
ngx_array_t *
ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size)
{
    ngx_array_t *a;

    a = ngx_palloc(p, sizeof(ngx_array_t));
    if (a == NULL) {
        return NULL;
    }

    if (ngx_array_init(a, p, n, size) != NGX_OK) {
        return NULL;
    }

    return a;
}

/*
@brief: 初始化数组。
@param array[inout]: 数组对象。
@param pool[inout]: 内存池对象。
@param n[in]: 数组的元素个数。
@param size[in]: 每个元素的大小。
@return: NGX_OK, NGX_ERROR。
*/
static ngx_inline ngx_int_t
ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    /*
     * set "array->nelts" before "array->elts", otherwise MSVC thinks
     * that "array->nelts" may be used without having been initialized
     */

    array->nelts = 0;
    array->size = size;
    array->nalloc = n;
    array->pool = pool;

    array->elts = ngx_palloc(pool, n * size);
    if (array->elts == NULL) {
        return NGX_ERROR;
    }

    return NGX_OK;
}

ngx_array_push

/*
@brief: 从数组中获取一个新的节点。
如果数组还没有满，直接一个新的节点就好了。
如果数组满了，1.数组的内存池空间还没满，就直接给数组增加一个元素。
如果数组满了，2.数组的内存池空间也满了，那就给内存池增加一个2倍于现在数组大小的空间。
@param a[inout]: 数组。
@return: 返回一个指向新元素的首地址的指针，如果内存分配失败返回NULL。
*/
void *
ngx_array_push(ngx_array_t *a)
{
    void        *elt, *new;
    size_t       size;
    ngx_pool_t  *p;

    if (a->nelts == a->nalloc) {

        /* the array is full */

        size = a->size * a->nalloc;

        p = a->pool;

        if ((u_char *) a->elts + size == p->d.last
            && p->d.last + a->size <= p->d.end)
        {
            /*
             * the array allocation is the last in the pool
             * and there is space for new allocation
             */

            p->d.last += a->size;
            a->nalloc++;

        } else {
            /* allocate a new array */

            new = ngx_palloc(p, 2 * size);
            if (new == NULL) {
                return NULL;
            }

            ngx_memcpy(new, a->elts, size);
            a->elts = new;
            a->nalloc *= 2;
        }
    }

    elt = (u_char *) a->elts + a->size * a->nelts;
    a->nelts++;

    return elt;
}

/*
@brief: 和ngx_array_push一样，只不过从一个元素变成了n个元素。
*/
void *
ngx_array_push_n(ngx_array_t *a, ngx_uint_t n)
{
    void        *elt, *new;
    size_t       size;
    ngx_uint_t   nalloc;
    ngx_pool_t  *p;

    size = n * a->size;

    if (a->nelts + n > a->nalloc) {

        /* the array is full */

        p = a->pool;

        if ((u_char *) a->elts + a->size * a->nalloc == p->d.last
            && p->d.last + size <= p->d.end)
        {
            /*
             * the array allocation is the last in the pool
             * and there is space for new allocation
             */

            p->d.last += size;
            a->nalloc += n;

        } else {
            /* allocate a new array */

            nalloc = 2 * ((n >= a->nalloc) ? n : a->nalloc);

            new = ngx_palloc(p, nalloc * a->size);
            if (new == NULL) {
                return NULL;
            }

            ngx_memcpy(new, a->elts, a->nelts * a->size);
            a->elts = new;
            a->nalloc = nalloc;
        }
    }

    elt = (u_char *) a->elts + a->size * a->nelts;
    a->nelts += n;

    return elt;
}

Read All

[Linux] memalign 和 posix_memalign

2017-08-07

Linux

Memalign Posix_memalign
memalign

在GNU系统中，malloc或realloc返回的内存块地址都是8的倍数（如果是64位系统，则为16的倍数）。如果你需要更大的粒度，请使用memalign或valloc。这些函数在头文件“stdlib.h”中声明。

在GNU库中，可以使用函数free释放memalign和valloc返回的内存块。但无法在BSD系统中使用，而且BSD系统中并未提供释放这样的内存块的途径。

函数：void * memalign (size_t boundary, size_t size) 函数memalign将分配一个由size指定大小，地址是boundary的倍数的内存块。参数boundary必须是2的幂！函数memalign可以分配较大的内存块，并且可以为返回的地址指定粒度。

函数：void * valloc (size_t size) 使用函数valloc与使用函数memalign类似，函数valloc的内部实现里，使用页的大小作为对齐长度，使用memalign来分配内存。它的实现如下所示：
```
void * valloc (size_t size)
{
    return memalign (getpagesize (), size);
}
```
posix_memalign

SYNOPSIS
```
#include <stdlib.h>
int posix_memalign(void **memptr, size_t alignment, size_t size); [Option End]
```
DESCRIPTION

The posix_memalign() function shall allocate size bytes aligned on a boundary specified by alignment, and shall return a pointer to the allocated memory in memptr. The value of alignment shall be a multiple of sizeof( void *), that is also a power of two. Upon successful completion, the value pointed to by memptr shall be a multiple of alignment.

The free() function shall deallocate memory that has previously been allocated by posix_memalign().

RETURN VALUE

Upon successful completion, posix_memalign() shall return zero; otherwise, an error number shall be returned to indicate the error.
Read All

Table 结构定义

Lua 的Table是由数组、哈希表一起实现的。

所以如果不清楚哈希表，建议先看看哈希表。 http://mdgsf.github.io/c/2016/07/01/c-hashtable.html

typedef unsigned char lu_byte;

typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode;  /* log2 of size of 'node' array */
  unsigned int sizearray;  /* size of 'array' array */
  TValue *array;  /* array part */
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  struct Table *metatable;
  GCObject *gclist;
} Table;

TValue *array; 是数组

unsigned int sizearray; 是数组的大小

Node *node; 应该就是哈希表了。

lu_byte lsizenode; 如果哈希表的容量为Size，那么lsizenode = log2(Size)

其他的成员变量暂时不关心。等等主要看下 TValue 和 Node 的结构体。

Table *luaH_new (lua_State *L) {
  GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table)); //其实就是分配一款内存空间
  Table *t = gco2t(o); //把指针类型转换为Table类型。
  t->metatable = NULL; //接下来的都是一些初始化的操作。
  t->flags = cast_byte(~0);
  t->array = NULL;
  t->sizearray = 0;
  setnodevector(L, t, 0);
  return t;
}

static void setnodevector (lua_State *L, Table *t, unsigned int size) {
  if (size == 0) {  /* no elements to hash part? */
    t->node = cast(Node *, dummynode);  /* use common 'dummynode' */
    t->lsizenode = 0;
    t->lastfree = NULL;  /* signal that it is using dummy node */
  }
  else {
      ... //这里我们暂时不关心，就先不看。
  }
}

#define cast(t, exp) ((t)(exp))   //类型转换，把表达式exp转换为t类型。

#define twoto(x) (1<<(x)) //计算2^x

#define sizenode(t) (twoto((t)->lsizenode)) //计算2^(t->lsizenode)的大小

void luaH_free (lua_State *L, Table *t) {
  if (!isdummy(t))
    luaM_freearray(L, t->node, cast(size_t, sizenode(t))); //释放哈希表的空间，大小为2^(t->lsizenode)
  luaM_freearray(L, t->array, t->sizearray); //释放数组的空间，大小为t->sizearray
  luaM_free(L, t); //释放Table的内存空间
}

Node TKey TValue

可以看到，数组是用TValue来保存值的，而哈希表是使用Node来保存值。

TValue *array; 是数组

Node *node; 应该就是哈希表了。

typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

typedef union TKey {
  struct {
    TValuefields;
    int next;  /* for chaining (offset for next node) */
  } nk;
  TValue tvk;
} TKey;

/*
** Tagged Values. This is the basic representation of values in Lua,
** an actual value plus a tag with its type.
*/

/*
** Union of all Lua values
*/
typedef union Value {
  GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  int b;           /* booleans */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
} Value;

#define TValuefields Value value_; int tt_

typedef struct lua_TValue {
  TValuefields;
} TValue;

其实 TKey 和 TValue 是同一个东西，只不过TKey里面多了一个next，主要是哈希表出现冲突时，用来解决冲突用的。

TKey中tvk是这个key的值，nk中的next则指向key冲突的下一个节点。lua的hash表的hash算法比较特别，一般的hash表都是根据key算出hash(key)，然后把这个key放在hash表的hash(key)位置上，如果有冲突的话，就放在hash(key)位置的链表上。

但是lua的hash表中，如果有冲突的话，lua会找hash表中一个空的位置（从后往前找，假设为x），然后把新的key放在这个空的位置x上，并且让hash表中hash(key)处的节点的nk.next指向x。这个意思就是，假如有冲突的话，不用重新分配空间来存储冲突的key，而是利用hash表上未用过的空格来存储。但是这样会引入另外一个问题，本来key是不应该放在x的，假设有另外一个key2，hash(key2)算出来的位置也在x的话，那就表示本来x这个位置应该是给key2的，但是由于x被key占用了，导致key2没地方放了。这时候lua的处理方式是把key放到另外一个空格，然后让key2占回x。当hash表已经没有空格的时候，lua就会resize这个hash表。这样做的好处主要是不用动态申请内存空间，hash表初始化的时候有多少内存空间就用多少，不够就resize这个hash表。

http://blog.csdn.net/u012611878/article/details/51873648

冲突解决技术可以分为两类：开散列方法( open hashing，也称为拉链法，separate chaining )和闭散列方法( closed hashing，也称为开地址方法，open addressing )。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。

Lua这里使用的是闭散列。

增删查改

LUAI_DDEC const TValue luaO_nilobject_;
#define luaO_nilobject (&luaO_nilobject_) //这是一个空对象，这样的好处是可以不需要处理NULL指针，在<<代码整洁之道>>里面有说。

TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
  const TValue *p = luaH_get(t, key); //应该是到Table中去查找key是不是存在。
  if (p != luaO_nilobject)
    return cast(TValue *, p); //如果存在，直接返回对应的TValue
  else return luaH_newkey(L, t, key); //如果不存在，则创建一个新的TValue，再返回。
}

很明显，上面有两个重要的函数 luaH_newkey 和 luaH_get。

luaH_newkey 应该就是插入函数了，向Table内插入一个新的值。

luaH_get 则是查找函数，在Table中查找对应的key是不是存在。

luaH_newkey

/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
/*
插入一个新的key到Table中。首先，检查key的main position是不是空的，main position 就是key要插入的位置吧。
if(main position != 空)
{
    检查冲突节点的main position是不是在它自己的位置上。
    if(冲突节点不是在它自己的位置上)
    {
        把冲突节点移动到一个空的位置上。
        把新的key放在它自己的main position上。
    }
    else
    {
        把新的key放到一个空的位置上。
    }
}
else //main position == 空
{
    把新的key放在它自己的main position上。
}
*/
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
  Node *mp;
  TValue aux;
  if (ttisnil(key)) luaG_runerror(L, "table index is nil");
  else if (ttisfloat(key)) {
    lua_Integer k;
    if (luaV_tointeger(key, &k, 0)) {  /* does index fit in an integer? */
      setivalue(&aux, k);
      key = &aux;  /* insert it as an integer */
    }
    else if (luai_numisnan(fltvalue(key)))
      luaG_runerror(L, "table index is NaN");
  }
  mp = mainposition(t, key);  ------------------------------------------//通过key可以获取到Table中的一个位置mp，哈希函数就在mainposition()这函数里面。
  if (!ttisnil(gval(mp)) || isdummy(t)) {  /* main position is taken? */
    Node *othern;
    Node *f = getfreepos(t);  /* get a free place */
    if (f == NULL) {  /* cannot find a free place? */
      rehash(L, t, key);  /* grow table */    ----------------------------//空间不足了，扩大空间。
      /* whatever called 'newkey' takes care of TM cache */
      return luaH_set(L, t, key);  /* insert key into grown table */
    }
    lua_assert(!isdummy(t));
    othern = mainposition(t, gkey(mp));  ---------------------------------//获取冲突节点的main position。
    if (othern != mp) {  /* is colliding node out of its main position? */
      /* yes; move colliding node into free position */
      while (othern + gnext(othern) != mp)  /* find previous */
        othern += gnext(othern);
      gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */
      *f = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
      if (gnext(mp) != 0) {
        gnext(f) += cast_int(mp - f);  /* correct 'next' */
        gnext(mp) = 0;  /* now 'mp' is free */
      }
      setnilvalue(gval(mp));
    }
    else {  /* colliding node is in its own main position */
      /* new node will go into free position */
      if (gnext(mp) != 0)
        gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */
      else lua_assert(gnext(f) == 0);
      gnext(mp) = cast_int(f - mp);  -------------------------------------//发生冲突时，next保存的是两个指针的差值，也就是当前节点到下一个节点在内存中的距离。
      mp = f;
    }
  }
  setnodekey(L, &mp->i_key, key);
  luaC_barrierback(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

//这里是上面用到的一些宏
#define gnode(t,i) (&(t)->node[i])
#define gnext(n) ((n)->i_key.nk.next)
#define gkey(n) cast(const TValue*, (&(n)->i_key.tvk))  //获取Node的key
#define gval(n) (&(n)->i_val)  //获取Node的value

/* type casts (a macro highlights casts in the code) */
#define cast(t, exp) ((t)(exp))
#define cast_int(i) cast(int, (i)) //转换为整形

#define isdummy(t) ((t)->lastfree == NULL)

#define LUA_TNIL 0
#define rttype(o) ((o)->tt_)
#define checktag(o,t) (rttype(o) == (t))
#define ttisnil(o) checktag((o), LUA_TNIL)

在这个函数里面，用到了3个函数：getfreepos，mainposition，rehash。我们需要看看到底是怎么实现的。

getfreepos: 获取一个空的位置。

rehash: 重新分配Table的内存空间。

mainposition: 根据key值，通过哈希函数算出在Table中的main position。

getfreepos

static Node *getfreepos (Table *t) {
  if (!isdummy(t)) {
    while (t->lastfree > t->node) {
      t->lastfree--; //这里再不断的向前遍历
      if (ttisnil(gkey(t->lastfree)))
        return t->lastfree;
    }
  }
  return NULL;  /* could not find a free place */
}

看来Table 中的 lastfree 这个变量是用来保存最后一个空闲位置的指针。

rehash

/*
** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
*/
/*
na: Table中数组中的元素个数 和 哈希表中可以放到数组中去的元素的个数 的总和。
totaluse: Table中所有元素的个数，包括数组和哈希表。
*/
static void rehash (lua_State *L, Table *t, const TValue *ek) {
  unsigned int asize;  /* optimal size for array part */
  unsigned int na;  /* number of keys in the array part */
  unsigned int nums[MAXABITS + 1];
  int i;
  int totaluse;
  for (i = 0; i <= MAXABITS; i++) nums[i] = 0;  /* reset counts */
  na = numusearray(t, nums);  /* count keys in array part */
  totaluse = na;  /* all those keys are integer keys */
  totaluse += numusehash(t, nums, &na);  /* count keys in hash part */
  /* count extra key */
  na += countint(ek, nums);
  totaluse++;
  /* compute new size for array part */
  asize = computesizes(nums, &na);
  /* resize the table to new computed sizes */
  luaH_resize(L, t, asize, totaluse - na);
}

/*
** Count keys in array part of table 't': Fill 'nums[i]' with
** number of keys that will go into corresponding slice and return
** total number of non-nil keys.
*/
/*
@brief 这个函数是用来计算Table中的数组部分的信息的。
@param t[in]: Table。
@param nums[out]: 这个数组的大小是32。
    nums[0]: array[0]
    nums[1]: array[1 - 2]
    nums[2]: array[2 - 4]
    nums[3]: array[4 - 8]
    ...
    nums[i]: array[2^(i-1) - 2^i]
    nums[i]保存着数组下标范围从 2^(i-1) 到 2^i 之间的所有非空元素的个数。
@return: 返回值是数组中所有的非空元素的个数。
*/
static unsigned int numusearray (const Table *t, unsigned int *nums) {
  int lg;
  unsigned int ttlg;  /* 2^lg */
  unsigned int ause = 0;  /* summation of 'nums' */
  unsigned int i = 1;  /* count to traverse all array keys */
  /* traverse each slice */
  for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
    unsigned int lc = 0;  /* counter */
    unsigned int lim = ttlg;
    if (lim > t->sizearray) {
      lim = t->sizearray;  /* adjust upper limit */
      if (i > lim)
        break;  /* no more elements to count */
    }
    /* count elements in range (2^(lg - 1), 2^lg] */
    for (; i <= lim; i++) {
      if (!ttisnil(&t->array[i-1]))
        lc++;
    }
    nums[lg] += lc;
    ause += lc;
  }
  return ause;
}

/*
@brief: 计算Table中哈希表的信息。
@param t[in]: Table。
@param nums[inout]:
@pram pna[inout]: 就是现在在哈希表中，但是可以移动到数组中去的元素的个数。
@return: 返回哈希表中所有元素的个数。
*/
static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) {
  int totaluse = 0;  /* total number of elements */
  int ause = 0;  /* elements added to 'nums' (can go to array part) */
  int i = sizenode(t);
  while (i--) {
    Node *n = &t->node[i];
    if (!ttisnil(gval(n))) {
      ause += countint(gkey(n), nums);
      totaluse++;
    }
  }
  *pna += ause;
  return totaluse;
}

/*
** Compute the optimal size for the array part of table 't'. 'nums' is a
** "count array" where 'nums[i]' is the number of integers in the table
** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
** integer keys in the table and leaves with the number of keys that
** will go to the array part; return the optimal size.
*/
static unsigned int computesizes (unsigned int nums[], unsigned int *pna) {
  int i;
  unsigned int twotoi;  /* 2^i (candidate for optimal size) */
  unsigned int a = 0;  /* number of elements smaller than 2^i */
  unsigned int na = 0;  /* number of elements to go to array part */
  unsigned int optimal = 0;  /* optimal size for array part */
  /* loop while keys can fill more than half of total size */
  for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2) {
    if (nums[i] > 0) {
      a += nums[i];
      if (a > twotoi/2) {  /* more than half elements present? */
        optimal = twotoi;  /* optimal size (till now) */
        na = a;  /* all elements up to 'optimal' will go to array part */
      }
    }
  }
  lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
  *pna = na;
  return optimal;
}

对于存放在数组有一个规则，每插入一个整数key时，都要判断包含当前key的区间[1, 2^n]里，是否满足table里所有整数类型key的数量大于2^(n - 1)，如果不成立则需要把这个key放在hash表里。这样设计，可以减少空间上的浪费，并可以进行空间的动态扩展。例如：

就是说数组的大小是：1,2,4,8,16,32,64,128,256….

也就是扩容的时候，每次都把空间翻一倍，和C++里面的vector是一样的。

如果我在a[0]位置插入一个值，那么数组的大小就是1，数组的利用率就是100%。

接着在a[100]位置插入一个值，那么数组的大小就要扩大到128，那就有126个位置是浪费的。

那如果在a[10000]位置插入一个值，那么10000多个位置是浪费的，空间浪费极大。

所以用哈希表做了优化：

在往数组中插入一个key时，我们可以计算出两个新的数值：

新数组的大小
插入这个key之后，新数组中元素的个数

如果新数组中元素的个数 > 新数组的大小/2，那就插入数组。否则就把key放到哈希表中去。

也就是数组的利用率要超过50%。

a［0］ = 1, a［1］ = 1, a［5］= 1

结果分析：数组大小4, hash大小1，a［5］本来是在8这个区间里的，但是有用个数3 < 8 / 2，所以a［5］放在了hash表里。

a［0］ = 1, a［1］ = 1, a［5］ = 1, a［6］ = 1,

结果分析：数组大小4，hash大小2,有用个数4 < 8 / 2，所以a［5］,a［6］放在hash表里。

a［0］ = 1, a［1］ = 1, a［5］ = 1, a［6］ = 1, a［7］ = 1

结果分析：数组大小8，hash大小0, 有用个数5 > 8 / 2。

http://blog.csdn.net/zr339361504/article/details/52432163

Read All

54/97

Welcome to MDGSF's Blog!

[Lua-love2d] 检测两个2D平面上2个矩形是否重叠

[Nginx] 红黑树

红黑树原理

红黑树的5条性质：

2-3树 和 红黑树

2-3-4树 和 红黑树

基础数据结构

[Nginx] palloc 内存分配

用到的结构体定义

ngx_align 内存对齐

ngx_alloc

ngx_calloc

ngx_create_pool

ngx_memalign

ngx_palloc 和 ngx_pnalloc

ngx_palloc_small

ngx_palloc_large

ngx_pmemalign

ngx_pfree

参考链接

[Nginx] array数组

结构体定义

ngx_array_create

ngx_array_push

[Linux] memalign 和 posix_memalign

memalign

posix_memalign

SYNOPSIS

DESCRIPTION

RETURN VALUE

[Lua] Table内部实现

Table 结构定义

Node TKey TValue

增删查改

luaH_newkey

getfreepos

rehash

2-3树和红黑树

2-3-4树和红黑树