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, Universitaetstr. 6, CH-8092 Zurich, 12 * Attn: Systems Group. 13 */ 14 15#ifndef _LIST_H_ 16#define _LIST_H_ 17 18#include <assert.h> 19#include <stdio.h> 20#include <string.h> 21#include <stdlib.h> 22#include <sys/cdefs.h> 23 24#ifdef WIN32 25#include <malloc.h> 26#include "stdint.h" 27#endif // WIN32 28 29#ifdef BARRELFISH 30#include <stdint.h> 31#include <barrelfish/barrelfish.h> 32#endif // BARRELFISH 33 34__BEGIN_DECLS 35 36/* 37 * Predicate function. 38 * Should return zero for false, non-zero otherwise. 39 */ 40typedef int32_t (*collections_list_predicate)(void *data, void *arg); 41 42/* 43 * a function that can be used to release the user-supplied 44 * data items. 45 */ 46typedef void (*collections_release_data)(void *data); 47 48/* 49 * structure of each element in the 50 * linked list. 51 */ 52struct _collections_listnode; 53 54typedef struct _collections_listnode { 55 // 56 // pointer to the previous node. 57 // 58 struct _collections_listnode *prev; 59 60 // 61 // pointer to the next node. 62 // 63 struct _collections_listnode *next; 64 65 // 66 // an abstract data value to store. 67 // 68 void *data; 69} collections_listnode; 70 71/* 72 * a header to the linked list 73 */ 74typedef struct _collections_header_data { 75 // total number of elements. 76 uint32_t size; 77 78 // comparison function provided by the user. 79 collections_release_data data_free; 80 81 // a pointer to keep track of 82 // traversing the list. 83 collections_listnode *cur_item; 84} collections_header_data; 85 86 87/* 88 * functions ... 89 */ 90 91void collections_list_create(collections_listnode **start, 92 collections_release_data func); 93void collections_list_release(collections_listnode *start); 94int32_t collections_list_insert(collections_listnode *start, void *data); 95int32_t collections_list_insert_tail(collections_listnode *start, void *data); 96void *collections_list_get_ith_item(collections_listnode *start, 97 uint32_t index); 98void *collections_list_find_if(collections_listnode *start, 99 collections_list_predicate p, void *arg); 100void *collections_list_remove_if(collections_listnode *start, 101 collections_list_predicate p, void *key); 102uint32_t collections_list_remove_if_all(collections_listnode *start, 103 collections_list_predicate p, 104 void *key); 105void *collections_list_remove_ith_item(collections_listnode *start, 106 uint32_t index); 107uint32_t collections_list_size(collections_listnode *start); 108int32_t collections_list_traverse_start(collections_listnode *start); 109void *collections_list_traverse_next(collections_listnode *start); 110int32_t collections_list_traverse_end(collections_listnode *start); 111 112/* 113 * Visitor function. Should return non-zero to continue iteration. 114 */ 115typedef int (*collections_list_visitor_func)(void *data, void *arg); 116/* 117 * Visit elements in list with function f until f indicates stop or end of list 118 * reached. 119 * Return non-zero if end of list reached, 0 otherwise. 120 */ 121int collections_list_visit(collections_listnode *start, 122 collections_list_visitor_func f, void *arg); 123 124__END_DECLS 125 126#endif 127