src/toolbox/chain.c

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