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