lib/list.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #include <config.h>
  17 #include "list.h"
  18
  19 /* Initializes 'list' as an empty list. */
  20 void
  21 list_init(struct list *list)
  22 {
  23     list->next = list->prev = list;
  24 }
  25
  26 /* Initializes 'list' with pointers that will (probably) cause segfaults if
  27  * dereferenced and, better yet, show up clearly in a debugger. */
  28 void
  29 list_poison(struct list *list)
  30 {
  31     memset(list, 0xcc, sizeof *list);
  32 }
  33
  34 /* Inserts 'elem' just before 'before'. */
  35 void
  36 list_insert(struct list *before, struct list *elem)
  37 {
  38     elem->prev = before->prev;
  39     elem->next = before;
  40     before->prev->next = elem;
  41     before->prev = elem;
  42 }
  43
  44 /* Removes elements 'first' though 'last' (exclusive) from their current list,
  45    then inserts them just before 'before'. */
  46 void
  47 list_splice(struct list *before, struct list *first, struct list *last)
  48 {
  49     if (first == last)
  50         return;
  51     last = last->prev;
  52
  53     /* Cleanly remove 'first'...'last' from its current list. */
  54     first->prev->next = last->next;
  55     last->next->prev = first->prev;
  56
  57     /* Splice 'first'...'last' into new list. */
  58     first->prev = before->prev;
  59     last->next = before;
  60     before->prev->next = first;
  61     before->prev = last;
  62 }
  63
  64 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
  65    'list'. */
  66 void
  67 list_push_front(struct list *list, struct list *elem)
  68 {
  69     list_insert(list->next, elem);
  70 }
  71
  72 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
  73  * 'list'. */
  74 void
  75 list_push_back(struct list *list, struct list *elem)
  76 {
  77     list_insert(list, elem);
  78 }
  79
  80 /* Puts 'elem' in the position currently occupied by 'position'.
  81  * Afterward, 'position' is not part of a list. */
  82 void
  83 list_replace(struct list *element, const struct list *position)
  84 {
  85     element->next = position->next;
  86     element->next->prev = element;
  87     element->prev = position->prev;
  88     element->prev->next = element;
  89 }
  90
  91 /* Adjusts pointers around 'list' to compensate for 'list' having been moved
  92  * around in memory (e.g. as a consequence of realloc()).
  93  *
  94  * This always works if 'list' is a member of a list, or if 'list' is the head
  95  * of a non-empty list.  It fails badly, however, if 'list' is the head of an
  96  * empty list; just use list_init() in that case. */
  97 void
  98 list_moved(struct list *list)
  99 {
 100     list->prev->next = list->next->prev = list;
 101 }
 102
 103 /* Removes 'elem' from its list and returns the element that followed it.
 104    Undefined behavior if 'elem' is not in a list. */
 105 struct list *
 106 list_remove(struct list *elem)
 107 {
 108     elem->prev->next = elem->next;
 109     elem->next->prev = elem->prev;
 110     return elem->next;
 111 }
 112
 113 /* Removes the front element from 'list' and returns it.  Undefined behavior if
 114    'list' is empty before removal. */
 115 struct list *
 116 list_pop_front(struct list *list)
 117 {
 118     struct list *front = list->next;
 119     list_remove(front);
 120     return front;
 121 }
 122
 123 /* Removes the back element from 'list' and returns it.
 124    Undefined behavior if 'list' is empty before removal. */
 125 struct list *
 126 list_pop_back(struct list *list)
 127 {
 128     struct list *back = list->prev;
 129     list_remove(back);
 130     return back;
 131 }
 132
 133 /* Returns the front element in 'list_'.
 134    Undefined behavior if 'list_' is empty. */
 135 struct list *
 136 list_front(const struct list *list_)
 137 {
 138     struct list *list = CONST_CAST(struct list *, list_);
 139
 140     ovs_assert(!list_is_empty(list));
 141     return list->next;
 142 }
 143
 144 /* Returns the back element in 'list_'.
 145    Undefined behavior if 'list_' is empty. */
 146 struct list *
 147 list_back(const struct list *list_)
 148 {
 149     struct list *list = CONST_CAST(struct list *, list_);
 150
 151     ovs_assert(!list_is_empty(list));
 152     return list->prev;
 153 }
 154
 155 /* Returns the number of elements in 'list'.
 156    Runs in O(n) in the number of elements. */
 157 size_t
 158 list_size(const struct list *list)
 159 {
 160     const struct list *e;
 161     size_t cnt = 0;
 162
 163     for (e = list->next; e != list; e = e->next)
 164         cnt++;
 165     return cnt;
 166 }
 167
 168 /* Returns true if 'list' is empty, false otherwise. */
 169 bool
 170 list_is_empty(const struct list *list)
 171 {
 172     return list->next == list;
 173 }
 174
 175 /* Returns true if 'list' has exactly 1 element, false otherwise. */
 176 bool
 177 list_is_singleton(const struct list *list)
 178 {
 179     return list_is_short(list) && !list_is_empty(list);
 180 }
 181
 182 /* Returns true if 'list' has 0 or 1 elements, false otherwise. */
 183 bool
 184 list_is_short(const struct list *list)
 185 {
 186     return list->next == list->prev;
 187 }