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 7784 2007-04-20 13:51:41Z 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_t *list_create(s4 nodeoffset)
  54 {
  55         list_t *l;
  56
  57         l = NEW(list_t);
  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         l->size       = 0;
  67
  68         return l;
  69 }
  70
  71
  72 /* list_create_dump ************************************************************
  73
  74    Allocates a new list on the dump memory.
  75
  76    ATTENTION: This list does NOT initialize the locking object!!!
  77
  78 *******************************************************************************/
  79
  80 list_t *list_create_dump(s4 nodeoffset)
  81 {
  82         list_t *l;
  83
  84         l = DNEW(list_t);
  85
  86         l->first      = NULL;
  87         l->last       = NULL;
  88         l->nodeoffset = nodeoffset;
  89         l->size       = 0;
  90
  91         return l;
  92 }
  93
  94
  95 /* list_add_first **************************************************************
  96
  97    Adds the element as first element.
  98
  99 *******************************************************************************/
 100
 101 void list_add_first(list_t *l, void *element)
 102 {
 103         listnode_t *ln;
 104
 105         ln = (listnode_t *) (((u1 *) element) + l->nodeoffset);
 106
 107         LOCK_MONITOR_ENTER(l);
 108
 109         if (l->first) {
 110                 ln->prev       = NULL;
 111                 ln->next       = l->first;
 112                 l->first->prev = ln;
 113                 l->first       = ln;
 114         }
 115         else {
 116                 ln->prev = NULL;
 117                 ln->next = NULL;
 118                 l->last  = ln;
 119                 l->first = ln;
 120         }
 121
 122         /* increase number of elements */
 123
 124         l->size++;
 125
 126         LOCK_MONITOR_EXIT(l);
 127 }
 128
 129
 130 /* list_add_last ***************************************************************
 131
 132    Adds the element as last element.
 133
 134 *******************************************************************************/
 135
 136 void list_add_last(list_t *l, void *element)
 137 {
 138         LOCK_MONITOR_ENTER(l);
 139
 140         list_add_last_unsynced(l, element);
 141
 142         LOCK_MONITOR_EXIT(l);
 143 }
 144
 145
 146 /* list_add_last_unsynced ******************************************************
 147
 148    Adds the element as last element but does NO locking!
 149
 150    ATTENTION: Use this function with care!!!
 151
 152 *******************************************************************************/
 153
 154 void list_add_last_unsynced(list_t *l, void *element)
 155 {
 156         listnode_t *ln;
 157
 158         ln = (listnode_t *) (((u1 *) element) + l->nodeoffset);
 159
 160         if (l->last) {
 161                 ln->prev      = l->last;
 162                 ln->next      = NULL;
 163                 l->last->next = ln;
 164                 l->last       = ln;
 165         }
 166         else {
 167                 ln->prev = NULL;
 168                 ln->next = NULL;
 169                 l->last  = ln;
 170                 l->first = ln;
 171         }
 172
 173         /* increase number of elements */
 174
 175         l->size++;
 176 }
 177
 178
 179 /* list_add_before *************************************************************
 180
 181    Adds the element newelement to the list l before element.
 182
 183    [ A ] <-> [ newn ] <-> [ n ] <-> [ B ]
 184
 185 *******************************************************************************/
 186
 187 void list_add_before(list_t *l, void *element, void *newelement)
 188 {
 189         listnode_t *ln;
 190         listnode_t *newln;
 191
 192         ln    = (listnode_t *) (((u1 *) element) + l->nodeoffset);
 193         newln = (listnode_t *) (((u1 *) newelement) + l->nodeoffset);
 194
 195         LOCK_MONITOR_ENTER(l);
 196
 197         /* set the new links */
 198
 199         newln->prev = ln->prev;
 200         newln->next = ln;
 201
 202         if (newln->prev)
 203                 newln->prev->next = newln;
 204
 205         ln->prev = newln;
 206
 207         /* set list's first and last if necessary */
 208
 209         if (l->first == ln)
 210                 l->first = newln;
 211
 212         if (l->last == ln)
 213                 l->last = newln;
 214
 215         /* increase number of elements */
 216
 217         l->size++;
 218
 219         LOCK_MONITOR_EXIT(l);
 220 }
 221
 222
 223 /* list_remove ***************************************************************
 224
 225    Removes the element.
 226
 227 *******************************************************************************/
 228
 229 void list_remove(list_t *l, void *element)
 230 {
 231         LOCK_MONITOR_ENTER(l);
 232
 233         list_remove_unsynced(l, element);
 234
 235         LOCK_MONITOR_EXIT(l);
 236 }
 237
 238
 239 /* list_remove_unsynced ********************************************************
 240
 241    Removes the element but does NO locking!
 242
 243    ATTENTION: Use this function with care!!!
 244
 245 *******************************************************************************/
 246
 247 void list_remove_unsynced(list_t *l, void *element)
 248 {
 249         listnode_t *ln;
 250
 251         ln = (listnode_t *) (((u1 *) element) + l->nodeoffset);
 252
 253         if (ln->next)
 254                 ln->next->prev = ln->prev;
 255         else
 256                 l->last = ln->prev;
 257
 258         if (ln->prev)
 259                 ln->prev->next = ln->next;
 260         else
 261                 l->first = ln->next;
 262
 263         ln->next = NULL;
 264         ln->prev = NULL;
 265
 266         /* decrease number of elements */
 267
 268         l->size--;
 269 }
 270
 271
 272 /* list_first ******************************************************************
 273
 274    Returns the first element of the list.
 275
 276 *******************************************************************************/
 277
 278 void *list_first(list_t *l)
 279 {
 280         void *el;
 281
 282         LOCK_MONITOR_ENTER(l);
 283
 284         el = list_first_unsynced(l);
 285
 286         LOCK_MONITOR_EXIT(l);
 287
 288         return el;
 289 }
 290
 291
 292 /* list_first_unsynced *********************************************************
 293
 294    Returns the first element of the list, but does NO locking!
 295
 296    ATTENTION: Use this function with care!!!
 297
 298 *******************************************************************************/
 299
 300 void *list_first_unsynced(list_t *l)
 301 {
 302         void *el;
 303
 304         if (l->first == NULL)
 305                 el = NULL;
 306         else
 307                 el = ((u1 *) l->first) - l->nodeoffset;
 308
 309         return el;
 310 }
 311
 312
 313 /* list_last *******************************************************************
 314
 315    Returns the last element of the list.
 316
 317 *******************************************************************************/
 318
 319 void *list_last(list_t *l)
 320 {
 321         void *el;
 322
 323         LOCK_MONITOR_ENTER(l);
 324
 325         el = list_last_unsynced(l);
 326
 327         LOCK_MONITOR_EXIT(l);
 328
 329         return el;
 330 }
 331
 332
 333 /* list_last_unsynced **********************************************************
 334
 335    Returns the last element of the list, but does NO locking!
 336
 337    ATTENTION: Use this function with care!!!
 338
 339 *******************************************************************************/
 340
 341 void *list_last_unsynced(list_t *l)
 342 {
 343         void *el;
 344
 345         if (l->last == NULL)
 346                 el = NULL;
 347         else
 348                 el = ((u1 *) l->last) - l->nodeoffset;
 349
 350         return el;
 351 }
 352
 353
 354 /* list_next *******************************************************************
 355
 356    Returns the next element of element from the list.
 357
 358 *******************************************************************************/
 359
 360 void *list_next(list_t *l, void *element)
 361 {
 362         void *el;
 363
 364         LOCK_MONITOR_ENTER(l);
 365
 366         el = list_next_unsynced(l, element);
 367
 368         LOCK_MONITOR_EXIT(l);
 369
 370         return el;
 371 }
 372
 373
 374 /* list_next_unsynced **********************************************************
 375
 376    Returns the next element of element from the list, but does NO
 377    locking!
 378
 379    ATTENTION: Use this function with care!!!
 380
 381 *******************************************************************************/
 382
 383 void *list_next_unsynced(list_t *l, void *element)
 384 {
 385         listnode_t *ln;
 386         void     *el;
 387
 388         ln = (listnode_t *) (((u1 *) element) + l->nodeoffset);
 389
 390         if (ln->next == NULL)
 391                 el = NULL;
 392         else
 393                 el = ((u1 *) ln->next) - l->nodeoffset;
 394
 395         return el;
 396 }
 397
 398
 399 /* list_prev *******************************************************************
 400
 401    Returns the previous element of element from the list.
 402
 403 *******************************************************************************/
 404
 405 void *list_prev(list_t *l, void *element)
 406 {
 407         void *el;
 408
 409         LOCK_MONITOR_ENTER(l);
 410
 411         el = list_prev_unsynced(l, element);
 412
 413         LOCK_MONITOR_EXIT(l);
 414
 415         return el;
 416 }
 417
 418
 419 /* list_prev_unsynced **********************************************************
 420
 421    Returns the previous element of element from the list, but does NO
 422    locking!
 423
 424    ATTENTION: Use this function with care!!!
 425
 426 *******************************************************************************/
 427
 428 void *list_prev_unsynced(list_t *l, void *element)
 429 {
 430         listnode_t *ln;
 431         void     *el;
 432
 433         ln = (listnode_t *) (((u1 *) element) + l->nodeoffset);
 434
 435         if (ln->prev == NULL)
 436                 el = NULL;
 437         else
 438                 el = ((u1 *) ln->prev) - l->nodeoffset;
 439
 440         return el;
 441 }
 442
 443
 444 /*
 445  * These are local overrides for various environment variables in Emacs.
 446  * Please do not remove this and leave it at the end of the file, where
 447  * Emacs will automagically detect them.
 448  * ---------------------------------------------------------------------
 449  * Local variables:
 450  * mode: c
 451  * indent-tabs-mode: t
 452  * c-basic-offset: 4
 453  * tab-width: 4
 454  * End:
 455  */