external/bsd/atf/dist/atf-c/list.c

   1 /*
   2  * Automated Testing Framework (atf)
   3  *
   4  * Copyright (c) 2008, 2009 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
  32 #include "atf-c/error.h"
  33 #include "atf-c/list.h"
  34 #include "atf-c/sanity.h"
  35
  36 /* ---------------------------------------------------------------------
  37  * Auxiliary functions.
  38  * --------------------------------------------------------------------- */
  39
  40 struct list_entry {
  41     struct list_entry *m_prev;
  42     struct list_entry *m_next;
  43     void *m_object;
  44     bool m_managed;
  45 };
  46
  47 static
  48 atf_list_citer_t
  49 entry_to_citer(const atf_list_t *l, const struct list_entry *le)
  50 {
  51     atf_list_citer_t iter;
  52     iter.m_list = l;
  53     iter.m_entry = le;
  54     return iter;
  55 }
  56
  57 static
  58 atf_list_iter_t
  59 entry_to_iter(atf_list_t *l, struct list_entry *le)
  60 {
  61     atf_list_iter_t iter;
  62     iter.m_list = l;
  63     iter.m_entry = le;
  64     return iter;
  65 }
  66
  67 static
  68 struct list_entry *
  69 new_entry(void *object, bool managed)
  70 {
  71     struct list_entry *le;
  72
  73     le = (struct list_entry *)malloc(sizeof(*le));
  74     if (le != NULL) {
  75         le->m_prev = le->m_next = NULL;
  76         le->m_object = object;
  77         le->m_managed = managed;
  78     } else
  79         free(object);
  80
  81     return le;
  82 }
  83
  84 static
  85 void
  86 delete_entry(struct list_entry *le)
  87 {
  88     if (le->m_managed)
  89         free(le->m_object);
  90
  91     free(le);
  92 }
  93
  94 static
  95 struct list_entry *
  96 new_entry_and_link(void *object, bool managed, struct list_entry *prev,
  97                    struct list_entry *next)
  98 {
  99     struct list_entry *le;
 100
 101     le = new_entry(object, managed);
 102     if (le != NULL) {
 103         le->m_prev = prev;
 104         le->m_next = next;
 105
 106         prev->m_next = le;
 107         next->m_prev = le;
 108     }
 109
 110     return le;
 111 }
 112
 113 /* ---------------------------------------------------------------------
 114  * The "atf_list_citer" type.
 115  * --------------------------------------------------------------------- */
 116
 117 /*
 118  * Getters.
 119  */
 120
 121 const void *
 122 atf_list_citer_data(const atf_list_citer_t citer)
 123 {
 124     const struct list_entry *le = citer.m_entry;
 125     PRE(le != NULL);
 126     return le->m_object;
 127 }
 128
 129 atf_list_citer_t
 130 atf_list_citer_next(const atf_list_citer_t citer)
 131 {
 132     const struct list_entry *le = citer.m_entry;
 133     atf_list_citer_t newciter;
 134
 135     PRE(le != NULL);
 136
 137     newciter = citer;
 138     newciter.m_entry = le->m_next;
 139
 140     return newciter;
 141 }
 142
 143 bool
 144 atf_equal_list_citer_list_citer(const atf_list_citer_t i1,
 145                                 const atf_list_citer_t i2)
 146 {
 147     return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry;
 148 }
 149
 150 /* ---------------------------------------------------------------------
 151  * The "atf_list_iter" type.
 152  * --------------------------------------------------------------------- */
 153
 154 /*
 155  * Getters.
 156  */
 157
 158 void *
 159 atf_list_iter_data(const atf_list_iter_t iter)
 160 {
 161     const struct list_entry *le = iter.m_entry;
 162     PRE(le != NULL);
 163     return le->m_object;
 164 }
 165
 166 atf_list_iter_t
 167 atf_list_iter_next(const atf_list_iter_t iter)
 168 {
 169     const struct list_entry *le = iter.m_entry;
 170     atf_list_iter_t newiter;
 171
 172     PRE(le != NULL);
 173
 174     newiter = iter;
 175     newiter.m_entry = le->m_next;
 176
 177     return newiter;
 178 }
 179
 180 bool
 181 atf_equal_list_iter_list_iter(const atf_list_iter_t i1,
 182                               const atf_list_iter_t i2)
 183 {
 184     return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry;
 185 }
 186
 187 /* ---------------------------------------------------------------------
 188  * The "atf_list" type.
 189  * --------------------------------------------------------------------- */
 190
 191 /*
 192  * Constructors and destructors.
 193  */
 194
 195 atf_error_t
 196 atf_list_init(atf_list_t *l)
 197 {
 198     struct list_entry *lebeg, *leend;
 199
 200     lebeg = new_entry(NULL, false);
 201     if (lebeg == NULL) {
 202         return atf_no_memory_error();
 203     }
 204
 205     leend = new_entry(NULL, false);
 206     if (leend == NULL) {
 207         free(lebeg);
 208         return atf_no_memory_error();
 209     }
 210
 211     lebeg->m_next = leend;
 212     lebeg->m_prev = NULL;
 213
 214     leend->m_next = NULL;
 215     leend->m_prev = lebeg;
 216
 217     l->m_size = 0;
 218     l->m_begin = lebeg;
 219     l->m_end = leend;
 220
 221     atf_object_init(&l->m_object);
 222
 223     return atf_no_error();
 224 }
 225
 226 void
 227 atf_list_fini(atf_list_t *l)
 228 {
 229     struct list_entry *le;
 230     size_t freed;
 231
 232     le = (struct list_entry *)l->m_begin;
 233     freed = 0;
 234     while (le != NULL) {
 235         struct list_entry *lenext;
 236
 237         lenext = le->m_next;
 238         delete_entry(le);
 239         le = lenext;
 240
 241         freed++;
 242     }
 243     INV(freed == l->m_size + 2);
 244
 245     atf_object_fini(&l->m_object);
 246 }
 247
 248 /*
 249  * Getters.
 250  */
 251
 252 atf_list_iter_t
 253 atf_list_begin(atf_list_t *l)
 254 {
 255     struct list_entry *le = l->m_begin;
 256     return entry_to_iter(l, le->m_next);
 257 }
 258
 259 atf_list_citer_t
 260 atf_list_begin_c(const atf_list_t *l)
 261 {
 262     const struct list_entry *le = l->m_begin;
 263     return entry_to_citer(l, le->m_next);
 264 }
 265
 266 atf_list_iter_t
 267 atf_list_end(atf_list_t *l)
 268 {
 269     return entry_to_iter(l, l->m_end);
 270 }
 271
 272 atf_list_citer_t
 273 atf_list_end_c(const atf_list_t *l)
 274 {
 275     return entry_to_citer(l, l->m_end);
 276 }
 277
 278 void *
 279 atf_list_index(atf_list_t *list, const size_t idx)
 280 {
 281     atf_list_iter_t iter;
 282
 283     PRE(idx < atf_list_size(list));
 284
 285     iter = atf_list_begin(list);
 286     {
 287         size_t pos = 0;
 288         while (pos < idx &&
 289                !atf_equal_list_iter_list_iter((iter), atf_list_end(list))) {
 290             iter = atf_list_iter_next(iter);
 291             pos++;
 292         }
 293     }
 294     return atf_list_iter_data(iter);
 295 }
 296
 297 const void *
 298 atf_list_index_c(const atf_list_t *list, const size_t idx)
 299 {
 300     atf_list_citer_t iter;
 301
 302     PRE(idx < atf_list_size(list));
 303
 304     iter = atf_list_begin_c(list);
 305     {
 306         size_t pos = 0;
 307         while (pos < idx &&
 308                !atf_equal_list_citer_list_citer((iter),
 309                                                 atf_list_end_c(list))) {
 310             iter = atf_list_citer_next(iter);
 311             pos++;
 312         }
 313     }
 314     return atf_list_citer_data(iter);
 315 }
 316
 317 size_t
 318 atf_list_size(const atf_list_t *l)
 319 {
 320     return l->m_size;
 321 }
 322
 323 /*
 324  * Modifiers.
 325  */
 326
 327 atf_error_t
 328 atf_list_append(atf_list_t *l, void *data, bool managed)
 329 {
 330     struct list_entry *le, *next, *prev;
 331     atf_error_t err;
 332
 333     next = (struct list_entry *)l->m_end;
 334     prev = next->m_prev;
 335     le = new_entry_and_link(data, managed, prev, next);
 336     if (le == NULL)
 337         err = atf_no_memory_error();
 338     else {
 339         l->m_size++;
 340         err = atf_no_error();
 341     }
 342
 343     return err;
 344 }
 345
 346 void
 347 atf_list_append_list(atf_list_t *l, atf_list_t *src)
 348 {
 349     struct list_entry *e1, *e2, *ghost1, *ghost2;
 350
 351     ghost1 = (struct list_entry *)l->m_end;
 352     ghost2 = (struct list_entry *)src->m_begin;
 353
 354     e1 = ghost1->m_prev;
 355     e2 = ghost2->m_next;
 356
 357     delete_entry(ghost1);
 358     delete_entry(ghost2);
 359
 360     e1->m_next = e2;
 361     e2->m_prev = e1;
 362
 363     l->m_end = src->m_end;
 364     l->m_size += src->m_size;
 365
 366     atf_object_fini(&src->m_object);
 367 }