[deliverable/binutils-gdb.git] / sim / common / sim-arange.c

/* 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 "libiberty.h"
#include "sim-basics.h"
#include "sim-assert.h"

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

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

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

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