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

/* 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)		*
 *																			*
 * Copyright 2004 Rob Swindell - http://www.synchro.net/copyright.html		*
 *																			*
 * 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.	*
 ****************************************************************************/

#include <stdlib.h>		/* malloc */
#include <string.h>		/* memset */
#include "link_list.h"

42
#if defined(LINK_LIST_THREADSAFE)
43 44 45 46
	#define MUTEX_INIT(list)	{ if(list->flags&LINK_LIST_MUTEX) pthread_mutex_init(&list->mutex,NULL);	}
	#define MUTEX_DESTROY(list)	{ if(list->flags&LINK_LIST_MUTEX) pthread_mutex_destroy(&list->mutex);		}
	#define MUTEX_LOCK(list)	{ if(list->flags&LINK_LIST_MUTEX) pthread_mutex_lock(&list->mutex);			}
	#define MUTEX_UNLOCK(list)	{ if(list->flags&LINK_LIST_MUTEX) pthread_mutex_unlock(&list->mutex);		}
47 48 49 50 51 52 53 54 55

#else
	#define MUTEX_INIT(list)
	#define MUTEX_DESTROY(list)
	#define MUTEX_LOCK(list)
	#define MUTEX_UNLOCK(list)
#endif

link_list_t* listInit(link_list_t* list, long flags)
56 57 58 59 60 61 62 63 64 65 66
{
	if(flags&LINK_LIST_MALLOC || list==NULL) {
		if((list=(link_list_t*)malloc(sizeof(link_list_t)))==NULL)
			return(NULL);
		flags |= LINK_LIST_MALLOC;
	} 

	memset(list,0,sizeof(link_list_t));

	list->flags = flags;

67 68
	MUTEX_INIT(list);

69 70 71
	return(list);
}

72
BOOL listFreeNodeData(list_node_t* node)
73
{
74
	if(node!=NULL && node->data!=NULL && !(node->flags&LINK_LIST_NODE_LOCKED)) {
75 76
		free(node->data);
		node->data = NULL;
77
		return(TRUE);
78
	}
79
	return(FALSE);
80 81
}

82
long listFreeNodes(link_list_t* list)
83 84 85 86 87 88
{
	list_node_t* node;
	list_node_t* next;

	for(node=list->first; node!=NULL; node=next) {

89 90 91
		if(node->flags&LINK_LIST_NODE_LOCKED)
			break;

92
		if(list->flags&LINK_LIST_ALWAYS_FREE || node->flags&LINK_LIST_MALLOC)
93 94 95 96 97
			listFreeNodeData(node);

		next = node->next;

		free(node);
98 99 100

		if(list->count)
			list->count--;
101 102
	}

103 104 105 106 107
	list->first = node;
	if(!list->count)
		list->last = NULL;

	return(list->count);
108 109
}

110
BOOL listFree(link_list_t* list)
111 112
{
	if(list==NULL)
113
		return(FALSE);
114

115 116
	if(listFreeNodes(list))
		return(FALSE);
117

118 119
	MUTEX_DESTROY(list);

120
	if(list->flags&LINK_LIST_MALLOC)
121
		free(list);
122

123
	return(TRUE);
124 125
}

126 127 128
#if defined(__BORLANDC__)
	#pragma argsused
#endif
129
void listLock(const link_list_t* list)
130 131 132 133
{
	MUTEX_LOCK(list);
}

134 135 136
#if defined(__BORLANDC__)
	#pragma argsused
#endif
137
void listUnlock(const link_list_t* list)
138 139 140 141
{
	MUTEX_UNLOCK(list);
}

142
long listCountNodes(const link_list_t* list)
143
{
rswindell's avatar
rswindell committed
144 145
	long			count=0;
	list_node_t*	node;
146 147

	if(list==NULL)
148
		return(-1);
149 150 151 152

	if(list->count)
		return(list->count);

153 154
	MUTEX_LOCK(list);

155 156 157
	for(node=list->first; node!=NULL; node=node->next)
		count++;

158 159
	MUTEX_UNLOCK(list);

160 161 162
	return(count);
}

