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