dapl_llist.c revision 9e39c5ba00a55fa05777cc94b148296af305e135
1N/A/*
1N/A * CDDL HEADER START
1N/A *
1N/A * The contents of this file are subject to the terms of the
1N/A * Common Development and Distribution License (the "License").
1N/A * You may not use this file except in compliance with the License.
1N/A *
1N/A * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
1N/A * or http://www.opensolaris.org/os/licensing.
1N/A * See the License for the specific language governing permissions
1N/A * and limitations under the License.
1N/A *
1N/A * When distributing Covered Code, include this CDDL HEADER in each
1N/A * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
1N/A * If applicable, add the following below this CDDL HEADER, with the
1N/A * fields enclosed by brackets "[]" replaced with your own identifying
1N/A * information: Portions Copyright [yyyy] [name of copyright owner]
1N/A *
1N/A * CDDL HEADER END
1N/A */
1N/A
1N/A/*
1N/A * Copyright (c) 2002-2003, Network Appliance, Inc. All rights reserved.
1N/A */
1N/A
1N/A/*
1N/A * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
1N/A * Use is subject to license terms.
1N/A */
1N/A
1N/A/*
1N/A *
1N/A * MODULE: dapl_llist.c
1N/A *
1N/A * PURPOSE: Manage doubly linked lists within the DAPL Reference Implementation
1N/A *
1N/A * A link list head points to the first member of a linked list, but
1N/A * is itself not a member of the list.
1N/A *
1N/A * +---------------------------------------------+
1N/A * | entry entry entry |
1N/A * HEAD -> | +-------+ +-------+ +-------+ |
1N/A * +--> | flink | --> | flink | --> | flink | >--+
1N/A * | data | | data | | data |
1N/A * +--< | blink | <-- | blink | <-- | blink | <--|
1N/A * | +-------+ +-------+ +-------+ |
1N/A * | |
1N/A * +---------------------------------------------+
1N/A *
1N/A * Note: Each of the remove functions takes an assertion failure if
1N/A * an element cannot be removed from the list.
1N/A *
1N/A * $Id: dapl_llist.c,v 1.9 2003/06/13 12:21:11 sjs2 Exp $
1N/A */
1N/A
1N/A#include "dapl.h"
1N/A
1N/A/*
1N/A * dapl_llist_init_head()
1N/A *
1N/A * Purpose: initialize a linked list head
1N/A */
1N/Avoid
1N/Adapl_llist_init_head(DAPL_LLIST_HEAD *head)
1N/A{
1N/A *head = NULL;
1N/A}
1N/A
1N/A/*
1N/A * dapl_llist_init_entry()
1N/A *
1N/A * Purpose: initialize a linked list entry
1N/A */
1N/Avoid
1N/Adapl_llist_init_entry(DAPL_LLIST_ENTRY *entry)
1N/A{
1N/A entry->blink = NULL;
1N/A entry->flink = NULL;
1N/A entry->data = 0;
1N/A entry->list_head = NULL;
1N/A}
1N/A
1N/A/*
1N/A * dapl_llist_is_empty()
1N/A *
1N/A * Purpose: returns TRUE if the linked list is empty
1N/A */
1N/ADAT_BOOLEAN
1N/Adapl_llist_is_empty(DAPL_LLIST_HEAD *head)
1N/A{
1N/A return (*head == NULL);
1N/A}
1N/A
1N/A/*
1N/A * dapl_llist_add_head()
1N/A *
1N/A * Purpose: Add an entry to the head of a linked list
1N/A */
1N/Avoid
1N/Adapl_llist_add_head(DAPL_LLIST_HEAD *head,
1N/A DAPL_LLIST_ENTRY *entry,
1N/A void *data)
1N/A{
1N/A DAPL_LLIST_ENTRY *first;
1N/A
1N/A /* deal with empty list */
1N/A if (dapl_llist_is_empty(head)) {
1N/A entry->flink = entry;
1N/A entry->blink = entry;
1N/A } else {
1N/A first = *head;
1N/A entry->flink = first;
1N/A entry->blink = first->blink;
1N/A first->blink->flink = entry;
1N/A first->blink = entry;
1N/A }
1N/A
1N/A *head = entry;
1N/A entry->data = data;
1N/A entry->list_head = head;
1N/A}
1N/A
1N/A/*
1N/A * dapl_llist_add_tail()
1N/A *
1N/A * Purpose: Add an entry to the tail of a linked list
*/
void
dapl_llist_add_tail(DAPL_LLIST_HEAD *head,
DAPL_LLIST_ENTRY *entry,
void *data)
{
DAPL_LLIST_ENTRY *last;
/* deal with empty list */
if (dapl_llist_is_empty(head)) {
*head = entry;
entry->flink = entry;
entry->blink = entry;
} else {
last = (*head)->blink;
entry->flink = last->flink;
entry->blink = last;
last->flink->blink = entry;
last->flink = entry;
}
entry->data = data;
entry->list_head = head;
}
/*
* dapl_llist_add_entry()
*
* Purpose: Add an entry before an element in the list
*/
void
dapl_llist_add_entry(DAPL_LLIST_HEAD * head,
DAPL_LLIST_ENTRY * entry,
DAPL_LLIST_ENTRY * new_entry,
void * data)
{
DAPL_LLIST_ENTRY *last;
/* deal with empty list */
if (dapl_llist_is_empty(head)) {
*head = entry;
entry->flink = entry;
entry->blink = entry;
} else {
last = entry->blink;
entry->blink = new_entry;
last->flink = new_entry;
new_entry->flink = entry;
new_entry->blink = last;
}
new_entry->data = data;
new_entry->list_head = head;
}
/*
* dapl_llist_remove_head()
*
* Purpose: Remove the first entry of a linked list
*/
void *
dapl_llist_remove_head(DAPL_LLIST_HEAD *head)
{
DAPL_LLIST_ENTRY *first;
dapl_os_assert(!dapl_llist_is_empty(head));
first = *head;
*head = first->flink;
first->flink->blink = first->blink;
first->blink->flink = first->flink;
if (first->flink == first) {
*head = NULL;
}
/* clean up the links for good measure */
first->flink = NULL;
first->blink = NULL;
first->list_head = NULL;
return (first->data);
}
/*
* dapl_llist_remove_tail()
*
* Purpose: Remove the last entry of a linked list
*/
void *
dapl_llist_remove_tail(DAPL_LLIST_HEAD *head)
{
DAPL_LLIST_ENTRY *last;
dapl_os_assert(!dapl_llist_is_empty(head));
last = (*head)->blink;
last->blink->flink = last->flink;
last->flink->blink = last->blink;
if (last->flink == last) {
*head = NULL;
}
/* clean up the links for good measure */
last->flink = NULL;
last->blink = NULL;
last->list_head = NULL;
return (last->data);
}
/*
* dapl_llist_remove_entry()
*
* Purpose: Remove the specified entry from a linked list
*/
void *
dapl_llist_remove_entry(DAPL_LLIST_HEAD *head, DAPL_LLIST_ENTRY *entry)
{
DAPL_LLIST_ENTRY *first;
dapl_os_assert(!dapl_llist_is_empty(head));
first = *head;
/* if it's the first entry, pull it off */
if (first == entry) {
(*head) = first->flink;
/* if it was the only entry, kill the list */
if (first->flink == first) {
(*head) = NULL;
}
}
#ifdef VERIFY_LINKED_LIST
else {
DAPL_LLIST_ENTRY *try_entry;
try_entry = first->flink;
for (;;) {
if (try_entry == first) {
/*
* not finding the element on the list
* is a BAD thing
*/
dapl_os_assert(0);
break;
}
if (try_entry == entry) {
break;
}
try_entry = try_entry->flink;
}
}
#endif /* VERIFY_LINKED_LIST */
dapl_os_assert(entry->list_head == head);
entry->list_head = NULL;
entry->flink->blink = entry->blink;
entry->blink->flink = entry->flink;
entry->flink = NULL;
entry->blink = NULL;
return (entry->data);
}
/*
* dapl_llist_peek_head
*/
void *
dapl_llist_peek_head(DAPL_LLIST_HEAD *head)
{
DAPL_LLIST_ENTRY *first;
dapl_os_assert(!dapl_llist_is_empty(head));
first = *head;
return (first->data);
}
/*
* dapl_llist_next_entry
*
* Obtain the next entry in the list, return NULL when we get to the
* head
*/
void *
dapl_llist_next_entry(IN DAPL_LLIST_HEAD *head,
IN DAPL_LLIST_ENTRY *cur_ent)
{
DAPL_LLIST_ENTRY *next;
dapl_os_assert(!dapl_llist_is_empty(head));
if (cur_ent == NULL) {
next = *head;
} else {
next = cur_ent->flink;
if (next == *head) {
return (NULL);
}
}
return (next->data);
}
/*
* dapl_llist_debug_print_list()
*
* Purpose: Prints the linked list for debugging
*/
void
dapl_llist_debug_print_list(DAPL_LLIST_HEAD *head)
{
DAPL_LLIST_ENTRY * entry;
DAPL_LLIST_ENTRY * first;
first = *head;
if (!first) {
dapl_dbg_log(DAPL_DBG_TYPE_RTN, "EMPTY_LIST\n");
return;
}
dapl_dbg_log(DAPL_DBG_TYPE_RTN, "HEAD %p\n", *head);
dapl_dbg_log(DAPL_DBG_TYPE_RTN, "Entry %p %p %p %p\n",
first,
first->flink,
first->blink,
first->data);
entry = first->flink;
while (entry != first) {
dapl_dbg_log(DAPL_DBG_TYPE_RTN, "Entry %p %p %p %p\n",
entry,
entry->flink,
entry->blink,
entry->data);
entry = entry->flink;
}
}