Synchronet now requires the libarchive development package (e.g. libarchive-dev on Debian-based Linux distros, libarchive.org for more info) to build successfully.

link_list.h 9.51 KB
Newer Older
1 2 3 4 5 6
/* Double-Linked-list library */

/****************************************************************************
 * @format.tab-size 4		(Plain Text/Source Code File Header)			*
 * @format.use-tabs true	(see http://www.synchro.net/ptsc_hdr.html)		*
 *																			*
7
 * Copyright Rob Swindell - http://www.synchro.net/copyright.html			*
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 *																			*
 * This library is free software; you can redistribute it and/or			*
 * modify it under the terms of the GNU Lesser General Public License		*
 * as published by the Free Software Foundation; either version 2			*
 * of the License, or (at your option) any later version.					*
 * See the GNU Lesser General Public License for more details: lgpl.txt or	*
 * http://www.fsf.org/copyleft/lesser.html									*
 *																			*
 * For Synchronet coding style and modification guidelines, see				*
 * http://www.synchro.net/source.html										*
 *																			*
 * Note: If this box doesn't appear square, then you need to fix your tabs.	*
 ****************************************************************************/

#ifndef _LINK_LIST_H
#define _LINK_LIST_H

#include <stddef.h>		/* size_t */
26
#include "wrapdll.h"
27
#include "str_list.h"	/* string list functions and types */
28

29
#if defined(LINK_LIST_THREADSAFE)
30 31
	#include "threadwrap.h"	/* mutexes */
	#include "semwrap.h"	/* semaphores */
32 33
#endif

