Subversion Repositories Kolibri OS

Rev

Rev 4251 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. /*
  2.  * Copyright © 2010-2012 Intel Corporation
  3.  * Copyright © 2010 Francisco Jerez <currojerez@riseup.net>
  4.  *
  5.  * Permission is hereby granted, free of charge, to any person obtaining a
  6.  * copy of this software and associated documentation files (the "Software"),
  7.  * to deal in the Software without restriction, including without limitation
  8.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  9.  * and/or sell copies of the Software, and to permit persons to whom the
  10.  * Software is furnished to do so, subject to the following conditions:
  11.  *
  12.  * The above copyright notice and this permission notice (including the next
  13.  * paragraph) shall be included in all copies or substantial portions of the
  14.  * Software.
  15.  *
  16.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  19.  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  22.  * IN THE SOFTWARE.
  23.  *
  24.  */
  25.  
  26. #ifndef _INTEL_LIST_H_
  27. #define _INTEL_LIST_H_
  28.  
  29. #include <stdbool.h>
  30.  
  31. /**
  32.  * @file Classic doubly-link circular list implementation.
  33.  * For real usage examples of the linked list, see the file test/list.c
  34.  *
  35.  * Example:
  36.  * We need to keep a list of struct foo in the parent struct bar, i.e. what
  37.  * we want is something like this.
  38.  *
  39.  *     struct bar {
  40.  *          ...
  41.  *          struct foo *list_of_foos; -----> struct foo {}, struct foo {}, struct foo{}
  42.  *          ...
  43.  *     }
  44.  *
  45.  * We need one list head in bar and a list element in all list_of_foos (both are of
  46.  * data type 'struct list').
  47.  *
  48.  *     struct bar {
  49.  *          ...
  50.  *          struct list list_of_foos;
  51.  *          ...
  52.  *     }
  53.  *
  54.  *     struct foo {
  55.  *          ...
  56.  *          struct list entry;
  57.  *          ...
  58.  *     }
  59.  *
  60.  * Now we initialize the list head:
  61.  *
  62.  *     struct bar bar;
  63.  *     ...
  64.  *     list_init(&bar.list_of_foos);
  65.  *
  66.  * Then we create the first element and add it to this list:
  67.  *
  68.  *     struct foo *foo = malloc(...);
  69.  *     ....
  70.  *     list_add(&foo->entry, &bar.list_of_foos);
  71.  *
  72.  * Repeat the above for each element you want to add to the list. Deleting
  73.  * works with the element itself.
  74.  *      list_del(&foo->entry);
  75.  *      free(foo);
  76.  *
  77.  * Note: calling list_del(&bar.list_of_foos) will set bar.list_of_foos to an empty
  78.  * list again.
  79.  *
  80.  * Looping through the list requires a 'struct foo' as iterator and the
  81.  * name of the field the subnodes use.
  82.  *
  83.  * struct foo *iterator;
  84.  * list_for_each_entry(iterator, &bar.list_of_foos, entry) {
  85.  *      if (iterator->something == ...)
  86.  *             ...
  87.  * }
  88.  *
  89.  * Note: You must not call list_del() on the iterator if you continue the
  90.  * loop. You need to run the safe for-each loop instead:
  91.  *
  92.  * struct foo *iterator, *next;
  93.  * list_for_each_entry_safe(iterator, next, &bar.list_of_foos, entry) {
  94.  *      if (...)
  95.  *              list_del(&iterator->entry);
  96.  * }
  97.  *
  98.  */
  99.  
  100. /**
  101.  * The linkage struct for list nodes. This struct must be part of your
  102.  * to-be-linked struct. struct list is required for both the head of the
  103.  * list and for each list node.
  104.  *
  105.  * Position and name of the struct list field is irrelevant.
  106.  * There are no requirements that elements of a list are of the same type.
  107.  * There are no requirements for a list head, any struct list can be a list
  108.  * head.
  109.  */
  110.  
  111. struct list {
  112.     struct list *next, *prev;
  113. };
  114.  
  115. /**
  116.  * Initialize the list as an empty list.
  117.  *
  118.  * Example:
  119.  * list_init(&bar->list_of_foos);
  120.  *
  121.  * @param The list to initialized.
  122.  */
  123. static void
  124. list_init(struct list *list)
  125. {
  126.     list->next = list->prev = list;
  127. }
  128.  
  129. static inline void
  130. __list_add(struct list *entry,
  131.             struct list *prev,
  132.             struct list *next)
  133. {
  134.     next->prev = entry;
  135.     entry->next = next;
  136.     entry->prev = prev;
  137.     prev->next = entry;
  138. }
  139.  
  140. /**
  141.  * Insert a new element after the given list head. The new element does not
  142.  * need to be initialised as empty list.
  143.  * The list changes from:
  144.  *      head → some element → ...
  145.  * to
  146.  *      head → new element → older element → ...
  147.  *
  148.  * Example:
  149.  * struct foo *newfoo = malloc(...);
  150.  * list_add(&newfoo->entry, &bar->list_of_foos);
  151.  *
  152.  * @param entry The new element to prepend to the list.
  153.  * @param head The existing list.
  154.  */
  155. static inline void
  156. list_add(struct list *entry, struct list *head)
  157. {
  158.     __list_add(entry, head, head->next);
  159. }
  160.  
  161. static inline void
  162. list_add_tail(struct list *entry, struct list *head)
  163. {
  164.     __list_add(entry, head->prev, head);
  165. }
  166.  
  167. static inline void list_replace(struct list *old,
  168.                                 struct list *new)
  169. {
  170.         new->next = old->next;
  171.         new->next->prev = new;
  172.         new->prev = old->prev;
  173.         new->prev->next = new;
  174. }
  175.  
  176. #define list_last_entry(ptr, type, member) \
  177.     list_entry((ptr)->prev, type, member)
  178.  
  179. #define list_for_each(pos, head)                                \
  180.     for (pos = (head)->next; pos != (head); pos = pos->next)
  181.  
  182. /**
  183.  * Append a new element to the end of the list given with this list head.
  184.  *
  185.  * The list changes from:
  186.  *      head → some element → ... → lastelement
  187.  * to
  188.  *      head → some element → ... → lastelement → new element
  189.  *
  190.  * Example:
  191.  * struct foo *newfoo = malloc(...);
  192.  * list_append(&newfoo->entry, &bar->list_of_foos);
  193.  *
  194.  * @param entry The new element to prepend to the list.
  195.  * @param head The existing list.
  196.  */
  197. static inline void
  198. list_append(struct list *entry, struct list *head)
  199. {
  200.     __list_add(entry, head->prev, head);
  201. }
  202.  
  203.  
  204. static inline void
  205. __list_del(struct list *prev, struct list *next)
  206. {
  207.         assert(next->prev == prev->next);
  208.         next->prev = prev;
  209.         prev->next = next;
  210. }
  211.  
  212. static inline void
  213. _list_del(struct list *entry)
  214. {
  215.     assert(entry->prev->next == entry);
  216.     assert(entry->next->prev == entry);
  217.     __list_del(entry->prev, entry->next);
  218. }
  219.  
  220. /**
  221.  * Remove the element from the list it is in. Using this function will reset
  222.  * the pointers to/from this element so it is removed from the list. It does
  223.  * NOT free the element itself or manipulate it otherwise.
  224.  *
  225.  * Using list_del on a pure list head (like in the example at the top of
  226.  * this file) will NOT remove the first element from
  227.  * the list but rather reset the list as empty list.
  228.  *
  229.  * Example:
  230.  * list_del(&foo->entry);
  231.  *
  232.  * @param entry The element to remove.
  233.  */
  234. static inline void
  235. list_del(struct list *entry)
  236. {
  237.     _list_del(entry);
  238.     list_init(entry);
  239. }
  240.  
  241. static inline void list_move(struct list *list, struct list *head)
  242. {
  243.         if (list->prev != head) {
  244.                 _list_del(list);
  245.                 list_add(list, head);
  246.         }
  247. }
  248.  
  249. static inline void list_move_tail(struct list *list, struct list *head)
  250. {
  251.         _list_del(list);
  252.         list_add_tail(list, head);
  253. }
  254.  
  255. /**
  256.  * Check if the list is empty.
  257.  *
  258.  * Example:
  259.  * list_is_empty(&bar->list_of_foos);
  260.  *
  261.  * @return True if the list contains one or more elements or False otherwise.
  262.  */
  263. static inline bool
  264. list_is_empty(struct list *head)
  265. {
  266.     return head->next == head;
  267. }
  268.  
  269. /**
  270.  * Alias of container_of
  271.  */
  272. #define list_entry(ptr, type, member) \
  273.     container_of(ptr, type, member)
  274.  
  275. /**
  276.  * Retrieve the first list entry for the given list pointer.
  277.  *
  278.  * Example:
  279.  * struct foo *first;
  280.  * first = list_first_entry(&bar->list_of_foos, struct foo, list_of_foos);
  281.  *
  282.  * @param ptr The list head
  283.  * @param type Data type of the list element to retrieve
  284.  * @param member Member name of the struct list field in the list element.
  285.  * @return A pointer to the first list element.
  286.  */
  287. #define list_first_entry(ptr, type, member) \
  288.     list_entry((ptr)->next, type, member)
  289.  
  290. /**
  291.  * Retrieve the last list entry for the given listpointer.
  292.  *
  293.  * Example:
  294.  * struct foo *first;
  295.  * first = list_last_entry(&bar->list_of_foos, struct foo, list_of_foos);
  296.  *
  297.  * @param ptr The list head
  298.  * @param type Data type of the list element to retrieve
  299.  * @param member Member name of the struct list field in the list element.
  300.  * @return A pointer to the last list element.
  301.  */
  302. #define list_last_entry(ptr, type, member) \
  303.     list_entry((ptr)->prev, type, member)
  304.  
  305. #define __container_of(ptr, sample, member)                             \
  306.     (void *)((char *)(ptr)                                              \
  307.              - ((char *)&(sample)->member - (char *)(sample)))
  308. /**
  309.  * Loop through the list given by head and set pos to struct in the list.
  310.  *
  311.  * Example:
  312.  * struct foo *iterator;
  313.  * list_for_each_entry(iterator, &bar->list_of_foos, entry) {
  314.  *      [modify iterator]
  315.  * }
  316.  *
  317.  * This macro is not safe for node deletion. Use list_for_each_entry_safe
  318.  * instead.
  319.  *
  320.  * @param pos Iterator variable of the type of the list elements.
  321.  * @param head List head
  322.  * @param member Member name of the struct list in the list elements.
  323.  *
  324.  */
  325. #define list_for_each_entry(pos, head, member)                          \
  326.     for (pos = __container_of((head)->next, pos, member);               \
  327.          &pos->member != (head);                                        \
  328.          pos = __container_of(pos->member.next, pos, member))
  329.  
  330. #define list_for_each_entry_reverse(pos, head, member)                          \
  331.     for (pos = __container_of((head)->prev, pos, member);               \
  332.          &pos->member != (head);                                        \
  333.          pos = __container_of(pos->member.prev, pos, member))
  334.  
  335. /**
  336.  * Loop through the list, keeping a backup pointer to the element. This
  337.  * macro allows for the deletion of a list element while looping through the
  338.  * list.
  339.  *
  340.  * See list_for_each_entry for more details.
  341.  */
  342. #define list_for_each_entry_safe(pos, tmp, head, member)                \
  343.     for (pos = __container_of((head)->next, pos, member),               \
  344.          tmp = __container_of(pos->member.next, pos, member);           \
  345.          &pos->member != (head);                                        \
  346.          pos = tmp, tmp = __container_of(pos->member.next, tmp, member))
  347.  
  348.  
  349. #undef container_of
  350. #define container_of(ptr, type, member) \
  351.         ((type *)((char *)(ptr) - (char *) &((type *)0)->member))
  352.  
  353. #endif /* _INTEL_LIST_H_ */
  354.  
  355.