OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gdb-6.8/] [sim/] [common/] [sim-arange.c] - Blame information for rev 225

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 24 jeremybenn
/* Address ranges.
2
   Copyright (C) 1998, 2007, 2008 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 3 of the License, or
10
(at your option) 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
18
along 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
 
42
static void
43
insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr)
44
{
45
  asr->next = *pos;
46
  *pos = asr;
47
}
48
 
49
/* Delete a range.  */
50
 
51
static void
52
delete_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
 
67
static void
68
frob_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
 
203
static void
204
free_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
 
217
static ADDR_RANGE_TREE *
218
build_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
 
241
static void
242
build_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
 
257
void
258
sim_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
 
270
void
271
sim_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
 
287
SIM_ARANGE_INLINE int
288
sim_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 */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.