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