163 164 165 166 167 168 169
list_node_t* listFindNode(const link_list_t* list, void* data, size_t length)
{
	list_node_t* node;

	if(list==NULL)
		return(NULL);

170 171
	MUTEX_LOCK(list);

172 173 174 175
	for(node=list->first; node!=NULL; node=node->next)
		if(node->data!=NULL && memcmp(node->data,data,length)==0)
			break;

176 177
	MUTEX_UNLOCK(list);

178 179 180 181 182 183 184
	return(node);
}

str_list_t listStringList(const link_list_t* list)
{
	list_node_t*	node;
	str_list_t		str_list;
rswindell's avatar
rswindell committed
185
	size_t			count=0;
186 187 188 189

	if(list==NULL)
		return(NULL);

190
	if((str_list=strListInit())==NULL)
191 192
		return(NULL);

193 194
	MUTEX_LOCK(list);

195 196
	for(node=list->first; node!=NULL; node=node->next) {
		if(node->data!=NULL)
197
			strListAppend(&str_list, (char*)node->data, count++);
198 199
	}

200 201
	MUTEX_UNLOCK(list);

202 203 204 205 206
	return(str_list);
}

str_list_t listSubStringList(const list_node_t* node, long max)
{
207
	long			count;
208 209 210 211 212
	str_list_t		str_list;

	if(node==NULL)
		return(NULL);

213
	if((str_list=strListInit())==NULL)
214 215
		return(NULL);

216 217
	MUTEX_LOCK(list);

218
	for(count=0; count<max && node!=NULL; node=node->next) {
rswindell's avatar
rswindell committed
219
		if(node->data!=NULL)
220
			strListAppend(&str_list, (char*)node->data, count++);
221 222
	}

223 224
	MUTEX_UNLOCK(list);

225 226 227
	return(str_list);
}

228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
list_node_t* listFirstNode(const link_list_t* list)
{
	if(list==NULL)
		return(NULL);

	return(list->first);
}

list_node_t* listLastNode(const link_list_t* list)
{
	list_node_t* node;
	list_node_t* last=NULL;

	if(list==NULL)
		return(NULL);

	if(list->last!=NULL)
		return(list->last);

247 248
	MUTEX_LOCK(list);

249 250 251
	for(node=list->first; node!=NULL; node=node->next)
		last=node;

252 253
	MUTEX_UNLOCK(list);

254 255 256
	return(last);
}

257 258 259 260 261 262 263 264
long listNodeIndex(const link_list_t* list, list_node_t* find_node)
{
	long			i=0;
	list_node_t*	node;

	if(list==NULL)
		return(-1);

265 266
	MUTEX_LOCK(list);

267 268 269 270
	for(node=list->first; node!=NULL; node=node->next)
		if(node==find_node)
			break;

271 272
	MUTEX_UNLOCK(list);

273 274 275 276 277 278 279 280 281 282 283 284 285 286
	if(node==NULL)
		return(-1);

	return(i);
}

list_node_t* listNodeAt(const link_list_t* list, long index)
{
	long			i=0;
	list_node_t*	node;

	if(list==NULL || index<0)
		return(NULL);

287 288
	MUTEX_LOCK(list);

289 290 291
	for(node=list->first; node!=NULL && i<index; node=node->next)
		i++;

292 293
	MUTEX_UNLOCK(list);

294 295 296
	return(node);
}

297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
list_node_t* listNextNode(const list_node_t* node)
{
	if(node==NULL)
		return(NULL);

	return(node->next);
}

list_node_t* listPrevNode(const list_node_t* node)
{
	if(node==NULL)
		return(NULL);

	return(node->prev);
}

void* listNodeData(const list_node_t* node)
{
	if(node==NULL)
		return(NULL);

	return(node->data);
}

321
BOOL listNodeIsLocked(const list_node_t* node)
322
{
323
	return(node!=NULL && node->flags&LINK_LIST_NODE_LOCKED);
324 325
}

326
BOOL listLockNode(list_node_t* node)
327
{
328 329 330 331 332 333
	if(node==NULL || node->flags&LINK_LIST_NODE_LOCKED)
		return(FALSE);

	node->flags|=LINK_LIST_NODE_LOCKED;

	return(TRUE);
334 335
}

