sim/common/sim-arange.c

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