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