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