/* Address ranges.
Copyright (C) 1998-2019 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 3 of the License, 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, see <http://www.gnu.org/licenses/>. */
/* 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
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#ifdef SIM_ARANGE_C_INCLUDED
/* 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);
}
#else /* SIM_ARANGE_C_INCLUDED */
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 /* SIM_ARANGE_C_INCLUDED */