1/** 2 * \file 3 * \brief Barrelfish collections library list data structure 4 */ 5/* 6 * Copyright (c) 2010, 2012, ETH Zurich. 7 * All rights reserved. 8 * 9 * This file is distributed under the terms in the attached LICENSE file. 10 * If you do not find this file, copies can be found by writing to: 11 * ETH Zurich D-INFK, CAB F.78, Universitaetstrasse 6, CH-8092 Zurich, 12 * Attn: Systems Group. 13 */ 14 15#include <collections/list.h> 16 17/****************************************************** 18 * a simple linked list implementation. 19 ******************************************************/ 20 21/* 22 * private functions. 23 */ 24 25static void list_push(collections_listnode *existing, 26 collections_listnode *insert) 27{ 28 insert->next = existing->next; 29 insert->prev = existing; 30 existing->next = insert; 31 insert->next->prev = insert; 32} 33 34static void *list_pop(collections_listnode *n) 35{ 36 void *data = n->data; 37 n->next->prev = n->prev; 38 n->prev->next = n->next; 39 n->next = n->prev = NULL; 40 return data; 41} 42 43/* 44 * Insert the data at the head. 45 */ 46static collections_listnode *list_create_node(collections_listnode *start, 47 collections_listnode *where, 48 void *data) 49{ 50 collections_listnode *newnode = (collections_listnode *) 51 malloc(sizeof(collections_listnode)); 52 newnode->data = data; 53 54 list_push(where, newnode); 55 ((collections_header_data *)(start->data))->size ++; 56 return newnode; 57} 58 59static void list_destroy_node(collections_listnode *start, 60 collections_listnode *node) 61{ 62 list_pop(node); 63 free(node); 64 ((collections_header_data*)start->data)->size--; 65} 66 67 68/* 69 * public functions. 70 */ 71 72/* 73 * Creates a new linked list. 74 */ 75void collections_list_create(collections_listnode **start, 76 collections_release_data func) 77{ 78 collections_listnode *t; 79 80 // 81 // this is an empty list containing only the header. 82 // 83 t = (collections_listnode *)malloc(sizeof(collections_listnode)); 84 t->next = t->prev = t; 85 collections_header_data *h = (collections_header_data *) 86 malloc(sizeof(collections_header_data)); 87 h->size = 0; 88 h->data_free = func; 89 h->cur_item = NULL; 90 t->data = (void *)h; 91 92 *start = t; 93} 94 95/* 96 * Releases all the nodes in the list. 97 */ 98void collections_list_release(collections_listnode *start) 99{ 100 collections_release_data data_free = 101 ((collections_header_data*)start->data)->data_free; 102 collections_listnode *cur = start->next; 103 104 // 105 // travel through the rest of the 106 // list and release all the nodes. 107 // 108 while (cur != start) 109 { 110 void *data = cur->data; 111 if (data != NULL && data_free) 112 { 113 data_free(data); 114 } 115 list_destroy_node(start, cur); 116 cur = start->next; 117 } 118 119 // 120 // release the header. 121 // 122 free(start->data); 123 free(start); 124 125 return; 126} 127 128/* 129 * Inserts an element in the head of the list. 130 */ 131int32_t collections_list_insert(collections_listnode *start, void *data) 132{ 133 collections_listnode *ret = list_create_node(start, start, data); 134 if (ret) { 135 // success ... 136 return 0; 137 } 138 return 1; 139} 140 141/* 142 * Inserts an element at the tail of the list. 143 */ 144int32_t collections_list_insert_tail(collections_listnode *start, void *data) 145{ 146 collections_listnode *ret = list_create_node(start, start->prev, data); 147 if (ret) { 148 // success ... 149 return 0; 150 } 151 return 1; 152} 153 154/* 155 * Returns the data that matches the user provided key. 156 */ 157void *collections_list_find_if(collections_listnode *start, 158 collections_list_predicate p, void *arg) 159{ 160 collections_listnode *cur = start->next; 161 while (cur != start) 162 { 163 if (p(cur->data, arg)) 164 { 165 return cur->data; 166 } 167 168 cur = cur->next; 169 } 170 return NULL; 171} 172 173/** 174 * Remove the first item that matches the given predicate and return it. 175 * 176 * \return The removed item. 177 */ 178void *collections_list_remove_if(collections_listnode *start, 179 collections_list_predicate p, void *arg) 180{ 181 collections_listnode *cur = start->next; 182 while (cur != start) 183 { 184 if (p(cur->data, arg)) 185 { 186 void *data = cur->data; 187 list_destroy_node(start, cur); 188 return data; 189 } 190 cur = cur->next; 191 } 192 return NULL; 193} 194 195/** 196 * Remove all the items that match the given predicate. 197 * 198 * \return The number of items removed. 199 */ 200uint32_t collections_list_remove_if_all(collections_listnode *start, 201 collections_list_predicate p, void *arg) 202{ 203 uint32_t items_removed = 0; 204 205 collections_listnode *cur = start->next; 206 while (cur != start) 207 { 208 if (p(cur->data, arg)) 209 { 210 list_destroy_node(start, cur); 211 items_removed++; 212 } 213 cur = cur->next; 214 } 215 216 return items_removed; 217} 218 219void *collections_list_remove_ith_item(collections_listnode *start, 220 uint32_t item) 221{ 222 void *element; 223 224 uint32_t n = collections_list_size(start); 225 if (item >= n) { 226 element = NULL; 227 } else if (item <= n/2) { 228 229 collections_listnode *cur = start->next; 230 while (item != 0) { 231 cur = cur->next; 232 item--; 233 } 234 element = cur->data; 235 list_destroy_node(start, cur); 236 237 } else { 238 239 collections_listnode *cur = start; 240 do { 241 cur = cur ->prev; 242 item++; 243 } while (item !=n); 244 element = cur->data; 245 list_destroy_node(start, cur); 246 } 247 248 return element; 249} 250 251void *collections_list_get_ith_item(collections_listnode *start, uint32_t item) 252{ 253 uint32_t n = collections_list_size(start); 254 if (item >= n) { 255 return NULL; 256 } 257 else if (item <= n / 2) 258 { 259 collections_listnode* cur = start->next; 260 while (item != 0) 261 { 262 cur = cur->next; 263 item--; 264 } 265 return cur->data; 266 } 267 else 268 { 269 collections_listnode *cur = start; 270 do { 271 cur = cur->prev; 272 item++; 273 } while (item != n); 274 return cur->data; 275 } 276} 277 278/* 279 * Return the total number of nodes in the list. 280 */ 281uint32_t collections_list_size(collections_listnode *start) 282{ 283 return ((collections_header_data *)(start->data))->size; 284} 285 286#if 0 287static void* list_front(collections_listnode* start) 288{ 289 return (start->next == start) ? NULL : start->next->data; 290} 291 292static void* list_back(collections_listnode* start) 293{ 294 return (start->prev == start) ? NULL : start->prev->data; 295} 296#endif 297 298/* 299 * A set of routines for iteratively traversing through 300 * the linked list. 301 */ 302 303/* 304 * Opens the list for traversal. 305 */ 306int32_t collections_list_traverse_start(collections_listnode *start) 307{ 308 collections_header_data* head = (collections_header_data *) start->data; 309 310 if (head->cur_item) { 311 // if the next item is not null, a 312 // traversal is already in progress. 313 printf("Error: list is already opened for traversal.\n"); 314 return -1; 315 } 316 317 head->cur_item = start; 318 319 return 1; 320} 321 322/* 323 * Fetches the next item in the list. 324 * If all the items have been fetched, 325 * returns null. 326 */ 327void *collections_list_traverse_next(collections_listnode *start) 328{ 329 collections_header_data *head = (collections_header_data *) start->data; 330 331 if (!head->cur_item) { 332 // asking for the next item without 333 // starting the traversal. 334 printf("Error: list must be opened for traversal.\n"); 335 return NULL; 336 } 337 338 head->cur_item = head->cur_item->next; 339 if (head->cur_item == start) 340 { 341 return NULL; 342 } 343 else 344 { 345 return head->cur_item->data; 346 } 347} 348 349/* 350 * Finishes the list traversal. 351 */ 352int32_t collections_list_traverse_end(collections_listnode *start) 353{ 354 collections_header_data *head = (collections_header_data *) start->data; 355 356 if (!head->cur_item) { 357 // closing without 358 // starting the traversal. 359 printf("Error: list must be opened before ending.\n"); 360 return -1; 361 } 362 363 head->cur_item = NULL; 364 365 return 1; 366} 367 368int collections_list_visit(collections_listnode *start, 369 collections_list_visitor_func func, void *arg) 370{ 371 collections_listnode *cur = start->next; 372 while (cur != start && func(cur->data, arg)) 373 { 374 cur = cur->next; 375 } 376 return cur == start; 377} 378