Home | History | Annotate | Line # | Download | only in util 
      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 
     81 void    ring_init(RING *ring)
     82 {
     83     ring->pred = ring->succ = ring;
     84 }
     85 
     86 /* ring_append - insert entry after ring head */
     87 
     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 
     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 
    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