Line data Source code
1 : /* src/toolbox/worklist.c - worklist implementation
2 :
3 : Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
4 : R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
5 : C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
6 : 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., 59 Temple Place - Suite 330, Boston, MA
23 : 02111-1307, USA.
24 :
25 : Contact: cacao@complang.tuwien.ac.at
26 :
27 : Authors: Christian Ullrich
28 :
29 :
30 : */
31 :
32 : #include "toolbox/worklist.hpp"
33 : #include <cassert>
34 : #include "bitvector.hpp" // for bv_get_bit, bv_new, etc
35 : #include "mm/dumpmemory.hpp" // for DMNEW, DNEW
36 :
37 : #if !defined(NDEBUG)
38 :
39 : /// define WL_DEBUG_CHECK to activate the bound checks
40 : // #define WL_DEBUG_CHECK
41 :
42 : #endif
43 :
44 : #if defined(WL_DEBUG_CHECK)
45 : #define _WL_CHECK_BOUNDS(i,l,h) assert( ((i) >= (l)) && ((i) < (h)));
46 : #define _WL_ASSERT(a) assert((a));
47 : #else
48 : #define _WL_CHECK_BOUNDS(i,l,h);
49 : #define _WL_ASSERT(a);
50 : #endif
51 :
52 : /******************************************************************************
53 :
54 : Worklist Implementation
55 :
56 : New Elements (integers) are pushed on a stack and remembered in a
57 : bitvector, to ensure efficitently uniqueness.
58 :
59 : ******************************************************************************/
60 :
61 : /*******************************************************************************
62 : wl_new
63 :
64 : IN: int size size of worklist
65 :
66 : RETURN: worklist * new worklist
67 : *******************************************************************************/
68 0 : worklist *wl_new(int size) {
69 0 : worklist *w = DNEW(worklist);
70 0 : w->W_stack = DMNEW(int, size);
71 0 : w->W_top = 0;
72 0 : w->W_bv = bv_new(size);
73 : #ifdef WL_DEBUG_CHECK
74 : w->size = size;
75 : #endif
76 0 : return w;
77 : }
78 :
79 : /*******************************************************************************
80 : wl_add
81 :
82 : Adds the integer element to the worklist, if this value is not already
83 : in the worklist.
84 :
85 : IN: worklist *w pointer to worklist created with wl_new
86 : int element integer element to be added
87 : *******************************************************************************/
88 0 : void wl_add(worklist *w, int element) {
89 : _WL_CHECK_BOUNDS(element, 0, w->size);
90 :
91 0 : if (!bv_get_bit(w->W_bv, element)) {
92 : _WL_ASSERT((w->W_top < w->size));
93 0 : w->W_stack[(w->W_top)++] = element;
94 0 : bv_set_bit(w->W_bv, element);
95 : }
96 0 : }
97 :
98 : /*******************************************************************************
99 : wl_get
100 :
101 : Returns and removes an element from the worklist.
102 :
103 : IN: worklist *w pointer to worklist created with wl_new
104 :
105 : RETURN int an element removed from the worklist
106 : *******************************************************************************/
107 0 : int wl_get(worklist *w) {
108 : _WL_ASSERT((w->W_top > 0));
109 :
110 0 : int element = w->W_stack[--(w->W_top)];
111 0 : bv_reset_bit(w->W_bv, element);
112 0 : return element;
113 : }
114 :
115 : /*******************************************************************************
116 : wl_is_empty
117 :
118 : Checks if the worklist is empty.
119 :
120 : IN: worklist *w pointer to worklist created with wl_new
121 :
122 : RETURN bool true if w is empty, false otherwise
123 : *******************************************************************************/
124 0 : bool wl_is_empty(worklist *w) {
125 0 : return (w->W_top == 0);
126 : }
127 :
128 : /*******************************************************************************
129 : wl_reset
130 :
131 : Empties the worklist.
132 :
133 : IN: worklist *w pointer to worklist created with wl_new
134 : *******************************************************************************/
135 0 : void wl_reset(worklist *w, int size) {
136 0 : w->W_top = 0;
137 0 : bv_reset(w->W_bv, size);
138 0 : }
139 :
140 : /*
141 : * These are local overrides for various environment variables in Emacs.
142 : * Please do not remove this and leave it at the end of the file, where
143 : * Emacs will automagically detect them.
144 : * ---------------------------------------------------------------------
145 : * Local variables:
146 : * mode: c++
147 : * indent-tabs-mode: t
148 : * c-basic-offset: 4
149 : * tab-width: 4
150 : * End:
151 : */
|
