sim/common/sim-arange.c

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