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#include <assert.h>
14#include <stdio.h>
15#include <stdlib.h>
16#include <concurrent/arch/cas.h>
17#include <concurrent/linked_list.h>
18
19static struct ll_element *search(struct ll_element *head,
20        struct ll_element *tail, struct ll_element **left_node, void* key)
21{
22    assert(head != NULL);
23    assert(tail != NULL);
24    assert(left_node != NULL);
25    assert(key != NULL);
26
27    *left_node = NULL; // for sanity-check assertion below
28
29    struct ll_element *left_node_next = NULL, *right_node = NULL;
30    struct ll_element *current = head, *next = head->next;
31
32    do {
33        // empty list?
34        if ((current == head) && (next == tail)) {
35            (*left_node) = head;
36            return tail;
37        }
38
39        // find left and right node
40        if (!is_marked_reference((uintptr_t) next)) {
41            (*left_node) = current;
42            left_node_next = next;
43        }
44        current = (struct ll_element*) get_unmarked_reference(
45                (uintptr_t) current->next);
46
47        if (current != tail) {
48            next = current->next;
49
50            if (is_marked_reference((uintptr_t) next) || (current->key < key
51                    && next != tail)) {
52                continue;
53            }
54        }
55
56        right_node = current;
57
58        // check if nodes are adjacent
59        if (left_node_next == right_node) {
60            if ((right_node != tail) && is_marked_reference(
61                    (uintptr_t) right_node->next)) {
62                // start again
63                current = head;
64                continue;
65            } else {
66                return right_node;
67            }
68        }
69
70        // remove marked nodes in between, since nodes are not adjacent
71        // TODO: optimize!
72        assert(*left_node != NULL);
73        if (cas((uintptr_t*) (*left_node)->next, *(uintptr_t*) left_node_next,
74                *(uintptr_t*) right_node)) {
75            if ((right_node != tail) && is_marked_reference(
76                    (uintptr_t) right_node->next)) {
77                // start again
78                current = head;
79                continue;
80            } else {
81                return right_node;
82            }
83        }
84
85    } while (1);
86    return tail;
87}
88
89bool ll_contains(struct ll_element *head, struct ll_element *tail, void* key)
90{
91    struct ll_element *prev;
92    struct ll_element *node = search(head, tail, &prev, key);
93    return node != tail && node->key == key;
94}
95
96void ll_create(struct ll_element **head, struct ll_element **tail)
97{
98    (*head) = malloc(sizeof(struct ll_element));
99    (**head).key = NULL;
100    (*tail) = malloc(sizeof(struct ll_element));
101    (**tail).key = NULL;
102    (*head)->next = (*tail);
103}
104
105bool ll_insert(struct ll_element *head, struct ll_element *tail, void* new_key,
106        void* data)
107{
108    assert(head != NULL);
109    assert(tail != NULL);
110    assert(new_key != NULL);
111    struct ll_element *new_elem = malloc(sizeof(struct ll_element));
112    assert(new_elem != NULL);
113    new_elem->key = new_key;
114    new_elem->data = data;
115
116    struct ll_element *left_node = NULL, *right_node;
117
118    do {
119        right_node = search(head, tail, &left_node, new_key);
120        assert(right_node != NULL);
121        assert(left_node != NULL);
122
123        if ((right_node != tail) && (right_node->key == new_key)) {
124            return false;
125        }
126        new_elem->next = right_node;
127    } while (!cas((uintptr_t*) &left_node->next, (uintptr_t) right_node,
128            (uintptr_t) new_elem));
129    return true;
130}
131
132bool ll_delete(struct ll_element *head, struct ll_element *tail, void* key)
133{
134    assert(head != NULL);
135    assert(tail != NULL);
136    assert(key != NULL);
137
138    struct ll_element *right_node, *right_node_next, *left_node;
139
140    do {
141        right_node = search(head, tail, &left_node, key);
142        if (right_node == tail || right_node->key != key) {
143            return false;
144        }
145        right_node_next = right_node->next;
146        if (!is_marked_reference((uintptr_t) right_node_next)) {
147            if (cas((uintptr_t*) &right_node->next,
148                    (uintptr_t) right_node_next, get_marked_reference(
149                            (uintptr_t) right_node_next))) {
150                break;
151            }
152        }
153    } while (1);
154    if (!cas((uintptr_t*) &left_node->next, (uintptr_t) right_node,
155            (uintptr_t) right_node_next)) {
156        right_node = search(head, tail, &left_node, right_node->key);
157    }
158    return true;
159}
160
161void ll_print(struct ll_element *head, struct ll_element *tail)
162{
163    printf("LIST {");
164    for (struct ll_element *current = head->next; current != tail; current
165            = current->next) {
166        assert(current->key != NULL);
167        printf("key %ld,", (uint64_t) * (uintptr_t*) current->key);
168
169        struct ll_element *next;
170        do {
171            next = current->next;
172            current = (struct ll_element *) get_unmarked_reference((uintptr_t) next);
173        } while (is_marked_reference((uintptr_t) next));
174    }
175    printf("}\n");
176}
177
178