string

nginx_str_主要解决c语言 \0截断的问题，网络字节流中可能出现\0截断问题 下面对比下可能的设计对应的不足

//1 柔性数组 使用场景
//printf 很不方便且必须连续内存(内存池分配),长度确定 str长度修改后内存分配问题
//一般用来不定长数据的传输
struct ngx_str_t {
    int len;
    char data[0]; //首字母
}

//2 nginx采用的指针数组
#nginx可以重复引用一段字符串内存，data可以指向任意内存，长度表示结束，
#而不用去copy一份自己的字符串
struct ngx_str_t {
    int len;
    char *data
}
//常见的宏
//字符串初始化
#define ngx_string(str)     { sizeof(str) - 1, (u_char *) str }
...

动态数组

typedef struct {
    void        *elts; //数据指针,实际存储的数据
    ngx_uint_t   nelts; //已存储数组元素个数
    size_t       size; //每个数组大小
    ngx_uint_t   nalloc; //分配的数组总个数
    ngx_pool_t  *pool; //对应内存池
} ngx_array_t;

//创建数组,内存池地址,数组元素个数,数组元素大小
ngx_array_t *ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size);
//如果是池中最后一个,且池还没满,会从池中扩容
//if (u_char *) a->elts + size == p->d.last && p->d.last + a->size <= p->d.end
//否则扩容2倍
void *ngx_array_push(ngx_array_t *a);
void *ngx_array_push_n(ngx_array_t *a, ngx_uint_t n);

//补充go的切片 1.18之前扩容1.25大于1024固定两倍
doublecap := newcap + newcap
if cap > doublecap {
    newcap = cap
} else {
    if old.len < 1024 {
        newcap = doublecap
    } else {
        for 0 < newcap && newcap < cap {
            newcap += newcap / 4
        }
        if newcap <= 0 {
            newcap = cap
        }
    }
}

//1.18之后 256内为两倍,256后每次为(newcap += (newcap + 3*threshold) / 4)直到分配到需要的容量
const threshold = 256
if old.cap < threshold {
    newcap = doublecap
} else {
    // Check 0 < newcap to detect overflow
    // and prevent an infinite loop.
    for 0 < newcap && newcap < cap {
    // Transition from growing 2x for small slices
    // to growing 1.25x for large slices. This formula
    // gives a smooth-ish transition between the two.
        newcap += (newcap + 3*threshold) / 4
    }
    // Set newcap to the requested cap when
    // the newcap calculation overflowed.
    if newcap <= 0 {
        newcap = cap
    }
}

list

//节点数据
struct ngx_list_part_s {
    void             *elts; //指向的内存块 大小size_t*ngx_uint_t
    ngx_uint_t        nelts; //已经使用了多少个
    ngx_list_part_t  *next; //下一个节点地址
};
//链表 节点大小都是一致 在一整块内存中
typedef struct {
    ngx_list_part_t  *last; //最后一个节点指针
    ngx_list_part_t   part; //第一个节点内容
    size_t            size; //size_t 每个节点大小
    ngx_uint_t        nalloc; //数量
    ngx_pool_t       *pool; //内存池地址
} ngx_list_t;
//初始化
ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);
ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size)

//只需要增加 同数组一样,返回内存地址,由用户自定义值,满了后,开辟新内存池
//释放直接释放整个pool
void *ngx_list_push(ngx_list_t *list);

队列

//双向循环链表，只有前后节点指针,我们来看数据是怎么存储的
struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};
//宏获取节点数据
//link 偏移量 相对于type 结构体开头字节的偏移量,偏移量则是queue在test的位置
//如struct test{int a;int b;ngx_queue_t queue;}
#define ngx_queue_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))

哈希表

一般哈希表实现为拉链法,开放地址寻址法,nginx采用的为开放地址寻址,当key冲突时像后便利, 散列值+1的地方是否有值存在,存在则继续向后便利,直到无值占用该位置,取值同理

//在nginx中 主要存储http head头
typedef struct {
    ngx_uint_t        hash;         //key hash值
    ngx_str_t         key;          //header key 如Status Code
    ngx_str_t         value;        //header value 如200
    u_char           *lowcase_key;  //key 全小写,
} ngx_table_elt_t;

//文件内存块
struct ngx_chain_s {
    ngx_buf_t    *buf;
    ngx_chain_t  *next;
};

struct ngx_buf_s {
    u_char          *pos; //内容起始
    u_char          *last; //内容结束
    off_t            file_pos; //文件定位开始
    off_t            file_last; //文件结束位置
    u_char          *start;         /* start of buffer */
    u_char          *end;           /* end of buffer */
    ngx_buf_tag_t    tag;
    ngx_file_t      *file;
    ngx_buf_t       *shadow;
    ......
};

红黑树,基数树

//后续补充