1 /*        $NetBSD: ring.c,v 1.2 2025/02/25 19:15:52 christos 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 * ring)81 void    ring_init(RING *ring)
82 {
83     ring->pred = ring->succ = ring;
84 }
85 
86 /* ring_append - insert entry after ring head */
87 
ring_append(RING * ring,RING * entry)88 void    ring_append(RING *ring, RING *entry)
89 {
90     entry->succ = ring->succ;
91     entry->pred = ring;
92     ring->succ->pred = entry;
93     ring->succ = entry;
94 }
95 
96 /* ring_prepend - insert new entry before ring head */
97 
ring_prepend(RING * ring,RING * entry)98 void    ring_prepend(RING *ring, RING *entry)
99 {
100     entry->pred = ring->pred;
101     entry->succ = ring;
102     ring->pred->succ = entry;
103     ring->pred = entry;
104 }
105 
106 /* ring_detach - remove entry from ring */
107 
ring_detach(RING * entry)108 void    ring_detach(RING *entry)
109 {
110     RING   *succ = entry->succ;
111     RING   *pred = entry->pred;
112 
113     pred->succ = succ;
114     succ->pred = pred;
115 
116     entry->succ = entry->pred = 0;
117 }
118