1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 /* $XConsortium: list.c /main/4 1996/10/14 15:03:56 swick $ */
  25 /** ------------------------------------------------------------------------
  26         This file contains routines for manipulating generic lists.
  27         Lists are implemented with a "harness".  In other words, each
  28         node in the list consists of two pointers, one to the data item
  29         and one to the next node in the list.  The head of the list is
  30         the same struct as each node, but the "item" ptr is used to point
  31         to the current member of the list (used by the first_in_list and
  32         next_in_list functions).
  33 
  34  This file is available under and governed by the GNU General Public
  35  License version 2 only, as published by the Free Software Foundation.
  36  However, the following notice accompanied the original version of this
  37  file:
  38 
  39 Copyright (c) 1994 Hewlett-Packard Co.
  40 Copyright (c) 1996  X Consortium
  41 
  42 Permission is hereby granted, free of charge, to any person obtaining
  43 a copy of this software and associated documentation files (the
  44 "Software"), to deal in the Software without restriction, including
  45 without limitation the rights to use, copy, modify, merge, publish,
  46 distribute, sublicense, and sell copies of the Software, and to
  47 permit persons to whom the Software is furnished to do so, subject to
  48 the following conditions:
  49 
  50 The above copyright notice and this permission notice shall be included
  51 in all copies or substantial portions of the Software.
  52 
  53 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  54 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  55 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  56 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR
  57 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  58 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  59 OTHER DEALINGS IN THE SOFTWARE.
  60 
  61 Except as contained in this notice, the name of the X Consortium shall
  62 not be used in advertising or otherwise to promote the sale, use or
  63 other dealings in this Software without prior written authorization
  64 from the X Consortium.
  65 
  66   ----------------------------------------------------------------------- **/
  67 
  68 #include <stdio.h>
  69 #include <stdlib.h>
  70 #include "list.h"
  71 
  72 
  73 /** ------------------------------------------------------------------------
  74         Sets the pointers of the specified list to NULL.
  75     --------------------------------------------------------------------- **/
  76 #if NeedFunctionPrototypes
  77 void zero_list(list_ptr lp)
  78 #else
  79 void zero_list(lp)
  80     list_ptr lp;
  81 #endif
  82 {
  83     lp->next = NULL;
  84     lp->ptr.item = NULL;
  85 }
  86 
  87 
  88 /** ------------------------------------------------------------------------
  89         Adds item to the list pointed to by lp.  Finds the end of the
  90         list, then mallocs a new list node onto the end of the list.
  91         The item pointer in the new node is set to "item" passed in,
  92         and the next pointer in the new node is set to NULL.
  93         Returns 1 if successful, 0 if the malloc failed.
  94     -------------------------------------------------------------------- **/
  95 #if NeedFunctionPrototypes
  96 int32_t add_to_list(list_ptr lp, void *item)
  97 #else
  98 int32_t add_to_list(lp, item)
  99     list_ptr lp;
 100     void *item;
 101 #endif
 102 {
 103     while (lp->next) {
 104         lp = lp->next;
 105     }

 106     
 107     lp->next = (list_ptr) malloc(sizeof(list_item));
 108     if (lp->next == NULL) {
 109         return 0;
 110     }
 111     lp->next->ptr.item = item;
 112     lp->next->next = NULL;
 113 
 114     return 1;
 115 }
 116 
 117 
 118 /** ------------------------------------------------------------------------
 119         Creates a new list and sets its pointers to NULL.
 120         Returns a pointer to the new list.
 121     -------------------------------------------------------------------- **/
 122 list_ptr new_list ()
 123 {
 124     list_ptr lp;
 125 
 126     lp = (list_ptr) malloc(sizeof(list_item));
 127     if (lp) {
 128         lp->next = NULL;
 129         lp->ptr.item = NULL;
 130     }
 131 
 132     return lp;
 133 }
 134 
 135 
 136 /** ------------------------------------------------------------------------
 137         Creates a new list head, pointing to the same list as the one
 138         passed in.  If start_at_curr is TRUE, the new list's first item
 139         is the "current" item (as set by calls to first/next_in_list()).
 140         If start_at_curr is FALSE, the first item in the new list is the
 141         same as the first item in the old list.  In either case, the
 142         curr pointer in the new list is the same as in the old list.
 143         Returns a pointer to the new list head.
 144     -------------------------------------------------------------------- **/
 145 #if NeedFunctionPrototypes
 146 list_ptr dup_list_head(list_ptr lp, int32_t start_at_curr)
 147 #else
 148 list_ptr dup_list_head(lp, start_at_curr)
 149     list_ptr lp;
 150     int32_t start_at_curr;
 151 #endif
 152 {
 153     list_ptr new_list;
 154 
 155     if ((new_list = (list_ptr) malloc( sizeof( list_item))) == NULL) {
 156 
 157         return (list_ptr)NULL;
 158     }
 159     new_list->next = start_at_curr ? lp->ptr.curr : lp->next;
 160     new_list->ptr.curr = lp->ptr.curr;
 161 
 162     return new_list;
 163 }
 164 
 165 
 166 /** ------------------------------------------------------------------------
 167         Returns the number of items in the list.
 168     -------------------------------------------------------------------- **/
 169 #if NeedFunctionPrototypes
 170 uint32_t list_length(list_ptr lp)
 171 #else
 172 uint32_t list_length(lp)
 173     list_ptr lp;
 174 #endif
 175 {
 176     uint32_t count = 0;
 177 
 178     while (lp->next) {
 179         count++;
 180         lp = lp->next;
 181     }
 182 
 183     return count;
 184 }
 185 
 186 
 187 /** ------------------------------------------------------------------------
 188         Scans thru list, looking for a node whose ptr.item is equal to
 189         the "item" passed in.  "Equal" here means the same address - no
 190         attempt is made to match equivalent values stored in different
 191         locations.  If a match is found, that node is deleted from the
 192         list.  Storage for the node is freed, but not for the item itself.
 193         Returns a pointer to the item, so the caller can free it if it
 194         so desires.  If a match is not found, returns NULL.
 195     -------------------------------------------------------------------- **/
 196 #if NeedFunctionPrototypes
 197 void *delete_from_list(list_ptr lp, void *item)
 198 #else
 199 void *delete_from_list(lp, item)
 200     list_ptr lp;
 201     void *item;
 202 #endif
 203 {
 204     list_ptr new_next;
 205 
 206     while (lp->next) {
 207         if (lp->next->ptr.item == item) {
 208             new_next = lp->next->next;
 209             free (lp->next);
 210             lp->next = new_next;
 211 
 212             return item;
 213         }
 214         lp = lp->next;
 215     }
 216 
 217     return NULL;
 218 }
 219 
 220 
 221 /** ------------------------------------------------------------------------
 222         Deletes each node in the list *except the head*.  This allows
 223         the deletion of lists where the head is not malloced or created
 224         with new_list().  If free_items is true, each item pointed to
 225         from the node is freed, in addition to the node itself.
 226     -------------------------------------------------------------------- **/
 227 #if NeedFunctionPrototypes
 228 void delete_list(list_ptr lp, int32_t free_items)
 229 #else
 230 void delete_list(lp, free_items)
 231     list_ptr lp;
 232     int32_t free_items;
 233 #endif
 234 {
 235     list_ptr del_node;
 236     void *item;
 237 
 238     while (lp->next) {
 239         del_node = lp->next;
 240         item = del_node->ptr.item;
 241         lp->next = del_node->next;
 242         free (del_node);
 243         if (free_items) {
 244             free( item);
 245         }
 246     }
 247 }
 248 
 249 #if NeedFunctionPrototypes
 250 void delete_list_destroying(list_ptr lp, void destructor(void *item))
 251 #else
 252 void delete_list_destroying(lp, destructor)
 253     list_ptr lp;
 254     void (*destructor)();
 255 #endif
 256 {
 257     list_ptr del_node;
 258     void *item;
 259 
 260     while (lp->next) {
 261         del_node = lp->next;
 262         item = del_node->ptr.item;
 263         lp->next = del_node->next;
 264         free( del_node);
 265         if (destructor) {
 266             destructor( item);
 267         }
 268     }
 269 }
 270 
 271 
 272 /** ------------------------------------------------------------------------
 273         Returns a ptr to the first *item* (not list node) in the list.
 274         Sets the list head node's curr ptr to the first node in the list.
 275         Returns NULL if the list is empty.
 276     -------------------------------------------------------------------- **/
 277 #if NeedFunctionPrototypes
 278 void * first_in_list(list_ptr lp)
 279 #else
 280 void * first_in_list(lp)
 281     list_ptr lp;
 282 #endif
 283 {
 284     if (! lp) {
 285 
 286         return NULL;
 287     }
 288     lp->ptr.curr = lp->next;
 289 
 290     return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
 291 }
 292 
 293 /** ------------------------------------------------------------------------
 294         Returns a ptr to the next *item* (not list node) in the list.
 295         Sets the list head node's curr ptr to the next node in the list.
 296         first_in_list must have been called prior.
 297         Returns NULL if no next item.
 298     -------------------------------------------------------------------- **/
 299 #if NeedFunctionPrototypes
 300 void * next_in_list(list_ptr lp)
 301 #else
 302 void * next_in_list(lp)
 303     list_ptr lp;
 304 #endif
 305 {
 306     if (! lp) {
 307 
 308         return NULL;
 309     }
 310     if (lp->ptr.curr) {
 311         lp->ptr.curr = lp->ptr.curr->next;
 312     }
 313 
 314     return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
 315 }
 316 
 317 #if NeedFunctionPrototypes
 318 int32_t list_is_empty(list_ptr lp)
 319 #else
 320 int32_t list_is_empty(lp)
 321     list_ptr lp;
 322 #endif
 323 {
 324     return (lp == NULL || lp->next == NULL);
 325 }
--- EOF ---