src/system/kernel/util/list.cpp

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