contrib/atf/atf-c/detail/list.c

   1 /*
   2  * Automated Testing Framework (atf)
   3  *
   4  * Copyright (c) 2008 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND
  17  * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  18  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  19  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY
  21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  23  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
  25  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  26  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
  27  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32
  33 #include "atf-c/error.h"
  34 #include "atf-c/utils.h"
  35
  36 #include "list.h"
  37 #include "sanity.h"
  38
  39 /* ---------------------------------------------------------------------
  40  * Auxiliary functions.
  41  * --------------------------------------------------------------------- */
  42
  43 struct list_entry {
  44     struct list_entry *m_prev;
  45     struct list_entry *m_next;
  46     void *m_object;
  47     bool m_managed;
  48 };
  49
  50 static
  51 atf_list_citer_t
  52 entry_to_citer(const atf_list_t *l, const struct list_entry *le)
  53 {
  54     atf_list_citer_t iter;
  55     iter.m_list = l;
  56     iter.m_entry = le;
  57     return iter;
  58 }
  59
  60 static
  61 atf_list_iter_t
  62 entry_to_iter(atf_list_t *l, struct list_entry *le)
  63 {
  64     atf_list_iter_t iter;
  65     iter.m_list = l;
  66     iter.m_entry = le;
  67     return iter;
  68 }
  69
  70 static
  71 struct list_entry *
  72 new_entry(void *object, bool managed)
  73 {
  74     struct list_entry *le;
  75
  76     le = (struct list_entry *)malloc(sizeof(*le));
  77     if (le != NULL) {
  78         le->m_prev = le->m_next = NULL;
  79         le->m_object = object;
  80         le->m_managed = managed;
  81     } else
  82         free(object);
  83
  84     return le;
  85 }
  86
  87 static
  88 void
  89 delete_entry(struct list_entry *le)
  90 {
  91     if (le->m_managed)
  92         free(le->m_object);
  93
  94     free(le);
  95 }
  96
  97 static
  98 struct list_entry *
  99 new_entry_and_link(void *object, bool managed, struct list_entry *prev,
 100                    struct list_entry *next)
 101 {
 102     struct list_entry *le;
 103
 104     le = new_entry(object, managed);
 105     if (le != NULL) {
 106         le->m_prev = prev;
 107         le->m_next = next;
 108
 109         prev->m_next = le;
 110         next->m_prev = le;
 111     }
 112
 113     return le;
 114 }
 115
 116 /* ---------------------------------------------------------------------
 117  * The "atf_list_citer" type.
 118  * --------------------------------------------------------------------- */
 119
 120 /*
 121  * Getters.
 122  */
 123
 124 const void *
 125 atf_list_citer_data(const atf_list_citer_t citer)
 126 {
 127     const struct list_entry *le = citer.m_entry;
 128     PRE(le != NULL);
 129     return le->m_object;
 130 }
 131
 132 atf_list_citer_t
 133 atf_list_citer_next(const atf_list_citer_t citer)
 134 {
 135     const struct list_entry *le = citer.m_entry;
 136     atf_list_citer_t newciter;
 137
 138     PRE(le != NULL);
 139
 140     newciter = citer;
 141     newciter.m_entry = le->m_next;
 142
 143     return newciter;
 144 }
 145
 146 bool
 147 atf_equal_list_citer_list_citer(const atf_list_citer_t i1,
 148                                 const atf_list_citer_t i2)
 149 {
 150     return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry;
 151 }
 152
 153 /* ---------------------------------------------------------------------
 154  * The "atf_list_iter" type.
 155  * --------------------------------------------------------------------- */
 156
 157 /*
 158  * Getters.
 159  */
 160
 161 void *
 162 atf_list_iter_data(const atf_list_iter_t iter)
 163 {
 164     const struct list_entry *le = iter.m_entry;
 165     PRE(le != NULL);
 166     return le->m_object;
 167 }
 168
 169 atf_list_iter_t
 170 atf_list_iter_next(const atf_list_iter_t iter)
 171 {
 172     const struct list_entry *le = iter.m_entry;
 173     atf_list_iter_t newiter;
 174
 175     PRE(le != NULL);
 176
 177     newiter = iter;
 178     newiter.m_entry = le->m_next;
 179
 180     return newiter;
 181 }
 182
 183 bool
 184 atf_equal_list_iter_list_iter(const atf_list_iter_t i1,
 185                               const atf_list_iter_t i2)
 186 {
 187     return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry;
 188 }
 189
 190 /* ---------------------------------------------------------------------
 191  * The "atf_list" type.
 192  * --------------------------------------------------------------------- */
 193
 194 /*
 195  * Constructors and destructors.
 196  */
 197
 198 atf_error_t
 199 atf_list_init(atf_list_t *l)
 200 {
 201     struct list_entry *lebeg, *leend;
 202
 203     lebeg = new_entry(NULL, false);
 204     if (lebeg == NULL) {
 205         return atf_no_memory_error();
 206     }
 207
 208     leend = new_entry(NULL, false);
 209     if (leend == NULL) {
 210         free(lebeg);
 211         return atf_no_memory_error();
 212     }
 213
 214     lebeg->m_next = leend;
 215     lebeg->m_prev = NULL;
 216
 217     leend->m_next = NULL;
 218     leend->m_prev = lebeg;
 219
 220     l->m_size = 0;
 221     l->m_begin = lebeg;
 222     l->m_end = leend;
 223
 224     return atf_no_error();
 225 }
 226
 227 void
 228 atf_list_fini(atf_list_t *l)
 229 {
 230     struct list_entry *le;
 231     size_t freed;
 232
 233     le = (struct list_entry *)l->m_begin;
 234     freed = 0;
 235     while (le != NULL) {
 236         struct list_entry *lenext;
 237
 238         lenext = le->m_next;
 239         delete_entry(le);
 240         le = lenext;
 241
 242         freed++;
 243     }
 244     INV(freed == l->m_size + 2);
 245 }
 246
 247 /*
 248  * Getters.
 249  */
 250
 251 atf_list_iter_t
 252 atf_list_begin(atf_list_t *l)
 253 {
 254     struct list_entry *le = l->m_begin;
 255     return entry_to_iter(l, le->m_next);
 256 }
 257
 258 atf_list_citer_t
 259 atf_list_begin_c(const atf_list_t *l)
 260 {
 261     const struct list_entry *le = l->m_begin;
 262     return entry_to_citer(l, le->m_next);
 263 }
 264
 265 atf_list_iter_t
 266 atf_list_end(atf_list_t *l)
 267 {
 268     return entry_to_iter(l, l->m_end);
 269 }
 270
 271 atf_list_citer_t
 272 atf_list_end_c(const atf_list_t *l)
 273 {
 274     return entry_to_citer(l, l->m_end);
 275 }
 276
 277 void *
 278 atf_list_index(atf_list_t *list, const size_t idx)
 279 {
 280     atf_list_iter_t iter;
 281
 282     PRE(idx < atf_list_size(list));
 283
 284     iter = atf_list_begin(list);
 285     {
 286         size_t pos = 0;
 287         while (pos < idx &&
 288                !atf_equal_list_iter_list_iter((iter), atf_list_end(list))) {
 289             iter = atf_list_iter_next(iter);
 290             pos++;
 291         }
 292     }
 293     return atf_list_iter_data(iter);
 294 }
 295
 296 const void *
 297 atf_list_index_c(const atf_list_t *list, const size_t idx)
 298 {
 299     atf_list_citer_t iter;
 300
 301     PRE(idx < atf_list_size(list));
 302
 303     iter = atf_list_begin_c(list);
 304     {
 305         size_t pos = 0;
 306         while (pos < idx &&
 307                !atf_equal_list_citer_list_citer((iter),
 308                                                 atf_list_end_c(list))) {
 309             iter = atf_list_citer_next(iter);
 310             pos++;
 311         }
 312     }
 313     return atf_list_citer_data(iter);
 314 }
 315
 316 size_t
 317 atf_list_size(const atf_list_t *l)
 318 {
 319     return l->m_size;
 320 }
 321
 322 char **
 323 atf_list_to_charpp(const atf_list_t *l)
 324 {
 325     char **array;
 326     atf_list_citer_t iter;
 327     size_t i;
 328
 329     array = malloc(sizeof(char *) * (atf_list_size(l) + 1));
 330     if (array == NULL)
 331         goto out;
 332
 333     i = 0;
 334     atf_list_for_each_c(iter, l) {
 335         array[i] = strdup((const char *)atf_list_citer_data(iter));
 336         if (array[i] == NULL) {
 337             atf_utils_free_charpp(array);
 338             array = NULL;
 339             goto out;
 340         }
 341
 342         i++;
 343     }
 344     array[i] = NULL;
 345
 346 out:
 347     return array;
 348 }
 349
 350 /*
 351  * Modifiers.
 352  */
 353
 354 atf_error_t
 355 atf_list_append(atf_list_t *l, void *data, bool managed)
 356 {
 357     struct list_entry *le, *next, *prev;
 358     atf_error_t err;
 359
 360     next = (struct list_entry *)l->m_end;
 361     prev = next->m_prev;
 362     le = new_entry_and_link(data, managed, prev, next);
 363     if (le == NULL)
 364         err = atf_no_memory_error();
 365     else {
 366         l->m_size++;
 367         err = atf_no_error();
 368     }
 369
 370     return err;
 371 }
 372
 373 void
 374 atf_list_append_list(atf_list_t *l, atf_list_t *src)
 375 {
 376     struct list_entry *e1, *e2, *ghost1, *ghost2;
 377
 378     ghost1 = (struct list_entry *)l->m_end;
 379     ghost2 = (struct list_entry *)src->m_begin;
 380
 381     e1 = ghost1->m_prev;
 382     e2 = ghost2->m_next;
 383
 384     delete_entry(ghost1);
 385     delete_entry(ghost2);
 386
 387     e1->m_next = e2;
 388     e2->m_prev = e1;
 389
 390     l->m_end = src->m_end;
 391     l->m_size += src->m_size;
 392 }