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