src/toolbox/list.c

   1 /* src/toolbox/list.c - double linked list
   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    $Id: list.c 5123 2006-07-12 21:45:34Z twisti $
  30
  31 */
  32
  33
  34 #include "config.h"
  35
  36 #include <stdlib.h>
  37
  38 #include "vm/types.h"
  39
  40 #include "mm/memory.h"
  41
  42 #if defined(ENABLE_THREADS)
  43 # include "threads/native/lock.h"
  44 # include "threads/native/threads.h"
  45 #else
  46 # include "threads/none/lock.h"
  47 #endif
  48
  49 #include "toolbox/list.h"
  50
  51
  52 /* list_create *****************************************************************
  53
  54    Allocates a new list and initializes the lock object.
  55
  56 *******************************************************************************/
  57
  58 list *list_create(s4 nodeoffset)
  59 {
  60         list *l;
  61
  62         l = NEW(list);
  63
  64 #if defined(ENABLE_THREADS)
  65         lock_init_object_lock((java_objectheader *) l);
  66 #endif
  67
  68         l->first      = NULL;
  69         l->last       = NULL;
  70         l->nodeoffset = nodeoffset;
  71
  72         return l;
  73 }
  74
  75
  76 void list_add_first(list *l, void *element)
  77 {
  78         listnode *ln;
  79
  80         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
  81
  82         LOCK_MONITOR_ENTER(l);
  83
  84         if (l->first) {
  85                 ln->prev       = NULL;
  86                 ln->next       = l->first;
  87                 l->first->prev = ln;
  88                 l->first       = ln;
  89         }
  90         else {
  91                 ln->prev = NULL;
  92                 ln->next = NULL;
  93                 l->last  = ln;
  94                 l->first = ln;
  95         }
  96
  97         LOCK_MONITOR_EXIT(l);
  98 }
  99
 100
 101 /* list_add_last ***************************************************************
 102
 103    Adds the element as last element.
 104
 105 *******************************************************************************/
 106
 107 void list_add_last(list *l, void *element)
 108 {
 109         listnode *ln;
 110
 111         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 112
 113         LOCK_MONITOR_ENTER(l);
 114
 115         if (l->last) {
 116                 ln->prev      = l->last;
 117                 ln->next      = NULL;
 118                 l->last->next = ln;
 119                 l->last       = ln;
 120         }
 121         else {
 122                 ln->prev = NULL;
 123                 ln->next = NULL;
 124                 l->last  = ln;
 125                 l->first = ln;
 126         }
 127
 128         LOCK_MONITOR_EXIT(l);
 129 }
 130
 131
 132 /* list_add_list_unsynced ******************************************************
 133
 134    Adds the element as last element but does NO locking!
 135
 136    ATTENTION: This function is used during bootstrap.  DON'T USE IT!!!
 137
 138 *******************************************************************************/
 139
 140 void list_add_last_unsynced(list *l, void *element)
 141 {
 142         listnode *ln;
 143
 144         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 145
 146         if (l->last) {
 147                 ln->prev      = l->last;
 148                 ln->next      = NULL;
 149                 l->last->next = ln;
 150                 l->last       = ln;
 151         }
 152         else {
 153                 ln->prev = NULL;
 154                 ln->next = NULL;
 155                 l->last  = ln;
 156                 l->first = ln;
 157         }
 158 }
 159
 160
 161 /* list_add_before *************************************************************
 162
 163    Adds the element newelement to the list l before element.
 164
 165    [ A ] <-> [ newn ] <-> [ n ] <-> [ B ]
 166
 167 *******************************************************************************/
 168
 169 void list_add_before(list *l, void *element, void *newelement)
 170 {
 171         listnode *ln;
 172         listnode *newln;
 173
 174         ln    = (listnode *) (((u1 *) element) + l->nodeoffset);
 175         newln = (listnode *) (((u1 *) newelement) + l->nodeoffset);
 176
 177         LOCK_MONITOR_ENTER(l);
 178
 179         /* set the new links */
 180
 181         newln->prev = ln->prev;
 182         newln->next = ln;
 183
 184         if (newln->prev)
 185                 newln->prev->next = newln;
 186
 187         ln->prev = newln;
 188
 189         /* set list's first and last if necessary */
 190
 191         if (l->first == ln)
 192                 l->first = newln;
 193
 194         if (l->last == ln)
 195                 l->last = newln;
 196
 197         LOCK_MONITOR_EXIT(l);
 198 }
 199
 200
 201 void list_remove(list *l, void *element)
 202 {
 203         listnode *ln;
 204
 205         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 206
 207         LOCK_MONITOR_ENTER(l);
 208
 209         if (ln->next)
 210                 ln->next->prev = ln->prev;
 211         else
 212                 l->last = ln->prev;
 213
 214         if (ln->prev)
 215                 ln->prev->next = ln->next;
 216         else
 217                 l->first = ln->next;
 218
 219         ln->next = NULL;
 220         ln->prev = NULL;
 221
 222         LOCK_MONITOR_EXIT(l);
 223 }
 224
 225
 226 void *list_first(list *l)
 227 {
 228         void *el;
 229
 230         LOCK_MONITOR_ENTER(l);
 231
 232         if (l->first == NULL)
 233                 el = NULL;
 234         else
 235                 el = ((u1 *) l->first) - l->nodeoffset;
 236
 237         LOCK_MONITOR_EXIT(l);
 238
 239         return el;
 240 }
 241
 242
 243 void *list_last(list *l)
 244 {
 245         void *el;
 246
 247         LOCK_MONITOR_ENTER(l);
 248
 249         if (l->last == NULL)
 250                 el = NULL;
 251         else
 252                 el = ((u1 *) l->last) - l->nodeoffset;
 253
 254         LOCK_MONITOR_EXIT(l);
 255
 256         return el;
 257 }
 258
 259
 260 void *list_next(list *l, void *element)
 261 {
 262         listnode *ln;
 263         void     *el;
 264
 265         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 266
 267         LOCK_MONITOR_ENTER(l);
 268
 269         if (ln->next == NULL)
 270                 el = NULL;
 271         else
 272                 el = ((u1 *) ln->next) - l->nodeoffset;
 273
 274         LOCK_MONITOR_EXIT(l);
 275
 276         return el;
 277 }
 278
 279
 280 void *list_prev(list *l, void *element)
 281 {
 282         listnode *ln;
 283         void     *el;
 284
 285         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 286
 287         LOCK_MONITOR_ENTER(l);
 288
 289         if (ln->prev == NULL)
 290                 el = NULL;
 291         else
 292                 el = ((u1 *) ln->prev) - l->nodeoffset;
 293
 294         LOCK_MONITOR_EXIT(l);
 295
 296         return el;
 297 }
 298
 299
 300 /*
 301  * These are local overrides for various environment variables in Emacs.
 302  * Please do not remove this and leave it at the end of the file, where
 303  * Emacs will automagically detect them.
 304  * ---------------------------------------------------------------------
 305  * Local variables:
 306  * mode: c
 307  * indent-tabs-mode: t
 308  * c-basic-offset: 4
 309  * tab-width: 4
 310  * End:
 311  */