1/* Address ranges. 2 Copyright (C) 1998, 2007 Free Software Foundation, Inc. 3 Contributed by Cygnus Solutions. 4 5This file is part of the GNU Simulators. 6 7This program is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3 of the License, or 10(at your option) any later version. 11 12This program is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along 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 42static void 43insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr) 44{ 45 asr->next = *pos; 46 *pos = asr; 47} 48 49/* Delete a range. */ 50 51static void 52delete_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 67static void 68frob_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 203static void 204free_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 217static ADDR_RANGE_TREE * 218build_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 241static void 242build_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 257void 258sim_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 270void 271sim_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 287SIM_ARANGE_INLINE int 288sim_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