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 39struct list_entry { 40 struct list_entry *m_prev; 41 struct list_entry *m_next; 42 void *m_object; 43 bool m_managed; 44}; 45 46static 47atf_list_citer_t 48entry_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 56static 57atf_list_iter_t 58entry_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 66static 67struct list_entry * 68new_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 if (managed) 78 free(object); 79 80 return le; 81} 82 83static 84void 85delete_entry(struct list_entry *le) 86{ 87 if (le->m_managed) 88 free(le->m_object); 89 90 free(le); 91} 92 93static 94struct list_entry * 95new_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 120const void * 121atf_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 128atf_list_citer_t 129atf_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 142bool 143atf_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 157void * 158atf_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 165atf_list_iter_t 166atf_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 179bool 180atf_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 194atf_error_t 195atf_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 223void 224atf_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 247atf_list_iter_t 248atf_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 254atf_list_citer_t 255atf_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 261atf_list_iter_t 262atf_list_end(atf_list_t *l) 263{ 264 return entry_to_iter(l, l->m_end); 265} 266 267atf_list_citer_t 268atf_list_end_c(const atf_list_t *l) 269{ 270 return entry_to_citer(l, l->m_end); 271} 272 273void * 274atf_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 292const void * 293atf_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 312size_t 313atf_list_size(const atf_list_t *l) 314{ 315 return l->m_size; 316} 317 318char ** 319atf_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 342out: 343 return array; 344} 345 346/* 347 * Modifiers. 348 */ 349 350atf_error_t 351atf_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 369void 370atf_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} 389