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