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