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