external/bsd/bind/dist/unit/atf-src/atf-c/detail/list.c

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