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