sim/common/sim-arange.c

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