34 35 36 37
#if defined(__cplusplus)
extern "C" {
#endif

38 39
#define FIRST_NODE				((list_node_t*)NULL)	/* Special value to specify first node in list */
#define LAST_NODE				((list_node_t*)-1)		/* Special value to specify last node in list */
40

41
/* Valid link_list_t.flags and list_node_t.flags bits */
42
#define LINK_LIST_MALLOC		(1<<0)	/* Node data allocated with malloc() */
43 44 45 46
#define LINK_LIST_ALWAYS_FREE	(1<<1)	/* ALWAYS free node data in listFreeNodes() */
#define LINK_LIST_NEVER_FREE	(1<<2)	/* NEVER free node data (careful of memory leaks!) */
#define LINK_LIST_MUTEX			(1<<3)	/* Mutex-protected linked-list */
#define LINK_LIST_SEMAPHORE		(1<<4)	/* Semaphore attached to linked-list */
47
#define LINK_LIST_LOCKED		(1<<5)	/* Node is locked */
48
#define LINK_LIST_ATTACH		(1<<6)	/* Attach during init */
49

50 51 52 53 54 55 56 57
/* in case the default tag type is not sufficient for your needs, you can over-ride */
#if !defined(list_node_tag_t)			
	typedef long list_node_tag_t;
#endif
#if !defined(LIST_NODE_TAG_DEFAULT)
	#define LIST_NODE_TAG_DEFAULT	0
#endif

58
typedef struct list_node {
59 60 61
	void*				data;			/* pointer to some kind of data */
	struct list_node*	next;			/* next node in list (or NULL) */
	struct list_node*	prev;			/* previous node in list (or NULL) */
62
	struct link_list*	list;
63 64
	unsigned long		flags;			/* private use flags (by this library) */
	list_node_tag_t		tag;			/* application use value */
65 66
} list_node_t;

67
typedef struct link_list {
68 69
	list_node_t*		first;			/* first node in list (or NULL) */
	list_node_t*		last;			/* last node in list (or NULL) */
70
	unsigned long		flags;			/* private use flags (by this library) */
71
	long				count;			/* number of nodes in list */
72
	void*				private_data;	/* for use by the application/caller */
73
	long				refs;			/* reference counter (attached clients) */
74
	long				locks;			/* recursive lock counter */
75 76
#if defined(LINK_LIST_THREADSAFE)
	pthread_mutex_t		mutex;
77
	sem_t				sem;
78
#endif
79 80 81
} link_list_t;

/* Initialization, Allocation, and Freeing of Lists and Nodes */
82 83 84 85
DLLEXPORT link_list_t*	listInit(link_list_t* /* NULL to auto-allocate */, long flags);
DLLEXPORT BOOL			listFree(link_list_t*);
DLLEXPORT long			listFreeNodes(link_list_t*);
DLLEXPORT BOOL			listFreeNodeData(list_node_t* node);
86

87
/* Increment/decrement reference counter (and auto-free when zero), returns -1 on error */
88 89
DLLEXPORT long	listAttach(link_list_t*);
DLLEXPORT long	listDetach(link_list_t*);
90

91
#if defined(LINK_LIST_THREADSAFE)
92 93 94 95
DLLEXPORT BOOL	listSemPost(link_list_t*);
DLLEXPORT BOOL	listSemWait(link_list_t*);
DLLEXPORT BOOL	listSemTryWait(link_list_t*);
DLLEXPORT BOOL	listSemTryWaitBlock(link_list_t*, unsigned long timeout);
96
#endif
97

98
/* Lock/unlock linked lists (works best for mutex-protected lists) */
rswindell's avatar
rswindell committed
99
/* Locks are recursive (e.g. must call Unlock for each call to Lock */
100 101 102
DLLEXPORT BOOL	listLock(link_list_t*);
DLLEXPORT BOOL	listUnlock(link_list_t*);
DLLEXPORT BOOL	listIsLocked(const link_list_t*);
103
#define	listForceUnlock(list)	while(listUnlock(list)==TRUE)
104

105
/* Return count or index of nodes, or -1 on error */
106 107
DLLEXPORT long	listCountNodes(link_list_t*);
DLLEXPORT long	listNodeIndex(link_list_t*, list_node_t*);
108

109
/* Get/Set list private data */
110 111
DLLEXPORT void*	listSetPrivateData(link_list_t*, void*);
DLLEXPORT void*	listGetPrivateData(link_list_t*);
112

113
/* Return an allocated string list (which must be freed), array of all strings in linked list */
114
DLLEXPORT str_list_t listStringList(link_list_t*);
115 116

/* Return an allocated string list (which must be freed), subset of strings in linked list */
117
DLLEXPORT str_list_t listSubStringList(const list_node_t*, long max);
118

119
/* Free a string list returned from either of the above functions */
120
DLLEXPORT void*	listFreeStringList(str_list_t);
121

122 123
/* Extract subset (up to max number of nodes) in linked list (src_node) and place into dest_list */
/* dest_list == NULL, then allocate a return a new linked list */
124
DLLEXPORT link_list_t*	listExtract(link_list_t* dest_list, const list_node_t* src_node, long max);
125

126
/* Simple search functions returning found node or NULL on error */
127
DLLEXPORT list_node_t*	listNodeAt(link_list_t*, long index);
128
/* Find a specific node by data or tag */
129
/* Pass length of 0 to search by data pointer rather than by data content comparison (memcmp) */
130
DLLEXPORT list_node_t*	listFindNode(link_list_t*, const void* data, size_t length);
131 132
/* Find a specific node by its tag value */
#define listFindTaggedNode(list, tag)	listFindNode(list, NULL, tag)
133
/* Pass length of 0 to search by data pointer rather than by data content comparison (memcmp) */
134
DLLEXPORT ulong			listCountMatches(link_list_t*, const void* data, size_t length);
135

136
/* Convenience functions */
137 138 139 140 141
DLLEXPORT list_node_t*	listFirstNode(link_list_t*);
DLLEXPORT list_node_t*	listLastNode(link_list_t*);
DLLEXPORT list_node_t*	listNextNode(const list_node_t*);
DLLEXPORT list_node_t*	listPrevNode(const list_node_t*);
DLLEXPORT void*			listNodeData(const list_node_t*);
142

143
/* Primitive node locking (not recursive) */
144 145 146
DLLEXPORT BOOL listLockNode(list_node_t*);
DLLEXPORT BOOL listUnlockNode(list_node_t*);
DLLEXPORT BOOL listNodeIsLocked(const list_node_t*);
147

148
/* Add node to list, returns pointer to new node or NULL on error */
149
DLLEXPORT list_node_t*	listAddNode(link_list_t*, void* data, list_node_tag_t, list_node_t* after /* NULL=insert */);
150

151
/* Add array of node data to list, returns number of nodes added (or negative on error) */
152
/* tag array may be NULL */
153
DLLEXPORT long		listAddNodes(link_list_t*, void** data, list_node_tag_t*, list_node_t* after /* NULL=insert */);
154

155
/* Add node to list, allocating and copying the data for the node */
156
DLLEXPORT list_node_t*	listAddNodeData(link_list_t*, const void* data, size_t length, list_node_tag_t, list_node_t* after);
157

158
/* Add node to list, allocating and copying ASCIIZ string data */
159
DLLEXPORT list_node_t*	listAddNodeString(link_list_t*, const char* str, list_node_tag_t, list_node_t* after);
160 161

/* Add a list of strings to the linked list, allocating and copying each */
162
/* tag array may be NULL */
163
DLLEXPORT long		listAddStringList(link_list_t*, str_list_t, list_node_tag_t*, list_node_t* after);
164

165
/* Add a list of nodes from a source linked list */
166
DLLEXPORT long		listAddNodeList(link_list_t*, const link_list_t* src, list_node_t* after); 
167 168 169

/* Merge a source linked list into the destination linked list */
/* after merging, the nodes in the source linked list should not be modified or freed */
170
DLLEXPORT long		listMerge(link_list_t* dest, const link_list_t* src, list_node_t* after);
171

172
/* Swap the data pointers and flags for 2 nodes (possibly in separate lists) */
173
DLLEXPORT BOOL		listSwapNodes(list_node_t* node1, list_node_t* node2);
174

175
/* Convenience macros for pushing, popping, and inserting nodes */
176 177 178 179 180 181 182 183
#define	listPushNode(list, data)				listAddNode(list, data, LIST_NODE_TAG_DEFAULT, LAST_NODE)
#define listInsertNode(list, data)				listAddNode(list, data, LIST_NODE_TAG_DEFAULT, FIRST_NODE)
#define listPushNodeData(list, data, length)	listAddNodeData(list, data, length, LIST_NODE_TAG_DEFAULT, LAST_NODE)
#define	listInsertNodeData(list, data, length)	listAddNodeData(list, data, length, LIST_NODE_TAG_DEFAULT, FIRST_NODE)
#define	listPushNodeString(list, str)			listAddNodeString(list, str, LIST_NODE_TAG_DEFAULT, LAST_NODE)
#define listInsertNodeString(list, str)			listAddNodeString(list, str, LIST_NODE_TAG_DEFAULT, FIRST_NODE)
#define	listPushStringList(list, str_list)		listAddStringList(list, str_list, NULL, LAST_NODE)
#define listInsertStringList(list, str_list)	listAddStringList(list, str_list, NULL, FIRST_NODE)
184
#define listPopNode(list)						listRemoveNode(list, LAST_NODE, FALSE)
185
#define listShiftNode(list)						listRemoveNode(list, FIRST_NODE, FALSE)
186 187

/* Remove node from list, returning the node's data (if not free'd) */
188 189
DLLEXPORT void*	listRemoveNode(link_list_t*, list_node_t* /* NULL=first */, BOOL free_data);
DLLEXPORT void* listRemoveTaggedNode(link_list_t*, list_node_tag_t, BOOL free_data);
190 191

/* Remove multiple nodes from list, returning the number of nodes removed */
192
DLLEXPORT long	listRemoveNodes(link_list_t*, list_node_t* /* NULL=first */, long count, BOOL free_data);
193

194
/* Reverse the nodes in a list */
195
DLLEXPORT void listReverse(link_list_t*);
196 197

/* Return >= 0 (count of nodes) if list is valid, negative otherwise */
198
DLLEXPORT long listVerify(link_list_t*);
199

200 201 202 203 204
#if defined(__cplusplus)
}
#endif

#endif	/* Don't add anything after this line */