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