Contiki 2.6

list.c

Go to the documentation of this file.
00001 /**
00002  * \addtogroup list
00003  * @{
00004  */
00005 
00006 /**
00007  * \file
00008  * Linked list library implementation.
00009  *
00010  * \author Adam Dunkels <adam@sics.se>
00011  *
00012  */
00013 
00014 /*
00015  * Copyright (c) 2004, Swedish Institute of Computer Science.
00016  * All rights reserved.
00017  *
00018  * Redistribution and use in source and binary forms, with or without
00019  * modification, are permitted provided that the following conditions
00020  * are met:
00021  * 1. Redistributions of source code must retain the above copyright
00022  *    notice, this list of conditions and the following disclaimer.
00023  * 2. Redistributions in binary form must reproduce the above copyright
00024  *    notice, this list of conditions and the following disclaimer in the
00025  *    documentation and/or other materials provided with the distribution.
00026  * 3. Neither the name of the Institute nor the names of its contributors
00027  *    may be used to endorse or promote products derived from this software
00028  *    without specific prior written permission.
00029  *
00030  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
00031  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00032  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00033  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
00034  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00035  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00036  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00037  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00038  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00039  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00040  * SUCH DAMAGE.
00041  *
00042  * This file is part of the Contiki operating system.
00043  *
00044  * Author: Adam Dunkels <adam@sics.se>
00045  *
00046  * $Id: list.c,v 1.5 2010/06/15 18:54:27 adamdunkels Exp $
00047  */
00048 #include "lib/list.h"
00049 
00050 #define NULL 0
00051 
00052 struct list {
00053   struct list *next;
00054 };
00055 
00056 /*---------------------------------------------------------------------------*/
00057 /**
00058  * Initialize a list.
00059  *
00060  * This function initalizes a list. The list will be empty after this
00061  * function has been called.
00062  *
00063  * \param list The list to be initialized.
00064  */
00065 void
00066 list_init(list_t list)
00067 {
00068   *list = NULL;
00069 }
00070 /*---------------------------------------------------------------------------*/
00071 /**
00072  * Get a pointer to the first element of a list.
00073  *
00074  * This function returns a pointer to the first element of the
00075  * list. The element will \b not be removed from the list.
00076  *
00077  * \param list The list.
00078  * \return A pointer to the first element on the list.
00079  *
00080  * \sa list_tail()
00081  */
00082 void *
00083 list_head(list_t list)
00084 {
00085   return *list;
00086 }
00087 /*---------------------------------------------------------------------------*/
00088 /**
00089  * Duplicate a list.
00090  *
00091  * This function duplicates a list by copying the list reference, but
00092  * not the elements.
00093  *
00094  * \note This function does \b not copy the elements of the list, but
00095  * merely duplicates the pointer to the first element of the list.
00096  *
00097  * \param dest The destination list.
00098  * \param src The source list.
00099  */
00100 void
00101 list_copy(list_t dest, list_t src)
00102 {
00103   *dest = *src;
00104 }
00105 /*---------------------------------------------------------------------------*/
00106 /**
00107  * Get the tail of a list.
00108  *
00109  * This function returns a pointer to the elements following the first
00110  * element of a list. No elements are removed by this function.
00111  *
00112  * \param list The list
00113  * \return A pointer to the element after the first element on the list.
00114  *
00115  * \sa list_head()
00116  */
00117 void *
00118 list_tail(list_t list)
00119 {
00120   struct list *l;
00121   
00122   if(*list == NULL) {
00123     return NULL;
00124   }
00125   
00126   for(l = *list; l->next != NULL; l = l->next);
00127   
00128   return l;
00129 }
00130 /*---------------------------------------------------------------------------*/
00131 /**
00132  * Add an item at the end of a list.
00133  *
00134  * This function adds an item to the end of the list.
00135  *
00136  * \param list The list.
00137  * \param item A pointer to the item to be added.
00138  *
00139  * \sa list_push()
00140  *
00141  */
00142 void
00143 list_add(list_t list, void *item)
00144 {
00145   struct list *l;
00146 
00147   /* Make sure not to add the same element twice */
00148   list_remove(list, item);
00149 
00150   ((struct list *)item)->next = NULL;
00151   
00152   l = list_tail(list);
00153 
00154   if(l == NULL) {
00155     *list = item;
00156   } else {
00157     l->next = item;
00158   }
00159 }
00160 /*---------------------------------------------------------------------------*/
00161 /**
00162  * Add an item to the start of the list.
00163  */
00164 void
00165 list_push(list_t list, void *item)
00166 {
00167   /*  struct list *l;*/
00168 
00169   /* Make sure not to add the same element twice */
00170   list_remove(list, item);
00171 
00172   ((struct list *)item)->next = *list;
00173   *list = item;
00174 }
00175 /*---------------------------------------------------------------------------*/
00176 /**
00177  * Remove the last object on the list.
00178  *
00179  * This function removes the last object on the list and returns it.
00180  *
00181  * \param list The list
00182  * \return The removed object
00183  *
00184  */
00185 void *
00186 list_chop(list_t list)
00187 {
00188   struct list *l, *r;
00189   
00190   if(*list == NULL) {
00191     return NULL;
00192   }
00193   if(((struct list *)*list)->next == NULL) {
00194     l = *list;
00195     *list = NULL;
00196     return l;
00197   }
00198   
00199   for(l = *list; l->next->next != NULL; l = l->next);
00200 
00201   r = l->next;
00202   l->next = NULL;
00203   
00204   return r;
00205 }
00206 /*---------------------------------------------------------------------------*/
00207 /**
00208  * Remove the first object on a list.
00209  *
00210  * This function removes the first object on the list and returns a
00211  * pointer to it.
00212  *
00213  * \param list The list.
00214  * \return Pointer to the removed element of list.
00215  */
00216 /*---------------------------------------------------------------------------*/
00217 void *
00218 list_pop(list_t list)
00219 {
00220   struct list *l;
00221   l = *list;
00222   if(*list != NULL) {
00223     *list = ((struct list *)*list)->next;
00224   }
00225 
00226   return l;
00227 }
00228 /*---------------------------------------------------------------------------*/
00229 /**
00230  * Remove a specific element from a list.
00231  *
00232  * This function removes a specified element from the list.
00233  *
00234  * \param list The list.
00235  * \param item The item that is to be removed from the list.
00236  *
00237  */
00238 /*---------------------------------------------------------------------------*/
00239 void
00240 list_remove(list_t list, void *item)
00241 {
00242   struct list *l, *r;
00243   
00244   if(*list == NULL) {
00245     return;
00246   }
00247   
00248   r = NULL;
00249   for(l = *list; l != NULL; l = l->next) {
00250     if(l == item) {
00251       if(r == NULL) {
00252         /* First on list */
00253         *list = l->next;
00254       } else {
00255         /* Not first on list */
00256         r->next = l->next;
00257       }
00258       l->next = NULL;
00259       return;
00260     }
00261     r = l;
00262   }
00263 }
00264 /*---------------------------------------------------------------------------*/
00265 /**
00266  * Get the length of a list.
00267  *
00268  * This function counts the number of elements on a specified list.
00269  *
00270  * \param list The list.
00271  * \return The length of the list.
00272  */
00273 /*---------------------------------------------------------------------------*/
00274 int
00275 list_length(list_t list)
00276 {
00277   struct list *l;
00278   int n = 0;
00279 
00280   for(l = *list; l != NULL; l = l->next) {
00281     ++n;
00282   }
00283 
00284   return n;
00285 }
00286 /*---------------------------------------------------------------------------*/
00287 /**
00288  * \brief      Insert an item after a specified item on the list
00289  * \param list The list
00290  * \param previtem The item after which the new item should be inserted
00291  * \param newitem  The new item that is to be inserted
00292  * \author     Adam Dunkels
00293  *
00294  *             This function inserts an item right after a specified
00295  *             item on the list. This function is useful when using
00296  *             the list module to ordered lists.
00297  *
00298  *             If previtem is NULL, the new item is placed at the
00299  *             start of the list.
00300  *
00301  */
00302 void
00303 list_insert(list_t list, void *previtem, void *newitem)
00304 {
00305   if(previtem == NULL) {
00306     list_push(list, newitem);
00307   } else {
00308   
00309     ((struct list *)newitem)->next = ((struct list *)previtem)->next;
00310     ((struct list *)previtem)->next = newitem;
00311   }
00312 }
00313 /*---------------------------------------------------------------------------*/
00314 /**
00315  * \brief      Get the next item following this item
00316  * \param item A list item
00317  * \returns    A next item on the list
00318  *
00319  *             This function takes a list item and returns the next
00320  *             item on the list, or NULL if there are no more items on
00321  *             the list. This function is used when iterating through
00322  *             lists.
00323  */
00324 void *
00325 list_item_next(void *item)
00326 {
00327   return item == NULL? NULL: ((struct list *)item)->next;
00328 }
00329 /*---------------------------------------------------------------------------*/
00330 /** @} */