sim/common/sim-arange.c

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