1 /* Address ranges. 2 Copyright (C) 1998-2024 Free Software Foundation, Inc. 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 9 the Free Software Foundation; either version 3 of the License, or 10 (at your option) any later version. 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 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/>. */ 19 20 #ifndef _SIM_ARANGE_C_ 21 #define _SIM_ARANGE_C_ 22 23 /* This must come before any other includes. */ 24 #include "defs.h" 25 26 #include <stdlib.h> 27 #include <string.h> 28 29 #include "libiberty.h" 30 31 #include "sim-basics.h" 32 #include "sim-arange.h" 33 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) 190 free (new_asr); 191 if (new_asr2) 192 free (new_asr2); 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 251 INLINE_SIM_ARANGE\ 252 (void) 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 265 INLINE_SIM_ARANGE\ 266 (void) 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 279 INLINE_SIM_ARANGE\ 280 (int) 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 297 #endif /* _SIM_ARANGE_C_ */ 298