libkmod/libkmod-list.c

   1 /*
   2  * libkmod - interface to kernel module operations
   3  *
   4  * Copyright (C) 2011-2013  ProFUSION embedded systems
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include <stdlib.h>
  21
  22 #include "libkmod.h"
  23 #include "libkmod-internal.h"
  24
  25 /**
  26  * SECTION:libkmod-list
  27  * @short_description: general purpose list
  28  */
  29
  30 static inline struct list_node *list_node_init(struct list_node *node)
  31 {
  32         node->next = node;
  33         node->prev = node;
  34
  35         return node;
  36 }
  37
  38 static inline void list_node_append(struct list_node *list,
  39                                                         struct list_node *node)
  40 {
  41         if (list == NULL) {
  42                 list_node_init(node);
  43                 return;
  44         }
  45
  46         node->prev = list->prev;
  47         list->prev->next = node;
  48         list->prev = node;
  49         node->next = list;
  50 }
  51
  52 static inline struct list_node *list_node_remove(struct list_node *node)
  53 {
  54         if (node->prev == node || node->next == node)
  55                 return NULL;
  56
  57         node->prev->next = node->next;
  58         node->next->prev = node->prev;
  59
  60         return node->next;
  61 }
  62
  63 static inline void list_node_insert_after(struct list_node *list,
  64                                                         struct list_node *node)
  65 {
  66         if (list == NULL) {
  67                 list_node_init(node);
  68                 return;
  69         }
  70
  71         node->prev = list;
  72         node->next = list->next;
  73         list->next->prev = node;
  74         list->next = node;
  75 }
  76
  77 static inline void list_node_insert_before(struct list_node *list,
  78                                                         struct list_node *node)
  79 {
  80         if (list == NULL) {
  81                 list_node_init(node);
  82                 return;
  83         }
  84
  85         node->next = list;
  86         node->prev = list->prev;
  87         list->prev->next = node;
  88         list->prev = node;
  89 }
  90
  91 static inline void list_node_append_list(struct list_node *list1,
  92                                                         struct list_node *list2)
  93 {
  94         struct list_node *list1_last;
  95
  96         if (list1 == NULL) {
  97                 list_node_init(list2);
  98                 return;
  99         }
 100
 101         list1->prev->next = list2;
 102         list2->prev->next = list1;
 103
 104         /* cache the last, because we will lose the pointer */
 105         list1_last = list1->prev;
 106
 107         list1->prev = list2->prev;
 108         list2->prev = list1_last;
 109 }
 110
 111 struct kmod_list *kmod_list_append(struct kmod_list *list, const void *data)
 112 {
 113         struct kmod_list *new;
 114
 115         new = malloc(sizeof(*new));
 116         if (new == NULL)
 117                 return NULL;
 118
 119         new->data = (void *)data;
 120         list_node_append(list ? &list->node : NULL, &new->node);
 121
 122         return list ? list : new;
 123 }
 124
 125 struct kmod_list *kmod_list_insert_after(struct kmod_list *list,
 126                                                         const void *data)
 127 {
 128         struct kmod_list *new;
 129
 130         if (list == NULL)
 131                 return kmod_list_append(list, data);
 132
 133         new = malloc(sizeof(*new));
 134         if (new == NULL)
 135                 return NULL;
 136
 137         new->data = (void *)data;
 138         list_node_insert_after(&list->node, &new->node);
 139
 140         return list;
 141 }
 142
 143 struct kmod_list *kmod_list_insert_before(struct kmod_list *list,
 144                                                         const void *data)
 145 {
 146         struct kmod_list *new;
 147
 148         if (list == NULL)
 149                 return kmod_list_append(list, data);
 150
 151         new = malloc(sizeof(*new));
 152         if (new == NULL)
 153                 return NULL;
 154
 155         new->data = (void *)data;
 156         list_node_insert_before(&list->node, &new->node);
 157
 158         return new;
 159 }
 160
 161 struct kmod_list *kmod_list_append_list(struct kmod_list *list1,
 162                                                 struct kmod_list *list2)
 163 {
 164         if (list1 == NULL)
 165                 return list2;
 166
 167         if (list2 == NULL)
 168                 return list1;
 169
 170         list_node_append_list(&list1->node, &list2->node);
 171
 172         return list1;
 173 }
 174
 175 struct kmod_list *kmod_list_prepend(struct kmod_list *list, const void *data)
 176 {
 177         struct kmod_list *new;
 178
 179         new = malloc(sizeof(*new));
 180         if (new == NULL)
 181                 return NULL;
 182
 183         new->data = (void *)data;
 184         list_node_append(list ? &list->node : NULL, &new->node);
 185
 186         return new;
 187 }
 188
 189 struct kmod_list *kmod_list_remove(struct kmod_list *list)
 190 {
 191         struct list_node *node;
 192
 193         if (list == NULL)
 194                 return NULL;
 195
 196         node = list_node_remove(&list->node);
 197         free(list);
 198
 199         if (node == NULL)
 200                 return NULL;
 201
 202         return container_of(node, struct kmod_list, node);
 203 }
 204
 205 struct kmod_list *kmod_list_remove_data(struct kmod_list *list,
 206                                                         const void *data)
 207 {
 208         struct kmod_list *itr;
 209         struct list_node *node;
 210
 211         for (itr = list; itr != NULL; itr = kmod_list_next(list, itr)) {
 212                 if (itr->data == data)
 213                         break;
 214         }
 215
 216         if (itr == NULL)
 217                 return list;
 218
 219         node = list_node_remove(&itr->node);
 220         free(itr);
 221
 222         if (node == NULL)
 223                 return NULL;
 224
 225         return container_of(node, struct kmod_list, node);
 226 }
 227
 228 /*
 229  * n must be greater to or equal the number of elements (we don't check the
 230  * condition)
 231  */
 232 struct kmod_list *kmod_list_remove_n_latest(struct kmod_list *list,
 233                                                         unsigned int n)
 234 {
 235         struct kmod_list *l = list;
 236         unsigned int i;
 237
 238         for (i = 0; i < n; i++) {
 239                 l = kmod_list_last(l);
 240                 l = kmod_list_remove(l);
 241         }
 242
 243         return l;
 244 }
 245
 246 /**
 247  * kmod_list_prev:
 248  * @list: the head of the list
 249  * @curr: the current node in the list
 250  *
 251  * Get the previous node in @list relative to @curr as if @list was not a
 252  * circular list. I.e.: the previous of the head is NULL. It can be used to
 253  * iterate a list by checking for NULL return to know when all elements were
 254  * iterated.
 255  *
 256  * Returns: node previous to @curr or NULL if either this node is the head of
 257  * the list or the list is empty.
 258  */
 259 KMOD_EXPORT struct kmod_list *kmod_list_prev(const struct kmod_list *list,
 260                                                 const struct kmod_list *curr)
 261 {
 262         if (list == NULL || curr == NULL)
 263                 return NULL;
 264
 265         if (list == curr)
 266                 return NULL;
 267
 268         return container_of(curr->node.prev, struct kmod_list, node);
 269 }
 270
 271 /**
 272  * kmod_list_next:
 273  * @list: the head of the list
 274  * @curr: the current node in the list
 275  *
 276  * Get the next node in @list relative to @curr as if @list was not a circular
 277  * list. I.e. calling this function in the last node of the list returns
 278  * NULL.. It can be used to iterate a list by checking for NULL return to know
 279  * when all elements were iterated.
 280  *
 281  * Returns: node next to @curr or NULL if either this node is the last of or
 282  * list is empty.
 283  */
 284 KMOD_EXPORT struct kmod_list *kmod_list_next(const struct kmod_list *list,
 285                                                 const struct kmod_list *curr)
 286 {
 287         if (list == NULL || curr == NULL)
 288                 return NULL;
 289
 290         if (curr->node.next == &list->node)
 291                 return NULL;
 292
 293         return container_of(curr->node.next, struct kmod_list, node);
 294 }
 295
 296 /**
 297  * kmod_list_last:
 298  * @list: the head of the list
 299  *
 300  * Get the last element of the @list. As @list is a circular list,
 301  * this is a cheap operation O(1) with the last element being the
 302  * previous element.
 303  *
 304  * If the list has a single element it will return the list itself (as
 305  * expected, and this is what differentiates from kmod_list_prev()).
 306  *
 307  * Returns: last node at @list or NULL if the list is empty.
 308  */
 309 KMOD_EXPORT struct kmod_list *kmod_list_last(const struct kmod_list *list)
 310 {
 311         if (list == NULL)
 312                 return NULL;
 313         return container_of(list->node.prev, struct kmod_list, node);
 314 }