core/lib/list.c

   1 /**
   2  * \addtogroup list
   3  * @{
   4  */
   5
   6 /**
   7  * \file
   8  * Linked list library implementation.
   9  *
  10  * \author Adam Dunkels <adam@sics.se>
  11  *
  12  */
  13
  14 /*
  15  * Copyright (c) 2004, Swedish Institute of Computer Science.
  16  * All rights reserved.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions
  20  * are met:
  21  * 1. Redistributions of source code must retain the above copyright
  22  *    notice, this list of conditions and the following disclaimer.
  23  * 2. Redistributions in binary form must reproduce the above copyright
  24  *    notice, this list of conditions and the following disclaimer in the
  25  *    documentation and/or other materials provided with the distribution.
  26  * 3. Neither the name of the Institute nor the names of its contributors
  27  *    may be used to endorse or promote products derived from this software
  28  *    without specific prior written permission.
  29  *
  30  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  31  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  32  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  34  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  35  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  36  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  37  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  38  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  39  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  40  * SUCH DAMAGE.
  41  *
  42  * This file is part of the Contiki operating system.
  43  *
  44  * Author: Adam Dunkels <adam@sics.se>
  45  *
  46  * $Id: list.c,v 1.5 2010/06/15 18:54:27 adamdunkels Exp $
  47  */
  48 #include "lib/list.h"
  49
  50 #define NULL 0
  51
  52 struct list {
  53   struct list *next;
  54 };
  55
  56 /*---------------------------------------------------------------------------*/
  57 /**
  58  * Initialize a list.
  59  *
  60  * This function initalizes a list. The list will be empty after this
  61  * function has been called.
  62  *
  63  * \param list The list to be initialized.
  64  */
  65 void
  66 list_init(list_t list)
  67 {
  68   *list = NULL;
  69 }
  70 /*---------------------------------------------------------------------------*/
  71 /**
  72  * Get a pointer to the first element of a list.
  73  *
  74  * This function returns a pointer to the first element of the
  75  * list. The element will \b not be removed from the list.
  76  *
  77  * \param list The list.
  78  * \return A pointer to the first element on the list.
  79  *
  80  * \sa list_tail()
  81  */
  82 void *
  83 list_head(list_t list)
  84 {
  85   return *list;
  86 }
  87 /*---------------------------------------------------------------------------*/
  88 /**
  89  * Duplicate a list.
  90  *
  91  * This function duplicates a list by copying the list reference, but
  92  * not the elements.
  93  *
  94  * \note This function does \b not copy the elements of the list, but
  95  * merely duplicates the pointer to the first element of the list.
  96  *
  97  * \param dest The destination list.
  98  * \param src The source list.
  99  */
 100 void
 101 list_copy(list_t dest, list_t src)
 102 {
 103   *dest = *src;
 104 }
 105 /*---------------------------------------------------------------------------*/
 106 /**
 107  * Get the tail of a list.
 108  *
 109  * This function returns a pointer to the elements following the first
 110  * element of a list. No elements are removed by this function.
 111  *
 112  * \param list The list
 113  * \return A pointer to the element after the first element on the list.
 114  *
 115  * \sa list_head()
 116  */
 117 void *
 118 list_tail(list_t list)
 119 {
 120   struct list *l;
 121
 122   if(*list == NULL) {
 123     return NULL;
 124   }
 125
 126   for(l = *list; l->next != NULL; l = l->next);
 127
 128   return l;
 129 }
 130 /*---------------------------------------------------------------------------*/
 131 /**
 132  * Add an item at the end of a list.
 133  *
 134  * This function adds an item to the end of the list.
 135  *
 136  * \param list The list.
 137  * \param item A pointer to the item to be added.
 138  *
 139  * \sa list_push()
 140  *
 141  */
 142 void
 143 list_add(list_t list, void *item)
 144 {
 145   struct list *l;
 146
 147   /* Make sure not to add the same element twice */
 148   list_remove(list, item);
 149
 150   ((struct list *)item)->next = NULL;
 151
 152   l = list_tail(list);
 153
 154   if(l == NULL) {
 155     *list = item;
 156   } else {
 157     l->next = item;
 158   }
 159 }
 160 /*---------------------------------------------------------------------------*/
 161 /**
 162  * Add an item to the start of the list.
 163  */
 164 void
 165 list_push(list_t list, void *item)
 166 {
 167   /*  struct list *l;*/
 168
 169   /* Make sure not to add the same element twice */
 170   list_remove(list, item);
 171
 172   ((struct list *)item)->next = *list;
 173   *list = item;
 174 }
 175 /*---------------------------------------------------------------------------*/
 176 /**
 177  * Remove the last object on the list.
 178  *
 179  * This function removes the last object on the list and returns it.
 180  *
 181  * \param list The list
 182  * \return The removed object
 183  *
 184  */
 185 void *
 186 list_chop(list_t list)
 187 {
 188   struct list *l, *r;
 189
 190   if(*list == NULL) {
 191     return NULL;
 192   }
 193   if(((struct list *)*list)->next == NULL) {
 194     l = *list;
 195     *list = NULL;
 196     return l;
 197   }
 198
 199   for(l = *list; l->next->next != NULL; l = l->next);
 200
 201   r = l->next;
 202   l->next = NULL;
 203
 204   return r;
 205 }
 206 /*---------------------------------------------------------------------------*/
 207 /**
 208  * Remove the first object on a list.
 209  *
 210  * This function removes the first object on the list and returns a
 211  * pointer to it.
 212  *
 213  * \param list The list.
 214  * \return Pointer to the removed element of list.
 215  */
 216 /*---------------------------------------------------------------------------*/
 217 void *
 218 list_pop(list_t list)
 219 {
 220   struct list *l;
 221   l = *list;
 222   if(*list != NULL) {
 223     *list = ((struct list *)*list)->next;
 224   }
 225
 226   return l;
 227 }
 228 /*---------------------------------------------------------------------------*/
 229 /**
 230  * Remove a specific element from a list.
 231  *
 232  * This function removes a specified element from the list.
 233  *
 234  * \param list The list.
 235  * \param item The item that is to be removed from the list.
 236  *
 237  */
 238 /*---------------------------------------------------------------------------*/
 239 void
 240 list_remove(list_t list, void *item)
 241 {
 242   struct list *l, *r;
 243
 244   if(*list == NULL) {
 245     return;
 246   }
 247
 248   r = NULL;
 249   for(l = *list; l != NULL; l = l->next) {
 250     if(l == item) {
 251       if(r == NULL) {
 252         /* First on list */
 253         *list = l->next;
 254       } else {
 255         /* Not first on list */
 256         r->next = l->next;
 257       }
 258       l->next = NULL;
 259       return;
 260     }
 261     r = l;
 262   }
 263 }
 264 /*---------------------------------------------------------------------------*/
 265 /**
 266  * Get the length of a list.
 267  *
 268  * This function counts the number of elements on a specified list.
 269  *
 270  * \param list The list.
 271  * \return The length of the list.
 272  */
 273 /*---------------------------------------------------------------------------*/
 274 int
 275 list_length(list_t list)
 276 {
 277   struct list *l;
 278   int n = 0;
 279
 280   for(l = *list; l != NULL; l = l->next) {
 281     ++n;
 282   }
 283
 284   return n;
 285 }
 286 /*---------------------------------------------------------------------------*/
 287 /**
 288  * \brief      Insert an item after a specified item on the list
 289  * \param list The list
 290  * \param previtem The item after which the new item should be inserted
 291  * \param newitem  The new item that is to be inserted
 292  * \author     Adam Dunkels
 293  *
 294  *             This function inserts an item right after a specified
 295  *             item on the list. This function is useful when using
 296  *             the list module to ordered lists.
 297  *
 298  *             If previtem is NULL, the new item is placed at the
 299  *             start of the list.
 300  *
 301  */
 302 void
 303 list_insert(list_t list, void *previtem, void *newitem)
 304 {
 305   if(previtem == NULL) {
 306     list_push(list, newitem);
 307   } else {
 308
 309     ((struct list *)newitem)->next = ((struct list *)previtem)->next;
 310     ((struct list *)previtem)->next = newitem;
 311   }
 312 }
 313 /*---------------------------------------------------------------------------*/
 314 /**
 315  * \brief      Get the next item following this item
 316  * \param item A list item
 317  * \returns    A next item on the list
 318  *
 319  *             This function takes a list item and returns the next
 320  *             item on the list, or NULL if there are no more items on
 321  *             the list. This function is used when iterating through
 322  *             lists.
 323  */
 324 void *
 325 list_item_next(void *item)
 326 {
 327   return item == NULL? NULL: ((struct list *)item)->next;
 328 }
 329 /*---------------------------------------------------------------------------*/
 330 /** @} */