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
BLI_linklist_lockfree_init(LockfreeLinkList * list)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
BLI_linklist_lockfree_free(LockfreeLinkList * list,LockfreeeLinkNodeFreeFP free_func)37 void BLI_linklist_lockfree_free(LockfreeLinkList *list, LockfreeeLinkNodeFreeFP free_func)
38 {
39 if (free_func != NULL) {
40 /* NOTE: We start from a first user-added node. */
41 LockfreeLinkNode *node = list->head->next;
42 while (node != NULL) {
43 LockfreeLinkNode *node_next = node->next;
44 free_func(node);
45 node = node_next;
46 }
47 }
48 }
49
BLI_linklist_lockfree_clear(LockfreeLinkList * list,LockfreeeLinkNodeFreeFP free_func)50 void BLI_linklist_lockfree_clear(LockfreeLinkList *list, LockfreeeLinkNodeFreeFP free_func)
51 {
52 BLI_linklist_lockfree_free(list, free_func);
53 BLI_linklist_lockfree_init(list);
54 }
55
BLI_linklist_lockfree_insert(LockfreeLinkList * list,LockfreeLinkNode * node)56 void BLI_linklist_lockfree_insert(LockfreeLinkList *list, LockfreeLinkNode *node)
57 {
58 /* Based on:
59 *
60 * John D. Valois
61 * Implementing Lock-Free Queues
62 *
63 * http://people.csail.mit.edu/bushl2/rpi/portfolio/lockfree-grape/documents/lock-free-linked-lists.pdf
64 */
65 bool keep_working;
66 LockfreeLinkNode *tail_node;
67 node->next = NULL;
68 do {
69 tail_node = list->tail;
70 keep_working = (atomic_cas_ptr((void **)&tail_node->next, NULL, node) != NULL);
71 if (keep_working) {
72 atomic_cas_ptr((void **)&list->tail, tail_node, tail_node->next);
73 }
74 } while (keep_working);
75 atomic_cas_ptr((void **)&list->tail, tail_node, node);
76 }
77
BLI_linklist_lockfree_begin(LockfreeLinkList * list)78 LockfreeLinkNode *BLI_linklist_lockfree_begin(LockfreeLinkList *list)
79 {
80 return list->head->next;
81 }
82