{"id":227,"date":"2016-03-06T14:03:35","date_gmt":"2016-03-06T14:03:35","guid":{"rendered":"http:\/\/emacslisp.com\/?p=227"},"modified":"2016-03-06T14:08:35","modified_gmt":"2016-03-06T14:08:35","slug":"linux-kernel-data-structure-list-in-includelinuxlist-h","status":"publish","type":"post","link":"http:\/\/emacslisp.com\/?p=227","title":{"rendered":"Linux Kernel – Data structure List in include\/linux\/list.h"},"content":{"rendered":"

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.<\/strong>
\nI will put some articles for these interesting data structures.<\/p>\n

List is most simple data structure we could start with.<\/p>\n

Even for such simple data structure, Linux Kernel still has some operation which User-Space data structure didn’t use.<\/p>\n

the definition of list_head<\/p>\n

 \r\nstruct list_head {\r\n    struct list_head *next, *prev;\r\n};\r\n<\/pre>\n
It is a double linked list.<\/p>\n
 \r\nstatic inline void\r\nINIT_LIST_HEAD(struct list_head *list)\r\n{\r\n    list->next = list->prev = list;\r\n}\r\n<\/pre>\n
 \r\nstatic inline void\r\n__list_add(struct list_head *entry,\r\n                struct list_head *prev, struct list_head *next)\r\n{\r\n    next->prev = entry;\r\n    entry->next = next;\r\n    entry->prev = prev;\r\n    prev->next = entry;\r\n}\r\n<\/pre>\n
what this function todo is put entry between next and prev.<\/p>\n
prev –> entry <--- next\n\n     \n\n\n
 \r\nstatic inline void list_add_tail(struct list_head *new, struct list_head *head)\r\n{\r\n\t__list_add(new, head->prev, head);\r\n}\r\n<\/pre>\n
append something into tail is to add entry between head and tail(head and tail are linked together)<\/p>\n
 \r\nstatic inline void __list_del(struct list_head * prev, struct list_head * next)\r\n{\r\n\tnext->prev = prev;\r\n\tprev->next = next;\r\n}\r\n<\/pre>\n
del is to delete all items between prev and next. therefore, set next’s prev to prev node.
\nand prev node’s next to be next node.<\/p>\n
 \r\nstatic inline void list_replace(struct list_head *old,\r\n\t\t\t\tstruct list_head *new)\r\n{\r\n\tnew->next = old->next;\r\n\tnew->next->prev = new;\r\n\tnew->prev = old->prev;\r\n\tnew->prev->next = new;\r\n}\r\nINIT_LIST_HEAD(old); \/\/ let old's all pointer pointed to itself.\r\n<\/pre>\n
delete old one and linked new one to old one’s postion.<\/p>\n
 \r\nstatic inline void list_move(struct list_head *list, struct list_head *head)\r\n{\r\n\t__list_del_entry(list);\r\n\tlist_add(list, head);\r\n}\r\n<\/pre>\n
delete from one list and add as another’s head<\/p>\n
 \r\nstatic inline void list_rotate_left(struct list_head *head)\r\n{\r\n\tstruct list_head *first;\r\n\r\n\tif (!list_empty(head)) {\r\n\t\tfirst = head->next;\r\n\t\tlist_move_tail(first, head);\r\n\t}\r\n}\r\n<\/pre>\n
move head->next to head and tail.<\/p>\n
some other functions such as list_cut_position is to split list into two.
\nand list_splice is to join two lists<\/p>\n
 \r\n#define list_for_each_prev_safe(pos, n, head) \\\r\n\tfor (pos = (head)->prev, n = pos->prev; \\\r\n\t     pos != (head); \\\r\n\t     pos = n, n = pos->prev)\r\n<\/pre>\n
some macro are defined in such format, there for developer don’t have to write “for” every time<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,11],"tags":[],"class_list":["post-227","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-linux-kernel-analysis"],"_links":{"self":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts\/227","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=227"}],"version-history":[{"count":6,"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts\/227\/revisions"}],"predecessor-version":[{"id":233,"href":"http:\/\/emacslisp.com\/index.php?rest_route=\/wp\/v2\/posts\/227\/revisions\/233"}],"wp:attachment":[{"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=227"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/emacslisp.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}