dapl_llist.c revision 9517:b4839b0aa7a4 
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 */
63void
64dapl_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 */
74void
75dapl_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 */
88DAT_BOOLEAN
89dapl_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 */
99void
100dapl_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 */
128void
129dapl_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 */
157void
158dapl_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 */
188void *
189dapl_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 */
215void *
216dapl_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 */
242void *
243dapl_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
295void *
296dapl_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
313void *
314dapl_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 */
336void
337dapl_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