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