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 <sys/cdefs.h>
  17
  18 __BEGIN_DECLS
  19
  20 struct ll_element {
  21     struct ll_element *next;
  22     void* key;
  23     void* data;
  24 };
  25
  26 /*
  27  * \brief create a new (empty) linked list. Creation is not thread-safe.
  28  */
  29 void ll_create(struct ll_element **head, struct ll_element **tail);
  30
  31 /*
  32  * \brief insert a new element into the linked list.
  33  */
  34 bool ll_insert(struct ll_element *head, struct ll_element *tail,
  35                 void* new_key, void* new_data);
  36
  37 /*
  38  * \brief delete an element from the list.
  39  */
  40 bool ll_delete(struct ll_element *head, struct ll_element *tail, void* key);
  41
  42 /*
  43  * \brief check if the list contains an element.
  44  */
  45 bool ll_contains(struct ll_element *head, struct ll_element *tail, void* key);
  46
  47 /*
  48  * \brief print the content of the list to the screen. For debugging.
  49  */
  50 void ll_print(struct ll_element *head, struct ll_element *tail);
  51
  52 static inline const bool is_marked_reference(const uintptr_t p)
  53 {
  54     return p & 0x1;
  55 }
  56
  57 static inline const uintptr_t get_unmarked_reference(const uintptr_t p)
  58 {
  59     return p & 0xFFFFFFFFFFFFFFFE;
  60 }
  61
  62 static inline const uintptr_t get_marked_reference(const uintptr_t p)
  63 {
  64     return p | 0x1;
  65 }
  66
  67 __END_DECLS
  68
  69 #endif /* LINKED_LIST_H_ */