uspace/app/sbi/src/list.c

   1 /*
   2  * Copyright (c) 2011 Jiri Svoboda
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @file Doubly linked list.
  30  *
  31  * Circular, with a head. Nodes structures are allocated separately from data.
  32  * Data is stored as 'void *'. We implement several sanity checks to prevent
  33  * common usage errors.
  34  */
  35
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <assert.h>
  39 #include "mytypes.h"
  40
  41 #include "list.h"
  42
  43 static list_node_t *list_node_new(void *data);
  44 static void list_node_delete(list_node_t *node);
  45 static void list_node_insert_between(list_node_t *n, list_node_t *a, list_node_t *b);
  46 static void list_node_unlink(list_node_t *n);
  47 static bool_t list_node_present(list_t *list, list_node_t *node);
  48
  49 /** Initialize list.
  50  *
  51  * @param list  List to initialize.
  52  */
  53 void list_init(list_t *list)
  54 {
  55         list->head.prev = &list->head;
  56         list->head.next = &list->head;
  57 }
  58
  59 /** Deinitialize list.
  60  *
  61  * @param list  List to deinitialize.
  62  */
  63 void list_fini(list_t *list)
  64 {
  65         assert(list_is_empty(list));
  66
  67         list->head.prev = NULL;
  68         list->head.next = NULL;
  69 }
  70
  71 /** Append data to list.
  72  *
  73  * Create a new list node and append it at the end of the list.
  74  *
  75  * @param list  Linked list.
  76  * @param data  Data for the new node.
  77  */
  78 void list_append(list_t *list, void *data)
  79 {
  80         list_node_t *node;
  81
  82         node = list_node_new(data);
  83         list_node_insert_between(node, list->head.prev, &list->head);
  84 }
  85
  86 /** Prepend data to list.
  87  *
  88  * Create a new list node and prepend it at the beginning of the list.
  89  *
  90  * @param list  Linked list.
  91  * @param data  Data for the new node.
  92  */
  93 void list_prepend(list_t *list, void *data)
  94 {
  95         list_node_t *node;
  96
  97         node = list_node_new(data);
  98         list_node_insert_between(node, list->head.prev, &list->head);
  99 }
 100
 101 /** Remove data from list.
 102  *
 103  * Removes the given node from a list and destroys it. Any data the node might
 104  * have is ignored. If asserts are on, we check wheter node is really present
 105  * in the list the caller is requesting us to remove it from.
 106  *
 107  * @param list  Linked list.
 108  * @param node  List node to remove.
 109  */
 110 void list_remove(list_t *list, list_node_t *node)
 111 {
 112         /* Check whether node is in the list as claimed. */
 113         assert(list_node_present(list, node));
 114         list_node_unlink(node);
 115         node->data = NULL;
 116         list_node_delete(node);
 117 }
 118
 119 /** Return first list node or NULL if list is empty.
 120  *
 121  * @param list  Linked list.
 122  * @return      First node of the list or @c NULL if the list is empty.
 123  */
 124 list_node_t *list_first(list_t *list)
 125 {
 126         list_node_t *node;
 127
 128         assert(list != NULL);
 129         node = list->head.next;
 130
 131         return (node != &list->head) ? node : NULL;
 132 }
 133
 134 /** Return last list node or NULL if list is empty.
 135  *
 136  * @param list  Linked list.
 137  * @return      Last node of the list or @c NULL if the list is empty.
 138  */
 139 list_node_t *list_last(list_t *list)
 140 {
 141         list_node_t *node;
 142
 143         assert(list != NULL);
 144         node = list->head.prev;
 145
 146         return (node != &list->head) ? node : NULL;
 147 }
 148
 149 /** Return next list node or NULL if this was the last one.
 150  *
 151  * @param list  Linked list.
 152  * @param node  Node whose successor we are interested in.
 153  * @return      Following list node or @c NULL if @a node is last.
 154  */
 155 list_node_t *list_next(list_t *list, list_node_t *node)
 156 {
 157         (void) list;
 158         assert(list != NULL);
 159         assert(node != NULL);
 160
 161         return (node->next != &list->head) ? node->next : NULL;
 162 }
 163
 164 /** Return previous list node or NULL if this was the last one.
 165  *
 166  * @param list  Linked list.
 167  * @param node  Node whose predecessor we are interested in.
 168  * @return      Preceding list node or @c NULL if @a node is last.
 169  */
 170 list_node_t *list_prev(list_t *list, list_node_t *node)
 171 {
 172         (void) list;
 173         assert(list != NULL);
 174         assert(node != NULL);
 175
 176         return (node->prev != &list->head) ? node->prev : NULL;
 177 }
 178
 179 /** Return b_true if list is empty.
 180  *
 181  * @param list  Linked list.
 182  * @return      @c b_true if list is empty, @c b_false otherwise.
 183  */
 184 bool_t list_is_empty(list_t *list)
 185 {
 186         return (list_first(list) == NULL);
 187 }
 188
 189 /** Change node data.
 190  *
 191  * Change the data associated with a node.
 192  *
 193  * @param node  List node.
 194  * @param data  New data for node.
 195  */
 196 void list_node_setdata(list_node_t *node, void *data)
 197 {
 198         node->data = data;
 199 }
 200
 201 /** Create new node.
 202  *
 203  * @param data  Initial data for node.
 204  * @return      New list node.
 205  */
 206 static list_node_t *list_node_new(void *data)
 207 {
 208         list_node_t *node;
 209
 210         node = malloc(sizeof(list_node_t));
 211         if (node == NULL) {
 212                 printf("Memory allocation failed.\n");
 213                 exit(1);
 214         }
 215
 216         node->prev = NULL;
 217         node->next = NULL;
 218         node->data = data;
 219
 220         return node;
 221 }
 222
 223 /** Delete node.
 224  *
 225  * @param node  List node. Must not take part in any list.
 226  */
 227 static void list_node_delete(list_node_t *node)
 228 {
 229         assert(node->prev == NULL);
 230         assert(node->next == NULL);
 231         assert(node->data == NULL);
 232         free(node);
 233 }
 234
 235 /** Insert node between two other nodes.
 236  *
 237  * Inserts @a n between neighboring nodes @a a and @a b.
 238  *
 239  * @param n     Node to insert.
 240  * @param a     Node to precede @a n.
 241  * @param b     Node to follow @a n.
 242  */
 243 static void list_node_insert_between(list_node_t *n, list_node_t *a,
 244     list_node_t *b)
 245 {
 246         assert(n->prev == NULL);
 247         assert(n->next == NULL);
 248         n->prev = a;
 249         n->next = b;
 250
 251         assert(a->next == b);
 252         assert(b->prev == a);
 253         a->next = n;
 254         b->prev = n;
 255 }
 256
 257 /** Unlink node.
 258  *
 259  * Unlink node from the list it is currently in.
 260  *
 261  * @param n     Node to unlink from its current list.
 262  */
 263 static void list_node_unlink(list_node_t *n)
 264 {
 265         list_node_t *a, *b;
 266         assert(n->prev != NULL);
 267         assert(n->next != NULL);
 268
 269         a = n->prev;
 270         b = n->next;
 271
 272         assert(a->next == n);
 273         assert(b->prev == n);
 274
 275         a->next = b;
 276         b->prev = a;
 277
 278         n->prev = NULL;
 279         n->next = NULL;
 280 }
 281
 282 /** Check whether @a node is in list @a list.
 283  *
 284  * @param list  Linked list.
 285  * @param node  Node.
 286  * @return      @c b_true if @a node is part of @a list, @c b_false otherwise.
 287  */
 288 static bool_t list_node_present(list_t *list, list_node_t *node)
 289 {
 290         list_node_t *m;
 291
 292         m = list->head.next;
 293         while (m != &list->head) {
 294                 if (m == node)
 295                         return b_true;
 296                 m = m->next;
 297         }
 298
 299         return b_false;
 300 }