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