![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to link_list.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Synchronet] / sbbs / src / xpdev|
Return to link_list.c CVS log | Up to [Synchronet] / sbbs / src / xpdev |
1.1 root 1: /* link_list.c */
2:
3: /* Double-Linked-list library */
4:
5: /* $Id: link_list.c,v 1.35 2006/05/29 07:32:43 rswindell Exp $ */
6:
7: /****************************************************************************
8: * @format.tab-size 4 (Plain Text/Source Code File Header) *
9: * @format.use-tabs true (see http://www.synchro.net/ptsc_hdr.html) *
10: * *
11: * Copyright 2006 Rob Swindell - http://www.synchro.net/copyright.html *
12: * *
13: * This library is free software; you can redistribute it and/or *
14: * modify it under the terms of the GNU Lesser General Public License *
15: * as published by the Free Software Foundation; either version 2 *
16: * of the License, or (at your option) any later version. *
17: * See the GNU Lesser General Public License for more details: lgpl.txt or *
18: * http://www.fsf.org/copyleft/lesser.html *
19: * *
20: * Anonymous FTP access to the most recent released source is available at *
21: * ftp://vert.synchro.net, ftp://cvs.synchro.net and ftp://ftp.synchro.net *
22: * *
23: * Anonymous CVS access to the development source and modification history *
24: * is available at cvs.synchro.net:/cvsroot/sbbs, example: *
25: * cvs -d :pserver:[email protected]:/cvsroot/sbbs login *
26: * (just hit return, no password is necessary) *
27: * cvs -d :pserver:[email protected]:/cvsroot/sbbs checkout src *
28: * *
29: * For Synchronet coding style and modification guidelines, see *
30: * http://www.synchro.net/source.html *
31: * *
32: * You are encouraged to submit any modifications (preferably in Unix diff *
33: * format) via e-mail to [email protected] *
34: * *
35: * Note: If this box doesn't appear square, then you need to fix your tabs. *
36: ****************************************************************************/
37:
38: #include <stdlib.h> /* malloc */
39: #include <string.h> /* memset */
40: #include "link_list.h"
41: #include "genwrap.h"
42:
43: #if defined(LINK_LIST_THREADSAFE)
44: #define MUTEX_INIT(list) { if(list->flags&LINK_LIST_MUTEX) pthread_mutex_init((pthread_mutex_t*)&list->mutex,NULL); }
45: #define MUTEX_DESTROY(list) { if(list->flags&LINK_LIST_MUTEX) { while(pthread_mutex_destroy((pthread_mutex_t*)&list->mutex)==EBUSY) SLEEP(1);} }
46: #define MUTEX_LOCK(list) { if(list->flags&LINK_LIST_MUTEX) pthread_mutex_lock((pthread_mutex_t*)&list->mutex); }
47: #define MUTEX_UNLOCK(list) { if(list->flags&LINK_LIST_MUTEX) pthread_mutex_unlock((pthread_mutex_t*)&list->mutex); }
48: #else
49: #define MUTEX_INIT(list)
50: #define MUTEX_DESTROY(list)
51: #define MUTEX_LOCK(list)
52: #define MUTEX_UNLOCK(list)
53: #endif
54:
55: link_list_t* DLLCALL listInit(link_list_t* list, long flags)
56: {
57: if(flags&LINK_LIST_MALLOC || list==NULL) {
58: if((list=(link_list_t*)malloc(sizeof(link_list_t)))==NULL)
59: return(NULL);
60: flags |= LINK_LIST_MALLOC;
61: }
62:
63: memset(list,0,sizeof(link_list_t));
64:
65: list->flags = flags;
66:
67: MUTEX_INIT(list);
68:
69: #if defined(LINK_LIST_THREADSAFE)
70: if(list->flags&LINK_LIST_SEMAPHORE)
71: sem_init(&list->sem,0,0);
72: #endif
73:
74: if(flags&LINK_LIST_ATTACH)
75: listAttach(list);
76:
77: return(list);
78: }
79:
80: BOOL DLLCALL listFreeNodeData(list_node_t* node)
81: {
82: if(node!=NULL && node->data!=NULL && !(node->flags&LINK_LIST_NODE_LOCKED)) {
83: free(node->data);
84: node->data = NULL;
85: return(TRUE);
86: }
87: return(FALSE);
88: }
89:
90: long DLLCALL listFreeNodes(link_list_t* list)
91: {
92: list_node_t* node;
93: list_node_t* next;
94:
95: for(node=list->first; node!=NULL; node=next) {
96:
97: if(node->flags&LINK_LIST_NODE_LOCKED)
98: break;
99:
100: if((list->flags&LINK_LIST_ALWAYS_FREE || node->flags&LINK_LIST_MALLOC)
101: && !(list->flags&LINK_LIST_NEVER_FREE))
102: listFreeNodeData(node);
103:
104: next = node->next;
105:
106: free(node);
107:
108: if(list->count)
109: list->count--;
110: }
111:
112: list->first = node;
113: if(!list->count)
114: list->last = NULL;
115:
116: return(list->count);
117: }
118:
119: BOOL DLLCALL listFree(link_list_t* list)
120: {
121: if(list==NULL)
122: return(FALSE);
123:
124: if(listFreeNodes(list))
125: return(FALSE);
126:
127: MUTEX_DESTROY(list);
128:
129: #if defined(LINK_LIST_THREADSAFE)
130: if(list->flags&LINK_LIST_SEMAPHORE) {
131: while(sem_destroy(&list->sem)==-1 && errno==EBUSY)
132: SLEEP(1);
133: list->sem=NULL;
134: }
135: #endif
136:
137: if(list->flags&LINK_LIST_MALLOC)
138: free(list);
139:
140: return(TRUE);
141: }
142:
143: long DLLCALL listAttach(link_list_t* list)
144: {
145: if(list==NULL)
146: return(-1);
147:
148: MUTEX_LOCK(list);
149: list->refs++;
150: MUTEX_UNLOCK(list);
151:
152: return(list->refs);
153: }
154:
155: long DLLCALL listDettach(link_list_t* list)
156: {
157: int refs;
158:
159: if(list==NULL || list->refs<1)
160: return(-1);
161:
162: MUTEX_LOCK(list);
163: if((refs=--list->refs)==0)
164: listFree(list);
165: else
166: MUTEX_UNLOCK(list);
167:
168: return(refs);
169: }
170:
171: void* DLLCALL listSetPrivateData(link_list_t* list, void* p)
172: {
173: void* old;
174:
175: if(list==NULL)
176: return(NULL);
177:
178: old=list->private_data;
179: list->private_data=p;
180: return(old);
181: }
182:
183: void* DLLCALL listGetPrivateData(link_list_t* list)
184: {
185: if(list==NULL)
186: return(NULL);
187: return(list->private_data);
188: }
189:
190: #if defined(LINK_LIST_THREADSAFE)
191:
192: BOOL DLLCALL listSemPost(link_list_t* list)
193: {
194: if(list==NULL || !(list->flags&LINK_LIST_SEMAPHORE))
195: return(FALSE);
196:
197: return(sem_post(&list->sem)==0);
198: }
199:
200: BOOL DLLCALL listSemWait(link_list_t* list)
201: {
202: if(list==NULL || !(list->flags&LINK_LIST_SEMAPHORE))
203: return(FALSE);
204:
205: return(sem_wait(&list->sem)==0);
206: }
207:
208: BOOL DLLCALL listSemTryWait(link_list_t* list)
209: {
210: if(list==NULL || !(list->flags&LINK_LIST_SEMAPHORE))
211: return(FALSE);
212:
213: return(sem_trywait(&list->sem)==0);
214: }
215:
216: BOOL DLLCALL listSemTryWaitBlock(link_list_t* list, unsigned long timeout)
217: {
218: if(list==NULL || !(list->flags&LINK_LIST_SEMAPHORE))
219: return(FALSE);
220:
221: return(sem_trywait_block(&list->sem,timeout)==0);
222: }
223:
224: #endif
225:
226: #if defined(__BORLANDC__)
227: #pragma argsused
228: #endif
229: void DLLCALL listLock(const link_list_t* list)
230: {
231: MUTEX_LOCK(list);
232: }
233:
234: #if defined(__BORLANDC__)
235: #pragma argsused
236: #endif
237: void DLLCALL listUnlock(const link_list_t* list)
238: {
239: MUTEX_UNLOCK(list);
240: }
241:
242: long DLLCALL listCountNodes(const link_list_t* list)
243: {
244: long count=0;
245: list_node_t* node;
246:
247: if(list==NULL)
248: return(-1);
249:
250: if(list->count)
251: return(list->count);
252:
253: MUTEX_LOCK(list);
254:
255: for(node=list->first; node!=NULL; node=node->next)
256: count++;
257:
258: MUTEX_UNLOCK(list);
259:
260: return(count);
261: }
262:
263: list_node_t* DLLCALL listFindNode(const link_list_t* list, const void* data, size_t length)
264: {
265: list_node_t* node;
266:
267: if(list==NULL)
268: return(NULL);
269:
270: MUTEX_LOCK(list);
271:
272: for(node=list->first; node!=NULL; node=node->next) {
273: if(length==0) {
274: if(node->data==data)
275: break;
276: } else if(node->data!=NULL && memcmp(node->data,data,length)==0)
277: break;
278: }
279:
280: MUTEX_UNLOCK(list);
281:
282: return(node);
283: }
284:
285: str_list_t DLLCALL listStringList(const link_list_t* list)
286: {
287: list_node_t* node;
288: str_list_t str_list;
289: size_t count=0;
290:
291: if(list==NULL)
292: return(NULL);
293:
294: if((str_list=strListInit())==NULL)
295: return(NULL);
296:
297: MUTEX_LOCK(list);
298:
299: for(node=list->first; node!=NULL; node=node->next) {
300: if(node->data!=NULL)
301: strListAppend(&str_list, (char*)node->data, count++);
302: }
303:
304: MUTEX_UNLOCK(list);
305:
306: return(str_list);
307: }
308:
309: str_list_t DLLCALL listSubStringList(const list_node_t* node, long max)
310: {
311: long count;
312: str_list_t str_list;
313:
314: if(node==NULL)
315: return(NULL);
316:
317: if((str_list=strListInit())==NULL)
318: return(NULL);
319:
320: MUTEX_LOCK(node->list);
321:
322: for(count=0; count<max && node!=NULL; node=node->next) {
323: if(node->data!=NULL)
324: strListAppend(&str_list, (char*)node->data, count++);
325: }
326:
327: MUTEX_UNLOCK(node->list);
328:
329: return(str_list);
330: }
331:
332: void* DLLCALL listFreeStringList(str_list_t list)
333: {
334: strListFree(&list);
335: return(list);
336: }
337:
338: list_node_t* DLLCALL listFirstNode(const link_list_t* list)
339: {
340: if(list==NULL)
341: return(NULL);
342:
343: return(list->first);
344: }
345:
346: list_node_t* DLLCALL listLastNode(const link_list_t* list)
347: {
348: list_node_t* node;
349: list_node_t* last=NULL;
350:
351: if(list==NULL)
352: return(NULL);
353:
354: if(list->last!=NULL)
355: return(list->last);
356:
357: MUTEX_LOCK(list);
358:
359: for(node=list->first; node!=NULL; node=node->next)
360: last=node;
361:
362: MUTEX_UNLOCK(list);
363:
364: return(last);
365: }
366:
367: long DLLCALL listNodeIndex(const link_list_t* list, list_node_t* find_node)
368: {
369: long i=0;
370: list_node_t* node;
371:
372: if(list==NULL)
373: return(-1);
374:
375: MUTEX_LOCK(list);
376:
377: for(node=list->first; node!=NULL; node=node->next)
378: if(node==find_node)
379: break;
380:
381: MUTEX_UNLOCK(list);
382:
383: if(node==NULL)
384: return(-1);
385:
386: return(i);
387: }
388:
389: list_node_t* DLLCALL listNodeAt(const link_list_t* list, long index)
390: {
391: long i=0;
392: list_node_t* node;
393:
394: if(list==NULL || index<0)
395: return(NULL);
396:
397: MUTEX_LOCK(list);
398:
399: for(node=list->first; node!=NULL && i<index; node=node->next)
400: i++;
401:
402: MUTEX_UNLOCK(list);
403:
404: return(node);
405: }
406:
407: list_node_t* DLLCALL listNextNode(const list_node_t* node)
408: {
409: if(node==NULL)
410: return(NULL);
411:
412: return(node->next);
413: }
414:
415: list_node_t* DLLCALL listPrevNode(const list_node_t* node)
416: {
417: if(node==NULL)
418: return(NULL);
419:
420: return(node->prev);
421: }
422:
423: void* DLLCALL listNodeData(const list_node_t* node)
424: {
425: if(node==NULL)
426: return(NULL);
427:
428: return(node->data);
429: }
430:
431: BOOL DLLCALL listNodeIsLocked(const list_node_t* node)
432: {
433: return(node!=NULL && node->flags&LINK_LIST_NODE_LOCKED);
434: }
435:
436: BOOL DLLCALL listLockNode(list_node_t* node)
437: {
438: if(node==NULL || node->flags&LINK_LIST_NODE_LOCKED)
439: return(FALSE);
440:
441: node->flags|=LINK_LIST_NODE_LOCKED;
442:
443: return(TRUE);
444: }
445:
446: BOOL DLLCALL listUnlockNode(list_node_t* node)
447: {
448: if(!listNodeIsLocked(node))
449: return(FALSE);
450:
451: node->flags&=~LINK_LIST_NODE_LOCKED;
452:
453: return(TRUE);
454: }
455:
456: static list_node_t* DLLCALL list_add_node(link_list_t* list, list_node_t* node, list_node_t* after)
457: {
458: if(list==NULL)
459: return(NULL);
460:
461: MUTEX_LOCK(list);
462:
463: node->list = list;
464: if(after==LAST_NODE) /* e.g. listPushNode() */
465: after=list->last;
466: node->prev = after;
467:
468: if(after==list->last) /* append to list */
469: list->last = node;
470: if(after==FIRST_NODE) { /* insert at beginning of list */
471: node->next = list->first;
472: if(node->next!=NULL)
473: node->next->prev = node;
474: list->first = node;
475: } else {
476: if(after->next!=NULL) {
477: after->next->prev = node;
478: node->next = after->next;
479: }
480: after->next = node;
481: }
482:
483: list->count++;
484:
485: MUTEX_UNLOCK(list);
486:
487: #if defined(LINK_LIST_THREADSAFE)
488: if(list->flags&LINK_LIST_SEMAPHORE)
489: listSemPost(list);
490: #endif
491:
492: return(node);
493: }
494:
495: list_node_t* DLLCALL listAddNode(link_list_t* list, void* data, list_node_t* after)
496: {
497: list_node_t* node;
498:
499: if(list==NULL || data==NULL)
500: return(NULL);
501:
502: if((node=(list_node_t*)malloc(sizeof(list_node_t)))==NULL)
503: return(NULL);
504:
505: memset(node,0,sizeof(list_node_t));
506: node->data = data;
507:
508: return(list_add_node(list,node,after));
509: }
510:
511: long DLLCALL listAddNodes(link_list_t* list, void** data, list_node_t* after)
512: {
513: long i;
514: list_node_t* node=NULL;
515:
516: if(data==NULL)
517: return(-1);
518:
519: for(i=0; data[i]!=NULL ;i++)
520: if((node=listAddNode(list,data[i],node==NULL ? after:node))==NULL)
521: return(i);
522:
523: return(i);
524: }
525:
526: list_node_t* DLLCALL listAddNodeData(link_list_t* list, const void* data, size_t length, list_node_t* after)
527: {
528: list_node_t* node;
529: void* buf;
530:
531: if((buf=malloc(length))==NULL)
532: return(NULL);
533: memcpy(buf,data,length);
534:
535: if((node=listAddNode(list,buf,after))==NULL) {
536: free(buf);
537: return(NULL);
538: }
539: node->flags |= LINK_LIST_MALLOC;
540:
541: return(node);
542: }
543:
544: list_node_t* DLLCALL listAddNodeString(link_list_t* list, const char* str, list_node_t* after)
545: {
546: list_node_t* node;
547: char* buf;
548:
549: if(str==NULL)
550: return(NULL);
551:
552: if((buf=strdup(str))==NULL)
553: return(NULL);
554:
555: if((node=listAddNode(list,buf,after))==NULL) {
556: free(buf);
557: return(NULL);
558: }
559: node->flags |= LINK_LIST_MALLOC;
560:
561: return(node);
562: }
563:
564: long DLLCALL listAddStringList(link_list_t* list, str_list_t str_list, list_node_t* after)
565: {
566: long i;
567: list_node_t* node=NULL;
568:
569: if(str_list==NULL)
570: return(-1);
571:
572: for(i=0; str_list[i]!=NULL ;i++)
573: if((node=listAddNodeString(list,str_list[i],node==NULL ? after:node))==NULL)
574: return(i);
575:
576: return(i);
577: }
578:
579: long DLLCALL listAddNodeList(link_list_t* list, const link_list_t* src, list_node_t* after)
580: {
581: long count=0;
582: list_node_t* node=NULL;
583: list_node_t* src_node;
584:
585: if(src==NULL)
586: return(-1);
587:
588: for(src_node=src->first; src_node!=NULL; src_node=src_node->next, count++) {
589: if((node=listAddNode(list, src_node->data, node==NULL ? after:node))==NULL)
590: return(count);
591: node->flags = src_node->flags;
592: }
593:
594: return(count);
595: }
596:
597: long DLLCALL listMerge(link_list_t* list, const link_list_t* src, list_node_t* after)
598: {
599: long count=0;
600: list_node_t* node=NULL;
601: list_node_t* src_node;
602:
603: if(src==NULL)
604: return(-1);
605:
606: for(src_node=src->first; src_node!=NULL; src_node=src_node->next, count++)
607: if((node=list_add_node(list, src_node, node==NULL ? after:node))==NULL)
608: return(count);
609:
610: return(count);
611: }
612:
613: link_list_t* DLLCALL listExtract(link_list_t* dest_list, const list_node_t* node, long max)
614: {
615: long count;
616: link_list_t* list;
617:
618: if(node==NULL || node->list==NULL)
619: return(NULL);
620:
621: if((list=listInit(dest_list, node->list->flags))==NULL)
622: return(NULL);
623:
624: for(count=0; count<max && node!=NULL; node=node->next) {
625: listAddNode(list, node->data, list->last);
626: count++;
627: }
628:
629: return(list);
630: }
631:
632: static void* list_remove_node(link_list_t* list, list_node_t* node, BOOL free_data)
633: {
634: void* data;
635:
636: if(node==FIRST_NODE)
637: node=list->first;
638: else if(node==LAST_NODE)
639: node=list->last;
640: if(node==NULL)
641: return(NULL);
642:
643: if(node->flags&LINK_LIST_NODE_LOCKED)
644: return(NULL);
645:
646: if(node->prev!=NULL)
647: node->prev->next = node->next;
648: if(node->next!=NULL)
649: node->next->prev = node->prev;
650: if(list->first==node)
651: list->first = node->next;
652: if(list->last==node)
653: list->last = node->prev;
654:
655: if(free_data)
656: listFreeNodeData(node);
657:
658: data = node->data;
659:
660: free(node);
661:
662: if(list->count)
663: list->count--;
664:
665: return(data);
666: }
667:
668: void* DLLCALL listRemoveNode(link_list_t* list, list_node_t* node, BOOL free_data)
669: {
670: void* data;
671:
672: if(list==NULL)
673: return(NULL);
674:
675: MUTEX_LOCK(list);
676:
677: data = list_remove_node(list, node, free_data);
678:
679: MUTEX_UNLOCK(list);
680:
681: return(data);
682: }
683:
684: long DLLCALL listRemoveNodes(link_list_t* list, list_node_t* node, long max, BOOL free_data)
685: {
686: long count;
687:
688: if(list==NULL)
689: return(-1);
690:
691: MUTEX_LOCK(list);
692:
693: if(node==FIRST_NODE)
694: node=list->first;
695:
696: for(count=0; node!=NULL && count<max; node=node->next, count++)
697: if(listRemoveNode(list, node, free_data)==NULL)
698: break;
699:
700: MUTEX_UNLOCK(list);
701:
702: return(count);
703: }
704:
705: BOOL DLLCALL listSwapNodes(list_node_t* node1, list_node_t* node2)
706: {
707: list_node_t tmp;
708:
709: if(node1==NULL || node2==NULL || node1==node2)
710: return(FALSE);
711:
712: if(listNodeIsLocked(node1) || listNodeIsLocked(node2))
713: return(FALSE);
714:
715: if(node1->list==NULL || node2->list==NULL)
716: return(FALSE);
717:
718: #if defined(LINK_LIST_THREADSAFE)
719: MUTEX_LOCK(node1->list);
720: if(node1->list != node2->list)
721: MUTEX_LOCK(node2->list);
722: #endif
723:
724: tmp=*node1;
725: node1->data=node2->data;
726: node1->flags=node2->flags;
727: node2->data=tmp.data;
728: node2->flags=tmp.flags;
729:
730: #if defined(LINK_LIST_THREADSAFE)
731: MUTEX_UNLOCK(node1->list);
732: if(node1->list != node2->list)
733: MUTEX_UNLOCK(node2->list);
734: #endif
735:
736: return(TRUE);
737: }
738:
739: #if 0
740:
741: #include <stdio.h> /* printf, sprintf */
742:
743: int main(int arg, char** argv)
744: {
745: int i;
746: char* p;
747: char str[32];
748: link_list_t list;
749:
750: listInit(&list,0);
751: for(i=0; i<100; i++) {
752: sprintf(str,"%u",i);
753: listPushNodeString(&list,str);
754: }
755:
756: while((p=listShiftNode(&list))!=NULL)
757: printf("%d %s\n",listCountNodes(&list),p), free(p);
758:
759: /* Yes, this test code leaks heap memory. :-) */
760: gets(str);
761: return 0;
762: }
763:
764: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.