cddl/contrib/opensolaris/tools/ctf/common/list.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 #pragma ident   "%Z%%M% %I%     %E% SMI"
  28
  29 /*
  30  * Routines for manipulating linked lists
  31  */
  32
  33 #include <stdio.h>
  34 #include <assert.h>
  35 #include <stdlib.h>
  36
  37 #include "list.h"
  38 #include "memory.h"
  39
  40 struct list {
  41         void *l_data;
  42         struct list *l_next;
  43 };
  44
  45 /* Add an element to a list */
  46 void
  47 list_add(list_t **list, void *data)
  48 {
  49         list_t *le;
  50
  51         le = xmalloc(sizeof (list_t));
  52         le->l_data = data;
  53         le->l_next = *list;
  54         *list = le;
  55 }
  56
  57 /* Add an element to a sorted list */
  58 void
  59 slist_add(list_t **list, void *data, int (*cmp)(void *, void *))
  60 {
  61         list_t **nextp;
  62
  63         for (nextp = list; *nextp; nextp = &((*nextp)->l_next)) {
  64                 if (cmp((*nextp)->l_data, data) > 0)
  65                         break;
  66         }
  67
  68         list_add(nextp, data);
  69 }
  70
  71 /*ARGSUSED2*/
  72 static int
  73 list_defcmp(void *d1, void *d2, void *private __unused)
  74 {
  75         return (d1 != d2);
  76 }
  77
  78 void *
  79 list_remove(list_t **list, void *data, int (*cmp)(void *, void *, void *),
  80     void *private)
  81 {
  82         list_t *le, **le2;
  83         void *led;
  84
  85         if (!cmp)
  86                 cmp = list_defcmp;
  87
  88         for (le = *list, le2 = list; le; le2 = &le->l_next, le = le->l_next) {
  89                 if (cmp(le->l_data, data, private) == 0) {
  90                         *le2 = le->l_next;
  91                         led = le->l_data;
  92                         free(le);
  93                         return (led);
  94                 }
  95         }
  96
  97         return (NULL);
  98 }
  99
 100 void
 101 list_free(list_t *list, void (*datafree)(void *, void *), void *private)
 102 {
 103         list_t *le;
 104
 105         while (list) {
 106                 le = list;
 107                 list = list->l_next;
 108                 if (le->l_data && datafree)
 109                         datafree(le->l_data, private);
 110                 free(le);
 111         }
 112 }
 113
 114 /*
 115  * This iterator is specifically designed to tolerate the deletion of the
 116  * node being iterated over.
 117  */
 118 int
 119 list_iter(list_t *list, int (*func)(void *, void *), void *private)
 120 {
 121         list_t *lnext;
 122         int cumrc = 0;
 123         int cbrc;
 124
 125         while (list) {
 126                 lnext = list->l_next;
 127                 if ((cbrc = func(list->l_data, private)) < 0)
 128                         return (cbrc);
 129                 cumrc += cbrc;
 130                 list = lnext;
 131         }
 132
 133         return (cumrc);
 134 }
 135
 136 /*ARGSUSED*/
 137 static int
 138 list_count_cb(void *data __unused, void *private __unused)
 139 {
 140         return (1);
 141 }
 142
 143 int
 144 list_count(list_t *list)
 145 {
 146         return (list_iter(list, list_count_cb, NULL));
 147 }
 148
 149 int
 150 list_empty(list_t *list)
 151 {
 152         return (list == NULL);
 153 }
 154
 155 void *
 156 list_find(list_t *list, void *tmpl, int (*cmp)(void *, void *))
 157 {
 158         for (; list; list = list->l_next) {
 159                 if (cmp(list->l_data, tmpl) == 0)
 160                         return (list->l_data);
 161         }
 162
 163         return (NULL);
 164 }
 165
 166 void *
 167 list_first(list_t *list)
 168 {
 169         return (list ? list->l_data : NULL);
 170 }
 171
 172 void
 173 list_concat(list_t **list1, list_t *list2)
 174 {
 175         list_t *l, *last;
 176
 177         for (l = *list1, last = NULL; l; last = l, l = l->l_next)
 178                 continue;
 179
 180         if (last == NULL)
 181                 *list1 = list2;
 182         else
 183                 last->l_next = list2;
 184 }
 185
 186 /*
 187  * Merges two sorted lists.  Equal nodes (as determined by cmp) are retained.
 188  */
 189 void
 190 slist_merge(list_t **list1p, list_t *list2, int (*cmp)(void *, void *))
 191 {
 192         list_t *list1, *next2;
 193         list_t *last1 = NULL;
 194
 195         if (*list1p == NULL) {
 196                 *list1p = list2;
 197                 return;
 198         }
 199
 200         list1 = *list1p;
 201         while (list2 != NULL) {
 202                 if (cmp(list1->l_data, list2->l_data) > 0) {
 203                         next2 = list2->l_next;
 204
 205                         if (last1 == NULL) {
 206                                 /* Insert at beginning */
 207                                 *list1p = last1 = list2;
 208                                 list2->l_next = list1;
 209                         } else {
 210                                 list2->l_next = list1;
 211                                 last1->l_next = list2;
 212                                 last1 = list2;
 213                         }
 214
 215                         list2 = next2;
 216                 } else {
 217
 218                         last1 = list1;
 219                         list1 = list1->l_next;
 220
 221                         if (list1 == NULL) {
 222                                 /* Add the rest to the end of list1 */
 223                                 last1->l_next = list2;
 224                                 list2 = NULL;
 225                         }
 226                 }
 227         }
 228 }