src/toolbox/chain.c

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