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 10.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
/* link_list.h */

/* Double-Linked-list library */

/* $Id$ */

/****************************************************************************
 * @format.tab-size 4		(Plain Text/Source Code File Header)			*
 * @format.use-tabs true	(see http://www.synchro.net/ptsc_hdr.html)		*
 *																			*
11
 * Copyright 2011 Rob Swindell - http://www.synchro.net/copyright.html		*
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
 *																			*
 * 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									*
 *																			*
 * Anonymous FTP access to the most recent released source is available at	*
 * ftp://vert.synchro.net, ftp://cvs.synchro.net and ftp://ftp.synchro.net	*
 *																			*
 * Anonymous CVS access to the development source and modification history	*
 * is available at cvs.synchro.net:/cvsroot/sbbs, example:					*
 * cvs -d :pserver:anonymous@cvs.synchro.net:/cvsroot/sbbs login			*
 *     (just hit return, no password is necessary)							*
 * cvs -d :pserver:anonymous@cvs.synchro.net:/cvsroot/sbbs checkout src		*
 *																			*
 * For Synchronet coding style and modification guidelines, see				*
 * http://www.synchro.net/source.html										*
 *																			*
 * You are encouraged to submit any modifications (preferably in Unix diff	*
 * format) via e-mail to mods@synchro.net									*
 *																			*
 * 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 */
42
#include "wrapdll.h"
43
#include "str_list.h"	/* string list functions and types */
44

45
#if defined(LINK_LIST_THREADSAFE)
46 47
	#include "threadwrap.h"	/* mutexes */
	#include "semwrap.h"	/* semaphores */
48 49
#endif

50 51 52 53
#if defined(__cplusplus)
extern "C" {
#endif

54 55
#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 */
56

57
/* Valid link_list_t.flags and list_node_t.flags bits */
58
#define LINK_LIST_MALLOC		(1<<0)	/* List/node allocated with malloc() */
59 60 61 62
#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 */
63
#define LINK_LIST_LOCKED		(1<<5)	/* Node is locked */
64
#define LINK_LIST_ATTACH		(1<<6)	/* Attach during init */
65

66 67 68 69 70 71 72 73
/* 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

74
typedef struct list_node {
75 76 77
	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) */
78
	struct link_list*	list;
79 80
	unsigned long		flags;			/* private use flags (by this library) */
	list_node_tag_t		tag;			/* application use value */
81 82
} list_node_t;

83
typedef struct link_list {
84 85
	list_node_t*		first;			/* first node in list (or NULL) */
	list_node_t*		last;			/* last node in list (or NULL) */
86
	unsigned long		flags;			/* private use flags (by this library) */
87
	long				count;			/* number of nodes in list */
88
	void*				private_data;	/* for use by the application/caller */
89
	long				refs;			/* reference counter (attached clients) */
90
	long				locks;			/* recursive lock counter */
91 92
#if defined(LINK_LIST_THREADSAFE)
	pthread_mutex_t		mutex;
93
	sem_t				sem;
94
#endif
95 96 97
} link_list_t;

/* Initialization, Allocation, and Freeing of Lists and Nodes */
98
DLLEXPORT link_list_t*	DLLCALL listInit(link_list_t* /* NULL to auto-allocate */, long flags);
99 100 101
DLLEXPORT BOOL			DLLCALL listFree(link_list_t*);
DLLEXPORT long			DLLCALL listFreeNodes(link_list_t*);
DLLEXPORT BOOL			DLLCALL listFreeNodeData(list_node_t* node);
102

103
/* Increment/decrement reference counter (and auto-free when zero), returns -1 on error */
104 105
DLLEXPORT long	DLLCALL listAttach(link_list_t*);
DLLEXPORT long	DLLCALL listDetach(link_list_t*);
106

107
#if defined(LINK_LIST_THREADSAFE)
108 109 110 111
DLLEXPORT BOOL	DLLCALL	listSemPost(link_list_t*);
DLLEXPORT BOOL	DLLCALL	listSemWait(link_list_t*);
DLLEXPORT BOOL	DLLCALL	listSemTryWait(link_list_t*);
DLLEXPORT BOOL	DLLCALL	listSemTryWaitBlock(link_list_t*, unsigned long timeout);
112
#endif
113

114
/* Lock/unlock linked lists (works best for mutex-protected lists) */
115
/* Locks are recusive (e.g. must call Unlock for each call to Lock */
116 117
DLLEXPORT BOOL	DLLCALL	listLock(link_list_t*);
DLLEXPORT BOOL	DLLCALL	listUnlock(link_list_t*);
118 119
DLLEXPORT BOOL	DLLCALL	listIsLocked(const link_list_t*);
#define	listForceUnlock(list)	while(listUnlock(list)==TRUE)
120

