libconcurrent: add include file to stddbool into header.
[barrelfish] / include / concurrent / linked_list.h
1 /** \file
2  *  \brief A non-blocking linked list implementation, derived from Tim Harris' `pragmatic implementation`.
3  */
4
5 /*
6  * Copyright (c) 2009, 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, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
12  */
13 #ifndef LINKED_LIST_H_
14 #define LINKED_LIST_H_
15
16 #include <stdbool.h>
17 #include <sys/cdefs.h>
18
19 __BEGIN_DECLS
20
21 struct ll_element {
22     struct ll_element *next;
23     void* key;
24     void* data;
25 };
26
27 /*
28  * \brief create a new (empty) linked list. Creation is not thread-safe.
29  */
30 void ll_create(struct ll_element **head, struct ll_element **tail);
31
32 /*
33  * \brief insert a new element into the linked list.
34  */
35 bool ll_insert(struct ll_element *head, struct ll_element *tail,
36                 void* new_key, void* new_data);
37
38 /*
39  * \brief delete an element from the list.
40  */
41 bool ll_delete(struct ll_element *head, struct ll_element *tail, void* key);
42
43 /*
44  * \brief check if the list contains an element.
45  */
46 bool ll_contains(struct ll_element *head, struct ll_element *tail, void* key);
47
48 /*
49  * \brief print the content of the list to the screen. For debugging.
50  */
51 void ll_print(struct ll_element *head, struct ll_element *tail);
52
53 static inline const bool is_marked_reference(const uintptr_t p)
54 {
55     return p & 0x1;
56 }
57
58 static inline const uintptr_t get_unmarked_reference(const uintptr_t p)
59 {
60     return p & 0xFFFFFFFFFFFFFFFE;
61 }
62
63 static inline const uintptr_t get_marked_reference(const uintptr_t p)
64 {
65     return p | 0x1;
66 }
67
68 __END_DECLS
69
70 #endif /* LINKED_LIST_H_ */