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