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