linux内核中的几种链表
参考
双向循环链表 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)
-
参考
Linux 内核 hlist 详解
linux内核分析--内核中使用的数据结构之哈希表hlist（三） -
应用
kernel/cgroup/cgroup.c
/*
* hash table for cgroup groups. This improves the performance to find
* an existing css_set. This hash doesn't (currently) take into
* account cgroups in empty hierarchies.
*/
#define CSS_SET_HASH_BITS 7
static DEFINE_HASHTABLE(css_set_table, CSS_SET_HASH_BITS);
key = css_set_hash(cset->subsys);
hash_add(css_set_table, &cset->hlist, key);
降序优先排序的双向链表 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);
-
参考：
Linux中的Plist -- 降序优先排序的双向链表 -
应用
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);
}