src/tools/fs_shell/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 "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