src/chain.c

   1 /*
   2  * routines to operate on double linked circular chains
   3  *
   4  * chain_init() - initialise a chain
   5  * chain_add() - add an item after the ref provided
   6  * chain_delete() - delete the item
   7  * chainins() - insert an item before the ref
   8  * chainnext() - get the next item on chain returning NULL if eof
   9  * chainprev() - get the previous item on chain returning NULL if eof
  10  * chain_empty_test() - is the chain empty?
  11  * chain_movebase() - move a chain of things onto (the end of) another base
  12  *
  13  * $Header$
  14  *
  15  * $Log$
  16  * Revision 1.1  2000-03-26 00:03:30  djk
  17  * first cut of client
  18  *
  19  * Revision 1.4  1998/01/02 19:39:58  djk
  20  * made various changes to cope with glibc
  21  * fixed problem with extended status in etsi_router
  22  *
  23  * Revision 1.3  1997/01/02 18:46:46  djk
  24  * Added conv.c from ETSI router
  25  * Changed qerror.c to use syslog rather than qerror.log
  26  * removed all the map27 stuff into a separate directory
  27  * added dump.c (a debugging tool for dumping frames of data)
  28  *
  29  * Revision 1.1  1996/08/08 11:33:44  djk
  30  * Initial revision
  31  *
  32  * Revision 1.2  1995/04/21  16:02:51  djk
  33  * remove rcs id
  34  *
  35  * Revision 1.1  1995/03/04  11:46:26  djk
  36  * Initial revision
  37  *
  38  * Revision 1.2  1995/01/24  15:09:39  djk
  39  * Changed Indent to Id in rcsid
  40  *
  41  * Revision 1.1  1995/01/24  15:06:28  djk
  42  * Initial revision
  43  *
  44  * Revision 1.3  91/03/08  13:21:56  dlp
  45  * changed the chain broken checks to dlpabort for dlperror
  46  *
  47  * Revision 1.2  90/09/15  22:37:39  dlp
  48  * checked in with -k by dirk at 91.02.20.15.53.51.
  49  *
  50  * Revision 1.2  90/09/15  22:37:39  dlp
  51  * *** empty log message ***
  52  *
  53  * Revision 1.1  90/09/15  22:18:23  dlp
  54  * Initial revision
  55  *
  56  */
  57
  58 #include <stdlib.h>
  59
  60 /* chain definitions */
  61 typedef struct _reft {
  62         struct _reft *next, *prev;
  63 } reft;
  64
  65 static char erm[] = "chain broken in %s";
  66 #define check(p, ss) if (p == (struct _reft *) 0 || p->prev->next != p || p->next->prev != p) die(erm, ss);
  67
  68 /*
  69  * chain_init()
  70  */
  71
  72 void chain_init(p)
  73 struct _reft *p;
  74 {
  75         p->next = p->prev = p;
  76 }
  77
  78 /*
  79  * chain_insert() - insert an item before the ref provided
  80  */
  81
  82 void chain_insert(p, q)
  83 struct _reft *p, *q;
  84 {
  85         check(p, "ins");
  86         q->prev = p->prev;
  87         q->next = p;
  88         p->prev->next = q;
  89         p->prev = q;
  90 }
  91 /*
  92  * chain_movebase() - insert an chain of items from one base to another
  93  */
  94
  95 void chain_movebase(p, q)
  96 struct _reft *p, *q;
  97 {
  98         check(p, "movebase");
  99         q->prev->prev = p->prev;
 100         q->next->next = p;
 101         p->prev->next = q->next;
 102         p->prev = q->prev;
 103         q->next = q->prev = q;
 104 }
 105
 106 /*
 107  * chain_add() - add an item after the ref
 108  */
 109
 110 void chain_add(p, q)
 111 struct _reft *p, *q;
 112 {
 113         check(p, "add");
 114         p = p->next;
 115         chain_insert(p, q);
 116 }
 117
 118 /*
 119  * chain_delete() - delete an item in a chain
 120  */
 121
 122 struct _reft *chain_delete(p)
 123 struct _reft *p;
 124 {
 125         check(p, "del");
 126         p->prev->next = p->next;
 127         p->next->prev = p->prev;
 128         return p->prev;
 129 }
 130
 131 /*
 132  * chain_empty_test() - test to see if the chain is empty
 133  */
 134
 135 int chain_empty_test(base)
 136 struct _reft *base;
 137 {
 138         check(base, "chain_empty_test")
 139                 return base->next == base;
 140 }
 141
 142 /*
 143  * chainnext() - get next item in chain
 144  */
 145
 146 struct _reft *chain_get_next(base, p)
 147 struct _reft *base, *p;
 148 {
 149
 150         check(base, "next base");
 151
 152         if (!p)
 153                 return (chain_empty_test(base)) ? 0 : base->next;
 154
 155         check(p, "next last ref");
 156         if (p->next != base)
 157                 return p->next;
 158         else
 159                 return (struct _reft *) 0;
 160 }
 161
 162 /*
 163  * chainprev() - get previous item in chain
 164  */
 165
 166 struct _reft *chain_get_prev(base, p)
 167 struct _reft *base, *p;
 168 {
 169         check(base, "prev base");
 170         if (!p)
 171                 return (chain_empty_test(base)) ? 0 : base->prev;
 172
 173         check(p, "prev last ref");
 174         if (p->prev != base)
 175                 return p->prev;
 176         else
 177                 return (struct _reft *) 0;
 178 }
 179
 180 /*
 181  * rechain() - re-chain an item at this point (usually after the chain base)
 182  */
 183
 184 void chain_rechain(base, p)
 185 struct _reft *base, *p;
 186 {
 187         check(base, "rechain base");
 188         check(p, "rechain last ref");
 189         chain_delete(p);
 190         chain_add(base, p);
 191 }
 192
 193 /*
 194  * emptychain() - remove all the elements in a chain, this frees all elements
 195  *                in a chain leaving just the base.
 196  */
 197
 198 void chain_flush(base)
 199 struct _reft *base;
 200 {
 201         struct _reft *p;
 202
 203         while (!chain_empty_test(base)) {
 204                 p = base->next;
 205                 chain_delete(p);
 206                 free(p);
 207         }
 208 }
 209
 210 /*
 211  * newchain() - create a new chain base in the heap
 212  */
 213
 214 reft *chain_new()
 215 {
 216         reft *p = malloc(sizeof(reft));
 217         if (!p)
 218                 die("out of room in chain_new");
 219         chain_init(p);
 220         return p;
 221 }
 222