1 /* 2 * Copyright 2003-2006, Axel Dörfler, axeld@pinc-software.de. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 7 #include <util/list.h> 8 9 10 #define GET_ITEM(list, item) ((void *)((uint8 *)item - list->offset)) 11 #define GET_LINK(list, item) ((list_link *)((uint8 *)item + list->offset)) 12 13 14 /** Initializes the list with a specified offset to the link 15 * structure in the items that will be part of the list. 16 */ 17 18 void 19 list_init_etc(struct list *list, int32 offset) 20 { 21 list->link.next = list->link.prev = &list->link; 22 list->offset = offset; 23 } 24 25 26 void 27 list_init(struct list *list) 28 { 29 list_init_etc(list, 0); 30 } 31 32 33 /** Adds a link to the head of the list 34 */ 35 36 void 37 list_add_link_to_head(struct list *list, void *_link) 38 { 39 list_link *link = (list_link *)_link; 40 41 link->next = list->link.next; 42 link->prev = &list->link; 43 44 list->link.next->prev = link; 45 list->link.next = link; 46 } 47 48 49 /** Adds a link to the tail of the list 50 */ 51 52 void 53 list_add_link_to_tail(struct list *list, void *_link) 54 { 55 list_link *link = (list_link *)_link; 56 57 link->next = &list->link; 58 link->prev = list->link.prev; 59 60 list->link.prev->next = link; 61 list->link.prev = link; 62 } 63 64 65 /** Removes a link from the list it's currently in. 66 * Note: the link has to be in a list when you call this function. 67 */ 68 69 void 70 list_remove_link(void *_link) 71 { 72 list_link *link = (list_link *)_link; 73 74 link->next->prev = link->prev; 75 link->prev->next = link->next; 76 } 77 78 79 static inline list_link * 80 get_next_link(struct list *list, list_link *link) 81 { 82 if (link->next == &list->link) 83 return NULL; 84 85 return link->next; 86 } 87 88 89 static inline list_link * 90 get_prev_link(struct list *list, list_link *link) 91 { 92 if (link->prev == &list->link) 93 return NULL; 94 95 return link->prev; 96 } 97 98 99 /** Gets the successor for the current item. If the passed 100 * item is NULL, it returns the first entry in the list, 101 * if there is one. 102 * Returns NULL if there aren't any more items in this list. 103 */ 104 105 void * 106 list_get_next_item(struct list *list, void *item) 107 { 108 list_link *link; 109 110 if (item == NULL) 111 return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.next); 112 113 link = get_next_link(list, GET_LINK(list, item)); 114 return link != NULL ? GET_ITEM(list, link) : NULL; 115 } 116 117 118 /** Gets the predecessor for the current item. If the passed 119 * item is NULL, it returns the last entry in the list, 120 * if there is one. 121 * Returns NULL if there aren't any previous items in this list. 122 */ 123 124 void * 125 list_get_prev_item(struct list *list, void *item) 126 { 127 list_link *link; 128 129 if (item == NULL) 130 return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.prev); 131 132 link = get_prev_link(list, GET_LINK(list, item)); 133 return link != NULL ? GET_ITEM(list, link) : NULL; 134 } 135 136 137 void * 138 list_get_last_item(struct list *list) 139 { 140 return list_is_empty(list) ? NULL : GET_ITEM(list, list->link.prev); 141 } 142 143 144 /** Adds an item to the end of the list. 145 * Similar to list_add_link_to_tail() but works on the item, not the link. 146 */ 147 148 void 149 list_add_item(struct list *list, void *item) 150 { 151 list_add_link_to_tail(list, GET_LINK(list, item)); 152 } 153 154 155 /** Removes an item from the list. 156 * Similar to list_remove_link() but works on the item, not the link. 157 */ 158 159 void 160 list_remove_item(struct list *list, void *item) 161 { 162 list_remove_link(GET_LINK(list, item)); 163 } 164 165 166 /** Inserts an item before another item in the list. 167 * If you pass NULL as \a before item, the item is added at the end of 168 * the list. 169 */ 170 171 void 172 list_insert_item_before(struct list *list, void *before, void *item) 173 { 174 list_link *beforeLink; 175 list_link *link; 176 177 if (before == NULL) { 178 list_add_item(list, item); 179 return; 180 } 181 182 beforeLink = GET_LINK(list, before); 183 link = GET_LINK(list, item); 184 185 link->prev = beforeLink->prev; 186 link->next = beforeLink; 187 188 beforeLink->prev->next = link; 189 beforeLink->prev = link; 190 } 191 192 193 /** Removes the first item in the list and returns it. 194 * Returns NULL if the list is empty. 195 */ 196 197 void * 198 list_remove_head_item(struct list *list) 199 { 200 list_link *link; 201 202 if (list_is_empty(list)) 203 return NULL; 204 205 list_remove_link(link = list->link.next); 206 return GET_ITEM(list, link); 207 } 208 209 210 /** Removes the last item in the list and returns it. 211 * Returns NULL if the list is empty. 212 */ 213 214 void * 215 list_remove_tail_item(struct list *list) 216 { 217 list_link *link; 218 219 if (list_is_empty(list)) 220 return NULL; 221 222 list_remove_link(link = list->link.prev); 223 return GET_ITEM(list, link); 224 } 225 226 227 /** Moves the contents of the source list to the target list. 228 * The target list will be emptied before the items are moved; 229 * this is a very fast operation. 230 */ 231 232 void 233 list_move_to_list(struct list *sourceList, struct list *targetList) 234 { 235 if (list_is_empty(sourceList)) { 236 targetList->link.next = targetList->link.prev = &targetList->link; 237 return; 238 } 239 240 *targetList = *sourceList; 241 242 // correct link pointers to this list 243 targetList->link.next->prev = &targetList->link; 244 targetList->link.prev->next = &targetList->link; 245 246 // empty source list 247 sourceList->link.next = sourceList->link.prev = &sourceList->link; 248 } 249 250 251