1 /*
   2  * Copyright (c) 1999, 2020, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  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 1994 Hewlett-Packard Co.
  40 Copyright 1996, 1998  The Open Group
  41 
  42 Permission to use, copy, modify, distribute, and sell this software and its
  43 documentation for any purpose is hereby granted without fee, provided that
  44 the above copyright notice appear in all copies and that both that
  45 copyright notice and this permission notice appear in supporting
  46 documentation.
  47 
  48 The above copyright notice and this permission notice shall be included
  49 in all copies or substantial portions of the Software.
  50 
  51 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  52 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  53 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  54 IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
  55 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  56 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  57 OTHER DEALINGS IN THE SOFTWARE.
  58 
  59 Except as contained in this notice, the name of The Open Group shall
  60 not be used in advertising or otherwise to promote the sale, use or
  61 other dealings in this Software without prior written authorization
  62 from The Open Group.
  63 
  64   ----------------------------------------------------------------------- **/
  65 
  66 #ifdef HEADLESS
  67     #error This file should not be included in headless library
  68 #endif
  69 
  70 #include <stdio.h>
  71 #include <stdlib.h>
  72 
  73 #include "list.h"
  74 
  75 
  76 /** ------------------------------------------------------------------------
  77         Sets the pointers of the specified list to NULL.
  78     --------------------------------------------------------------------- **/
  79 void zero_list(list_ptr lp)
  80 {
  81     lp->next = NULL;
  82     lp->ptr.item = NULL;
  83 }
  84 
  85 
  86 /** ------------------------------------------------------------------------
  87         Adds item to the list pointed to by lp.  Finds the end of the
  88         list, then mallocs a new list node onto the end of the list.
  89         The item pointer in the new node is set to "item" passed in,
  90         and the next pointer in the new node is set to NULL.
  91         Returns 1 if successful, 0 if the malloc failed.
  92     -------------------------------------------------------------------- **/
  93 int add_to_list(list_ptr lp, void *item)
  94 {
  95     while (lp->next) {
  96         lp = lp->next;
  97     }
  98     if ((lp->next = (list_ptr) malloc( sizeof( list_item))) == NULL) {
  99 
 100         return 0;
 101     }
 102     lp->next->ptr.item = item;
 103     lp->next->next = NULL;
 104 
 105     return 1;
 106 }
 107 
 108 
 109 /** ------------------------------------------------------------------------
 110         Creates a new list and sets its pointers to NULL.
 111         Returns a pointer to the new list.
 112     -------------------------------------------------------------------- **/
 113 list_ptr new_list (void)
 114 {
 115     list_ptr lp;
 116 
 117     if ((lp = (list_ptr) malloc( sizeof( list_item)))) {
 118         lp->next = NULL;
 119         lp->ptr.item = NULL;
 120     }
 121 
 122     return lp;
 123 }
 124 
 125 
 126 /** ------------------------------------------------------------------------
 127         Creates a new list head, pointing to the same list as the one
 128         passed in.  If start_at_curr is TRUE, the new list's first item
 129         is the "current" item (as set by calls to first/next_in_list()).
 130         If start_at_curr is FALSE, the first item in the new list is the
 131         same as the first item in the old list.  In either case, the
 132         curr pointer in the new list is the same as in the old list.
 133         Returns a pointer to the new list head.
 134     -------------------------------------------------------------------- **/
 135 list_ptr dup_list_head(list_ptr lp, int start_at_curr)
 136 {
 137     list_ptr new_listp;
 138 
 139     if ((new_listp = (list_ptr) malloc( sizeof( list_item))) == NULL) {
 140 
 141         return (list_ptr)NULL;
 142     }
 143     new_listp->next = start_at_curr ? lp->ptr.curr : lp->next;
 144     new_listp->ptr.curr = lp->ptr.curr;
 145 
 146     return new_listp;
 147 }
 148 
 149 
 150 /** ------------------------------------------------------------------------
 151         Returns the number of items in the list.
 152     -------------------------------------------------------------------- **/
 153 unsigned int list_length(list_ptr lp)
 154 {
 155     unsigned int count = 0;
 156 
 157     while (lp->next) {
 158         count++;
 159         lp = lp->next;
 160     }
 161 
 162     return count;
 163 }
 164 
 165 
 166 /** ------------------------------------------------------------------------
 167         Scans thru list, looking for a node whose ptr.item is equal to
 168         the "item" passed in.  "Equal" here means the same address - no
 169         attempt is made to match equivalent values stored in different
 170         locations.  If a match is found, that node is deleted from the
 171         list.  Storage for the node is freed, but not for the item itself.
 172         Returns a pointer to the item, so the caller can free it if it
 173         so desires.  If a match is not found, returns NULL.
 174     -------------------------------------------------------------------- **/
 175 void *delete_from_list(list_ptr lp, void *item)
 176 {
 177     list_ptr new_next;
 178 
 179     while (lp->next) {
 180         if (lp->next->ptr.item == item) {
 181             new_next = lp->next->next;
 182             free (lp->next);
 183             lp->next = new_next;
 184 
 185             return item;
 186         }
 187         lp = lp->next;
 188     }
 189 
 190     return NULL;
 191 }
 192 
 193 
 194 /** ------------------------------------------------------------------------
 195         Deletes each node in the list *except the head*.  This allows
 196         the deletion of lists where the head is not malloced or created
 197         with new_list().  If free_items is true, each item pointed to
 198         from the node is freed, in addition to the node itself.
 199     -------------------------------------------------------------------- **/
 200 void delete_list(list_ptr lp, int free_items)
 201 {
 202     list_ptr del_node;
 203     void *item;
 204 
 205     while (lp->next) {
 206         del_node = lp->next;
 207         item = del_node->ptr.item;
 208         lp->next = del_node->next;
 209         free (del_node);
 210         if (free_items) {
 211             free( item);
 212         }
 213     }
 214 }
 215 
 216 void delete_list_destroying(list_ptr lp, void destructor(void *item))
 217 {
 218     list_ptr del_node;
 219     void *item;
 220 
 221     while (lp->next) {
 222         del_node = lp->next;
 223         item = del_node->ptr.item;
 224         lp->next = del_node->next;
 225         free( del_node);
 226         if (destructor) {
 227             destructor( item);
 228         }
 229     }
 230 }
 231 
 232 
 233 /** ------------------------------------------------------------------------
 234         Returns a ptr to the first *item* (not list node) in the list.
 235         Sets the list head node's curr ptr to the first node in the list.
 236         Returns NULL if the list is empty.
 237     -------------------------------------------------------------------- **/
 238 void * first_in_list(list_ptr lp)
 239 {
 240     if (! lp) {
 241 
 242         return NULL;
 243     }
 244     lp->ptr.curr = lp->next;
 245 
 246     return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
 247 }
 248 
 249 /** ------------------------------------------------------------------------
 250         Returns a ptr to the next *item* (not list node) in the list.
 251         Sets the list head node's curr ptr to the next node in the list.
 252         first_in_list must have been called prior.
 253         Returns NULL if no next item.
 254     -------------------------------------------------------------------- **/
 255 void * next_in_list(list_ptr lp)
 256 {
 257     if (! lp) {
 258 
 259         return NULL;
 260     }
 261     if (lp->ptr.curr) {
 262         lp->ptr.curr = lp->ptr.curr->next;
 263     }
 264 
 265     return lp->ptr.curr ? lp->ptr.curr->ptr.item : NULL;
 266 }
 267 
 268 int list_is_empty(list_ptr lp)
 269 {
 270     return (lp == NULL || lp->next == NULL);
 271 }
 272 
--- EOF ---