1 /* $NetBSD: ring.c,v 1.1.1.1 2009/06/23 10:09:00 tron Exp $ */ 2 3 /*++ 4 /* NAME 5 /* ring 3 6 /* SUMMARY 7 /* circular list management 8 /* SYNOPSIS 9 /* #include <ring.h> 10 /* 11 /* void ring_init(list) 12 /* RING *list; 13 /* 14 /* void ring_prepend(list, element) 15 /* RING *list; 16 /* RING *element; 17 /* 18 /* void ring_append(list, element) 19 /* RING *list; 20 /* RING *element; 21 /* 22 /* RING *ring_pred(element) 23 /* RING *element; 24 /* 25 /* RING *ring_succ(element) 26 /* RING *element; 27 /* 28 /* void ring_detach(element) 29 /* RING *element; 30 /* 31 /* RING_FOREACH(RING *element, RING *head) 32 /* DESCRIPTION 33 /* This module manages circular, doubly-linked, lists. It provides 34 /* operations to initialize a list, to add or remove an element, 35 /* and to iterate over a list. Although the documentation appears 36 /* to emphasize the special role of the list head, each operation 37 /* can be applied to each list member. 38 /* 39 /* Examples of applications: any sequence of objects such as queue, 40 /* unordered list, or stack. Typically, an application embeds a RING 41 /* structure into its own data structure, and uses the RING primitives 42 /* to maintain the linkage between application-specific data objects. 43 /* 44 /* ring_init() initializes its argument to a list of just one element. 45 /* 46 /* ring_append() appends the named element to the named list head. 47 /* 48 /* ring_prepend() prepends the named element to the named list head. 49 /* 50 /* ring_succ() returns the list element that follows its argument. 51 /* 52 /* ring_pred() returns the list element that precedes its argument. 53 /* 54 /* ring_detach() disconnects a list element from its neighbors 55 /* and closes the hole. This routine performs no implicit ring_init() 56 /* on the removed element. 57 /* 58 /* RING_FOREACH() is a macro that expands to a for (... ; ... ; ...) 59 /* statement that iterates over each list element in forward order. 60 /* Upon completion, the \fIelement\fR variable is set equal to 61 /* \fIhead\fR. The list head itself is not treated as a list member. 62 /* LICENSE 63 /* .ad 64 /* .fi 65 /* The Secure Mailer license must be distributed with this software. 66 /* AUTHOR(S) 67 /* Wietse Venema 68 /* IBM T.J. Watson Research 69 /* P.O. Box 704 70 /* Yorktown Heights, NY 10598, USA 71 /*--*/ 72 73 /* System libraries. */ 74 75 /* Application-specific. */ 76 77 #include "ring.h" 78 79 /* ring_init - initialize ring head */ 80 81 void ring_init(ring) 82 RING *ring; 83 { 84 ring->pred = ring->succ = ring; 85 } 86 87 /* ring_append - insert entry after ring head */ 88 89 void ring_append(ring, entry) 90 RING *ring; 91 RING *entry; 92 { 93 entry->succ = ring->succ; 94 entry->pred = ring; 95 ring->succ->pred = entry; 96 ring->succ = entry; 97 } 98 99 /* ring_prepend - insert new entry before ring head */ 100 101 void ring_prepend(ring, entry) 102 RING *ring; 103 RING *entry; 104 { 105 entry->pred = ring->pred; 106 entry->succ = ring; 107 ring->pred->succ = entry; 108 ring->pred = entry; 109 } 110 111 /* ring_detach - remove entry from ring */ 112 113 void ring_detach(entry) 114 RING *entry; 115 { 116 RING *succ = entry->succ; 117 RING *pred = entry->pred; 118 119 pred->succ = succ; 120 succ->pred = pred; 121 122 entry->succ = entry->pred = 0; 123 } 124