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