# 优先级队列

优先级列表，就是在插入链表时，要考虑链表元素的某个特征值。在内核中优先级列表由两个双链表组合实现。

## 单个的样子

```
    plist_node
    +-----------------------+
    |prio                   |
    |    (int)              |
    |prio_list              |
    |node_list              |
    |    (struct list_head*)|
    +-----------------------+
```

其中

* prio表示元素的优先级
* prio\_list是优先级链表元素
* node\_list是整个链表元素

乍一看觉得为啥要两个链表，从下面整体的图上会看得比较清楚。

## 整体的样子

内核开发者给优先级列表画了图：

```
pl:prio_list (only for plist_node)
nl:node_list
  HEAD|             NODE(S)
      |
      ||------------------------------------|
      ||->|pl|<->|pl|<--------------->|pl|<-|
      |   |10|   |21|   |21|   |21|   |40|   (prio)
      |   |  |   |  |   |  |   |  |   |  |
      |   |  |   |  |   |  |   |  |   |  |
|->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-|
|-------------------------------------------|
```

意思是

* prio\_list是链接没有优先级中第一个元素的链表
* node\_list则是所有的元素都会链接的链表

不知道是不是讲清楚了，不过实现上就是这么有意思。

## 常用API

* plist\_add()
* plist\_del()

主要就是这两个，没啥花花肠子。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://richardweiyang-2.gitbook.io/kernel-exploring/00-index-3/03-plist.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.