1/* Address ranges.
2   Copyright (C) 1998, 2007, 2008, 2009, 2010, 2011
3   Free Software Foundation, Inc.
4   Contributed by Cygnus Solutions.
5
6This file is part of the GNU Simulators.
7
8This program is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3 of the License, or
11(at your option) any later version.
12
13This program is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
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
43static void
44insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr)
45{
46  asr->next = *pos;
47  *pos = asr;
48}
49
50/* Delete a range.  */
51
52static void
53delete_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
68static void
69frob_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
204static void
205free_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
218static ADDR_RANGE_TREE *
219build_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
242static void
243build_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
258void
259sim_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
271void
272sim_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
288SIM_ARANGE_INLINE int
289sim_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 */
306