1/* Address ranges.
2   Copyright (C) 1998, 2007 Free Software Foundation, Inc.
3   Contributed by Cygnus Solutions.
4
5This file is part of the GNU Simulators.
6
7This program is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3 of the License, or
10(at your option) any later version.
11
12This program is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
19
20/* Tell sim-arange.h it's us.  */
21#define SIM_ARANGE_C
22
23#include "libiberty.h"
24#include "sim-basics.h"
25#include "sim-assert.h"
26
27#ifdef HAVE_STDLIB_H
28#include <stdlib.h>
29#endif
30
31#ifdef HAVE_STRING_H
32#include <string.h>
33#endif
34
35#define DEFINE_INLINE_P (! defined (SIM_ARANGE_C_INCLUDED))
36#define DEFINE_NON_INLINE_P defined (SIM_ARANGE_C_INCLUDED)
37
38#if DEFINE_NON_INLINE_P
39
40/* Insert a range.  */
41
42static void
43insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr)
44{
45  asr->next = *pos;
46  *pos = asr;
47}
48
49/* Delete a range.  */
50
51static void
52delete_range (ADDR_SUBRANGE **thisasrp)
53{
54  ADDR_SUBRANGE *thisasr;
55
56  thisasr = *thisasrp;
57  *thisasrp = thisasr->next;
58
59  free (thisasr);
60}
61
62/* Add or delete an address range.
63   This code was borrowed from linux's locks.c:posix_lock_file().
64   ??? Todo: Given our simpler needs this could be simplified
65   (split into two fns).  */
66
67static void
68frob_range (ADDR_RANGE *ar, address_word start, address_word end, int delete_p)
69{
70  ADDR_SUBRANGE *asr;
71  ADDR_SUBRANGE *new_asr, *new_asr2;
72  ADDR_SUBRANGE *left = NULL;
73  ADDR_SUBRANGE *right = NULL;
74  ADDR_SUBRANGE **before;
75  ADDR_SUBRANGE init_caller;
76  ADDR_SUBRANGE *caller = &init_caller;
77  int added_p = 0;
78
79  memset (caller, 0, sizeof (ADDR_SUBRANGE));
80  new_asr = ZALLOC (ADDR_SUBRANGE);
81  new_asr2 = ZALLOC (ADDR_SUBRANGE);
82
83  caller->start = start;
84  caller->end = end;
85  before = &ar->ranges;
86
87  while ((asr = *before) != NULL)
88    {
89      if (! delete_p)
90	{
91	  /* Try next range if current range preceeds new one and not
92	     adjacent or overlapping.  */
93	  if (asr->end < caller->start - 1)
94	    goto next_range;
95
96	  /* Break out if new range preceeds current one and not
97	     adjacent or overlapping.  */
98	  if (asr->start > caller->end + 1)
99	    break;
100
101	  /* If we come here, the new and current ranges are adjacent or
102	     overlapping. Make one range yielding from the lower start address
103	     of both ranges to the higher end address.  */
104	  if (asr->start > caller->start)
105	    asr->start = caller->start;
106	  else
107	    caller->start = asr->start;
108	  if (asr->end < caller->end)
109	    asr->end = caller->end;
110	  else
111	    caller->end = asr->end;
112
113	  if (added_p)
114	    {
115	      delete_range (before);
116	      continue;
117	    }
118	  caller = asr;
119	  added_p = 1;
120	}
121      else /* deleting a range */
122	{
123	  /* Try next range if current range preceeds new one.  */
124	  if (asr->end < caller->start)
125	    goto next_range;
126
127	  /* Break out if new range preceeds current one.  */
128	  if (asr->start > caller->end)
129	    break;
130
131	  added_p = 1;
132
133	  if (asr->start < caller->start)
134	    left = asr;
135
136	  /* If the next range in the list has a higher end
137	     address than the new one, insert the new one here.  */
138	  if (asr->end > caller->end)
139	    {
140	      right = asr;
141	      break;
142	    }
143	  if (asr->start >= caller->start)
144	    {
145	      /* The new range completely replaces an old
146	         one (This may happen several times).  */
147	      if (added_p)
148		{
149		  delete_range (before);
150		  continue;
151		}
152
153	      /* Replace the old range with the new one.  */
154	      asr->start = caller->start;
155	      asr->end = caller->end;
156	      caller = asr;
157	      added_p = 1;
158	    }
159	}
160
161      /* Go on to next range.  */
162    next_range:
163      before = &asr->next;
164    }
165
166  if (!added_p)
167    {
168      if (delete_p)
169	goto out;
170      new_asr->start = caller->start;
171      new_asr->end = caller->end;
172      insert_range (before, new_asr);
173      new_asr = NULL;
174    }
175  if (right)
176    {
177      if (left == right)
178	{
179	  /* The new range breaks the old one in two pieces,
180	     so we have to use the second new range.  */
181	  new_asr2->start = right->start;
182	  new_asr2->end = right->end;
183	  left = new_asr2;
184	  insert_range (before, left);
185	  new_asr2 = NULL;
186	}
187      right->start = caller->end + 1;
188    }
189  if (left)
190    {
191      left->end = caller->start - 1;
192    }
193
194 out:
195  if (new_asr)
196    free(new_asr);
197  if (new_asr2)
198    free(new_asr2);
199}
200
201/* Free T and all subtrees.  */
202
203static void
204free_search_tree (ADDR_RANGE_TREE *t)
205{
206  if (t != NULL)
207    {
208      free_search_tree (t->lower);
209      free_search_tree (t->higher);
210      free (t);
211    }
212}
213
214/* Subroutine of build_search_tree to recursively build a balanced tree.
215   ??? It's not an optimum tree though.  */
216
217static ADDR_RANGE_TREE *
218build_tree_1 (ADDR_SUBRANGE **asrtab, unsigned int n)
219{
220  unsigned int mid = n / 2;
221  ADDR_RANGE_TREE *t;
222
223  if (n == 0)
224    return NULL;
225  t = (ADDR_RANGE_TREE *) xmalloc (sizeof (ADDR_RANGE_TREE));
226  t->start = asrtab[mid]->start;
227  t->end = asrtab[mid]->end;
228  if (mid != 0)
229    t->lower = build_tree_1 (asrtab, mid);
230  else
231    t->lower = NULL;
232  if (n > mid + 1)
233    t->higher = build_tree_1 (asrtab + mid + 1, n - mid - 1);
234  else
235    t->higher = NULL;
236  return t;
237}
238
239/* Build a search tree for address range AR.  */
240
241static void
242build_search_tree (ADDR_RANGE *ar)
243{
244  /* ??? Simple version for now.  */
245  ADDR_SUBRANGE *asr,**asrtab;
246  unsigned int i, n;
247
248  for (n = 0, asr = ar->ranges; asr != NULL; ++n, asr = asr->next)
249    continue;
250  asrtab = (ADDR_SUBRANGE **) xmalloc (n * sizeof (ADDR_SUBRANGE *));
251  for (i = 0, asr = ar->ranges; i < n; ++i, asr = asr->next)
252    asrtab[i] = asr;
253  ar->range_tree = build_tree_1 (asrtab, n);
254  free (asrtab);
255}
256
257void
258sim_addr_range_add (ADDR_RANGE *ar, address_word start, address_word end)
259{
260  frob_range (ar, start, end, 0);
261
262  /* Rebuild the search tree.  */
263  /* ??? Instead of rebuilding it here it could be done in a module resume
264     handler, say by first checking for a `changed' flag, assuming of course
265     this would never be done while the simulation is running.  */
266  free_search_tree (ar->range_tree);
267  build_search_tree (ar);
268}
269
270void
271sim_addr_range_delete (ADDR_RANGE *ar, address_word start, address_word end)
272{
273  frob_range (ar, start, end, 1);
274
275  /* Rebuild the search tree.  */
276  /* ??? Instead of rebuilding it here it could be done in a module resume
277     handler, say by first checking for a `changed' flag, assuming of course
278     this would never be done while the simulation is running.  */
279  free_search_tree (ar->range_tree);
280  build_search_tree (ar);
281}
282
283#endif /* DEFINE_NON_INLINE_P */
284
285#if DEFINE_INLINE_P
286
287SIM_ARANGE_INLINE int
288sim_addr_range_hit_p (ADDR_RANGE *ar, address_word addr)
289{
290  ADDR_RANGE_TREE *t = ar->range_tree;
291
292  while (t != NULL)
293    {
294      if (addr < t->start)
295	t = t->lower;
296      else if (addr > t->end)
297	t = t->higher;
298      else
299	return 1;
300    }
301  return 0;
302}
303
304#endif /* DEFINE_INLINE_P */
305