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 7481 2007-03-08 13:12:21Z 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_last_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 /* list_remove ***************************************************************
 204
 205    Removes the element.
 206
 207 *******************************************************************************/
 208
 209 void list_remove(list *l, void *element)
 210 {
 211         LOCK_MONITOR_ENTER(l);
 212
 213         list_remove_unsynced(l, element);
 214
 215         LOCK_MONITOR_EXIT(l);
 216 }
 217
 218
 219 /* list_remove_unsynced ********************************************************
 220
 221    Removes the element but does NO locking!
 222
 223    ATTENTION: Use this function with care!!!
 224
 225 *******************************************************************************/
 226
 227 void list_remove_unsynced(list *l, void *element)
 228 {
 229         listnode *ln;
 230
 231         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 232
 233         if (ln->next)
 234                 ln->next->prev = ln->prev;
 235         else
 236                 l->last = ln->prev;
 237
 238         if (ln->prev)
 239                 ln->prev->next = ln->next;
 240         else
 241                 l->first = ln->next;
 242
 243         ln->next = NULL;
 244         ln->prev = NULL;
 245 }
 246
 247
 248 /* list_first ******************************************************************
 249
 250    Returns the first element of the list.
 251
 252 *******************************************************************************/
 253
 254 void *list_first(list *l)
 255 {
 256         void *el;
 257
 258         LOCK_MONITOR_ENTER(l);
 259
 260         el = list_first_unsynced(l);
 261
 262         LOCK_MONITOR_EXIT(l);
 263
 264         return el;
 265 }
 266
 267
 268 /* list_first_unsynced *********************************************************
 269
 270    Returns the first element of the list, but does NO locking!
 271
 272    ATTENTION: Use this function with care!!!
 273
 274 *******************************************************************************/
 275
 276 void *list_first_unsynced(list *l)
 277 {
 278         void *el;
 279
 280         if (l->first == NULL)
 281                 el = NULL;
 282         else
 283                 el = ((u1 *) l->first) - l->nodeoffset;
 284
 285         return el;
 286 }
 287
 288
 289 /* list_last *******************************************************************
 290
 291    Returns the last element of the list.
 292
 293 *******************************************************************************/
 294
 295 void *list_last(list *l)
 296 {
 297         void *el;
 298
 299         LOCK_MONITOR_ENTER(l);
 300
 301         el = list_last_unsynced(l);
 302
 303         LOCK_MONITOR_EXIT(l);
 304
 305         return el;
 306 }
 307
 308
 309 /* list_last_unsynced **********************************************************
 310
 311    Returns the last element of the list, but does NO locking!
 312
 313    ATTENTION: Use this function with care!!!
 314
 315 *******************************************************************************/
 316
 317 void *list_last_unsynced(list *l)
 318 {
 319         void *el;
 320
 321         if (l->last == NULL)
 322                 el = NULL;
 323         else
 324                 el = ((u1 *) l->last) - l->nodeoffset;
 325
 326         return el;
 327 }
 328
 329
 330 /* list_next *******************************************************************
 331
 332    Returns the next element of element from the list.
 333
 334 *******************************************************************************/
 335
 336 void *list_next(list *l, void *element)
 337 {
 338         void *el;
 339
 340         LOCK_MONITOR_ENTER(l);
 341
 342         el = list_next_unsynced(l, element);
 343
 344         LOCK_MONITOR_EXIT(l);
 345
 346         return el;
 347 }
 348
 349
 350 /* list_next_unsynced **********************************************************
 351
 352    Returns the next element of element from the list, but does NO
 353    locking!
 354
 355    ATTENTION: Use this function with care!!!
 356
 357 *******************************************************************************/
 358
 359 void *list_next_unsynced(list *l, void *element)
 360 {
 361         listnode *ln;
 362         void     *el;
 363
 364         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 365
 366         if (ln->next == NULL)
 367                 el = NULL;
 368         else
 369                 el = ((u1 *) ln->next) - l->nodeoffset;
 370
 371         return el;
 372 }
 373
 374
 375 /* list_prev *******************************************************************
 376
 377    Returns the previous element of element from the list.
 378
 379 *******************************************************************************/
 380
 381 void *list_prev(list *l, void *element)
 382 {
 383         void *el;
 384
 385         LOCK_MONITOR_ENTER(l);
 386
 387         el = list_prev_unsynced(l, element);
 388
 389         LOCK_MONITOR_EXIT(l);
 390
 391         return el;
 392 }
 393
 394
 395 /* list_prev_unsynced **********************************************************
 396
 397    Returns the previous element of element from the list, but does NO
 398    locking!
 399
 400    ATTENTION: Use this function with care!!!
 401
 402 *******************************************************************************/
 403
 404 void *list_prev_unsynced(list *l, void *element)
 405 {
 406         listnode *ln;
 407         void     *el;
 408
 409         ln = (listnode *) (((u1 *) element) + l->nodeoffset);
 410
 411         if (ln->prev == NULL)
 412                 el = NULL;
 413         else
 414                 el = ((u1 *) ln->prev) - l->nodeoffset;
 415
 416         return el;
 417 }
 418
 419
 420 /*
 421  * These are local overrides for various environment variables in Emacs.
 422  * Please do not remove this and leave it at the end of the file, where
 423  * Emacs will automagically detect them.
 424  * ---------------------------------------------------------------------
 425  * Local variables:
 426  * mode: c
 427  * indent-tabs-mode: t
 428  * c-basic-offset: 4
 429  * tab-width: 4
 430  * End:
 431  */