数组和链表safe

数组和链表safe"/>

数组和链表safe

 数组

数组是需要使用连续内存时候申请的一种内存，int a[10],声明定义必须制定大小

int a[]可作为参数传入是代表a的首地址

访问数组内的数据：a[1]下表方式，其实也是一个地址取值，去a+1的地址上取值*(a+1)

一个数据+1代表，地址后移数据的类型大小sizeof(a)

连续内存申请：

 结构体中的最后一个元素为int buf[0],这时候buf是不占内存大小的

当malloc申请大于结构体本身内存大小时候，buf就可以指向了后台多余内存的地址和类型

链表

链表用于不定长的不连续内存的申请

不定长：每加一个元素都是看时机的，所以每次都要malloc

不连续，每次malloc的时候只是一个元素，和前面元素不连续，就需要一根线连起来，不然我们就把前面的元素弄丢了

struct list {

    struct list *prev,*next;

};

链表仅是一根线，线上有自己的数据类型mydata

struct mylist {

    void *mydata;

    struct list;

};

还需要解决的问题：添加一个，删除一个，遍历查找数据

struct inline void __list_add(struct list  *new, struct list  *prev, struct list  *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

添加需要知道新的数据地址，要添加的地方，

需要建立关系：前一数据的后，后一数据的前，新数据的前，新数据的后

struct inline void list_add(struct list  *new, struct list  *head)
{
    __list_add(new, head, head->next);
}

添加尾部，确定位置是链表头的前一元素

struct inline void list_add_tail(struct list  *new, struct list  *head)
{
    __list_add(new, head->prev, head);
}

删除一个元素，需要确定关系删除数据的前面数据的后，删除数据的后面数据的前

struct inline void __list_del(struct list  *prev, struct list *next)
{
    prev->next = next;
    next->prev = prev;
}

要删除的元素需要链表赋值清零

struct inline void list_del(struct list  *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = (void *) 0;
    entry->prev = (void *) 0;
}

遍历，从头开始遍历，到循环到头停止

开始赋值，pos=head->next，这里head没有mydata

条件：pos!=head

执行动作：pos=pos->next

safe：删除当前节点时候，执行动作会有空指针，所以需要n预先存储pos->next

//CPU提供的 prefetch 指令将数据放入缓存
#define list_for_each(pos,head) \
for (pos = head->next, prefetch(pos->next); pos != head;\
    pos = pos->next, prefetch(pos->next))

#define list_for_each_prev(pos,head) \
for (pos = head->prev; pos != head; pos = pos->prev)
//因此只遍历链表不删除节点时可以使用前者，若有删除节点的操作，则要使用后者

#define list_for_each_safe(pos, n, head) \
for (pos = head->next, n = pos->next; pos != head; pos = n, n = pos->next)

知道结构体内某一成员变量地址，求结构体地址
//上到下加法，下到上减法
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

type 0地址是结构体所在地址，那么member就是绝对地址，member的相对地址ptr就可以求得结构体当前地址

#define container_of(ptr, type, member) ({          \
    const typeof(((type *)0)->member)*__mptr = (ptr);    \
             (type *)((char *)__mptr - offsetof(type, member)); })