doxygen: add newline after \file
[blender.git] / source / blender / blenlib / intern / BLI_linklist_lockfree.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2018 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bli
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_linklist_lockfree.h"
27 #include "BLI_strict_flags.h"
28
29 #include "atomic_ops.h"
30
31 void BLI_linklist_lockfree_init(LockfreeLinkList *list)
32 {
33         list->dummy_node.next = NULL;
34         list->head = list->tail = &list->dummy_node;
35 }
36
37 void BLI_linklist_lockfree_free(LockfreeLinkList *list,
38                                 LockfreeeLinkNodeFreeFP free_func)
39 {
40         if (free_func != NULL) {
41                 /* NOTE: We start from a first user-added node. */
42                 LockfreeLinkNode *node = list->head->next;
43                 while (node != NULL) {
44                         LockfreeLinkNode *node_next = node->next;
45                         free_func(node);
46                         node = node_next;
47                 }
48         }
49 }
50
51 void BLI_linklist_lockfree_clear(LockfreeLinkList *list,
52                                  LockfreeeLinkNodeFreeFP free_func)
53 {
54         BLI_linklist_lockfree_free(list, free_func);
55         BLI_linklist_lockfree_init(list);
56 }
57
58 void BLI_linklist_lockfree_insert(LockfreeLinkList *list,
59                                   LockfreeLinkNode *node)
60 {
61         /* Based on:
62          *
63          *   John D. Valois
64          *   Implementing Lock-Free Queues
65          *
66          *   http://people.csail.mit.edu/bushl2/rpi/portfolio/lockfree-grape/documents/lock-free-linked-lists.pdf
67          */
68         bool keep_working;
69         LockfreeLinkNode *tail_node;
70         node->next = NULL;
71         do {
72                 tail_node = list->tail;
73                 keep_working =
74                         (atomic_cas_ptr((void **)&tail_node->next, NULL, node) != NULL);
75                 if (keep_working) {
76                         atomic_cas_ptr((void **)&list->tail, tail_node, tail_node->next);
77                 }
78         } while (keep_working);
79         atomic_cas_ptr((void **)&list->tail, tail_node, node);
80 }
81
82 LockfreeLinkNode *BLI_linklist_lockfree_begin(LockfreeLinkList *list)
83 {
84         return list->head->next;
85 }