Linux Kernel has lots of data structure such as list (including linked list, double linked lists), red-black tree, B Tree , Interval tree, Heap, Radix tree, spin locks and so on.
I will put some articles for these interesting data structures.
List is most simple data structure we could start with.
Even for such simple data structure, Linux Kernel still has some operation which User-Space data structure didn’t use.
the definition of list_head
1
2
3
| struct list_head {
struct list_head *next, *prev;
}; |
struct list_head {
struct list_head *next, *prev;
};
It is a double linked list.
1
2
3
4
5
| static inline void
INIT_LIST_HEAD(struct list_head *list)
{
list->next = list->prev = list;
} |
static inline void
INIT_LIST_HEAD(struct list_head *list)
{
list->next = list->prev = list;
}
1
2
3
4
5
6
7
8
9
| static inline void
__list_add(struct list_head *entry,
struct list_head *prev, struct list_head *next)
{
next->prev = entry;
entry->next = next;
entry->prev = prev;
prev->next = entry;
} |
static inline void
__list_add(struct list_head *entry,
struct list_head *prev, struct list_head *next)
{
next->prev = entry;
entry->next = next;
entry->prev = prev;
prev->next = entry;
}
what this function todo is put entry between next and prev.
prev –> entry <--- next
1
2
3
4
| static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
} |
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
append something into tail is to add entry between head and tail(head and tail are linked together)
1
2
3
4
5
| static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
} |
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
del is to delete all items between prev and next. therefore, set next’s prev to prev node.
and prev node’s next to be next node.
1
2
3
4
5
6
7
8
9
| static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
INIT_LIST_HEAD(old); // let old's all pointer pointed to itself. |
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
INIT_LIST_HEAD(old); // let old's all pointer pointed to itself.
delete old one and linked new one to old one’s postion.
1
2
3
4
5
| static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
} |
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
}
delete from one list and add as another’s head
1
2
3
4
5
6
7
8
9
| static inline void list_rotate_left(struct list_head *head)
{
struct list_head *first;
if (!list_empty(head)) {
first = head->next;
list_move_tail(first, head);
}
} |
static inline void list_rotate_left(struct list_head *head)
{
struct list_head *first;
if (!list_empty(head)) {
first = head->next;
list_move_tail(first, head);
}
}
move head->next to head and tail.
some other functions such as list_cut_position is to split list into two.
and list_splice is to join two lists
1
2
3
4
| #define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev) |
#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev)
some macro are defined in such format, there for developer don’t have to write “for” every time
