src/toolbox/list.h

   1 /* src/toolbox/list.h - synchronized 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.h 8295 2007-08-11 17:57:24Z michi $
  26
  27 */
  28
  29
  30 #ifndef _LIST_H
  31 #define _LIST_H
  32
  33 #include "config.h"
  34 #include "vm/types.h"
  35
  36 #include "vm/global.h"
  37
  38
  39 /* ---------------------- interface description -----------------------------
  40
  41 The list management with this module works like this:
  42
  43         - to be used in a list, a structure must have an element of type
  44           'listnode'.
  45
  46         - there needs to be a structure of type 'list'.
  47
  48         - the function list_init(l, nodeoffset) initializes the structure.
  49           nodeoffset is the offset of the 'listnode' from the start of the
  50           structure in bytes.
  51
  52         - The remaining functions provide inserting, removing and searching.
  53
  54 This small example aims to demonstrate correct usage:
  55
  56
  57
  58         void bsp() {
  59                 struct node {
  60                         listnode linkage;
  61                         int value;
  62                         } a,b,c, *el;
  63
  64                 list l;
  65
  66                 a.value = 7;
  67                 b.value = 9;
  68                 c.value = 11;
  69
  70                 list_init (&l, OFFSET(struct node,linkage) );
  71                 list_addlast (&l, a);
  72                 list_addlast (&l, b);
  73                 list_addlast (&l, c);
  74
  75                 e = list_first (&l);
  76                 while (e) {
  77                         printf ("Element: %d\n", e->value);
  78                         e = list_next (&l,e);
  79                         }
  80         }
  81
  82
  83         The output from this program should be:
  84                 7
  85                 9
  86                 11
  87
  88
  89
  90 The reason for the usage of 'nodeoffset' is that this way, the same node can
  91 part of different lists (there must be one 'listnode' element for every
  92 distinct list).
  93
  94 */
  95
  96 /* listnode_t *****************************************************************/
  97
  98 typedef struct listnode_t listnode_t;
  99
 100 struct listnode_t {
 101         listnode_t *next;
 102         listnode_t *prev;
 103 };
 104
 105
 106 /* list_t *********************************************************************/
 107
 108 typedef struct list_t list_t;
 109
 110 struct list_t {
 111 #if defined(ENABLE_THREADS)
 112         java_object_t      lock;            /* threads lock object                */
 113 #endif
 114         listnode_t        *first;
 115         listnode_t        *last;
 116         s4                 nodeoffset;
 117         s4                 size;            /* number of elements in the list     */
 118 };
 119
 120
 121 /* function prototypes ********************************************************/
 122
 123 list_t *list_create(s4 nodeoffset);
 124 list_t *list_create_dump(s4 nodeoffset);
 125
 126 void    list_add_first(list_t *l, void *element);
 127 void    list_add_first_unsynced(list_t *l, void *element);
 128
 129 void    list_add_last(list_t *l, void *element);
 130 void    list_add_last_unsynced(list_t *l, void *element);
 131
 132 void    list_add_before(list_t *l, void *element, void *newelement);
 133
 134 void    list_remove(list_t *l, void *element);
 135 void    list_remove_unsynced(list_t *l, void *element);
 136
 137 void   *list_first(list_t *l);
 138 void   *list_first_unsynced(list_t *l);
 139
 140 void   *list_last(list_t *l);
 141 void   *list_last_unsynced(list_t *l);
 142
 143 void   *list_next(list_t *l, void *element);
 144 void   *list_next_unsynced(list_t *l, void *element);
 145
 146 void   *list_prev(list_t *l, void *element);
 147 void   *list_prev_unsynced(list_t *l, void *element);
 148
 149 #endif /* _LIST_H */
 150
 151
 152 /*
 153  * These are local overrides for various environment variables in Emacs.
 154  * Please do not remove this and leave it at the end of the file, where
 155  * Emacs will automagically detect them.
 156  * ---------------------------------------------------------------------
 157  * Local variables:
 158  * mode: c
 159  * indent-tabs-mode: t
 160  * c-basic-offset: 4
 161  * tab-width: 4
 162  * End:
 163  */