76f6b8e649145bed19f36b689a906eca3c39be87
[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 <sys/cdefs.h>
17
18 __BEGIN_DECLS
19
20 struct ll_element {
21     struct ll_element *next;
22     void* key;
23     void* data;
24 };
25
26 /*
27  * \brief create a new (empty) linked list. Creation is not thread-safe.
28  */
29 void ll_create(struct ll_element **head, struct ll_element **tail);
30
31 /*
32  * \brief insert a new element into the linked list.
33  */
34 bool ll_insert(struct ll_element *head, struct ll_element *tail,
35                 void* new_key, void* new_data);
36
37 /*
38  * \brief delete an element from the list.
39  */
40 bool ll_delete(struct ll_element *head, struct ll_element *tail, void* key);
41
42 /*
43  * \brief check if the list contains an element.
44  */
45 bool ll_contains(struct ll_element *head, struct ll_element *tail, void* key);
46
47 /*
48  * \brief print the content of the list to the screen. For debugging.
49  */
50 void ll_print(struct ll_element *head, struct ll_element *tail);
51
52 static inline const bool is_marked_reference(const uintptr_t p)
53 {
54     return p & 0x1;
55 }
56
57 static inline const uintptr_t get_unmarked_reference(const uintptr_t p)
58 {
59     return p & 0xFFFFFFFFFFFFFFFE;
60 }
61
62 static inline const uintptr_t get_marked_reference(const uintptr_t p)
63 {
64     return p | 0x1;
65 }
66
67 __END_DECLS
68
69 #endif /* LINKED_LIST_H_ */