xref: /titanic_51/usr/src/lib/udapl/udapl_tavor/common/dapl_llist.c (revision 9e39c5ba00a55fa05777cc94b148296af305e135) 
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright (c) 2002-2003, Network Appliance, Inc. All rights reserved.
24  */
25 
26 /*
27  * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
28  * Use is subject to license terms.
29  */
30 
31 /*
32  *
33  * MODULE: dapl_llist.c
34  *
35  * PURPOSE: Manage doubly linked lists within the DAPL Reference Implementation
36  *
37  *	A link list head points to the first member of a linked list, but
38  *	is itself not a member of the list.
39  *
40  *          +---------------------------------------------+
41  *          |      entry         entry         entry      |
42  *  HEAD -> |    +-------+     +-------+     +-------+    |
43  *          +--> | flink | --> | flink | --> | flink | >--+
44  *	         | data  |     | data  |     | data  |
45  *	    +--< | blink | <-- | blink | <-- | blink | <--|
46  *          |    +-------+     +-------+     +-------+    |
47  *          |                                             |
48  *          +---------------------------------------------+
49  *
50  * Note:  Each of the remove functions takes an assertion failure if
51  *        an element cannot be removed from the list.
52  *
53  * $Id: dapl_llist.c,v 1.9 2003/06/13 12:21:11 sjs2 Exp $
54  */
55 
56 #include "dapl.h"
57 
58 /*
59  * dapl_llist_init_head()
60  *
61  * Purpose: initialize a linked list head
62  */
63 void
64 dapl_llist_init_head(DAPL_LLIST_HEAD *head)
65 {
66 	*head = NULL;
67 }
68 
69 /*
70  * dapl_llist_init_entry()
71  *
72  * Purpose: initialize a linked list entry
73  */
74 void
75 dapl_llist_init_entry(DAPL_LLIST_ENTRY *entry)
76 {
77 	entry->blink = NULL;
78 	entry->flink = NULL;
79 	entry->data = 0;
80 	entry->list_head = NULL;
81 }
82 
83 /*
84  * dapl_llist_is_empty()
85  *
86  * Purpose: returns TRUE if the linked list is empty
87  */
88 DAT_BOOLEAN
89 dapl_llist_is_empty(DAPL_LLIST_HEAD *head)
90 {
91 	return (*head == NULL);
92 }
93 
94 /*
95  * dapl_llist_add_head()
96  *
97  * Purpose: Add an entry to the head of a linked list
98  */
99 void
100 dapl_llist_add_head(DAPL_LLIST_HEAD *head,
101 		DAPL_LLIST_ENTRY *entry,
102 		void *data)
103 {
104 	DAPL_LLIST_ENTRY *first;
105 
106 	/* deal with empty list */
107 	if (dapl_llist_is_empty(head)) {
108 		entry->flink = entry;
109 		entry->blink = entry;
110 	} else {
111 		first = *head;
112 		entry->flink = first;
113 		entry->blink = first->blink;
114 		first->blink->flink = entry;
115 		first->blink = entry;
116 	}
117 
118 	*head		= entry;
119 	entry->data	= data;
120 	entry->list_head = head;
121 }
122 
123 /*
124  * dapl_llist_add_tail()
125  *
126  * Purpose: Add an entry to the tail of a linked list
127  */
128 void
129 dapl_llist_add_tail(DAPL_LLIST_HEAD *head,
130 	DAPL_LLIST_ENTRY *entry,
131 	void *data)
132 {
133 	DAPL_LLIST_ENTRY *last;
134 
135 	/* deal with empty list */
136 	if (dapl_llist_is_empty(head)) {
137 		*head = entry;
138 		entry->flink = entry;
139 		entry->blink = entry;
140 	} else {
141 		last = (*head)->blink;
142 		entry->flink = last->flink;
143 		entry->blink = last;
144 		last->flink->blink = entry;
145 		last->flink = entry;
146 	}
147 	entry->data = data;
148 	entry->list_head = head;
149 }
150 
151 
152 /*
153  * dapl_llist_add_entry()
154  *
155  * Purpose: Add an entry before an element in the list
156  */
157 void
158 dapl_llist_add_entry(DAPL_LLIST_HEAD * head,
159 		DAPL_LLIST_ENTRY * entry,
160 		DAPL_LLIST_ENTRY * new_entry,
161 		void * data)
162 {
163 	DAPL_LLIST_ENTRY *last;
164 
165 	/* deal with empty list */
166 	if (dapl_llist_is_empty(head)) {
167 		*head = entry;
168 		entry->flink = entry;
169 		entry->blink = entry;
170 	} else {
171 		last = entry->blink;
172 		entry->blink = new_entry;
173 		last->flink  = new_entry;
174 
175 		new_entry->flink = entry;
176 		new_entry->blink = last;
177 
178 	}
179 	new_entry->data = data;
180 	new_entry->list_head = head;
181 }
182 
183 /*
184  * dapl_llist_remove_head()
185  *
186  * Purpose: Remove the first entry of a linked list
187  */
188 void *
189 dapl_llist_remove_head(DAPL_LLIST_HEAD *head)
190 {
191 	DAPL_LLIST_ENTRY *first;
192 
193 	dapl_os_assert(!dapl_llist_is_empty(head));
194 	first = *head;
195 	*head = first->flink;
196 
197 	first->flink->blink = first->blink;
198 	first->blink->flink = first->flink;
199 
200 	if (first->flink == first) {
201 		*head = NULL;
202 	}
203 	/* clean up the links for good measure */
204 	first->flink = NULL;
205 	first->blink = NULL;
206 	first->list_head = NULL;
207 	return (first->data);
208 }
209 
210 /*
211  * dapl_llist_remove_tail()
212  *
213  * Purpose: Remove the last entry of a linked list
214  */
215 void *
216 dapl_llist_remove_tail(DAPL_LLIST_HEAD *head)
217 {
218 	DAPL_LLIST_ENTRY *last;
219 
220 	dapl_os_assert(!dapl_llist_is_empty(head));
221 	last = (*head)->blink;
222 
223 	last->blink->flink = last->flink;
224 	last->flink->blink = last->blink;
225 
226 	if (last->flink == last) {
227 		*head = NULL;
228 	}
229 	/* clean up the links for good measure */
230 	last->flink = NULL;
231 	last->blink = NULL;
232 	last->list_head = NULL;
233 
234 	return (last->data);
235 }
236 
237 /*
238  * dapl_llist_remove_entry()
239  *
240  * Purpose: Remove the specified entry from a linked list
241  */
242 void *
243 dapl_llist_remove_entry(DAPL_LLIST_HEAD *head, DAPL_LLIST_ENTRY *entry)
244 {
245 	DAPL_LLIST_ENTRY *first;
246 
247 	dapl_os_assert(!dapl_llist_is_empty(head));
248 	first = *head;
249 
250 	/* if it's the first entry, pull it off */
251 	if (first == entry) {
252 		(*head) = first->flink;
253 		/* if it was the only entry, kill the list */
254 		if (first->flink == first) {
255 			(*head) = NULL;
256 		}
257 	}
258 #ifdef VERIFY_LINKED_LIST
259 	else {
260 		DAPL_LLIST_ENTRY *try_entry;
261 
262 		try_entry = first->flink;
263 		for (;;) {
264 			if (try_entry == first) {
265 				/*
266 				 * not finding the element on the list
267 				 * is a BAD thing
268 				 */
269 				dapl_os_assert(0);
270 				break;
271 			}
272 			if (try_entry == entry) {
273 				break;
274 			}
275 			try_entry = try_entry->flink;
276 		}
277 	}
278 #endif /* VERIFY_LINKED_LIST */
279 
280 	dapl_os_assert(entry->list_head == head);
281 	entry->list_head = NULL;
282 
283 	entry->flink->blink = entry->blink;
284 	entry->blink->flink = entry->flink;
285 	entry->flink = NULL;
286 	entry->blink = NULL;
287 
288 	return (entry->data);
289 }
290 
291 /*
292  * dapl_llist_peek_head
293  */
294 
295 void *
296 dapl_llist_peek_head(DAPL_LLIST_HEAD *head)
297 {
298 	DAPL_LLIST_ENTRY *first;
299 
300 	dapl_os_assert(!dapl_llist_is_empty(head));
301 	first = *head;
302 	return (first->data);
303 }
304 
305 
306 /*
307  * dapl_llist_next_entry
308  *
309  * Obtain the next entry in the list, return NULL when we get to the
310  * head
311  */
312 
313 void *
314 dapl_llist_next_entry(IN    DAPL_LLIST_HEAD 	*head,
315     IN    DAPL_LLIST_ENTRY 	*cur_ent)
316 {
317 	DAPL_LLIST_ENTRY *next;
318 
319 	dapl_os_assert(!dapl_llist_is_empty(head));
320 	if (cur_ent == NULL) {
321 		next = *head;
322 	} else {
323 		next = cur_ent->flink;
324 		if (next == *head) {
325 			return (NULL);
326 		}
327 	}
328 	return (next->data);
329 }
330 
331 /*
332  * dapl_llist_debug_print_list()
333  *
334  * Purpose: Prints the linked list for debugging
335  */
336 void
337 dapl_llist_debug_print_list(DAPL_LLIST_HEAD *head)
338 {
339 	DAPL_LLIST_ENTRY * entry;
340 	DAPL_LLIST_ENTRY * first;
341 	first = *head;
342 	if (!first) {
343 		dapl_dbg_log(DAPL_DBG_TYPE_RTN, "EMPTY_LIST\n");
344 		return;
345 	}
346 	dapl_dbg_log(DAPL_DBG_TYPE_RTN, "HEAD %p\n", *head);
347 	dapl_dbg_log(DAPL_DBG_TYPE_RTN, "Entry %p %p %p %p\n",
348 	    first,
349 	    first->flink,
350 	    first->blink,
351 	    first->data);
352 	entry = first->flink;
353 	while (entry != first) {
354 		dapl_dbg_log(DAPL_DBG_TYPE_RTN, "Entry %p %p %p %p\n",
355 		    entry,
356 		    entry->flink,
357 		    entry->blink,
358 		    entry->data);
359 		entry = entry->flink;
360 	}
361 }
362