参考
双向循环链表 list_head
- 相关文件：
include/linux/list.h - 数据结构：
struct list_head { struct list_head *next, *prev; };
- 接口
static inline void INIT_LIST_HEAD(struct list_head *list); static inline void list_add(struct list_head *new, struct list_head *head); static inline void list_del(struct list_head *entry);
哈希链表 hlist
- 相关文件：
include/linux/list.h
include/linux/hashtable.h - 数据结构
struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; };
- 接口
static inline void hlist_del(struct hlist_node *n); static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h); hlist_for_each_entry(pos, head, member)
kernel/cgroup/cgroup.c
无锁链表llist
- 相关文件
lib/llist.c
降序优先排序的双向链表 plist
- 相关文件
include/linux/plist.h
lib/plist.c - 数据结构
struct plist_head { struct list_head node_list; }; struct plist_node { int prio; struct list_head prio_list; struct list_head node_list; };
- 接口
static inline void plist_head_init(struct plist_head *head); static inline void plist_node_init(struct plist_node *node, int prio); void plist_add(struct plist_node *node, struct plist_head *head); void plist_del(struct plist_node *node, struct plist_head *head);
mm/swapfile.c
/* * all active swap_info_structs * protected with swap_lock, and ordered by priority. */ PLIST_HEAD(swap_active_head); static void setup_swap_info(struct swap_info_struct *p, int prio, unsigned char *swap_map, struct swap_cluster_info *cluster_info) { int i; if (prio >= 0) p->prio = prio; else p->prio = --least_priority; /* * the plist prio is negated because plist ordering is * low-to-high, while swap ordering is high-to-low */ p->list.prio = -p->prio; for_each_node(i) { if (p->prio >= 0) p->avail_lists[i].prio = -p->prio; else { if (swap_node(p) == i) p->avail_lists[i].prio = 1; else p->avail_lists[i].prio = -p->prio; } } p->swap_map = swap_map; p->cluster_info = cluster_info; } static void _enable_swap_info(struct swap_info_struct *p) { p->flags |= SWP_WRITEOK | SWP_VALID; atomic_long_add(p->pages, &nr_swap_pages); total_swap_pages += p->pages; plist_add(&p->list, &swap_active_head); add_to_avail_list(p); }
