2 Copyright (C) 1998 Free Software Foundation, Inc.
3 Contributed by Cygnus Solutions.
5 This file is part of the GNU Simulators.
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
9 the Free Software Foundation; either version 2, or (at your option)
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.
17 You should have received a copy of the GNU General Public License along
18 with this program; if not, write to the Free Software Foundation, Inc.,
19 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
21 /* Tell sim-arange.h it's us. */
24 #include "libiberty.h"
25 #include "sim-basics.h"
26 #include "sim-assert.h"
32 #define DEFINE_INLINE_P (! defined (SIM_ARANGE_C_INCLUDED))
33 #define DEFINE_NON_INLINE_P defined (SIM_ARANGE_C_INCLUDED)
35 #if DEFINE_NON_INLINE_P
40 insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr)
49 delete_range (ADDR_SUBRANGE **thisasrp)
51 ADDR_SUBRANGE *thisasr;
54 *thisasrp = thisasr->next;
59 /* Add or delete an address range.
60 This code was borrowed from linux's locks.c:posix_lock_file().
61 ??? Todo: Given our simpler needs this could be simplified
62 (split into two fns). */
65 frob_range (ADDR_RANGE *ar, address_word start, address_word end, int delete_p)
68 ADDR_SUBRANGE *new_asr, *new_asr2;
69 ADDR_SUBRANGE *left = NULL;
70 ADDR_SUBRANGE *right = NULL;
71 ADDR_SUBRANGE **before;
72 ADDR_SUBRANGE init_caller;
73 ADDR_SUBRANGE *caller = &init_caller;
76 memset (caller, 0, sizeof (ADDR_SUBRANGE));
77 new_asr = ZALLOC (ADDR_SUBRANGE);
78 new_asr2 = ZALLOC (ADDR_SUBRANGE);
80 caller->start = start;
84 while ((asr = *before) != NULL)
88 /* Try next range if current range preceeds new one and not
89 adjacent or overlapping. */
90 if (asr->end < caller->start - 1)
93 /* Break out if new range preceeds current one and not
94 adjacent or overlapping. */
95 if (asr->start > caller->end + 1)
98 /* If we come here, the new and current ranges are adjacent or
99 overlapping. Make one range yielding from the lower start address
100 of both ranges to the higher end address. */
101 if (asr->start > caller->start)
102 asr->start = caller->start;
104 caller->start = asr->start;
105 if (asr->end < caller->end)
106 asr->end = caller->end;
108 caller->end = asr->end;
112 delete_range (before);
118 else /* deleting a range */
120 /* Try next range if current range preceeds new one. */
121 if (asr->end < caller->start)
124 /* Break out if new range preceeds current one. */
125 if (asr->start > caller->end)
130 if (asr->start < caller->start)
133 /* If the next range in the list has a higher end
134 address than the new one, insert the new one here. */
135 if (asr->end > caller->end)
140 if (asr->start >= caller->start)
142 /* The new range completely replaces an old
143 one (This may happen several times). */
146 delete_range (before);
150 /* Replace the old range with the new one. */
151 asr->start = caller->start;
152 asr->end = caller->end;
158 /* Go on to next range. */
167 new_asr->start = caller->start;
168 new_asr->end = caller->end;
169 insert_range (before, new_asr);
176 /* The new range breaks the old one in two pieces,
177 so we have to use the second new range. */
178 new_asr2->start = right->start;
179 new_asr2->end = right->end;
181 insert_range (before, left);
184 right->start = caller->end + 1;
188 left->end = caller->start - 1;
198 /* Free T and all subtrees. */
201 free_search_tree (ADDR_RANGE_TREE *t)
205 free_search_tree (t->lower);
206 free_search_tree (t->higher);
211 /* Subroutine of build_search_tree to recursively build a balanced tree.
212 ??? It's not an optimum tree though. */
214 static ADDR_RANGE_TREE *
215 build_tree_1 (ADDR_SUBRANGE **asrtab, unsigned int n)
217 unsigned int mid = n / 2;
222 t = (ADDR_RANGE_TREE *) xmalloc (sizeof (ADDR_RANGE_TREE));
223 t->start = asrtab[mid]->start;
224 t->end = asrtab[mid]->end;
226 t->lower = build_tree_1 (asrtab, mid);
230 t->higher = build_tree_1 (asrtab + mid + 1, n - mid - 1);
236 /* Build a search tree for address range AR. */
239 build_search_tree (ADDR_RANGE *ar)
241 /* ??? Simple version for now. */
242 ADDR_SUBRANGE *asr,**asrtab;
245 for (n = 0, asr = ar->ranges; asr != NULL; ++n, asr = asr->next)
247 asrtab = (ADDR_SUBRANGE **) xmalloc (n * sizeof (ADDR_SUBRANGE *));
248 for (i = 0, asr = ar->ranges; i < n; ++i, asr = asr->next)
250 ar->range_tree = build_tree_1 (asrtab, n);
255 sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end)
257 frob_range (ar, start, end, 0);
259 /* Rebuild the search tree. */
260 /* ??? Instead of rebuilding it here it could be done in a module resume
261 handler, say by first checking for a `changed' flag, assuming of course
262 this would never be done while the simulation is running. */
263 free_search_tree (ar->range_tree);
264 build_search_tree (ar);
268 sim_addr_range_delete (ADDR_RANGE *ar, address_word start, address_word end)
270 frob_range (ar, start, end, 1);
272 /* Rebuild the search tree. */
273 /* ??? Instead of rebuilding it here it could be done in a module resume
274 handler, say by first checking for a `changed' flag, assuming of course
275 this would never be done while the simulation is running. */
276 free_search_tree (ar->range_tree);
277 build_search_tree (ar);
280 #endif /* DEFINE_NON_INLINE_P */
284 SIM_ARANGE_INLINE int
285 sim_addr_range_hit_p (ADDR_RANGE *ar, address_word addr)
287 ADDR_RANGE_TREE *t = ar->range_tree;
293 else if (addr > t->end)
301 #endif /* DEFINE_INLINE_P */