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

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