2 Copyright (C) 1998-2021 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 3 of the License, or
10 (at your option) any later version.
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
18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20 #ifndef _SIM_ARANGE_C_
21 #define _SIM_ARANGE_C_
23 /* This must come before any other includes. */
26 #include "libiberty.h"
27 #include "sim-basics.h"
28 #include "sim-arange.h"
36 insert_range (ADDR_SUBRANGE
**pos
, ADDR_SUBRANGE
*asr
)
45 delete_range (ADDR_SUBRANGE
**thisasrp
)
47 ADDR_SUBRANGE
*thisasr
;
50 *thisasrp
= thisasr
->next
;
55 /* Add or delete an address range.
56 This code was borrowed from linux's locks.c:posix_lock_file().
57 ??? Todo: Given our simpler needs this could be simplified
58 (split into two fns). */
61 frob_range (ADDR_RANGE
*ar
, address_word start
, address_word end
, int delete_p
)
64 ADDR_SUBRANGE
*new_asr
, *new_asr2
;
65 ADDR_SUBRANGE
*left
= NULL
;
66 ADDR_SUBRANGE
*right
= NULL
;
67 ADDR_SUBRANGE
**before
;
68 ADDR_SUBRANGE init_caller
;
69 ADDR_SUBRANGE
*caller
= &init_caller
;
72 memset (caller
, 0, sizeof (ADDR_SUBRANGE
));
73 new_asr
= ZALLOC (ADDR_SUBRANGE
);
74 new_asr2
= ZALLOC (ADDR_SUBRANGE
);
76 caller
->start
= start
;
80 while ((asr
= *before
) != NULL
)
84 /* Try next range if current range preceeds new one and not
85 adjacent or overlapping. */
86 if (asr
->end
< caller
->start
- 1)
89 /* Break out if new range preceeds current one and not
90 adjacent or overlapping. */
91 if (asr
->start
> caller
->end
+ 1)
94 /* If we come here, the new and current ranges are adjacent or
95 overlapping. Make one range yielding from the lower start address
96 of both ranges to the higher end address. */
97 if (asr
->start
> caller
->start
)
98 asr
->start
= caller
->start
;
100 caller
->start
= asr
->start
;
101 if (asr
->end
< caller
->end
)
102 asr
->end
= caller
->end
;
104 caller
->end
= asr
->end
;
108 delete_range (before
);
114 else /* deleting a range */
116 /* Try next range if current range preceeds new one. */
117 if (asr
->end
< caller
->start
)
120 /* Break out if new range preceeds current one. */
121 if (asr
->start
> caller
->end
)
126 if (asr
->start
< caller
->start
)
129 /* If the next range in the list has a higher end
130 address than the new one, insert the new one here. */
131 if (asr
->end
> caller
->end
)
136 if (asr
->start
>= caller
->start
)
138 /* The new range completely replaces an old
139 one (This may happen several times). */
142 delete_range (before
);
146 /* Replace the old range with the new one. */
147 asr
->start
= caller
->start
;
148 asr
->end
= caller
->end
;
154 /* Go on to next range. */
163 new_asr
->start
= caller
->start
;
164 new_asr
->end
= caller
->end
;
165 insert_range (before
, new_asr
);
172 /* The new range breaks the old one in two pieces,
173 so we have to use the second new range. */
174 new_asr2
->start
= right
->start
;
175 new_asr2
->end
= right
->end
;
177 insert_range (before
, left
);
180 right
->start
= caller
->end
+ 1;
184 left
->end
= caller
->start
- 1;
194 /* Free T and all subtrees. */
197 free_search_tree (ADDR_RANGE_TREE
*t
)
201 free_search_tree (t
->lower
);
202 free_search_tree (t
->higher
);
207 /* Subroutine of build_search_tree to recursively build a balanced tree.
208 ??? It's not an optimum tree though. */
210 static ADDR_RANGE_TREE
*
211 build_tree_1 (ADDR_SUBRANGE
**asrtab
, unsigned int n
)
213 unsigned int mid
= n
/ 2;
218 t
= (ADDR_RANGE_TREE
*) xmalloc (sizeof (ADDR_RANGE_TREE
));
219 t
->start
= asrtab
[mid
]->start
;
220 t
->end
= asrtab
[mid
]->end
;
222 t
->lower
= build_tree_1 (asrtab
, mid
);
226 t
->higher
= build_tree_1 (asrtab
+ mid
+ 1, n
- mid
- 1);
232 /* Build a search tree for address range AR. */
235 build_search_tree (ADDR_RANGE
*ar
)
237 /* ??? Simple version for now. */
238 ADDR_SUBRANGE
*asr
,**asrtab
;
241 for (n
= 0, asr
= ar
->ranges
; asr
!= NULL
; ++n
, asr
= asr
->next
)
243 asrtab
= (ADDR_SUBRANGE
**) xmalloc (n
* sizeof (ADDR_SUBRANGE
*));
244 for (i
= 0, asr
= ar
->ranges
; i
< n
; ++i
, asr
= asr
->next
)
246 ar
->range_tree
= build_tree_1 (asrtab
, n
);
252 sim_addr_range_add (ADDR_RANGE
*ar
, address_word start
, address_word end
)
254 frob_range (ar
, start
, end
, 0);
256 /* Rebuild the search tree. */
257 /* ??? Instead of rebuilding it here it could be done in a module resume
258 handler, say by first checking for a `changed' flag, assuming of course
259 this would never be done while the simulation is running. */
260 free_search_tree (ar
->range_tree
);
261 build_search_tree (ar
);
266 sim_addr_range_delete (ADDR_RANGE
*ar
, address_word start
, address_word end
)
268 frob_range (ar
, start
, end
, 1);
270 /* Rebuild the search tree. */
271 /* ??? Instead of rebuilding it here it could be done in a module resume
272 handler, say by first checking for a `changed' flag, assuming of course
273 this would never be done while the simulation is running. */
274 free_search_tree (ar
->range_tree
);
275 build_search_tree (ar
);
280 sim_addr_range_hit_p (ADDR_RANGE
*ar
, address_word addr
)
282 ADDR_RANGE_TREE
*t
= ar
->range_tree
;
288 else if (addr
> t
->end
)
296 #endif /* _SIM_ARANGE_C_ */