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 17STATIC_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 24void 25list_init_etc(struct list *list, int32 offset) 26{ 27 list->link.next = list->link.prev = &list->link; 28 list->offset = offset; 29} 30 31 32void 33list_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 42void 43list_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 62void 63list_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 83void 84list_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 97static inline list_link * 98get_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 107static inline list_link * 108get_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 123void * 124list_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 142void * 143list_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 155void * 156list_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 166void 167list_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 177void 178list_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 189void 190list_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 215void * 216list_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 232void * 233list_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 250void 251list_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