121
/* Return count or index of nodes, or -1 on error */
122 123
DLLEXPORT long	DLLCALL	listCountNodes(const link_list_t*);
DLLEXPORT long	DLLCALL	listNodeIndex(const link_list_t*, list_node_t*);
124

125
/* Get/Set list private data */
126 127
DLLEXPORT void*	DLLCALL	listSetPrivateData(link_list_t*, void*);
DLLEXPORT void*	DLLCALL	listGetPrivateData(link_list_t*);
128

129
/* Return an allocated string list (which must be freed), array of all strings in linked list */
130
DLLEXPORT str_list_t DLLCALL listStringList(const link_list_t*);
131 132

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

135
/* Free a string list returned from either of the above functions */
136
DLLEXPORT void*	DLLCALL listFreeStringList(str_list_t);
137

138 139
/* 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 */
140
DLLEXPORT link_list_t*	DLLCALL	listExtract(link_list_t* dest_list, const list_node_t* src_node, long max);
141

142
/* Simple search functions returning found node or NULL on error */
143
DLLEXPORT list_node_t*	DLLCALL	listNodeAt(const link_list_t*, long index);
144 145
/* Find a specific node by data */
/* Pass length of 0 to search by data pointer rather than by data content comparison (memcmp) */
146
DLLEXPORT list_node_t*	DLLCALL	listFindNode(const link_list_t*, const void* data, size_t length);
147 148
/* Find a specific node by its tag value */
#define listFindTaggedNode(list, tag)	listFindNode(list, NULL, tag)
149

150
/* Convenience functions */
151 152 153 154 155
DLLEXPORT list_node_t*	DLLCALL	listFirstNode(const link_list_t*);
DLLEXPORT list_node_t*	DLLCALL	listLastNode(const link_list_t*);
DLLEXPORT list_node_t*	DLLCALL	listNextNode(const list_node_t*);
DLLEXPORT list_node_t*	DLLCALL	listPrevNode(const list_node_t*);
DLLEXPORT void*			DLLCALL	listNodeData(const list_node_t*);
156

157
/* Primitive node locking (not recursive) */
158 159 160
DLLEXPORT BOOL DLLCALL	listLockNode(list_node_t*);
DLLEXPORT BOOL DLLCALL	listUnlockNode(list_node_t*);
DLLEXPORT BOOL DLLCALL	listNodeIsLocked(const list_node_t*);
161

162
/* Add node to list, returns pointer to new node or NULL on error */
163
DLLEXPORT list_node_t*	DLLCALL	listAddNode(link_list_t*, void* data, list_node_tag_t, list_node_t* after /* NULL=insert */);
164

165
/* Add array of node data to list, returns number of nodes added (or negative on error) */
166 167
/* tag array may be NULL */
DLLEXPORT long		DLLCALL	listAddNodes(link_list_t*, void** data, list_node_tag_t*, list_node_t* after /* NULL=insert */);
168

169
/* Add node to list, allocating and copying the data for the node */
170
DLLEXPORT list_node_t*	DLLCALL	listAddNodeData(link_list_t*, const void* data, size_t length, list_node_tag_t, list_node_t* after);
171

172
/* Add node to list, allocating and copying ASCIIZ string data */
173
DLLEXPORT list_node_t*	DLLCALL listAddNodeString(link_list_t*, const char* str, list_node_tag_t, list_node_t* after);
174 175

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

179
/* Add a list of nodes from a source linked list */
180
DLLEXPORT long		DLLCALL	listAddNodeList(link_list_t*, const link_list_t* src, list_node_t* after); 
181 182 183

/* 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 */
184
DLLEXPORT long		DLLCALL	listMerge(link_list_t* dest, const link_list_t* src, list_node_t* after);
185

186
/* Swap the data pointers and flags for 2 nodes (possibly in separate lists) */
187
DLLEXPORT BOOL		DLLCALL	listSwapNodes(list_node_t* node1, list_node_t* node2);
188

189
/* Convenience macros for pushing, popping, and inserting nodes */
190 191 192 193 194 195 196 197
#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)
198
#define listPopNode(list)						listRemoveNode(list, LAST_NODE, FALSE)
199
#define listShiftNode(list)						listRemoveNode(list, FIRST_NODE, FALSE)
200 201

/* Remove node from list, returning the node's data (if not free'd) */
202
DLLEXPORT void*	DLLCALL	listRemoveNode(link_list_t*, list_node_t* /* NULL=first */, BOOL free_data);
203
DLLEXPORT void* DLLCALL listRemoveTaggedNode(link_list_t*, list_node_tag_t, BOOL free_data);
204 205

/* Remove multiple nodes from list, returning the number of nodes removed */
206
DLLEXPORT long	DLLCALL	listRemoveNodes(link_list_t*, list_node_t* /* NULL=first */, long count, BOOL free_data);
207 208 209 210 211 212

#if defined(__cplusplus)
}
#endif

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