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 14 namespace 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 21 void 22 list_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 29 void 30 list_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 39 void 40 list_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 55 void 56 list_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 72 void 73 list_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 82 static inline list_link * 83 get_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 92 static inline list_link * 93 get_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 108 void * 109 list_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 127 void * 128 list_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 140 void * 141 list_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 151 void 152 list_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 162 void 163 list_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 174 void 175 list_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 200 void * 201 list_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 217 void * 218 list_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 235 void 236 list_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