Context Navigation

source: libabac/utlist.h @ 5d1c372

abac0-leak

Last change on this file since 5d1c372 was 15200be, checked in by Mike Ryan <mikeryan@…>, 14 years ago
move libabac into its own directory
Property mode set to `100644`
File size: 36.1 KB

Rev	Line
[3d277c0]	1	/*
	2	Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net
	3	All rights reserved.
	4
	5	Redistribution and use in source and binary forms, with or without
	6	modification, are permitted provided that the following conditions are met:
	7
	8	* Redistributions of source code must retain the above copyright
	9	notice, this list of conditions and the following disclaimer.
	10
	11	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
	12	IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
	13	TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
	14	PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
	15	OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	16	EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	17	PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	18	PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
	19	LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
	20	NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
	21	SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	22	*/
	23
	24	#ifndef UTLIST_H
	25	#define UTLIST_H
	26
	27	#define UTLIST_VERSION 1.9.1
	28
	29	/*
	30	* This file contains macros to manipulate singly and doubly-linked lists.
	31	*
	32	* 1. LL_ macros: singly-linked lists.
	33	* 2. DL_ macros: doubly-linked lists.
	34	* 3. CDL_ macros: circular doubly-linked lists.
	35	*
	36	* To use singly-linked lists, your structure must have a "next" pointer.
	37	* To use doubly-linked lists, your structure must "prev" and "next" pointers.
	38	* Either way, the pointer to the head of the list must be initialized to NULL.
	39	*
	40	* ----------------.EXAMPLE -------------------------
	41	* struct item {
	42	* int id;
	43	* struct item prev, next;
	44	* }
	45	*
	46	* struct item *list = NULL:
	47	*
	48	* int main() {
	49	* struct item *item;
	50	* ... allocate and populate item ...
	51	* DL_APPEND(list, item);
	52	* }
	53	* --------------------------------------------------
	54	*
	55	* For doubly-linked lists, the append and delete macros are O(1)
	56	* For singly-linked lists, append and delete are O(n) but prepend is O(1)
	57	* The sort macro is O(n log(n)) for all types of single/double/circular lists.
	58	*/
	59
	60	/* These macros use decltype or the earlier __typeof GNU extension.
	61	As decltype is only available in newer compilers (VS2010 or gcc 4.3+
	62	when compiling c++ code), this code uses whatever method is needed
	63	or, for VS2008 where neither is available, uses casting workarounds. */
	64	#ifdef _MSC_VER /* MS compiler */
	65	#if _MSC_VER >= 1600 && __cplusplus /* VS2010 and newer in C++ mode */
	66	#define LDECLTYPE(x) decltype(x)
	67	#else /* VS2008 or older (or VS2010 in C mode) */
	68	#define NO_DECLTYPE
	69	#define LDECLTYPE(x) char*
	70	#endif
	71	#else /* GNU, Sun and other compilers */
	72	#define LDECLTYPE(x) __typeof(x)
	73	#endif
	74
	75	/* for VS2008 we use some workarounds to get around the lack of decltype,
	76	* namely, we always reassign our tmp variable to the list head if we need
	77	* to dereference its prev/next pointers, and save/restore the real head.*/
	78	#ifdef NO_DECLTYPE
	79	#define _SV(elt,list) _tmp = (char)(list); {char _alias = (char)&(list); _alias = (elt); }
	80	#define _NEXT(elt,list) ((char*)((list)->next))
	81	#define _NEXTASGN(elt,list,to) { char _alias = (char)&((list)->next); _alias=(char)(to); }
	82	#define _PREV(elt,list) ((char*)((list)->prev))
	83	#define _PREVASGN(elt,list,to) { char _alias = (char)&((list)->prev); _alias=(char)(to); }
	84	#define _RS(list) { char _alias = (char)&(list); *_alias=_tmp; }
	85	#define _CASTASGN(a,b) { char _alias = (char)&(a); _alias=(char)(b); }
	86	#else
	87	#define _SV(elt,list)
	88	#define _NEXT(elt,list) ((elt)->next)
	89	#define _NEXTASGN(elt,list,to) ((elt)->next)=(to)
	90	#define _PREV(elt,list) ((elt)->prev)
	91	#define _PREVASGN(elt,list,to) ((elt)->prev)=(to)
	92	#define _RS(list)
	93	#define _CASTASGN(a,b) (a)=(b)
	94	#endif
	95
	96	/******************************************************************************
	97	* The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
	98	* Unwieldy variable names used here to avoid shadowing passed-in variables. *
	99	*****************************************************************************/
	100	#define LL_SORT(list, cmp) \
	101	do { \
	102	LDECLTYPE(list) _ls_p; \
	103	LDECLTYPE(list) _ls_q; \
	104	LDECLTYPE(list) _ls_e; \
	105	LDECLTYPE(list) _ls_tail; \
	106	LDECLTYPE(list) _ls_oldhead; \
	107	LDECLTYPE(list) _tmp; \
	108	int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
	109	if (list) { \
	110	_ls_insize = 1; \
	111	_ls_looping = 1; \
	112	while (_ls_looping) { \
	113	_CASTASGN(_ls_p,list); \
	114	_CASTASGN(_ls_oldhead,list); \
	115	list = NULL; \
	116	_ls_tail = NULL; \
	117	_ls_nmerges = 0; \
	118	while (_ls_p) { \
	119	_ls_nmerges++; \
	120	_ls_q = _ls_p; \
	121	_ls_psize = 0; \
	122	for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
	123	_ls_psize++; \
	124	_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
	125	if (!_ls_q) break; \
	126	} \
	127	_ls_qsize = _ls_insize; \
	128	while (_ls_psize > 0 \|\| (_ls_qsize > 0 && _ls_q)) { \
	129	if (_ls_psize == 0) { \
	130	_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
	131	} else if (_ls_qsize == 0 \|\| !_ls_q) { \
	132	_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
	133	} else if (cmp(_ls_p,_ls_q) <= 0) { \
	134	_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
	135	} else { \
	136	_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
	137	} \
	138	if (_ls_tail) { \
	139	_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
	140	} else { \
	141	_CASTASGN(list,_ls_e); \
	142	} \
	143	_ls_tail = _ls_e; \
	144	} \
	145	_ls_p = _ls_q; \
	146	} \
	147	_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
	148	if (_ls_nmerges <= 1) { \
	149	_ls_looping=0; \
	150	} \
	151	_ls_insize *= 2; \
	152	} \
	153	} else _tmp=NULL; /* quiet gcc unused variable warning */ \
	154	} while (0)
	155
	156	#define DL_SORT(list, cmp) \
	157	do { \
	158	LDECLTYPE(list) _ls_p; \
	159	LDECLTYPE(list) _ls_q; \
	160	LDECLTYPE(list) _ls_e; \
	161	LDECLTYPE(list) _ls_tail; \
	162	LDECLTYPE(list) _ls_oldhead; \
	163	LDECLTYPE(list) _tmp; \
	164	int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
	165	if (list) { \
	166	_ls_insize = 1; \
	167	_ls_looping = 1; \
	168	while (_ls_looping) { \
	169	_CASTASGN(_ls_p,list); \
	170	_CASTASGN(_ls_oldhead,list); \
	171	list = NULL; \
	172	_ls_tail = NULL; \
	173	_ls_nmerges = 0; \
	174	while (_ls_p) { \
	175	_ls_nmerges++; \
	176	_ls_q = _ls_p; \
	177	_ls_psize = 0; \
	178	for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
	179	_ls_psize++; \
	180	_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
	181	if (!_ls_q) break; \
	182	} \
	183	_ls_qsize = _ls_insize; \
	184	while (_ls_psize > 0 \|\| (_ls_qsize > 0 && _ls_q)) { \
	185	if (_ls_psize == 0) { \
	186	_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
	187	} else if (_ls_qsize == 0 \|\| !_ls_q) { \
	188	_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
	189	} else if (cmp(_ls_p,_ls_q) <= 0) { \
	190	_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
	191	} else { \
	192	_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
	193	} \
	194	if (_ls_tail) { \
	195	_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
	196	} else { \
	197	_CASTASGN(list,_ls_e); \
	198	} \
	199	_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
	200	_ls_tail = _ls_e; \
	201	} \
	202	_ls_p = _ls_q; \
	203	} \
	204	_CASTASGN(list->prev, _ls_tail); \
	205	_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
	206	if (_ls_nmerges <= 1) { \
	207	_ls_looping=0; \
	208	} \
	209	_ls_insize *= 2; \
	210	} \
	211	} else _tmp=NULL; /* quiet gcc unused variable warning */ \
	212	} while (0)
	213
	214	#define CDL_SORT(list, cmp) \
	215	do { \
	216	LDECLTYPE(list) _ls_p; \
	217	LDECLTYPE(list) _ls_q; \
	218	LDECLTYPE(list) _ls_e; \
	219	LDECLTYPE(list) _ls_tail; \
	220	LDECLTYPE(list) _ls_oldhead; \
	221	LDECLTYPE(list) _tmp; \
	222	LDECLTYPE(list) _tmp2; \
	223	int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
	224	if (list) { \
	225	_ls_insize = 1; \
	226	_ls_looping = 1; \
	227	while (_ls_looping) { \
	228	_CASTASGN(_ls_p,list); \
	229	_CASTASGN(_ls_oldhead,list); \
	230	list = NULL; \
	231	_ls_tail = NULL; \
	232	_ls_nmerges = 0; \
	233	while (_ls_p) { \
	234	_ls_nmerges++; \
	235	_ls_q = _ls_p; \
	236	_ls_psize = 0; \
	237	for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
	238	_ls_psize++; \
	239	_SV(_ls_q,list); \
	240	if (_NEXT(_ls_q,list) == _ls_oldhead) { \
	241	_ls_q = NULL; \
	242	} else { \
	243	_ls_q = _NEXT(_ls_q,list); \
	244	} \
	245	_RS(list); \
	246	if (!_ls_q) break; \
	247	} \
	248	_ls_qsize = _ls_insize; \
	249	while (_ls_psize > 0 \|\| (_ls_qsize > 0 && _ls_q)) { \
	250	if (_ls_psize == 0) { \
	251	_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
	252	if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
	253	} else if (_ls_qsize == 0 \|\| !_ls_q) { \
	254	_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
	255	if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
	256	} else if (cmp(_ls_p,_ls_q) <= 0) { \
	257	_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
	258	if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
	259	} else { \
	260	_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
	261	if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
	262	} \
	263	if (_ls_tail) { \
	264	_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
	265	} else { \
	266	_CASTASGN(list,_ls_e); \
	267	} \
	268	_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
	269	_ls_tail = _ls_e; \
	270	} \
	271	_ls_p = _ls_q; \
	272	} \
	273	_CASTASGN(list->prev,_ls_tail); \
	274	_CASTASGN(_tmp2,list); \
	275	_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \
	276	if (_ls_nmerges <= 1) { \
	277	_ls_looping=0; \
	278	} \
	279	_ls_insize *= 2; \
	280	} \
	281	} else _tmp=NULL; /* quiet gcc unused variable warning */ \
	282	} while (0)
	283
	284	/******************************************************************************
	285	* singly linked list macros (non-circular) *
	286	*****************************************************************************/
	287	#define LL_PREPEND(head,add) \
	288	do { \
	289	(add)->next = head; \
	290	head = add; \
	291	} while (0)
	292
	293	#define LL_APPEND(head,add) \
	294	do { \
	295	LDECLTYPE(head) _tmp; \
	296	(add)->next=NULL; \
	297	if (head) { \
	298	_tmp = head; \
	299	while (_tmp->next) { _tmp = _tmp->next; } \
	300	_tmp->next=(add); \
	301	} else { \
	302	(head)=(add); \
	303	} \
	304	} while (0)
	305
	306	#define LL_DELETE(head,del) \
	307	do { \
	308	LDECLTYPE(head) _tmp; \
	309	if ((head) == (del)) { \
	310	(head)=(head)->next; \
	311	} else { \
	312	_tmp = head; \
	313	while (_tmp->next && (_tmp->next != (del))) { \
	314	_tmp = _tmp->next; \
	315	} \
	316	if (_tmp->next) { \
	317	_tmp->next = ((del)->next); \
	318	} \
	319	} \
	320	} while (0)
	321
	322	/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
	323	#define LL_APPEND_VS2008(head,add) \
	324	do { \
	325	if (head) { \
	326	(add)->next = head; /* use add->next as a temp variable */ \
	327	while ((add)->next->next) { (add)->next = (add)->next->next; } \
	328	(add)->next->next=(add); \
	329	} else { \
	330	(head)=(add); \
	331	} \
	332	(add)->next=NULL; \
	333	} while (0)
	334
	335	#define LL_DELETE_VS2008(head,del) \
	336	do { \
	337	if ((head) == (del)) { \
	338	(head)=(head)->next; \
	339	} else { \
	340	char _tmp = (char)(head); \
	341	while (head->next && (head->next != (del))) { \
	342	head = head->next; \
	343	} \
	344	if (head->next) { \
	345	head->next = ((del)->next); \
	346	} \
	347	{ \
	348	char _head_alias = (char)&(head); \
	349	*_head_alias = _tmp; \
	350	} \
	351	} \
	352	} while (0)
	353	#ifdef NO_DECLTYPE
	354	#undef LL_APPEND
	355	#define LL_APPEND LL_APPEND_VS2008
	356	#undef LL_DELETE
	357	#define LL_DELETE LL_DELETE_VS2008
	358	#endif
	359	/* end VS2008 replacements */
	360
	361	#define LL_FOREACH(head,el) \
	362	for(el=head;el;el=el->next)
	363
	364	#define LL_FOREACH_SAFE(head,el,tmp) \
	365	for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
	366
	367	#define LL_SEARCH_SCALAR(head,out,field,val) \
	368	do { \
	369	LL_FOREACH(head,out) { \
	370	if ((out)->field == (val)) break; \
	371	} \
	372	} while(0)
	373
	374	#define LL_SEARCH(head,out,elt,cmp) \
	375	do { \
	376	LL_FOREACH(head,out) { \
	377	if ((cmp(out,elt))==0) break; \
	378	} \
	379	} while(0)
	380
	381	/******************************************************************************
	382	* doubly linked list macros (non-circular) *
	383	*****************************************************************************/
	384	#define DL_PREPEND(head,add) \
	385	do { \
	386	(add)->next = head; \
	387	if (head) { \
	388	(add)->prev = (head)->prev; \
	389	(head)->prev = (add); \
	390	} else { \
	391	(add)->prev = (add); \
	392	} \
	393	(head) = (add); \
	394	} while (0)
	395
	396	#define DL_APPEND(head,add) \
	397	do { \
	398	if (head) { \
	399	(add)->prev = (head)->prev; \
	400	(head)->prev->next = (add); \
	401	(head)->prev = (add); \
	402	(add)->next = NULL; \
	403	} else { \
	404	(head)=(add); \
	405	(head)->prev = (head); \
	406	(head)->next = NULL; \
	407	} \
	408	} while (0);
	409
	410	#define DL_DELETE(head,del) \
	411	do { \
	412	if ((del)->prev == (del)) { \
	413	(head)=NULL; \
	414	} else if ((del)==(head)) { \
	415	(del)->next->prev = (del)->prev; \
	416	(head) = (del)->next; \
	417	} else { \
	418	(del)->prev->next = (del)->next; \
	419	if ((del)->next) { \
	420	(del)->next->prev = (del)->prev; \
	421	} else { \
	422	(head)->prev = (del)->prev; \
	423	} \
	424	} \
	425	} while (0);
	426
	427
	428	#define DL_FOREACH(head,el) \
	429	for(el=head;el;el=el->next)
	430
	431	/* this version is safe for deleting the elements during iteration */
	432	#define DL_FOREACH_SAFE(head,el,tmp) \
	433	for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
	434
	435	/* these are identical to their singly-linked list counterparts */
	436	#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
	437	#define DL_SEARCH LL_SEARCH
	438
	439	/******************************************************************************
	440	* circular doubly linked list macros *
	441	*****************************************************************************/
	442	#define CDL_PREPEND(head,add) \
	443	do { \
	444	if (head) { \
	445	(add)->prev = (head)->prev; \
	446	(add)->next = (head); \
	447	(head)->prev = (add); \
	448	(add)->prev->next = (add); \
	449	} else { \
	450	(add)->prev = (add); \
	451	(add)->next = (add); \
	452	} \
	453	(head)=(add); \
	454	} while (0)
	455
	456	#define CDL_DELETE(head,del) \
	457	do { \
	458	if ( ((head)==(del)) && ((head)->next == (head))) { \
	459	(head) = 0L; \
	460	} else { \
	461	(del)->next->prev = (del)->prev; \
	462	(del)->prev->next = (del)->next; \
	463	if ((del) == (head)) (head)=(del)->next; \
	464	} \
	465	} while (0);
	466
	467	#define CDL_FOREACH(head,el) \
	468	for(el=head;el;el=(el->next==head ? 0L : el->next))
	469
	470	#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
	471	for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
	472	(el) && ((tmp2)=(el)->next, 1); \
	473	((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
	474
	475	#define CDL_SEARCH_SCALAR(head,out,field,val) \
	476	do { \
	477	CDL_FOREACH(head,out) { \
	478	if ((out)->field == (val)) break; \
	479	} \
	480	} while(0)
	481
	482	#define CDL_SEARCH(head,out,elt,cmp) \
	483	do { \
	484	CDL_FOREACH(head,out) { \
	485	if ((cmp(out,elt))==0) break; \
	486	} \
	487	} while(0)
	488
	489	#endif /* UTLIST_H */
	490

Note: See TracBrowser for help on using the repository browser.

Download in other formats: