lists.c

Last change on this file was 1127:1af09cc156d6, checked in by Sebastien Decugis <sdecugis@freediameter.net>, 8 years ago
Updated copyright information
File size: 5.3 KB

Line
1	/*********************************************************************************************************
2	* Software License Agreement (BSD License) *
3	* Author: Sebastien Decugis <sdecugis@freediameter.net> *
4	* *
5	* Copyright (c) 2013, WIDE Project and NICT *
6	* All rights reserved. *
7	* *
8	* Redistribution and use of this software in source and binary forms, with or without modification, are *
9	* permitted provided that the following conditions are met: *
10	* *
11	* * Redistributions of source code must retain the above *
12	* copyright notice, this list of conditions and the *
13	* following disclaimer. *
14	* *
15	* * Redistributions in binary form must reproduce the above *
16	* copyright notice, this list of conditions and the *
17	* following disclaimer in the documentation and/or other *
18	* materials provided with the distribution. *
19	* *
20	* * Neither the name of the WIDE Project or NICT nor the *
21	* names of its contributors may be used to endorse or *
22	* promote products derived from this software without *
23	* specific prior written permission of WIDE Project and *
24	* NICT. *
25	* *
26	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED *
27	* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
28	* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR *
29	* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
30	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS *
31	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR *
32	* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF *
33	* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
34	*********************************************************************************************************/
35
36	#include "fdproto-internal.h"
37
38	/* Initialize a list element */
39	void fd_list_init ( struct fd_list * list, void * obj )
40	{
41	memset(list, 0, sizeof(struct fd_list));
42	list->next = list;
43	list->prev = list;
44	list->head = list;
45	list->o = obj;
46	}
47
48	#define CHECK_SINGLE( li ) { \
49	ASSERT( ((struct fd_list *)(li))->next == (li) ); \
50	ASSERT( ((struct fd_list *)(li))->prev == (li) ); \
51	ASSERT( ((struct fd_list *)(li))->head == (li) ); \
52	}
53
54	/* insert after a reference, checks done */
55	static void list_insert_after( struct fd_list * ref, struct fd_list * item )
56	{
57	item->prev = ref;
58	item->next = ref->next;
59	item->head = ref->head;
60	ref->next->prev = item;
61	ref->next = item;
62	}
63
64	/* insert after a reference */
65	void fd_list_insert_after ( struct fd_list * ref, struct fd_list * item )
66	{
67	ASSERT(item != NULL);
68	ASSERT(ref != NULL);
69	CHECK_SINGLE ( item );
70	ASSERT(ref->head != item);
71	list_insert_after(ref, item);
72	}
73
74	/* Move all elements of list senti at the end of list ref */
75	void fd_list_move_end(struct fd_list * ref, struct fd_list * senti)
76	{
77	struct fd_list * li;
78	ASSERT(ref->head == ref);
79	ASSERT(senti->head == senti);
80
81	if (senti->next == senti)
82	return;
83
84	for (li = senti->next; li != senti; li = li->next)
85	li->head = ref;
86
87	senti->next->prev = ref->prev;
88	ref->prev->next = senti->next;
89	senti->prev->next = ref;
90	ref->prev = senti->prev;
91	senti->prev = senti;
92	senti->next = senti;
93	}
94
95	/* insert before a reference, checks done */
96	static void list_insert_before ( struct fd_list * ref, struct fd_list * item )
97	{
98	item->prev = ref->prev;
99	item->next = ref;
100	item->head = ref->head;
101	ref->prev->next = item;
102	ref->prev = item;
103	}
104
105	/* insert before a reference */
106	void fd_list_insert_before ( struct fd_list * ref, struct fd_list * item )
107	{
108	ASSERT(item != NULL);
109	ASSERT(ref != NULL);
110	CHECK_SINGLE ( item );
111	ASSERT(ref->head != item);
112	list_insert_before(ref, item);
113	}
114
115	/* Insert an item in an ordered list -- ordering function provided. If duplicate object found, it is returned in ref_duplicate */
116	int fd_list_insert_ordered( struct fd_list * head, struct fd_list * item, int (cmp_fct)(void , void ), void * ref_duplicate)
117	{
118	struct fd_list * ptr = head;
119	int cmp;
120
121	/* Some debug sanity checks */
122	ASSERT(head != NULL);
123	ASSERT(item != NULL);
124	ASSERT(cmp_fct != NULL);
125	ASSERT(head->head == head);
126	CHECK_SINGLE ( item );
127
128	/* loop in the list */
129	while (ptr->next != head)
130	{
131	/* Compare the object to insert with the next object in list */
132	cmp = cmp_fct( item->o, ptr->next->o );
133	if (!cmp) {
134	/* An element with the same key already exists */
135	if (ref_duplicate != NULL)
136	*ref_duplicate = ptr->next->o;
137	return EEXIST;
138	}
139
140	if (cmp < 0)
141	break; /* We must insert the element here */
142
143	ptr = ptr->next;
144	}
145
146	/* Now insert the element between ptr and ptr->next */
147	list_insert_after( ptr, item );
148
149	/* Ok */
150	return 0;
151	}
152
153	/* Unlink an object */
154	void fd_list_unlink ( struct fd_list * item )
155	{
156	ASSERT(item != NULL);
157	if (item->head == item)
158	return;
159	/* unlink */
160	item->next->prev = item->prev;
161	item->prev->next = item->next;
162	/* sanitize */
163	item->next = item;
164	item->prev = item;
165	item->head = item;
166	}
167
168

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

Navigation

source: freeDiameter/libfdproto/lists.c

Download in other formats: