1 /* Address ranges. 2 Copyright (C) 1998-2019 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 /* Tell sim-arange.h it's us. */ 21 #define SIM_ARANGE_C 22 23 #include "libiberty.h" 24 #include "sim-basics.h" 25 #include "sim-assert.h" 26 27 #ifdef HAVE_STDLIB_H 28 #include <stdlib.h> 29 #endif 30 31 #ifdef HAVE_STRING_H 32 #include <string.h> 33 #endif 34 35 #ifdef SIM_ARANGE_C_INCLUDED 36 37 /* Insert a range. */ 38 39 static void 40 insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr) 41 { 42 asr->next = *pos; 43 *pos = asr; 44 } 45 46 /* Delete a range. */ 47 48 static void 49 delete_range (ADDR_SUBRANGE **thisasrp) 50 { 51 ADDR_SUBRANGE *thisasr; 52 53 thisasr = *thisasrp; 54 *thisasrp = thisasr->next; 55 56 free (thisasr); 57 } 58 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). */ 63 64 static void 65 frob_range (ADDR_RANGE *ar, address_word start, address_word end, int delete_p) 66 { 67 ADDR_SUBRANGE *asr; 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; 74 int added_p = 0; 75 76 memset (caller, 0, sizeof (ADDR_SUBRANGE)); 77 new_asr = ZALLOC (ADDR_SUBRANGE); 78 new_asr2 = ZALLOC (ADDR_SUBRANGE); 79 80 caller->start = start; 81 caller->end = end; 82 before = &ar->ranges; 83 84 while ((asr = *before) != NULL) 85 { 86 if (! delete_p) 87 { 88 /* Try next range if current range preceeds new one and not 89 adjacent or overlapping. */ 90 if (asr->end < caller->start - 1) 91 goto next_range; 92 93 /* Break out if new range preceeds current one and not 94 adjacent or overlapping. */ 95 if (asr->start > caller->end + 1) 96 break; 97 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; 103 else 104 caller->start = asr->start; 105 if (asr->end < caller->end) 106 asr->end = caller->end; 107 else 108 caller->end = asr->end; 109 110 if (added_p) 111 { 112 delete_range (before); 113 continue; 114 } 115 caller = asr; 116 added_p = 1; 117 } 118 else /* deleting a range */ 119 { 120 /* Try next range if current range preceeds new one. */ 121 if (asr->end < caller->start) 122 goto next_range; 123 124 /* Break out if new range preceeds current one. */ 125 if (asr->start > caller->end) 126 break; 127 128 added_p = 1; 129 130 if (asr->start < caller->start) 131 left = asr; 132 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) 136 { 137 right = asr; 138 break; 139 } 140 if (asr->start >= caller->start) 141 { 142 /* The new range completely replaces an old 143 one (This may happen several times). */ 144 if (added_p) 145 { 146 delete_range (before); 147 continue; 148 } 149 150 /* Replace the old range with the new one. */ 151 asr->start = caller->start; 152 asr->end = caller->end; 153 caller = asr; 154 added_p = 1; 155 } 156 } 157 158 /* Go on to next range. */ 159 next_range: 160 before = &asr->next; 161 } 162 163 if (!added_p) 164 { 165 if (delete_p) 166 goto out; 167 new_asr->start = caller->start; 168 new_asr->end = caller->end; 169 insert_range (before, new_asr); 170 new_asr = NULL; 171 } 172 if (right) 173 { 174 if (left == right) 175 { 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; 180 left = new_asr2; 181 insert_range (before, left); 182 new_asr2 = NULL; 183 } 184 right->start = caller->end + 1; 185 } 186 if (left) 187 { 188 left->end = caller->start - 1; 189 } 190 191 out: 192 if (new_asr) 193 free (new_asr); 194 if (new_asr2) 195 free (new_asr2); 196 } 197 198 /* Free T and all subtrees. */ 199 200 static void 201 free_search_tree (ADDR_RANGE_TREE *t) 202 { 203 if (t != NULL) 204 { 205 free_search_tree (t->lower); 206 free_search_tree (t->higher); 207 free (t); 208 } 209 } 210 211 /* Subroutine of build_search_tree to recursively build a balanced tree. 212 ??? It's not an optimum tree though. */ 213 214 static ADDR_RANGE_TREE * 215 build_tree_1 (ADDR_SUBRANGE **asrtab, unsigned int n) 216 { 217 unsigned int mid = n / 2; 218 ADDR_RANGE_TREE *t; 219 220 if (n == 0) 221 return NULL; 222 t = (ADDR_RANGE_TREE *) xmalloc (sizeof (ADDR_RANGE_TREE)); 223 t->start = asrtab[mid]->start; 224 t->end = asrtab[mid]->end; 225 if (mid != 0) 226 t->lower = build_tree_1 (asrtab, mid); 227 else 228 t->lower = NULL; 229 if (n > mid + 1) 230 t->higher = build_tree_1 (asrtab + mid + 1, n - mid - 1); 231 else 232 t->higher = NULL; 233 return t; 234 } 235 236 /* Build a search tree for address range AR. */ 237 238 static void 239 build_search_tree (ADDR_RANGE *ar) 240 { 241 /* ??? Simple version for now. */ 242 ADDR_SUBRANGE *asr,**asrtab; 243 unsigned int i, n; 244 245 for (n = 0, asr = ar->ranges; asr != NULL; ++n, asr = asr->next) 246 continue; 247 asrtab = (ADDR_SUBRANGE **) xmalloc (n * sizeof (ADDR_SUBRANGE *)); 248 for (i = 0, asr = ar->ranges; i < n; ++i, asr = asr->next) 249 asrtab[i] = asr; 250 ar->range_tree = build_tree_1 (asrtab, n); 251 free (asrtab); 252 } 253 254 void 255 sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end) 256 { 257 frob_range (ar, start, end, 0); 258 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); 265 } 266 267 void 268 sim_addr_range_delete (ADDR_RANGE *ar, address_word start, address_word end) 269 { 270 frob_range (ar, start, end, 1); 271 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); 278 } 279 280 #else /* SIM_ARANGE_C_INCLUDED */ 281 282 SIM_ARANGE_INLINE int 283 sim_addr_range_hit_p (ADDR_RANGE *ar, address_word addr) 284 { 285 ADDR_RANGE_TREE *t = ar->range_tree; 286 287 while (t != NULL) 288 { 289 if (addr < t->start) 290 t = t->lower; 291 else if (addr > t->end) 292 t = t->higher; 293 else 294 return 1; 295 } 296 return 0; 297 } 298 299 #endif /* SIM_ARANGE_C_INCLUDED */ 300