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
ring_init(ring)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
ring_append(ring,entry)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
ring_prepend(ring,entry)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
ring_detach(entry)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