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