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