git.gag.com Git - fw/altos/blob - src/kernel/ao_list.h

   1 /*
   2  * Copyright © 2012 Keith Packard <keithp@keithp.com>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
  17  */
  18
  19 #ifndef _AO_LIST_H_
  20 #define _AO_LIST_H_
  21
  22 #include <stddef.h>
  23
  24 struct ao_list {
  25         struct ao_list  *next, *prev;
  26 };
  27
  28 static inline void
  29 ao_list_init(struct ao_list *list)
  30 {
  31         list->next = list->prev = list;
  32 }
  33
  34 static inline void
  35 __ao_list_add(struct ao_list *list, struct ao_list *prev, struct ao_list *next)
  36 {
  37         next->prev = list;
  38         list->next = next;
  39         list->prev = prev;
  40         prev->next = list;
  41 }
  42
  43 /**
  44  * Insert a new element after the given list head. The new element does not
  45  * need to be initialised as empty list.
  46  * The list changes from:
  47  *      head → some element → ...
  48  * to
  49  *      head → new element → older element → ...
  50  *
  51  * Example:
  52  * struct foo *newfoo = malloc(...);
  53  * ao_list_add(&newfoo->entry, &bar->list_of_foos);
  54  *
  55  * @param entry The new element to prepend to the list.
  56  * @param head The existing list.
  57  */
  58 static inline void
  59 ao_list_insert(struct ao_list *entry, struct ao_list *head)
  60 {
  61     __ao_list_add(entry, head, head->next);
  62 }
  63
  64 /**
  65  * Append a new element to the end of the list given with this list head.
  66  *
  67  * The list changes from:
  68  *      head → some element → ... → lastelement
  69  * to
  70  *      head → some element → ... → lastelement → new element
  71  *
  72  * Example:
  73  * struct foo *newfoo = malloc(...);
  74  * ao_list_append(&newfoo->entry, &bar->list_of_foos);
  75  *
  76  * @param entry The new element to prepend to the list.
  77  * @param head The existing list.
  78  */
  79 static inline void
  80 ao_list_append(struct ao_list *entry, struct ao_list *head)
  81 {
  82     __ao_list_add(entry, head->prev, head);
  83 }
  84
  85 static inline void
  86 __ao_list_del(struct ao_list *prev, struct ao_list *next)
  87 {
  88     next->prev = prev;
  89     prev->next = next;
  90 }
  91
  92 /**
  93  * Remove the element from the list it is in. Using this function will reset
  94  * the pointers to/from this element so it is removed from the list. It does
  95  * NOT free the element itself or manipulate it otherwise.
  96  *
  97  * Using ao_list_del on a pure list head (like in the example at the top of
  98  * this file) will NOT remove the first element from
  99  * the list but rather reset the list as empty list.
 100  *
 101  * Example:
 102  * ao_list_del(&foo->entry);
 103  *
 104  * @param entry The element to remove.
 105  */
 106 static inline void
 107 ao_list_del(struct ao_list *entry)
 108 {
 109     __ao_list_del(entry->prev, entry->next);
 110     ao_list_init(entry);
 111 }
 112
 113 /**
 114  * Check if the list is empty.
 115  *
 116  * Example:
 117  * ao_list_is_empty(&bar->list_of_foos);
 118  *
 119  * @return True if the list contains one or more elements or False otherwise.
 120  */
 121 static inline uint8_t
 122 ao_list_is_empty(struct ao_list *head)
 123 {
 124     return head->next == head;
 125 }
 126
 127 /**
 128  * Returns a pointer to the container of this list element.
 129  *
 130  * Example:
 131  * struct foo* f;
 132  * f = container_of(&foo->entry, struct foo, entry);
 133  * assert(f == foo);
 134  *
 135  * @param ptr Pointer to the struct ao_list.
 136  * @param type Data type of the list element.
 137  * @param member Member name of the struct ao_list field in the list element.
 138  * @return A pointer to the data struct containing the list head.
 139  */
 140 #define ao_container_of(ptr, type, member) \
 141         ((type *)((void *) ((char *)(ptr) - offsetof(type, member))))
 142
 143 /**
 144  * Alias of ao_container_of
 145  */
 146 #define ao_list_entry(ptr, type, member) \
 147     ao_container_of(ptr, type, member)
 148
 149 /**
 150  * Retrieve the first list entry for the given list pointer.
 151  *
 152  * Example:
 153  * struct foo *first;
 154  * first = ao_list_first_entry(&bar->list_of_foos, struct foo, list_of_foos);
 155  *
 156  * @param ptr The list head
 157  * @param type Data type of the list element to retrieve
 158  * @param member Member name of the struct ao_list field in the list element.
 159  * @return A pointer to the first list element.
 160  */
 161 #define ao_list_first_entry(ptr, type, member) \
 162     ao_list_entry((ptr)->next, type, member)
 163
 164 /**
 165  * Retrieve the last list entry for the given listpointer.
 166  *
 167  * Example:
 168  * struct foo *first;
 169  * first = ao_list_last_entry(&bar->list_of_foos, struct foo, list_of_foos);
 170  *
 171  * @param ptr The list head
 172  * @param type Data type of the list element to retrieve
 173  * @param member Member name of the struct ao_list field in the list element.
 174  * @return A pointer to the last list element.
 175  */
 176 #define ao_list_last_entry(ptr, type, member) \
 177     ao_list_entry((ptr)->prev, type, member)
 178
 179 /**
 180  * Loop through the list given by head and set pos to struct in the list.
 181  *
 182  * Example:
 183  * struct foo *iterator;
 184  * ao_list_for_each_entry(iterator, &bar->list_of_foos, entry) {
 185  *      [modify iterator]
 186  * }
 187  *
 188  * This macro is not safe for node deletion. Use ao_list_for_each_entry_safe
 189  * instead.
 190  *
 191  * @param pos Iterator variable of the type of the list elements.
 192  * @param head List head
 193  * @param member Member name of the struct ao_list in the list elements.
 194  *
 195  */
 196 #define ao_list_for_each_entry(pos, head, type, member)                 \
 197     for (pos = ao_container_of((head)->next, type, member);             \
 198          &pos->member != (head);                                        \
 199          pos = ao_container_of(pos->member.next, type, member))
 200
 201 /**
 202  * Loop through the list, keeping a backup pointer to the element. This
 203  * macro allows for the deletion of a list element while looping through the
 204  * list.
 205  *
 206  * See ao_list_for_each_entry for more details.
 207  */
 208 #define ao_list_for_each_entry_safe(pos, tmp, head, type, member)               \
 209         for ((pos = ao_container_of((head)->next, type, member)),               \
 210              (tmp = ao_container_of(pos->member.next, type, member));           \
 211              &pos->member != (head);                                            \
 212              (pos = tmp), (tmp = ao_container_of(pos->member.next, type, member)))
 213
 214 #endif /* _AO_LIST_H_ */