336
BOOL listUnlockNode(list_node_t* node)
337
{
338 339 340 341 342 343
	if(!listNodeIsLocked(node))
		return(FALSE);

	node->flags&=~LINK_LIST_NODE_LOCKED;

	return(TRUE);
344 345
}

346
static list_node_t* list_add_node(link_list_t* list, list_node_t* node, list_node_t* after)
347 348 349 350
{
	if(list==NULL)
		return(NULL);

351 352 353
	MUTEX_LOCK(list);

	node->list = list;
354 355 356 357
	node->prev = after;

	if(after==list->last)					/* append to list */
		list->last = node;
358
	if(after==FIRST_NODE) {					/* insert at beginning of list */
359 360
		if(list->first!=NULL)
			list->first->prev = node;
361
		list->first = node;
362
	} else {
363 364 365 366 367 368 369 370 371
		if(after->next!=NULL) {
			after->next->prev = node;
			node->next = after->next;
		}
		after->next = node;
	}

	list->count++;

372 373
	MUTEX_UNLOCK(list);

374 375 376
	return(node);
}

377 378 379 380
list_node_t* listAddNode(link_list_t* list, void* data, list_node_t* after)
{
	list_node_t* node;

381
	if(list==NULL || data==NULL)
382 383 384 385 386 387 388 389
		return(NULL);

	if((node=(list_node_t*)malloc(sizeof(list_node_t)))==NULL)
		return(NULL);

	return(list_add_node(list,node,after));
}

390
long listAddNodes(link_list_t* list, void** data, list_node_t* after)
391
{
392
	long			i;
393 394 395
	list_node_t*	node=NULL;

	if(data==NULL)
396
		return(-1);
397

398
	for(i=0; data[i]!=NULL ;i++)
399
		if((node=listAddNode(list,data[i],node==NULL ? after:node))==NULL)
400
			return(i);
401

402
	return(i);
403 404
}

405 406 407 408 409 410 411 412 413 414 415 416 417
list_node_t* listAddNodeData(link_list_t* list, const void* data, size_t length, list_node_t* after)
{
	list_node_t*	node;
	void*			buf;

	if((buf=malloc(length))==NULL)
		return(NULL);
	memcpy(buf,data,length);

	if((node=listAddNode(list,buf,after))==NULL) {
		free(buf);
		return(NULL);
	}
418
	node->flags |= LINK_LIST_MALLOC;
419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
	
	return(node);
}

list_node_t* listAddNodeString(link_list_t* list, const char* str, list_node_t* after)
{
	list_node_t*	node;
	char*			buf;
	size_t			length;

	if(str==NULL)
		return(NULL);

	length = strlen(str)+1;

434
	if((buf=(char*)malloc(length))==NULL)
435 436 437 438 439 440 441
		return(NULL);
	memcpy(buf,str,length);

	if((node=listAddNode(list,buf,after))==NULL) {
		free(buf);
		return(NULL);
	}
442 443
	node->flags |= LINK_LIST_MALLOC;

444 445 446
	return(node);
}

447
long listAddStringList(link_list_t* list, str_list_t str_list, list_node_t* after)
448
{
449
	long			i;
450
	list_node_t*	node=NULL;
451

452
	if(str_list==NULL)
453
		return(-1);
454

455
	for(i=0; str_list[i]!=NULL ;i++)
456
		if((node=listAddNodeString(list,str_list[i],node==NULL ? after:node))==NULL)
457
			return(i);
458

459
	return(i);
460 461
}

462
long listAddNodeList(link_list_t* list, const link_list_t* src, list_node_t* after)
463
{
464
	long			count=0;
465 466 467 468
	list_node_t*	node=NULL;
	list_node_t*	src_node;

	if(src==NULL)
469
		return(-1);
470

471
	for(src_node=src->first; src_node!=NULL; src_node=src_node->next, count++) {
472
		if((node=listAddNode(list, src_node->data, node==NULL ? after:node))==NULL)
473
			return(count);
474 475 476
		node->flags = src_node->flags;
	}

477
	return(count);
478 479
}

