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
21struct 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 */
30void ll_create(struct ll_element **head, struct ll_element **tail);
31
32/*
33 * \brief insert a new element into the linked list.
34 */
35bool 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 */
41bool ll_delete(struct ll_element *head, struct ll_element *tail, void* key);
42
43/*
44 * \brief check if the list contains an element.
45 */
46bool 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 */
51void ll_print(struct ll_element *head, struct ll_element *tail);
52
53static inline const bool is_marked_reference(const uintptr_t p)
54{
55    return p & 0x1;
56}
57
58static inline const uintptr_t get_unmarked_reference(const uintptr_t p)
59{
60    return p & 0xFFFFFFFFFFFFFFFE;
61}
62
63static 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_ */
71