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/BLI_linklist_lockfree.h | |
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/BLI_linklist_lockfree.h')
-rw-r--r-- | source/blender/blenlib/BLI_linklist_lockfree.h | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_linklist_lockfree.h b/source/blender/blenlib/BLI_linklist_lockfree.h new file mode 100644 index 00000000000..7e7400361e3 --- /dev/null +++ b/source/blender/blenlib/BLI_linklist_lockfree.h @@ -0,0 +1,88 @@ +/* + * ***** 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 ***** + */ + +#ifndef __BLI_LINKLIST_LOCKFREE_H__ +#define __BLI_LINKLIST_LOCKFREE_H__ + +/** \file BLI_linklist_lockfree.h + * \ingroup bli + */ + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct LockfreeLinkNode { + struct LockfreeLinkNode *next; + /* NOTE: "Subclass" this structure to add custom-defined data. */ +} LockfreeLinkNode; + +typedef struct LockfreeLinkList { + /* We keep a dummy node at the beginning of the list all the time. + * This allows us to make sure head and tail pointers are always + * valid, and saves from annoying exception cases in insert(). + */ + LockfreeLinkNode dummy_node; + /* NOTE: This fields might point to a dummy node. */ + LockfreeLinkNode *head, *tail; +} LockfreeLinkList; + +typedef void (*LockfreeeLinkNodeFreeFP)(void *link); + +/* ************************************************************************** */ +/* NOTE: These functions are NOT safe for use from threads. */ +/* NOTE: !!! I REPEAT: DO NOT USE THEM WITHOUT EXTERNAL LOCK !!! */ + +/* Make list ready for lock-free access. */ +void BLI_linklist_lockfree_init(LockfreeLinkList *list); + +/* Completely free the whole list, it is NOT re-usable after this. */ +void BLI_linklist_lockfree_free(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func); + +/* Remove all the elements from the list, keep it usable for further + * inserts. + */ +void BLI_linklist_lockfree_clear(LockfreeLinkList *list, + LockfreeeLinkNodeFreeFP free_func); + + +/* Begin iteration of lock-free linked list, starting with a + * first user=defined node. Will ignore the dummy node. + */ +LockfreeLinkNode *BLI_linklist_lockfree_begin(LockfreeLinkList *list); + + +/* ************************************************************************** */ +/* NOTE: These functions are safe for use from threads. */ + +void BLI_linklist_lockfree_insert(LockfreeLinkList *list, + LockfreeLinkNode *node); + +#ifdef __cplusplus +} +#endif + +#endif /* __BLI_LINKLIST_H__ */ |