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 43struct list_entry { 44 struct list_entry *m_prev; 45 struct list_entry *m_next; 46 void *m_object; 47 bool m_managed; 48}; 49 50static 51atf_list_citer_t 52entry_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 60static 61atf_list_iter_t 62entry_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 70static 71struct list_entry * 72new_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 87static 88void 89delete_entry(struct list_entry *le) 90{ 91 if (le->m_managed) 92 free(le->m_object); 93 94 free(le); 95} 96 97static 98struct list_entry * 99new_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 124const void * 125atf_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 132atf_list_citer_t 133atf_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 146bool 147atf_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 161void * 162atf_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 169atf_list_iter_t 170atf_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 183bool 184atf_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 198atf_error_t 199atf_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 227void 228atf_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 251atf_list_iter_t 252atf_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 258atf_list_citer_t 259atf_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 265atf_list_iter_t 266atf_list_end(atf_list_t *l) 267{ 268 return entry_to_iter(l, l->m_end); 269} 270 271atf_list_citer_t 272atf_list_end_c(const atf_list_t *l) 273{ 274 return entry_to_citer(l, l->m_end); 275} 276 277void * 278atf_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 296const void * 297atf_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 316size_t 317atf_list_size(const atf_list_t *l) 318{ 319 return l->m_size; 320} 321 322char ** 323atf_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 346out: 347 return array; 348} 349 350/* 351 * Modifiers. 352 */ 353 354atf_error_t 355atf_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 373void 374atf_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} 393