src/toolbox/list.c

   1 /* src/toolbox/list.c - double linked list
   2
   3    Copyright (C) 1996-2005, 2006, 2007 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    $Id: list.c 7246 2007-01-29 18:49:05Z twisti $
  26
  27 */
  28
  29
  30 #include "config.h"
  31
  32 #include <stdlib.h>
  33
  34 #include "vm/types.h"
  35
  36 #include "mm/memory.h"
  37
  38 #if defined(ENABLE_THREADS)
  39 # include "threads/native/lock.h"
  40 #else
  41 # include "threads/none/lock.h"
  42 #endif
  43
  44 #include "toolbox/list.h"
  45
  46
  47 /* list_create *****************************************************************
  48
  49    Allocates a new list and initializes the lock object.
  50
  51 *******************************************************************************/
  52
  53 list *list_create(s4 nodeoffset)
  54 {
  55         list *l;
  56
  57         l = NEW(list);
  58
  59 #if defined(ENABLE_THREADS)
  60         lock_init_object_lock((java_objectheader *) l);
  61 #endif
  62
  63         l->first      = NULL;
  64         l->last       = NULL;
  65         l->nodeoffset = nodeoffset;
  66
  67         return l;
  68 }
  69
  70
  71 /* list_create_dump ************************************************************
  72
  73    Allocates a new list on the dump memory.
  74
  75    ATTENTION: This list does NOT initialize the locking object!!!
  76
  77 *******************************************************************************/
  78
  79 list *list_create_dump(s4 nodeoffset)
  80 {
  81         list *l;
  82
  83         l = DNEW(list);
  84
  85         l->first      = NULL;
  86         l->last       = NULL;
  87         l->nodeoffset = nodeoffset;
  88
  89         return l;
  90 }
  91
  92
  93 void list_add_first(list *l, void *element)
  94 {
  95         listnode *ln;
  96
  97         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
  98
  99         LOCK_MONITOR_ENTER(l);
 100
 101         if (l->first) {
 102                 ln->prev       = NULL;
 103                 ln->next       = l->first;
 104                 l->first->prev = ln;
 105                 l->first       = ln;
 106         }
 107         else {
 108                 ln->prev = NULL;
 109                 ln->next = NULL;
 110                 l->last  = ln;
 111                 l->first = ln;
 112         }
 113
 114         LOCK_MONITOR_EXIT(l);
 115 }
 116
 117
 118 /* list_add_last ***************************************************************
 119
 120    Adds the element as last element.
 121
 122 *******************************************************************************/
 123
 124 void list_add_last(list *l, void *element)
 125 {
 126         LOCK_MONITOR_ENTER(l);
 127
 128         list_add_last_unsynced(l, element);
 129
 130         LOCK_MONITOR_EXIT(l);
 131 }
 132
 133
 134 /* list_add_list_unsynced ******************************************************
 135
 136    Adds the element as last element but does NO locking!
 137
 138    ATTENTION: Use this function with care!!!
 139
 140 *******************************************************************************/
 141
 142 void list_add_last_unsynced(list *l, void *element)
 143 {
 144         listnode *ln;
 145
 146         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 147
 148         if (l->last) {
 149                 ln->prev      = l->last;
 150                 ln->next      = NULL;
 151                 l->last->next = ln;
 152                 l->last       = ln;
 153         }
 154         else {
 155                 ln->prev = NULL;
 156                 ln->next = NULL;
 157                 l->last  = ln;
 158                 l->first = ln;
 159         }
 160 }
 161
 162
 163 /* list_add_before *************************************************************
 164
 165    Adds the element newelement to the list l before element.
 166
 167    [ A ] <-> [ newn ] <-> [ n ] <-> [ B ]
 168
 169 *******************************************************************************/
 170
 171 void list_add_before(list *l, void *element, void *newelement)
 172 {
 173         listnode *ln;
 174         listnode *newln;
 175
 176         ln    = (listnode *) (((u1 *) element) + l->nodeoffset);
 177         newln = (listnode *) (((u1 *) newelement) + l->nodeoffset);
 178
 179         LOCK_MONITOR_ENTER(l);
 180
 181         /* set the new links */
 182
 183         newln->prev = ln->prev;
 184         newln->next = ln;
 185
 186         if (newln->prev)
 187                 newln->prev->next = newln;
 188
 189         ln->prev = newln;
 190
 191         /* set list's first and last if necessary */
 192
 193         if (l->first == ln)
 194                 l->first = newln;
 195
 196         if (l->last == ln)
 197                 l->last = newln;
 198
 199         LOCK_MONITOR_EXIT(l);
 200 }
 201
 202
 203 void list_remove(list *l, void *element)
 204 {
 205         listnode *ln;
 206
 207         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 208
 209         LOCK_MONITOR_ENTER(l);
 210
 211         if (ln->next)
 212                 ln->next->prev = ln->prev;
 213         else
 214                 l->last = ln->prev;
 215
 216         if (ln->prev)
 217                 ln->prev->next = ln->next;
 218         else
 219                 l->first = ln->next;
 220
 221         ln->next = NULL;
 222         ln->prev = NULL;
 223
 224         LOCK_MONITOR_EXIT(l);
 225 }
 226
 227
 228 /* list_first ******************************************************************
 229
 230    Returns the first element of the list.
 231
 232 *******************************************************************************/
 233
 234 void *list_first(list *l)
 235 {
 236         void *el;
 237
 238         LOCK_MONITOR_ENTER(l);
 239
 240         el = list_first_unsynced(l);
 241
 242         LOCK_MONITOR_EXIT(l);
 243
 244         return el;
 245 }
 246
 247
 248 /* list_first_unsynced *********************************************************
 249
 250    Returns the first element of the list, but does NO locking!
 251
 252    ATTENTION: Use this function with care!!!
 253
 254 *******************************************************************************/
 255
 256 void *list_first_unsynced(list *l)
 257 {
 258         void *el;
 259
 260         if (l->first == NULL)
 261                 el = NULL;
 262         else
 263                 el = ((u1 *) l->first) - l->nodeoffset;
 264
 265         return el;
 266 }
 267
 268
 269 /* list_last *******************************************************************
 270
 271    Returns the last element of the list.
 272
 273 *******************************************************************************/
 274
 275 void *list_last(list *l)
 276 {
 277         void *el;
 278
 279         LOCK_MONITOR_ENTER(l);
 280
 281         el = list_last_unsynced(l);
 282
 283         LOCK_MONITOR_EXIT(l);
 284
 285         return el;
 286 }
 287
 288
 289 /* list_last_unsynced **********************************************************
 290
 291    Returns the last element of the list, but does NO locking!
 292
 293    ATTENTION: Use this function with care!!!
 294
 295 *******************************************************************************/
 296
 297 void *list_last_unsynced(list *l)
 298 {
 299         void *el;
 300
 301         if (l->last == NULL)
 302                 el = NULL;
 303         else
 304                 el = ((u1 *) l->last) - l->nodeoffset;
 305
 306         return el;
 307 }
 308
 309
 310 /* list_next *******************************************************************
 311
 312    Returns the next element of element from the list.
 313
 314 *******************************************************************************/
 315
 316 void *list_next(list *l, void *element)
 317 {
 318         void *el;
 319
 320         LOCK_MONITOR_ENTER(l);
 321
 322         el = list_next_unsynced(l, element);
 323
 324         LOCK_MONITOR_EXIT(l);
 325
 326         return el;
 327 }
 328
 329
 330 /* list_next_unsynced **********************************************************
 331
 332    Returns the next element of element from the list, but does NO
 333    locking!
 334
 335    ATTENTION: Use this function with care!!!
 336
 337 *******************************************************************************/
 338
 339 void *list_next_unsynced(list *l, void *element)
 340 {
 341         listnode *ln;
 342         void     *el;
 343
 344         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 345
 346         if (ln->next == NULL)
 347                 el = NULL;
 348         else
 349                 el = ((u1 *) ln->next) - l->nodeoffset;
 350
 351         return el;
 352 }
 353
 354
 355 /* list_prev *******************************************************************
 356
 357    Returns the previous element of element from the list.
 358
 359 *******************************************************************************/
 360
 361 void *list_prev(list *l, void *element)
 362 {
 363         void *el;
 364
 365         LOCK_MONITOR_ENTER(l);
 366
 367         el = list_prev_unsynced(l, element);
 368
 369         LOCK_MONITOR_EXIT(l);
 370
 371         return el;
 372 }
 373
 374
 375 /* list_prev_unsynced **********************************************************
 376
 377    Returns the previous element of element from the list, but does NO
 378    locking!
 379
 380    ATTENTION: Use this function with care!!!
 381
 382 *******************************************************************************/
 383
 384 void *list_prev_unsynced(list *l, void *element)
 385 {
 386         listnode *ln;
 387         void     *el;
 388
 389         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 390
 391         if (ln->prev == NULL)
 392                 el = NULL;
 393         else
 394                 el = ((u1 *) ln->prev) - l->nodeoffset;
 395
 396         return el;
 397 }
 398
 399
 400 /*
 401  * These are local overrides for various environment variables in Emacs.
 402  * Please do not remove this and leave it at the end of the file, where
 403  * Emacs will automagically detect them.
 404  * ---------------------------------------------------------------------
 405  * Local variables:
 406  * mode: c
 407  * indent-tabs-mode: t
 408  * c-basic-offset: 4
 409  * tab-width: 4
 410  * End:
 411  */