diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2018-04-13 14:31:55 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2018-04-16 11:18:43 +0300 |
commit | 5bfe6126f8bd7cd59bafd90658a12c19687a26fb (patch) | |
tree | 5b144437acd5412e71b22043263dd4519f8357f5 /source/blender/blenlib/intern/BLI_linklist_lockfree.c | |
parent | 2720667566d73c52a3cc293d057d297ac775c74d (diff) |
Added lock-free single linked list implementation
Only supports lock-free insertion for now, can not delete element
or traverse the list at the same time.
Diffstat (limited to 'source/blender/blenlib/intern/BLI_linklist_lockfree.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_linklist_lockfree.c | 91 |
1 files changed, 91 insertions, 0 deletions
diff --git a/source/blender/blenlib/intern/BLI_linklist_lockfree.c b/source/blender/blenlib/intern/BLI_linklist_lockfree.c new file mode 100644 index 00000000000..c004ddb6b66 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_linklist_lockfree.c @@ -0,0 +1,91 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2018 Blender Foundation. + * All rights reserved. + * + * Contributor(s): Sergey Sharybin. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/BLI_linklist_lockfree.c + * \ingroup bli + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_linklist_lockfree.h" +#include "BLI_strict_flags.h" + +#include "atomic_ops.h" + +void BLI_linklist_lockfree_init(LockfreeLinkList *list) +{ + list->dummy_node.next = NULL; + list->head = list->tail = &list->dummy_node; +} + +void BLI_linklist_lockfree_free(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func) +{ + if (free_func != NULL) { + /* NOTE: We start from a first user-added node. */ + LockfreeLinkNode *node = list->head->next; + while (node != NULL) { + LockfreeLinkNode *node_next = node->next; + free_func(node); + node = node_next; + } + } +} + +void BLI_linklist_lockfree_clear(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func) +{ + BLI_linklist_lockfree_free(list, free_func); + BLI_linklist_lockfree_init(list); +} + +void BLI_linklist_lockfree_insert(LockfreeLinkList *list, + LockfreeLinkNode *node) +{ + /* Based on: + * + * John D. Valois + * Implementing Lock-Free Queues + * + * http://people.csail.mit.edu/bushl2/rpi/portfolio/lockfree-grape/documents/lock-free-linked-lists.pdf + */ + bool keep_working; + LockfreeLinkNode *tail_node; + node->next = NULL; + do { + tail_node = list->tail; + keep_working = + (atomic_cas_ptr((void**)&tail_node->next, NULL, node) != NULL); + if (keep_working) { + atomic_cas_ptr((void**)&list->tail, tail_node, tail_node->next); + } + } while (keep_working); + atomic_cas_ptr((void**)&list->tail, tail_node, node); +} + +LockfreeLinkNode *BLI_linklist_lockfree_begin(LockfreeLinkList *list) +{ + return list->head->next; +} |