1 /* Address ranges. 2 Copyright (C) 1998-2020 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 #include "libiberty.h" 24 #include "sim-basics.h" 25 #include "sim-arange.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 /* Insert a range. */ 36 37 static void 38 insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr) 39 { 40 asr->next = *pos; 41 *pos = asr; 42 } 43 44 /* Delete a range. */ 45 46 static void 47 delete_range (ADDR_SUBRANGE **thisasrp) 48 { 49 ADDR_SUBRANGE *thisasr; 50 51 thisasr = *thisasrp; 52 *thisasrp = thisasr->next; 53 54 free (thisasr); 55 } 56 57 /* Add or delete an address range. 58 This code was borrowed from linux's locks.c:posix_lock_file(). 59 ??? Todo: Given our simpler needs this could be simplified 60 (split into two fns). */ 61 62 static void 63 frob_range (ADDR_RANGE *ar, address_word start, address_word end, int delete_p) 64 { 65 ADDR_SUBRANGE *asr; 66 ADDR_SUBRANGE *new_asr, *new_asr2; 67 ADDR_SUBRANGE *left = NULL; 68 ADDR_SUBRANGE *right = NULL; 69 ADDR_SUBRANGE **before; 70 ADDR_SUBRANGE init_caller; 71 ADDR_SUBRANGE *caller = &init_caller; 72 int added_p = 0; 73 74 memset (caller, 0, sizeof (ADDR_SUBRANGE)); 75 new_asr = ZALLOC (ADDR_SUBRANGE); 76 new_asr2 = ZALLOC (ADDR_SUBRANGE); 77 78 caller->start = start; 79 caller->end = end; 80 before = &ar->ranges; 81 82 while ((asr = *before) != NULL) 83 { 84 if (! delete_p) 85 { 86 /* Try next range if current range preceeds new one and not 87 adjacent or overlapping. */ 88 if (asr->end < caller->start - 1) 89 goto next_range; 90 91 /* Break out if new range preceeds current one and not 92 adjacent or overlapping. */ 93 if (asr->start > caller->end + 1) 94 break; 95 96 /* If we come here, the new and current ranges are adjacent or 97 overlapping. Make one range yielding from the lower start address 98 of both ranges to the higher end address. */ 99 if (asr->start > caller->start) 100 asr->start = caller->start; 101 else 102 caller->start = asr->start; 103 if (asr->end < caller->end) 104 asr->end = caller->end; 105 else 106 caller->end = asr->end; 107 108 if (added_p) 109 { 110 delete_range (before); 111 continue; 112 } 113 caller = asr; 114 added_p = 1; 115 } 116 else /* deleting a range */ 117 { 118 /* Try next range if current range preceeds new one. */ 119 if (asr->end < caller->start) 120 goto next_range; 121 122 /* Break out if new range preceeds current one. */ 123 if (asr->start > caller->end) 124 break; 125 126 added_p = 1; 127 128 if (asr->start < caller->start) 129 left = asr; 130 131 /* If the next range in the list has a higher end 132 address than the new one, insert the new one here. */ 133 if (asr->end > caller->end) 134 { 135 right = asr; 136 break; 137 } 138 if (asr->start >= caller->start) 139 { 140 /* The new range completely replaces an old 141 one (This may happen several times). */ 142 if (added_p) 143 { 144 delete_range (before); 145 continue; 146 } 147 148 /* Replace the old range with the new one. */ 149 asr->start = caller->start; 150 asr->end = caller->end; 151 caller = asr; 152 added_p = 1; 153 } 154 } 155 156 /* Go on to next range. */ 157 next_range: 158 before = &asr->next; 159 } 160 161 if (!added_p) 162 { 163 if (delete_p) 164 goto out; 165 new_asr->start = caller->start; 166 new_asr->end = caller->end; 167 insert_range (before, new_asr); 168 new_asr = NULL; 169 } 170 if (right) 171 { 172 if (left == right) 173 { 174 /* The new range breaks the old one in two pieces, 175 so we have to use the second new range. */ 176 new_asr2->start = right->start; 177 new_asr2->end = right->end; 178 left = new_asr2; 179 insert_range (before, left); 180 new_asr2 = NULL; 181 } 182 right->start = caller->end + 1; 183 } 184 if (left) 185 { 186 left->end = caller->start - 1; 187 } 188 189 out: 190 if (new_asr) 191 free (new_asr); 192 if (new_asr2) 193 free (new_asr2); 194 } 195 196 /* Free T and all subtrees. */ 197 198 static void 199 free_search_tree (ADDR_RANGE_TREE *t) 200 { 201 if (t != NULL) 202 { 203 free_search_tree (t->lower); 204 free_search_tree (t->higher); 205 free (t); 206 } 207 } 208 209 /* Subroutine of build_search_tree to recursively build a balanced tree. 210 ??? It's not an optimum tree though. */ 211 212 static ADDR_RANGE_TREE * 213 build_tree_1 (ADDR_SUBRANGE **asrtab, unsigned int n) 214 { 215 unsigned int mid = n / 2; 216 ADDR_RANGE_TREE *t; 217 218 if (n == 0) 219 return NULL; 220 t = (ADDR_RANGE_TREE *) xmalloc (sizeof (ADDR_RANGE_TREE)); 221 t->start = asrtab[mid]->start; 222 t->end = asrtab[mid]->end; 223 if (mid != 0) 224 t->lower = build_tree_1 (asrtab, mid); 225 else 226 t->lower = NULL; 227 if (n > mid + 1) 228 t->higher = build_tree_1 (asrtab + mid + 1, n - mid - 1); 229 else 230 t->higher = NULL; 231 return t; 232 } 233 234 /* Build a search tree for address range AR. */ 235 236 static void 237 build_search_tree (ADDR_RANGE *ar) 238 { 239 /* ??? Simple version for now. */ 240 ADDR_SUBRANGE *asr,**asrtab; 241 unsigned int i, n; 242 243 for (n = 0, asr = ar->ranges; asr != NULL; ++n, asr = asr->next) 244 continue; 245 asrtab = (ADDR_SUBRANGE **) xmalloc (n * sizeof (ADDR_SUBRANGE *)); 246 for (i = 0, asr = ar->ranges; i < n; ++i, asr = asr->next) 247 asrtab[i] = asr; 248 ar->range_tree = build_tree_1 (asrtab, n); 249 free (asrtab); 250 } 251 252 INLINE_SIM_ARANGE\ 253 (void) 254 sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end) 255 { 256 frob_range (ar, start, end, 0); 257 258 /* Rebuild the search tree. */ 259 /* ??? Instead of rebuilding it here it could be done in a module resume 260 handler, say by first checking for a `changed' flag, assuming of course 261 this would never be done while the simulation is running. */ 262 free_search_tree (ar->range_tree); 263 build_search_tree (ar); 264 } 265 266 INLINE_SIM_ARANGE\ 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 INLINE_SIM_ARANGE\ 281 (int) 282 sim_addr_range_hit_p (ADDR_RANGE *ar, address_word addr) 283 { 284 ADDR_RANGE_TREE *t = ar->range_tree; 285 286 while (t != NULL) 287 { 288 if (addr < t->start) 289 t = t->lower; 290 else if (addr > t->end) 291 t = t->higher; 292 else 293 return 1; 294 } 295 return 0; 296 } 297 298 #endif /* _SIM_ARANGE_C_ */ 299