# 优先级队列

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

## 单个的样子

```
    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()

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