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