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