src/toolbox/chain.c

   1 /* toolbox/chain.c - management of doubly linked lists with external linking
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    Institut f. Computersprachen, TU Wien
   5    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
   6    S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
   7    J. Wenninger
   8
   9    This file is part of CACAO.
  10
  11    This program is free software; you can redistribute it and/or
  12    modify it under the terms of the GNU General Public License as
  13    published by the Free Software Foundation; either version 2, or (at
  14    your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful, but
  17    WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19    General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  24    02111-1307, USA.
  25
  26    Contact: cacao@complang.tuwien.ac.at
  27
  28    Authors: Reinhard Grafl
  29
  30    $Id: chain.c 1621 2004-11-30 13:06:55Z twisti $
  31
  32 */
  33
  34
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <assert.h>
  38
  39 #include "mm/memory.h"
  40 #include "toolbox/chain.h"
  41
  42
  43 chain *chain_new()
  44 {
  45         chain *c;
  46
  47         c = NEW(chain);
  48         c->usedump = 0;
  49         c->first = NULL;
  50         c->last = NULL;
  51         c->active = NULL;
  52
  53         return c;
  54 }
  55
  56
  57 chain *chain_dnew()
  58 {
  59         chain *c;
  60
  61         c = DNEW(chain);
  62         c->usedump = 1;
  63         c->first = NULL;
  64         c->last = NULL;
  65         c->active = NULL;
  66
  67         return c;
  68 }
  69
  70
  71 void chain_free(chain *c)
  72 {
  73         chainlink *l;
  74
  75         assert(!c->usedump);
  76
  77         l = c->first;
  78         while (l) {
  79                 chainlink *nextl = l->next;
  80
  81                 FREE(l, chainlink);
  82                 l = nextl;
  83         }
  84
  85         FREE(c, chain);
  86 }
  87
  88
  89 void chain_addafter(chain *c, void *element)
  90 {
  91         chainlink *active;
  92         chainlink *newlink;
  93
  94     active = c->active;
  95
  96         if (c->usedump) {
  97                 newlink = DNEW(chainlink);
  98
  99         } else {
 100                 newlink = NEW(chainlink);
 101         }
 102
 103         newlink->element = element;
 104
 105         if (active) {
 106                 newlink->next = active->next;
 107                 newlink->prev = active;
 108
 109                 active->next = newlink;
 110                 if (newlink->next) {
 111                         newlink->next->prev = newlink;
 112
 113                 } else {
 114                         c->last = newlink;
 115                 }
 116
 117         } else {
 118                 newlink->next = NULL;
 119                 newlink->prev = NULL;
 120
 121                 c->active = newlink;
 122                 c->first = newlink;
 123                 c->last = newlink;
 124         }
 125 }
 126
 127
 128 void chain_addbefore(chain *c, void *element)
 129 {
 130         chainlink *active;
 131         chainlink *newlink;
 132
 133     active = c->active;
 134
 135         if (c->usedump) {
 136                 newlink = DNEW(chainlink);
 137
 138         } else {
 139                 newlink = NEW(chainlink);
 140         }
 141
 142         newlink->element = element;
 143
 144         if (active) {
 145                 newlink->next = active;
 146                 newlink->prev = active->prev;
 147
 148                 active->prev = newlink;
 149                 if (newlink->prev) {
 150                         newlink->prev->next = newlink;
 151
 152                 } else {
 153                         c->first = newlink;
 154                 }
 155
 156         } else {
 157                 newlink->next = NULL;
 158                 newlink->prev = NULL;
 159
 160                 c->active = newlink;
 161                 c->first = newlink;
 162                 c->last = newlink;
 163         }
 164 }
 165
 166
 167 void chain_addlast(chain *c, void *e)
 168 {
 169         chain_last(c);
 170         chain_addafter(c, e);
 171 }
 172
 173
 174 void chain_addfirst(chain *c, void *e)
 175 {
 176         chain_first(c);
 177         chain_addbefore(c, e);
 178 }
 179
 180
 181 void chain_remove(chain *c)
 182 {
 183         chainlink *active;
 184
 185         active = c->active;
 186         assert(active);
 187
 188         if (active->next) {
 189                 active->next->prev = active->prev;
 190
 191         } else {
 192                 c->last = active->prev;
 193         }
 194
 195         if (active->prev) {
 196                 active->prev->next = active->next;
 197
 198         } else {
 199                 c->first = active->next;
 200         }
 201
 202
 203         if (active->prev) {
 204                 c->active = active->prev;
 205
 206         } else {
 207                 c->active = active->next;
 208         }
 209
 210         if (!c->usedump)
 211                 FREE(active, chainlink);
 212 }
 213
 214
 215 void *chain_remove_go_prev(chain *c)
 216 {
 217         chain_remove(c);
 218         return chain_this(c);
 219 }
 220
 221
 222
 223 void chain_removespecific(chain *c, void *e)
 224 {
 225         void *ce;
 226
 227         ce = chain_first(c);
 228         while (ce) {
 229                 if (e == ce) {
 230                         chain_remove(c);
 231                         return;
 232                 }
 233
 234         ce = chain_next(c);
 235         }
 236 }
 237
 238
 239 void *chain_next(chain *c)
 240 {
 241         chainlink *active;
 242
 243         active = c->active;
 244
 245         if (!active)
 246                 return NULL;
 247
 248         if (active->next) {
 249                 c->active = active->next;
 250                 return c->active->element;
 251         }
 252
 253         return NULL;
 254 }
 255
 256
 257 void *chain_prev(chain *c)
 258 {
 259         chainlink *active;
 260
 261         active = c->active;
 262
 263         if (!active)
 264                 return NULL;
 265
 266         if (active->prev) {
 267                 c->active = active->prev;
 268                 return c->active->element;
 269         }
 270
 271         return NULL;
 272 }
 273
 274
 275 void *chain_this(chain *c)
 276 {
 277         if (c->active)
 278                 return c->active->element;
 279
 280         return NULL;
 281 }
 282
 283
 284 void *chain_first(chain *c)
 285 {
 286         c->active = c->first;
 287
 288         if (c -> active)
 289                 return c->active->element;
 290
 291         return NULL;
 292 }
 293
 294 void *chain_last(chain *c)
 295 {
 296         c->active = c->last;
 297
 298         if (c->active)
 299                 return c->active->element;
 300
 301         return NULL;
 302 }
 303
 304
 305 /*
 306  * These are local overrides for various environment variables in Emacs.
 307  * Please do not remove this and leave it at the end of the file, where
 308  * Emacs will automagically detect them.
 309  * ---------------------------------------------------------------------
 310  * Local variables:
 311  * mode: c
 312  * indent-tabs-mode: t
 313  * c-basic-offset: 4
 314  * tab-width: 4
 315  * End:
 316  */