1275988Sngie/* Copyright (c) 2008 The NetBSD Foundation, Inc. 2240116Smarcel * All rights reserved. 3240116Smarcel * 4240116Smarcel * Redistribution and use in source and binary forms, with or without 5240116Smarcel * modification, are permitted provided that the following conditions 6240116Smarcel * are met: 7240116Smarcel * 1. Redistributions of source code must retain the above copyright 8240116Smarcel * notice, this list of conditions and the following disclaimer. 9240116Smarcel * 2. Redistributions in binary form must reproduce the above copyright 10240116Smarcel * notice, this list of conditions and the following disclaimer in the 11240116Smarcel * documentation and/or other materials provided with the distribution. 12240116Smarcel * 13240116Smarcel * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND 14240116Smarcel * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 15240116Smarcel * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 16240116Smarcel * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17240116Smarcel * IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY 18240116Smarcel * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19240116Smarcel * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 20240116Smarcel * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 21240116Smarcel * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER 22240116Smarcel * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 23240116Smarcel * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN 24275988Sngie * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ 25240116Smarcel 26275988Sngie#include "atf-c/detail/list.h" 27275988Sngie 28240116Smarcel#include <stdlib.h> 29240116Smarcel#include <string.h> 30240116Smarcel 31275988Sngie#include "atf-c/detail/sanity.h" 32240116Smarcel#include "atf-c/error.h" 33240116Smarcel#include "atf-c/utils.h" 34240116Smarcel 35240116Smarcel/* --------------------------------------------------------------------- 36240116Smarcel * Auxiliary functions. 37240116Smarcel * --------------------------------------------------------------------- */ 38240116Smarcel 39240116Smarcelstruct list_entry { 40240116Smarcel struct list_entry *m_prev; 41240116Smarcel struct list_entry *m_next; 42240116Smarcel void *m_object; 43240116Smarcel bool m_managed; 44240116Smarcel}; 45240116Smarcel 46240116Smarcelstatic 47240116Smarcelatf_list_citer_t 48240116Smarcelentry_to_citer(const atf_list_t *l, const struct list_entry *le) 49240116Smarcel{ 50240116Smarcel atf_list_citer_t iter; 51240116Smarcel iter.m_list = l; 52240116Smarcel iter.m_entry = le; 53240116Smarcel return iter; 54240116Smarcel} 55240116Smarcel 56240116Smarcelstatic 57240116Smarcelatf_list_iter_t 58240116Smarcelentry_to_iter(atf_list_t *l, struct list_entry *le) 59240116Smarcel{ 60240116Smarcel atf_list_iter_t iter; 61240116Smarcel iter.m_list = l; 62240116Smarcel iter.m_entry = le; 63240116Smarcel return iter; 64240116Smarcel} 65240116Smarcel 66240116Smarcelstatic 67240116Smarcelstruct list_entry * 68240116Smarcelnew_entry(void *object, bool managed) 69240116Smarcel{ 70240116Smarcel struct list_entry *le; 71240116Smarcel 72240116Smarcel le = (struct list_entry *)malloc(sizeof(*le)); 73240116Smarcel if (le != NULL) { 74240116Smarcel le->m_prev = le->m_next = NULL; 75240116Smarcel le->m_object = object; 76240116Smarcel le->m_managed = managed; 77240116Smarcel } else 78240116Smarcel free(object); 79240116Smarcel 80240116Smarcel return le; 81240116Smarcel} 82240116Smarcel 83240116Smarcelstatic 84240116Smarcelvoid 85240116Smarceldelete_entry(struct list_entry *le) 86240116Smarcel{ 87240116Smarcel if (le->m_managed) 88240116Smarcel free(le->m_object); 89240116Smarcel 90240116Smarcel free(le); 91240116Smarcel} 92240116Smarcel 93240116Smarcelstatic 94240116Smarcelstruct list_entry * 95240116Smarcelnew_entry_and_link(void *object, bool managed, struct list_entry *prev, 96240116Smarcel struct list_entry *next) 97240116Smarcel{ 98240116Smarcel struct list_entry *le; 99240116Smarcel 100240116Smarcel le = new_entry(object, managed); 101240116Smarcel if (le != NULL) { 102240116Smarcel le->m_prev = prev; 103240116Smarcel le->m_next = next; 104240116Smarcel 105240116Smarcel prev->m_next = le; 106240116Smarcel next->m_prev = le; 107240116Smarcel } 108240116Smarcel 109240116Smarcel return le; 110240116Smarcel} 111240116Smarcel 112240116Smarcel/* --------------------------------------------------------------------- 113240116Smarcel * The "atf_list_citer" type. 114240116Smarcel * --------------------------------------------------------------------- */ 115240116Smarcel 116240116Smarcel/* 117240116Smarcel * Getters. 118240116Smarcel */ 119240116Smarcel 120240116Smarcelconst void * 121240116Smarcelatf_list_citer_data(const atf_list_citer_t citer) 122240116Smarcel{ 123240116Smarcel const struct list_entry *le = citer.m_entry; 124240116Smarcel PRE(le != NULL); 125240116Smarcel return le->m_object; 126240116Smarcel} 127240116Smarcel 128240116Smarcelatf_list_citer_t 129240116Smarcelatf_list_citer_next(const atf_list_citer_t citer) 130240116Smarcel{ 131240116Smarcel const struct list_entry *le = citer.m_entry; 132240116Smarcel atf_list_citer_t newciter; 133240116Smarcel 134240116Smarcel PRE(le != NULL); 135240116Smarcel 136240116Smarcel newciter = citer; 137240116Smarcel newciter.m_entry = le->m_next; 138240116Smarcel 139240116Smarcel return newciter; 140240116Smarcel} 141240116Smarcel 142240116Smarcelbool 143240116Smarcelatf_equal_list_citer_list_citer(const atf_list_citer_t i1, 144240116Smarcel const atf_list_citer_t i2) 145240116Smarcel{ 146240116Smarcel return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry; 147240116Smarcel} 148240116Smarcel 149240116Smarcel/* --------------------------------------------------------------------- 150240116Smarcel * The "atf_list_iter" type. 151240116Smarcel * --------------------------------------------------------------------- */ 152240116Smarcel 153240116Smarcel/* 154240116Smarcel * Getters. 155240116Smarcel */ 156240116Smarcel 157240116Smarcelvoid * 158240116Smarcelatf_list_iter_data(const atf_list_iter_t iter) 159240116Smarcel{ 160240116Smarcel const struct list_entry *le = iter.m_entry; 161240116Smarcel PRE(le != NULL); 162240116Smarcel return le->m_object; 163240116Smarcel} 164240116Smarcel 165240116Smarcelatf_list_iter_t 166240116Smarcelatf_list_iter_next(const atf_list_iter_t iter) 167240116Smarcel{ 168240116Smarcel const struct list_entry *le = iter.m_entry; 169240116Smarcel atf_list_iter_t newiter; 170240116Smarcel 171240116Smarcel PRE(le != NULL); 172240116Smarcel 173240116Smarcel newiter = iter; 174240116Smarcel newiter.m_entry = le->m_next; 175240116Smarcel 176240116Smarcel return newiter; 177240116Smarcel} 178240116Smarcel 179240116Smarcelbool 180240116Smarcelatf_equal_list_iter_list_iter(const atf_list_iter_t i1, 181240116Smarcel const atf_list_iter_t i2) 182240116Smarcel{ 183240116Smarcel return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry; 184240116Smarcel} 185240116Smarcel 186240116Smarcel/* --------------------------------------------------------------------- 187240116Smarcel * The "atf_list" type. 188240116Smarcel * --------------------------------------------------------------------- */ 189240116Smarcel 190240116Smarcel/* 191240116Smarcel * Constructors and destructors. 192240116Smarcel */ 193240116Smarcel 194240116Smarcelatf_error_t 195240116Smarcelatf_list_init(atf_list_t *l) 196240116Smarcel{ 197240116Smarcel struct list_entry *lebeg, *leend; 198240116Smarcel 199240116Smarcel lebeg = new_entry(NULL, false); 200240116Smarcel if (lebeg == NULL) { 201240116Smarcel return atf_no_memory_error(); 202240116Smarcel } 203240116Smarcel 204240116Smarcel leend = new_entry(NULL, false); 205240116Smarcel if (leend == NULL) { 206240116Smarcel free(lebeg); 207240116Smarcel return atf_no_memory_error(); 208240116Smarcel } 209240116Smarcel 210240116Smarcel lebeg->m_next = leend; 211240116Smarcel lebeg->m_prev = NULL; 212240116Smarcel 213240116Smarcel leend->m_next = NULL; 214240116Smarcel leend->m_prev = lebeg; 215240116Smarcel 216240116Smarcel l->m_size = 0; 217240116Smarcel l->m_begin = lebeg; 218240116Smarcel l->m_end = leend; 219240116Smarcel 220240116Smarcel return atf_no_error(); 221240116Smarcel} 222240116Smarcel 223240116Smarcelvoid 224240116Smarcelatf_list_fini(atf_list_t *l) 225240116Smarcel{ 226240116Smarcel struct list_entry *le; 227240116Smarcel size_t freed; 228240116Smarcel 229240116Smarcel le = (struct list_entry *)l->m_begin; 230240116Smarcel freed = 0; 231240116Smarcel while (le != NULL) { 232240116Smarcel struct list_entry *lenext; 233240116Smarcel 234240116Smarcel lenext = le->m_next; 235240116Smarcel delete_entry(le); 236240116Smarcel le = lenext; 237240116Smarcel 238240116Smarcel freed++; 239240116Smarcel } 240240116Smarcel INV(freed == l->m_size + 2); 241240116Smarcel} 242240116Smarcel 243240116Smarcel/* 244240116Smarcel * Getters. 245240116Smarcel */ 246240116Smarcel 247240116Smarcelatf_list_iter_t 248240116Smarcelatf_list_begin(atf_list_t *l) 249240116Smarcel{ 250240116Smarcel struct list_entry *le = l->m_begin; 251240116Smarcel return entry_to_iter(l, le->m_next); 252240116Smarcel} 253240116Smarcel 254240116Smarcelatf_list_citer_t 255240116Smarcelatf_list_begin_c(const atf_list_t *l) 256240116Smarcel{ 257240116Smarcel const struct list_entry *le = l->m_begin; 258240116Smarcel return entry_to_citer(l, le->m_next); 259240116Smarcel} 260240116Smarcel 261240116Smarcelatf_list_iter_t 262240116Smarcelatf_list_end(atf_list_t *l) 263240116Smarcel{ 264240116Smarcel return entry_to_iter(l, l->m_end); 265240116Smarcel} 266240116Smarcel 267240116Smarcelatf_list_citer_t 268240116Smarcelatf_list_end_c(const atf_list_t *l) 269240116Smarcel{ 270240116Smarcel return entry_to_citer(l, l->m_end); 271240116Smarcel} 272240116Smarcel 273240116Smarcelvoid * 274240116Smarcelatf_list_index(atf_list_t *list, const size_t idx) 275240116Smarcel{ 276240116Smarcel atf_list_iter_t iter; 277240116Smarcel 278240116Smarcel PRE(idx < atf_list_size(list)); 279240116Smarcel 280240116Smarcel iter = atf_list_begin(list); 281240116Smarcel { 282240116Smarcel size_t pos = 0; 283240116Smarcel while (pos < idx && 284240116Smarcel !atf_equal_list_iter_list_iter((iter), atf_list_end(list))) { 285240116Smarcel iter = atf_list_iter_next(iter); 286240116Smarcel pos++; 287240116Smarcel } 288240116Smarcel } 289240116Smarcel return atf_list_iter_data(iter); 290240116Smarcel} 291240116Smarcel 292240116Smarcelconst void * 293240116Smarcelatf_list_index_c(const atf_list_t *list, const size_t idx) 294240116Smarcel{ 295240116Smarcel atf_list_citer_t iter; 296240116Smarcel 297240116Smarcel PRE(idx < atf_list_size(list)); 298240116Smarcel 299240116Smarcel iter = atf_list_begin_c(list); 300240116Smarcel { 301240116Smarcel size_t pos = 0; 302240116Smarcel while (pos < idx && 303240116Smarcel !atf_equal_list_citer_list_citer((iter), 304240116Smarcel atf_list_end_c(list))) { 305240116Smarcel iter = atf_list_citer_next(iter); 306240116Smarcel pos++; 307240116Smarcel } 308240116Smarcel } 309240116Smarcel return atf_list_citer_data(iter); 310240116Smarcel} 311240116Smarcel 312240116Smarcelsize_t 313240116Smarcelatf_list_size(const atf_list_t *l) 314240116Smarcel{ 315240116Smarcel return l->m_size; 316240116Smarcel} 317240116Smarcel 318240116Smarcelchar ** 319240116Smarcelatf_list_to_charpp(const atf_list_t *l) 320240116Smarcel{ 321240116Smarcel char **array; 322240116Smarcel atf_list_citer_t iter; 323240116Smarcel size_t i; 324240116Smarcel 325240116Smarcel array = malloc(sizeof(char *) * (atf_list_size(l) + 1)); 326240116Smarcel if (array == NULL) 327240116Smarcel goto out; 328240116Smarcel 329240116Smarcel i = 0; 330240116Smarcel atf_list_for_each_c(iter, l) { 331240116Smarcel array[i] = strdup((const char *)atf_list_citer_data(iter)); 332240116Smarcel if (array[i] == NULL) { 333240116Smarcel atf_utils_free_charpp(array); 334240116Smarcel array = NULL; 335240116Smarcel goto out; 336240116Smarcel } 337240116Smarcel 338240116Smarcel i++; 339240116Smarcel } 340240116Smarcel array[i] = NULL; 341240116Smarcel 342240116Smarcelout: 343240116Smarcel return array; 344240116Smarcel} 345240116Smarcel 346240116Smarcel/* 347240116Smarcel * Modifiers. 348240116Smarcel */ 349240116Smarcel 350240116Smarcelatf_error_t 351240116Smarcelatf_list_append(atf_list_t *l, void *data, bool managed) 352240116Smarcel{ 353240116Smarcel struct list_entry *le, *next, *prev; 354240116Smarcel atf_error_t err; 355240116Smarcel 356240116Smarcel next = (struct list_entry *)l->m_end; 357240116Smarcel prev = next->m_prev; 358240116Smarcel le = new_entry_and_link(data, managed, prev, next); 359240116Smarcel if (le == NULL) 360240116Smarcel err = atf_no_memory_error(); 361240116Smarcel else { 362240116Smarcel l->m_size++; 363240116Smarcel err = atf_no_error(); 364240116Smarcel } 365240116Smarcel 366240116Smarcel return err; 367240116Smarcel} 368240116Smarcel 369240116Smarcelvoid 370240116Smarcelatf_list_append_list(atf_list_t *l, atf_list_t *src) 371240116Smarcel{ 372240116Smarcel struct list_entry *e1, *e2, *ghost1, *ghost2; 373240116Smarcel 374240116Smarcel ghost1 = (struct list_entry *)l->m_end; 375240116Smarcel ghost2 = (struct list_entry *)src->m_begin; 376240116Smarcel 377240116Smarcel e1 = ghost1->m_prev; 378240116Smarcel e2 = ghost2->m_next; 379240116Smarcel 380240116Smarcel delete_entry(ghost1); 381240116Smarcel delete_entry(ghost2); 382240116Smarcel 383240116Smarcel e1->m_next = e2; 384240116Smarcel e2->m_prev = e1; 385240116Smarcel 386240116Smarcel l->m_end = src->m_end; 387240116Smarcel l->m_size += src->m_size; 388240116Smarcel} 389