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

Subversion Repositories or1k

[/] [or1k/] [trunk/] [gdb-5.3/] [sim/] [common/] [sim-arange.c] - Blame information for rev 1765

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 1181 sfurman
/* 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
#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
 
43
static void
44
insert_range (ADDR_SUBRANGE **pos, ADDR_SUBRANGE *asr)
45
{
46
  asr->next = *pos;
47
  *pos = asr;
48
}
49
 
50
/* Delete a range.  */
51
 
52
static void
53
delete_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
 
68
static void
69
frob_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
 
204
static void
205
free_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
 
218
static ADDR_RANGE_TREE *
219
build_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
 
242
static void
243
build_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
 
258
void
259
sim_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
 
271
void
272
sim_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
 
288
SIM_ARANGE_INLINE int
289
sim_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 */

powered by: WebSVN 2.1.0

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