]>
Commit | Line | Data |
---|---|---|
c906108c | 1 | /* Address ranges. |
1d506c26 | 2 | Copyright (C) 1998-2024 Free Software Foundation, Inc. |
c906108c SS |
3 | Contributed by Cygnus Solutions. |
4 | ||
5 | This file is part of the GNU Simulators. | |
6 | ||
7 | This program is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
4744ac1b JB |
9 | the Free Software Foundation; either version 3 of the License, or |
10 | (at your option) any later version. | |
c906108c SS |
11 | |
12 | This program is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
4744ac1b JB |
17 | You should have received a copy of the GNU General Public License |
18 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
c906108c | 19 | |
ef986697 SH |
20 | #ifndef _SIM_ARANGE_C_ |
21 | #define _SIM_ARANGE_C_ | |
c906108c | 22 | |
6df01ab8 MF |
23 | /* This must come before any other includes. */ |
24 | #include "defs.h" | |
25 | ||
20a8e078 MF |
26 | #include <stdlib.h> |
27 | #include <string.h> | |
28 | ||
c906108c | 29 | #include "libiberty.h" |
20a8e078 | 30 | |
c906108c | 31 | #include "sim-basics.h" |
ef986697 | 32 | #include "sim-arange.h" |
c906108c | 33 | |
c906108c SS |
34 | /* Insert a range. */ |
35 | ||
36 | static void | |
37 | insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr) | |
38 | { | |
39 | asr->next = *pos; | |
40 | *pos = asr; | |
41 | } | |
42 | ||
43 | /* Delete a range. */ | |
44 | ||
45 | static void | |
46 | delete_range (ADDR_SUBRANGE **thisasrp) | |
47 | { | |
48 | ADDR_SUBRANGE *thisasr; | |
49 | ||
50 | thisasr = *thisasrp; | |
51 | *thisasrp = thisasr->next; | |
52 | ||
53 | free (thisasr); | |
54 | } | |
55 | ||
56 | /* Add or delete an address range. | |
57 | This code was borrowed from linux's locks.c:posix_lock_file(). | |
58 | ??? Todo: Given our simpler needs this could be simplified | |
59 | (split into two fns). */ | |
60 | ||
61 | static void | |
62 | frob_range (ADDR_RANGE *ar, address_word start, address_word end, int delete_p) | |
63 | { | |
64 | ADDR_SUBRANGE *asr; | |
65 | ADDR_SUBRANGE *new_asr, *new_asr2; | |
66 | ADDR_SUBRANGE *left = NULL; | |
67 | ADDR_SUBRANGE *right = NULL; | |
68 | ADDR_SUBRANGE **before; | |
69 | ADDR_SUBRANGE init_caller; | |
70 | ADDR_SUBRANGE *caller = &init_caller; | |
71 | int added_p = 0; | |
72 | ||
73 | memset (caller, 0, sizeof (ADDR_SUBRANGE)); | |
74 | new_asr = ZALLOC (ADDR_SUBRANGE); | |
75 | new_asr2 = ZALLOC (ADDR_SUBRANGE); | |
76 | ||
77 | caller->start = start; | |
78 | caller->end = end; | |
79 | before = &ar->ranges; | |
80 | ||
81 | while ((asr = *before) != NULL) | |
82 | { | |
83 | if (! delete_p) | |
84 | { | |
85 | /* Try next range if current range preceeds new one and not | |
86 | adjacent or overlapping. */ | |
87 | if (asr->end < caller->start - 1) | |
88 | goto next_range; | |
89 | ||
90 | /* Break out if new range preceeds current one and not | |
91 | adjacent or overlapping. */ | |
92 | if (asr->start > caller->end + 1) | |
93 | break; | |
94 | ||
95 | /* If we come here, the new and current ranges are adjacent or | |
96 | overlapping. Make one range yielding from the lower start address | |
97 | of both ranges to the higher end address. */ | |
98 | if (asr->start > caller->start) | |
99 | asr->start = caller->start; | |
100 | else | |
101 | caller->start = asr->start; | |
102 | if (asr->end < caller->end) | |
103 | asr->end = caller->end; | |
104 | else | |
105 | caller->end = asr->end; | |
106 | ||
107 | if (added_p) | |
108 | { | |
109 | delete_range (before); | |
110 | continue; | |
111 | } | |
112 | caller = asr; | |
113 | added_p = 1; | |
114 | } | |
115 | else /* deleting a range */ | |
116 | { | |
117 | /* Try next range if current range preceeds new one. */ | |
118 | if (asr->end < caller->start) | |
119 | goto next_range; | |
120 | ||
121 | /* Break out if new range preceeds current one. */ | |
122 | if (asr->start > caller->end) | |
123 | break; | |
124 | ||
125 | added_p = 1; | |
126 | ||
127 | if (asr->start < caller->start) | |
128 | left = asr; | |
129 | ||
130 | /* If the next range in the list has a higher end | |
131 | address than the new one, insert the new one here. */ | |
132 | if (asr->end > caller->end) | |
133 | { | |
134 | right = asr; | |
135 | break; | |
136 | } | |
137 | if (asr->start >= caller->start) | |
138 | { | |
139 | /* The new range completely replaces an old | |
140 | one (This may happen several times). */ | |
141 | if (added_p) | |
142 | { | |
143 | delete_range (before); | |
144 | continue; | |
145 | } | |
146 | ||
147 | /* Replace the old range with the new one. */ | |
148 | asr->start = caller->start; | |
149 | asr->end = caller->end; | |
150 | caller = asr; | |
151 | added_p = 1; | |
152 | } | |
153 | } | |
154 | ||
155 | /* Go on to next range. */ | |
156 | next_range: | |
157 | before = &asr->next; | |
158 | } | |
159 | ||
160 | if (!added_p) | |
161 | { | |
162 | if (delete_p) | |
163 | goto out; | |
164 | new_asr->start = caller->start; | |
165 | new_asr->end = caller->end; | |
166 | insert_range (before, new_asr); | |
167 | new_asr = NULL; | |
168 | } | |
169 | if (right) | |
170 | { | |
171 | if (left == right) | |
172 | { | |
173 | /* The new range breaks the old one in two pieces, | |
174 | so we have to use the second new range. */ | |
175 | new_asr2->start = right->start; | |
176 | new_asr2->end = right->end; | |
177 | left = new_asr2; | |
178 | insert_range (before, left); | |
179 | new_asr2 = NULL; | |
180 | } | |
181 | right->start = caller->end + 1; | |
182 | } | |
183 | if (left) | |
184 | { | |
185 | left->end = caller->start - 1; | |
186 | } | |
187 | ||
188 | out: | |
189 | if (new_asr) | |
34b47c38 | 190 | free (new_asr); |
c906108c | 191 | if (new_asr2) |
34b47c38 | 192 | free (new_asr2); |
c906108c SS |
193 | } |
194 | ||
195 | /* Free T and all subtrees. */ | |
196 | ||
197 | static void | |
198 | free_search_tree (ADDR_RANGE_TREE *t) | |
199 | { | |
200 | if (t != NULL) | |
201 | { | |
202 | free_search_tree (t->lower); | |
203 | free_search_tree (t->higher); | |
204 | free (t); | |
205 | } | |
206 | } | |
207 | ||
208 | /* Subroutine of build_search_tree to recursively build a balanced tree. | |
209 | ??? It's not an optimum tree though. */ | |
210 | ||
211 | static ADDR_RANGE_TREE * | |
212 | build_tree_1 (ADDR_SUBRANGE **asrtab, unsigned int n) | |
213 | { | |
214 | unsigned int mid = n / 2; | |
215 | ADDR_RANGE_TREE *t; | |
216 | ||
217 | if (n == 0) | |
218 | return NULL; | |
219 | t = (ADDR_RANGE_TREE *) xmalloc (sizeof (ADDR_RANGE_TREE)); | |
220 | t->start = asrtab[mid]->start; | |
221 | t->end = asrtab[mid]->end; | |
222 | if (mid != 0) | |
223 | t->lower = build_tree_1 (asrtab, mid); | |
224 | else | |
225 | t->lower = NULL; | |
226 | if (n > mid + 1) | |
227 | t->higher = build_tree_1 (asrtab + mid + 1, n - mid - 1); | |
228 | else | |
229 | t->higher = NULL; | |
230 | return t; | |
231 | } | |
232 | ||
233 | /* Build a search tree for address range AR. */ | |
234 | ||
235 | static void | |
236 | build_search_tree (ADDR_RANGE *ar) | |
237 | { | |
238 | /* ??? Simple version for now. */ | |
239 | ADDR_SUBRANGE *asr,**asrtab; | |
240 | unsigned int i, n; | |
241 | ||
242 | for (n = 0, asr = ar->ranges; asr != NULL; ++n, asr = asr->next) | |
243 | continue; | |
244 | asrtab = (ADDR_SUBRANGE **) xmalloc (n * sizeof (ADDR_SUBRANGE *)); | |
245 | for (i = 0, asr = ar->ranges; i < n; ++i, asr = asr->next) | |
246 | asrtab[i] = asr; | |
247 | ar->range_tree = build_tree_1 (asrtab, n); | |
248 | free (asrtab); | |
249 | } | |
250 | ||
ef986697 SH |
251 | INLINE_SIM_ARANGE\ |
252 | (void) | |
c906108c SS |
253 | sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end) |
254 | { | |
255 | frob_range (ar, start, end, 0); | |
256 | ||
257 | /* Rebuild the search tree. */ | |
258 | /* ??? Instead of rebuilding it here it could be done in a module resume | |
259 | handler, say by first checking for a `changed' flag, assuming of course | |
260 | this would never be done while the simulation is running. */ | |
261 | free_search_tree (ar->range_tree); | |
262 | build_search_tree (ar); | |
263 | } | |
264 | ||
ef986697 SH |
265 | INLINE_SIM_ARANGE\ |
266 | (void) | |
c906108c SS |
267 | sim_addr_range_delete (ADDR_RANGE *ar, address_word start, address_word end) |
268 | { | |
269 | frob_range (ar, start, end, 1); | |
270 | ||
271 | /* Rebuild the search tree. */ | |
272 | /* ??? Instead of rebuilding it here it could be done in a module resume | |
273 | handler, say by first checking for a `changed' flag, assuming of course | |
274 | this would never be done while the simulation is running. */ | |
275 | free_search_tree (ar->range_tree); | |
276 | build_search_tree (ar); | |
277 | } | |
278 | ||
ef986697 SH |
279 | INLINE_SIM_ARANGE\ |
280 | (int) | |
c906108c SS |
281 | sim_addr_range_hit_p (ADDR_RANGE *ar, address_word addr) |
282 | { | |
283 | ADDR_RANGE_TREE *t = ar->range_tree; | |
284 | ||
285 | while (t != NULL) | |
286 | { | |
287 | if (addr < t->start) | |
288 | t = t->lower; | |
289 | else if (addr > t->end) | |
290 | t = t->higher; | |
291 | else | |
292 | return 1; | |
293 | } | |
294 | return 0; | |
295 | } | |
296 | ||
ef986697 | 297 | #endif /* _SIM_ARANGE_C_ */ |