Contiki 2.6
|
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 /** @} */