address range support

1 files changed, 290 insertions, 0 deletions

diff --git a/sim/common/sim-arange.c b/sim/common/sim-arange.c
new file mode 100644
index 0000000..43c5789
--- /dev/null
+++ b/sim/common/sim-arange.c
@@ -0,0 +1,290 @@
+/* Address ranges.
+   Copyright (C) 1998 Free Software Foundation, Inc.
+   Contributed by Cygnus Solutions.
+
+This file is part of the GNU Simulators.
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along
+with this program; if not, write to the Free Software Foundation, Inc.,
+59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Tell sim-arange.h it's us.  */
+#define SIM_ARANGE_C
+
+#include "sim-basics.h"
+#include "sim-assert.h"
+
+#define DEFINE_INLINE_P (! defined (SIM_ARANGE_C_INCLUDED))
+#define DEFINE_NON_INLINE_P defined (SIM_ARANGE_C_INCLUDED)
+
+#if DEFINE_NON_INLINE_P
+
+/* Insert a range.  */
+
+static void
+insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr)
+{
+  asr->next = *pos;
+  *pos = asr;
+}
+
+/* Delete a range.  */
+
+static void
+delete_range (ADDR_SUBRANGE **thisasrp)
+{
+  ADDR_SUBRANGE *thisasr;
+
+  thisasr = *thisasrp;
+  *thisasrp = thisasr->next;
+
+  free (thisasr);
+}
+
+/* Add or delete an address range.
+   This code was borrowed from linux's locks.c:posix_lock_file().
+   ??? Todo: Given our simpler needs this could be simplified
+   (split into two fns).  */
+
+static void
+frob_range (ADDR_RANGE *ar, address_word start, address_word end, int delete_p)
+{
+  ADDR_SUBRANGE *asr;
+  ADDR_SUBRANGE *new_asr, *new_asr2;
+  ADDR_SUBRANGE *left = NULL;
+  ADDR_SUBRANGE *right = NULL;
+  ADDR_SUBRANGE **before;
+  ADDR_SUBRANGE init_caller;
+  ADDR_SUBRANGE *caller = &init_caller;
+  int added_p = 0;
+
+  memset (caller, 0, sizeof (ADDR_SUBRANGE));
+  new_asr = ZALLOC (ADDR_SUBRANGE);
+  new_asr2 = ZALLOC (ADDR_SUBRANGE);
+
+  caller->start = start;
+  caller->end = end;
+  before = &ar->ranges;
+
+  while ((asr = *before) != NULL)
+    {
+      if (! delete_p)
+	{
+	  /* Try next range if current range preceeds new one and not
+	     adjacent or overlapping.  */
+	  if (asr->end < caller->start - 1)
+	    goto next_range;
+
+	  /* Break out if new range preceeds current one and not
+	     adjacent or overlapping.  */
+	  if (asr->start > caller->end + 1)
+	    break;
+
+	  /* If we come here, the new and current ranges are adjacent or
+	     overlapping. Make one range yielding from the lower start address
+	     of both ranges to the higher end address.  */
+	  if (asr->start > caller->start)
+	    asr->start = caller->start;
+	  else
+	    caller->start = asr->start;
+	  if (asr->end < caller->end)
+	    asr->end = caller->end;
+	  else
+	    caller->end = asr->end;
+
+	  if (added_p)
+	    {
+	      delete_range (before);
+	      continue;
+	    }
+	  caller = asr;
+	  added_p = 1;
+	}
+      else /* deleting a range */
+	{
+	  /* Try next range if current range preceeds new one.  */
+	  if (asr->end < caller->start)
+	    goto next_range;
+
+	  /* Break out if new range preceeds current one.  */
+	  if (asr->start > caller->end)
+	    break;
+
+	  added_p = 1;
+
+	  if (asr->start < caller->start)
+	    left = asr;
+
+	  /* If the next range in the list has a higher end
+	     address than the new one, insert the new one here.  */
+	  if (asr->end > caller->end)
+	    {
+	      right = asr;
+	      break;
+	    }
+	  if (asr->start >= caller->start)
+	    {
+	      /* The new range completely replaces an old
+	         one (This may happen several times).  */
+	      if (added_p)
+		{
+		  delete_range (before);
+		  continue;
+		}
+
+	      /* Replace the old range with the new one.  */
+	      asr->start = caller->start;
+	      asr->end = caller->end;
+	      caller = asr;
+	      added_p = 1;
+	    }
+	}
+
+      /* Go on to next range.  */
+    next_range:
+      before = &asr->next;
+    }
+
+  if (!added_p)
+    {
+      if (delete_p)
+	goto out;
+      new_asr->start = caller->start;
+      new_asr->end = caller->end;
+      insert_range (before, new_asr);
+      new_asr = NULL;
+    }
+  if (right)
+    {
+      if (left == right)
+	{
+	  /* The new range breaks the old one in two pieces,
+	     so we have to use the second new range.  */
+	  new_asr2->start = right->start;
+	  new_asr2->end = right->end;
+	  left = new_asr2;
+	  insert_range (before, left);
+	  new_asr2 = NULL;
+	}
+      right->start = caller->end + 1;
+    }
+  if (left)
+    {
+      left->end = caller->start - 1;
+    }
+
+ out:
+  if (new_asr)
+    free(new_asr);
+  if (new_asr2)
+    free(new_asr2);
+}
+
+/* Free T and all subtrees.  */
+
+static void
+free_search_tree (ADDR_RANGE_TREE *t)
+{
+  if (t != NULL)
+    {
+      free_search_tree (t->lower);
+      free_search_tree (t->higher);
+      free (t);
+    }
+}
+
+/* Subroutine of build_search_tree to recursively build a balanced tree.
+   ??? It's not an optimum tree though.  */
+
+static ADDR_RANGE_TREE *
+build_tree_1 (ADDR_SUBRANGE **asrtab, unsigned int n)
+{
+  unsigned int mid = n / 2;
+  ADDR_RANGE_TREE *t;
+
+  if (n == 0)
+    return NULL;
+  t = (ADDR_RANGE_TREE *) xmalloc (sizeof (ADDR_RANGE_TREE));
+  t->start = asrtab[mid]->start;
+  t->end = asrtab[mid]->end;
+  if (mid != 0)
+    t->lower = build_tree_1 (asrtab, mid);
+  else
+    t->lower = NULL;
+  if (n > mid + 1)
+    t->higher = build_tree_1 (asrtab + mid + 1, n - mid - 1);
+  else
+    t->higher = NULL;
+  return t;
+}
+
+/* Build a search tree for address range AR.  */
+
+static void
+build_search_tree (ADDR_RANGE *ar)
+{
+  /* ??? Simple version for now.  */
+  ADDR_SUBRANGE *asr,**asrtab;
+  unsigned int i, n;
+
+  for (n = 0, asr = ar->ranges; asr != NULL; ++n, asr = asr->next)
+    continue;
+  asrtab = (ADDR_SUBRANGE **) xmalloc (n * sizeof (ADDR_SUBRANGE *));
+  for (i = 0, asr = ar->ranges; i < n; ++i, asr = asr->next)
+    asrtab[i] = asr;
+  ar->range_tree = build_tree_1 (asrtab, n);
+  free (asrtab);
+}
+
+void
+sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end)
+{
+  frob_range (ar, start, end, 0);
+
+  /* Rebuild the search tree.  */
+  free_search_tree (ar->range_tree);
+  build_search_tree (ar);
+}
+
+void
+sim_addr_range_delete (ADDR_RANGE *ar, address_word start, address_word end)
+{
+  frob_range (ar, start, end, 1);
+
+  /* Rebuild the search tree.  */
+  free_search_tree (ar->range_tree);
+  build_search_tree (ar);
+}
+
+#endif /* DEFINE_NON_INLINE_P */
+
+#if DEFINE_INLINE_P
+
+SIM_ARANGE_INLINE int
+sim_addr_range_hit_p (ADDR_RANGE *ar, address_word addr)
+{
+  ADDR_RANGE_TREE *t = ar->range_tree;
+
+  while (t != NULL)
+    {
+      if (addr < t->start)
+	t = t->lower;
+      else if (addr > t->end)
+	t = t->higher;
+      else
+	return 1;
+    }
+  return 0;
+}
+
+#endif /* DEFINE_INLINE_P */