sim/common/sim-arange.c

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