赞
踩
目录
- struct list_head {
- struct list_head *next, *prev;
- };
头插法,将新元素new使用头插法插入到head后面
- /*
- * Insert a new entry between two known consecutive entries.
- *
- * This is only for internal list manipulation where we know
- * the prev/next entries already!
- */
- static inline void __list_add(struct list_head *new,
- struct list_head *prev,
- struct list_head *next)
- {
- next->prev = new;
- new->next = next;
- new->prev = prev;
- prev->next = new;
- }
-
- /**
- * list_add - add a new entry
- * @new: new entry to be added
- * @head: list head to add it after
- *
- * Insert a new entry after the specified head.
- * This is good for implementing stacks.
- */
- static inline void list_add(struct list_head *new, struct list_head *head)
- {
- __list_add(new, head, head->next);
- }
尾插法,将新元素插入尾部,因为是循环链表,直接插在head前面也就相当于插在链表
- static inline void __list_add(struct list_head *new,
- struct list_head *prev,
- struct list_head *next)
- {
- next->prev = new;
- new->next = next;
- new->prev = prev;
- prev->next = new;
- }
-
- /**
- * list_add_tail - add a new entry
- * @new: new entry to be added
- * @head: list head to add it before
- *
- * Insert a new entry before the specified head.
- * This is useful for implementing queues.
- */
- static inline void list_add_tail(struct list_head *new, struct list_head *head)
- {
- __list_add(new, head->prev, head);
- }
删除链表中的指定元素
- /*
- * These are non-NULL pointers that will result in page faults
- * under normal circumstances, used to verify that nobody uses
- * non-initialized list entries.
- */
- #define LIST_POISON1 ((void *) 0x00100100)
- #define LIST_POISON2 ((void *) 0x00200200)
-
- /*
- * Delete a list entry by making the prev/next entries
- * point to each other.
- *
- * This is only for internal list manipulation where we know
- * the prev/next entries already!
- */
- static inline void __list_del(struct list_head * prev, struct list_head * next)
- {
- next->prev = prev;
- prev->next = next;
- }
-
- /**
- * list_del - deletes entry from list.
- * @entry: the element to delete from the list.
- * Note: list_empty() on entry does not return true after this, the entry is
- * in an undefined state.
- */
- static inline void list_del(struct list_head *entry)
- {
- __list_del(entry->prev, entry->next);
- entry->next = LIST_POISON1;
- entry->prev = LIST_POISON2;
- }
判断链表是否为空
- /**
- * list_empty - tests whether a list is empty
- * @head: the list to test.
- */
- static inline int list_empty(const struct list_head *head)
- {
- return head->next == head;
- }
合并链表,将list链表头插到head链表
- /**
- * list_empty - tests whether a list is empty
- * @head: the list to test.
- */
- static inline int list_empty(const struct list_head *head)
- {
- return head->next == head;
- }
-
- static inline void __list_splice(const struct list_head *list,
- struct list_head *head)
- {
- struct list_head *first = list->next;
- struct list_head *last = list->prev;
- struct list_head *at = head->next;
-
- first->prev = head;
- head->next = first;
-
- last->next = at;
- at->prev = last;
- }
-
- /**
- * list_splice - join two lists
- * @list: the new list to add.
- * @head: the place to add it in the first list.
- */
- static inline void list_splice(const struct list_head *list,
- struct list_head *head)
- {
- if (!list_empty(list))
- __list_splice(list, head);
- }
获取结构体实例的首地址
- #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
-
- /**
- * container_of - cast a member of a structure out to the containing structure
- * @ptr: the pointer to the member.
- * @type: the type of the container struct this is embedded in.
- * @member: the name of the member within the struct.
- *
- */
- #define container_of(ptr, type, member) ({ \
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
- (type *)( (char *)__mptr - offsetof(type,member) );})
-
- /**
- * list_entry - get the struct for this entry
- * @ptr: the &struct list_head pointer.
- * @type: the type of the struct this is embedded in.
- * @member: the name of the list_struct within the struct.
- */
- #define list_entry(ptr, type, member) \
- container_of(ptr, type, member)
- //最终的宏定义如下:
- //ptr:结构体实例中特定成员的地址
- //type:结构体类型
- //member:结构体实例中特定成员的名称
- #define list_entry(ptr, type, member) ({ \
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
- (type *)( (char *)__mptr - &((type *)0)->member) );})
-
- /*
- &(type *)0)->member: 在0x0地址上面建立sizeof(type)个字节的type结构体, ->member 取出这个0地址上type结构体里的member成员,最后获取到member距离0x0的偏移.
- typeof( ((type *)0)->member ): 获取member的类型
- const typeof( ((type *)0)->member ) *__mptr = (ptr): 定义一个指针__mptr指向实际地址
- (type *)( (char *)__mptr - &((type *)0)->member) ):m_ptr代表的地址减去member在结构体中的偏移,即为结构体实例的首地址
- */
写到这,突然有个感慨:有些自己觉得不合理的东西,可能是因为自己的无知造成的.
遍历链表
- //__builtin_prefetch() 是 gcc 的一个内置函数。它通过对数据手工预取的方法,减少了读取延迟,从而提高了性能,但该函数也需要 CPU 的支持。
- void __builtin_prefetch (const void *addr, ...);
-
- #define prefetch(x) __builtin_prefetch(x)
-
- /**
- * list_for_each - iterate over a list
- * @pos: the &struct list_head to use as a loop cursor.
- * @head: the head for your list.
- */
- #define list_for_each(pos, head) \
- for (pos = (head)->next; prefetch(pos->next), pos != (head); \
- pos = pos->next)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。