lib/list.c

   1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
   2  * Junior University
   3  *
   4  * We are making the OpenFlow specification and associated documentation
   5  * (Software) available for public use and benefit with the expectation
   6  * that others will use, modify and enhance the Software and contribute
   7  * those enhancements back to the community. However, since we would
   8  * like to make the Software available for broadest use, with as few
   9  * restrictions as possible permission is hereby granted, free of
  10  * charge, to any person obtaining a copy of this Software to deal in
  11  * the Software under the copyrights without restriction, including
  12  * without limitation the rights to use, copy, modify, merge, publish,
  13  * distribute, sublicense, and/or sell copies of the Software, and to
  14  * permit persons to whom the Software is furnished to do so, subject to
  15  * the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27  * SOFTWARE.
  28  *
  29  * The name and trademarks of copyright holder(s) may NOT be used in
  30  * advertising or publicity pertaining to the Software or any
  31  * derivatives without specific, written prior permission.
  32  */
  33 #include "list.h"
  34 #include <assert.h>
  35
  36 /* Initializes 'list' as an empty list. */
  37 void
  38 list_init(struct list *list)
  39 {
  40     list->next = list->prev = list;
  41 }
  42
  43 /* Inserts 'elem' just before 'before'. */
  44 void
  45 list_insert(struct list *before, struct list *elem)
  46 {
  47   elem->prev = before->prev;
  48   elem->next = before;
  49   before->prev->next = elem;
  50   before->prev = elem;
  51 }
  52
  53 /* Removes elements 'first' though 'last' (exclusive) from their current list,
  54    then inserts them just before 'before'. */
  55 void
  56 list_splice(struct list *before, struct list *first, struct list *last)
  57 {
  58   if (first == last)
  59     return;
  60   last = last->prev;
  61
  62   /* Cleanly remove 'first'...'last' from its current list. */
  63   first->prev->next = last->next;
  64   last->next->prev = first->prev;
  65
  66   /* Splice 'first'...'last' into new list. */
  67   first->prev = before->prev;
  68   last->next = before;
  69   before->prev->next = first;
  70   before->prev = last;
  71 }
  72
  73 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
  74    'list'. */
  75 void
  76 list_push_front(struct list *list, struct list *elem)
  77 {
  78   list_insert(list->next, elem);
  79 }
  80
  81 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
  82  * 'list'. */
  83 void
  84 list_push_back(struct list *list, struct list *elem)
  85 {
  86   list_insert(list, elem);
  87 }
  88
  89 /* Puts 'elem' in the position currently occupied by 'position'.
  90  * Afterward, 'position' is not part of a list. */
  91 void
  92 list_replace(struct list *element, const struct list *position)
  93 {
  94     element->next = position->next;
  95     element->next->prev = element;
  96     element->prev = position->prev;
  97     element->prev->next = element;
  98 }
  99
 100 /* Removes 'elem' from its list and returns the element that followed it.
 101    Undefined behavior if 'elem' is not in a list. */
 102 struct list *
 103 list_remove(struct list *elem)
 104 {
 105   elem->prev->next = elem->next;
 106   elem->next->prev = elem->prev;
 107   return elem->next;
 108 }
 109
 110 /* Removes the front element from 'list' and returns it.  Undefined behavior if
 111    'list' is empty before removal. */
 112 struct list *
 113 list_pop_front(struct list *list)
 114 {
 115   struct list *front = list->next;
 116   list_remove(front);
 117   return front;
 118 }
 119
 120 /* Removes the back element from 'list' and returns it.
 121    Undefined behavior if 'list' is empty before removal. */
 122 struct list *
 123 list_pop_back(struct list *list)
 124 {
 125   struct list *back = list->prev;
 126   list_remove(back);
 127   return back;
 128 }
 129
 130 /* Returns the front element in 'list'.
 131    Undefined behavior if 'list' is empty. */
 132 struct list *
 133 list_front(struct list *list)
 134 {
 135   assert(!list_is_empty(list));
 136   return list->next;
 137 }
 138
 139 /* Returns the back element in 'list'.
 140    Undefined behavior if 'list' is empty. */
 141 struct list *
 142 list_back(struct list *list)
 143 {
 144   assert(!list_is_empty(list));
 145   return list->prev;
 146 }
 147
 148 /* Returns the number of elements in 'list'.
 149    Runs in O(n) in the number of elements. */
 150 size_t
 151 list_size(const struct list *list)
 152 {
 153   const struct list *e;
 154   size_t cnt = 0;
 155
 156   for (e = list->next; e != list; e = e->next)
 157     cnt++;
 158   return cnt;
 159 }
 160
 161 /* Returns true if 'list' is empty, false otherwise. */
 162 bool
 163 list_is_empty(const struct list *list)
 164 {
 165   return list->next == list;
 166 }