Nginx学习笔记（三） Nginx基本数据结构

manf

Nginx基本数据结构

　　话说学习一种编程语言，例如C语言，我们首先学的也是数据结构，这是以后开发程序的关键。为了更好更方便的开发Nginx，Nginx自己实现了很多适合nginx的数据结构。

Nginx中的数组
　　ngx_array_s是Nginx中的数组,原型为ngx_array_t。



typedef struct {
void        *elts;           //指向数据的指针
ngx_uint_t   nelts;          //数组中元素的个数
size_t       size;　　　　　　 //数组中每个元素的大小
ngx_uint_t   nalloc;　　　　　 //数据容量
ngx_pool_t  *pool;　　　　　　 //用来分配内存的内存池
} ngx_array_t;
　　这里的数组已经远远超出了C语言中数据的概念，类似于Vector。
　　具体操作参见源码。

Nginx中的队列
　　ngx_queue_t是Nginx中的队列元素，原型为ngx_queue_s.



struct ngx_queue_s {
ngx_queue_t  *prev;
ngx_queue_t  *next;
};
　　具体操作参见源码。

Nginx中的链表
　　ngx_list_t是Nginx中的list结构。



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_part_t是Nginx中的List的元素结构。



struct ngx_list_part_s {
void             *elts;　　　　//指向数据
ngx_uint_t        nelts;　　　 //长度
ngx_list_part_t  *next;
};
　　具体操作参见源码。

Nginx中的string--ngx_str_t
　　ngx_str_t为Nginx自身实现的string结构，与c中的字符串不同。



typedef struct {
size_t      len;   //字符串长度
u_char     *data;  //指向字符串的指针
} ngx_str_t;
　　ngx_str_t包括两部分，一部分是字符串的长度，另外一部分是数据。注意：这里的数据是指向字符的一个指针，且这个字符串不是以“0”结尾，是通过长度来控制的。使用指针，省去了拷贝所占用的内存空间。
　　其他Nginx-String的操作可以看Nginx源码，还是蛮清晰的。

Ngnix中的内存分配和释放
　　在Ngnix中负责内存分配和释放的结构体为ngx_pool_t，它的原型为ngx_pool_s。



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;
};
　　具体操作参考源码。

Nginx中的Hash表
　　ngx_hash_t是Nginx中的hash表。



typedef struct {
ngx_hash_elt_t  **buckets;
ngx_uint_t        size;
} ngx_hash_t;
　　其中ngx_hash_elt_t为数据。



typedef struct {
void             *value;　　　　//数据 value　　      
u_short           len;         //数据长度？
u_char            name[1];　　　//key
} ngx_hash_elt_t;
　　但是ngx_hash_t的实现又有其几个显著的特点:

• ngx_hash_t不像其他的hash表的实现，可以插入删除元素，它只能一次初始化，就构建起整个hash表以后，既不能再删除，也不能在插入元素了。
  
• ngx_hash_t的开链并不是真的开了一个链表，实际上是开了一段连续的存储空间，几乎可以看做是一个数组。这是因为ngx_hash_t在初始化的时候，会经历一次预计算的过程，提前把每个桶里面会有多少元素放进去给计算出来，这样就提前知道每个桶的大小了。那么就不需要使用链表，一段连续的存储空间就足够了。这也从一定程度上节省了内存的使用。
  

　　实际上ngx_hash_t的使用是非常简单，首先是初始化，然后就可以在里面进行查找了。

Nginx中的红黑树
　　ngx_rbtree_node_s是Nginx中的红黑树节点。



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;
};
　　ngx_rbtree_s是Nginx中的红黑树。



struct ngx_rbtree_s {
ngx_rbtree_node_t     *root;
ngx_rbtree_node_t     *sentinel;
ngx_rbtree_insert_pt   insert;
};
　　具体操作参见源码。

待添加（以后再看)

　　ngx_time_t
　　ngx_slab_
　　ngx_chain_t
　　ngx_hash_key_arrays_t
　　ngx_hash_combined_t
　　ngx_hash_wildcard_t
　　ngx_buf_t