480
long listMerge(link_list_t* list, const link_list_t* src, list_node_t* after)
481
{
482
	long			count=0;
483 484 485 486
	list_node_t*	node=NULL;
	list_node_t*	src_node;

	if(src==NULL)
487
		return(-1);
488

489
	for(src_node=src->first; src_node!=NULL; src_node=src_node->next, count++)
490
		if((node=list_add_node(list, src_node, node==NULL ? after:node))==NULL)
491
			return(count);
492

493
	return(count);
494 495
}

496 497
link_list_t* listExtract(link_list_t* dest_list, const list_node_t* node, long max)
{
498
	long			count;
499 500
	link_list_t*	list;

501
	if(node==NULL || node->list==NULL)
502 503
		return(NULL);

504
	if((list=listInit(dest_list, node->list->flags))==NULL)
505 506 507 508 509 510 511 512 513 514
		return(NULL);

	for(count=0; count<max && node!=NULL; node=node->next) {
		listAddNode(list, node->data, list->last);
		count++;
	}

	return(list);
}

515 516 517 518
void* listRemoveNode(link_list_t* list, list_node_t* node)
{
	void*	data;

519 520 521
	if(list==NULL)
		return(NULL);

522
	if(node==FIRST_NODE)
523 524
		node=list->first;
	if(node==NULL)
525 526
		return(NULL);

527 528 529
	if(node->flags&LINK_LIST_NODE_LOCKED)
		return(NULL);

530 531
	MUTEX_LOCK(list);

532 533 534 535 536 537 538 539 540
	if(node->prev!=NULL)
		node->prev->next = node->next;
	if(node->next!=NULL)
		node->next->prev = node->prev;
	if(list->first==node)
		list->first = node->next;
	if(list->last==node)
		list->last = node->prev;

541
	if(list->flags&LINK_LIST_ALWAYS_FREE || node->flags&LINK_LIST_MALLOC)
542
		listFreeNodeData(node);
543 544

	data = node->data;
545 546 547 548 549 550

	free(node);

	if(list->count)
		list->count--;

551 552
	MUTEX_UNLOCK(list);

553 554 555
	return(data);
}

556
long listRemoveNodes(link_list_t* list, list_node_t* node, long max)
557
{
558
	long count;
559

560 561 562
	if(list==NULL)
		return(-1);

563 564
	MUTEX_LOCK(list);

565
	if(node==FIRST_NODE)
566 567 568
		node=list->first;

	for(count=0; node!=NULL && count<max; node=node->next, count++)
569 570
		if(listRemoveNode(list, node)==NULL)
			break;
571 572

	MUTEX_UNLOCK(list);
573 574
	
	return(count);
575 576
}

577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606
BOOL listSwapNodes(list_node_t* node1, list_node_t* node2)
{
	list_node_t	tmp;

	if(node1==NULL || node2==NULL || node1==node2)
		return(FALSE);

	if(listNodeIsLocked(node1) || listNodeIsLocked(node2))
		return(FALSE);

	if(node1->list==NULL || node2->list==NULL)
		return(FALSE);

	MUTEX_LOCK(node1->list);
	if(node1->list != node2->list)
		MUTEX_LOCK(node2->list);

	tmp=*node1;
	node1->data=node2->data;
	node1->flags=node2->flags;
	node2->data=tmp.data;
	node2->flags=tmp.flags;

	MUTEX_UNLOCK(node1->list);
	if(node1->list != node2->list)
		MUTEX_UNLOCK(node2->list);

	return(TRUE);
}

607
#if 0
608

609 610 611
#include <stdio.h>	/* printf, sprintf */

int main(int arg, char** argv)
612
{
613 614 615 616 617 618
	int		i;
	char*	p;
	char	str[32];
	link_list_t list;

	listInit(&list,0);
619
	for(i=0; i<100; i++) {
620 621 622 623 624 625 626 627 628
		sprintf(str,"%u",i);
		listPushNodeString(&list,str);
	}

	while((p=listRemoveNode(&list,NULL))!=NULL)
		printf("%d %s\n",listCountNodes(&list),p), free(p);

	gets(str);
	return 0;
629
}
630

631
#endif