sim/common/sim-arange.c - binutils-gdb - Git at Google

 /* Address ranges.
    Copyright (C) 1998-2021 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 3 of the License, 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, see <http://www.gnu.org/licenses/>.  */

 #ifndef _SIM_ARANGE_C_
 #define _SIM_ARANGE_C_

 /* This must come before any other includes.  */
 #include "defs.h"

 #include "libiberty.h"
 #include "sim-basics.h"
 #include "sim-arange.h"

 #include <stdlib.h>
 #include <string.h>

 /* 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);
 }

 INLINE_SIM_ARANGE\
 (void)
 sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end)
 {
   frob_range (ar, start, end, 0);

   /* Rebuild the search tree.  */
   /* ??? Instead of rebuilding it here it could be done in a module resume
      handler, say by first checking for a `changed' flag, assuming of course
      this would never be done while the simulation is running.  */
   free_search_tree (ar->range_tree);
   build_search_tree (ar);
 }

 INLINE_SIM_ARANGE\
 (void)
 sim_addr_range_delete (ADDR_RANGE *ar, address_word start, address_word end)
 {
   frob_range (ar, start, end, 1);

   /* Rebuild the search tree.  */
   /* ??? Instead of rebuilding it here it could be done in a module resume
      handler, say by first checking for a `changed' flag, assuming of course
      this would never be done while the simulation is running.  */
   free_search_tree (ar->range_tree);
   build_search_tree (ar);
 }

 INLINE_SIM_ARANGE\
 (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 /* _SIM_ARANGE_C_ */
	/* Address ranges.
	Copyright (C) 1998-2021 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 3 of the License, 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, see <http://www.gnu.org/licenses/>. */

	#ifndef _SIM_ARANGE_C_
	#define _SIM_ARANGE_C_

	/* This must come before any other includes. */
	#include "defs.h"

	#include "libiberty.h"
	#include "sim-basics.h"
	#include "sim-arange.h"

	#include <stdlib.h>
	#include <string.h>

	/* 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);
	}

	INLINE_SIM_ARANGE\
	(void)
	sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end)
	{
	frob_range (ar, start, end, 0);

	/* Rebuild the search tree. */
	/* ??? Instead of rebuilding it here it could be done in a module resume
	handler, say by first checking for a `changed' flag, assuming of course
	this would never be done while the simulation is running. */
	free_search_tree (ar->range_tree);
	build_search_tree (ar);
	}

	INLINE_SIM_ARANGE\
	(void)
	sim_addr_range_delete (ADDR_RANGE *ar, address_word start, address_word end)
	{
	frob_range (ar, start, end, 1);

	/* Rebuild the search tree. */
	/* ??? Instead of rebuilding it here it could be done in a module resume
	handler, say by first checking for a `changed' flag, assuming of course
	this would never be done while the simulation is running. */
	free_search_tree (ar->range_tree);
	build_search_tree (ar);
	}

	INLINE_SIM_ARANGE\
	(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 /* _SIM_ARANGE_C_ */