libdm/datastruct/list.c

   1 /*
   2  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
   3  * Copyright (C) 2004-2010 Red Hat, Inc. All rights reserved.
   4  *
   5  * This file is part of LVM2.
   6  *
   7  * This copyrighted material is made available to anyone wishing to use,
   8  * modify, copy, or redistribute it subject to the terms and conditions
   9  * of the GNU Lesser General Public License v.2.1.
  10  *
  11  * You should have received a copy of the GNU Lesser General Public License
  12  * along with this program; if not, write to the Free Software Foundation,
  13  * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  14  */
  15
  16 #include "lib.h"
  17 #include <assert.h>
  18
  19 /*
  20  * Initialise a list before use.
  21  * The list head's next and previous pointers point back to itself.
  22  */
  23 void dm_list_init(struct dm_list *head)
  24 {
  25         head->n = head->p = head;
  26 }
  27
  28 /*
  29  * Insert an element before 'head'.
  30  * If 'head' is the list head, this adds an element to the end of the list.
  31  */
  32 void dm_list_add(struct dm_list *head, struct dm_list *elem)
  33 {
  34         assert(head->n);
  35
  36         elem->n = head;
  37         elem->p = head->p;
  38
  39         head->p->n = elem;
  40         head->p = elem;
  41 }
  42
  43 /*
  44  * Insert an element after 'head'.
  45  * If 'head' is the list head, this adds an element to the front of the list.
  46  */
  47 void dm_list_add_h(struct dm_list *head, struct dm_list *elem)
  48 {
  49         assert(head->n);
  50
  51         elem->n = head->n;
  52         elem->p = head;
  53
  54         head->n->p = elem;
  55         head->n = elem;
  56 }
  57
  58 /*
  59  * Delete an element from its list.
  60  * Note that this doesn't change the element itself - it may still be safe
  61  * to follow its pointers.
  62  */
  63 void dm_list_del(struct dm_list *elem)
  64 {
  65         elem->n->p = elem->p;
  66         elem->p->n = elem->n;
  67 }
  68
  69 /*
  70  * Remove an element from existing list and insert before 'head'.
  71  */
  72 void dm_list_move(struct dm_list *head, struct dm_list *elem)
  73 {
  74         dm_list_del(elem);
  75         dm_list_add(head, elem);
  76 }
  77
  78 /*
  79  * Is the list empty?
  80  */
  81 int dm_list_empty(const struct dm_list *head)
  82 {
  83         return head->n == head;
  84 }
  85
  86 /*
  87  * Is this the first element of the list?
  88  */
  89 int dm_list_start(const struct dm_list *head, const struct dm_list *elem)
  90 {
  91         return elem->p == head;
  92 }
  93
  94 /*
  95  * Is this the last element of the list?
  96  */
  97 int dm_list_end(const struct dm_list *head, const struct dm_list *elem)
  98 {
  99         return elem->n == head;
 100 }
 101
 102 /*
 103  * Return first element of the list or NULL if empty
 104  */
 105 struct dm_list *dm_list_first(const struct dm_list *head)
 106 {
 107         return (dm_list_empty(head) ? NULL : head->n);
 108 }
 109
 110 /*
 111  * Return last element of the list or NULL if empty
 112  */
 113 struct dm_list *dm_list_last(const struct dm_list *head)
 114 {
 115         return (dm_list_empty(head) ? NULL : head->p);
 116 }
 117
 118 /*
 119  * Return the previous element of the list, or NULL if we've reached the start.
 120  */
 121 struct dm_list *dm_list_prev(const struct dm_list *head, const struct dm_list *elem)
 122 {
 123         return (dm_list_start(head, elem) ? NULL : elem->p);
 124 }
 125
 126 /*
 127  * Return the next element of the list, or NULL if we've reached the end.
 128  */
 129 struct dm_list *dm_list_next(const struct dm_list *head, const struct dm_list *elem)
 130 {
 131         return (dm_list_end(head, elem) ? NULL : elem->n);
 132 }
 133
 134 /*
 135  * Return the number of elements in a list by walking it.
 136  */
 137 unsigned int dm_list_size(const struct dm_list *head)
 138 {
 139         unsigned int s = 0;
 140         const struct dm_list *v;
 141
 142         dm_list_iterate(v, head)
 143             s++;
 144
 145         return s;
 146 }
 147
 148 /*
 149  * Join two lists together.
 150  * This moves all the elements of the list 'head1' to the end of the list
 151  * 'head', leaving 'head1' empty.
 152  */
 153 void dm_list_splice(struct dm_list *head, struct dm_list *head1)
 154 {
 155         assert(head->n);
 156         assert(head1->n);
 157
 158         if (dm_list_empty(head1))
 159             return;
 160
 161         head1->p->n = head;
 162         head1->n->p = head->p;
 163
 164         head->p->n = head1->n;
 165         head->p = head1->p;
 166
 167         dm_list_init(head1);
 168 }