From 17f07639b43998b42f49d11e860388de7d3a180a Mon Sep 17 00:00:00 2001 From: Doug Evans Date: Sat, 5 Dec 1998 02:19:39 +0000 Subject: [PATCH] address range support --- sim/common/.Sanitize | 2 + sim/common/ChangeLog | 14 +++ sim/common/sim-arange.c | 290 ++++++++++++++++++++++++++++++++++++++++++++++++ sim/common/sim-arange.h | 83 ++++++++++++++ 4 files changed, 389 insertions(+) create mode 100644 sim/common/sim-arange.c create mode 100644 sim/common/sim-arange.h diff --git a/sim/common/.Sanitize b/sim/common/.Sanitize index e6b50e3..fe8142b 100644 --- a/sim/common/.Sanitize +++ b/sim/common/.Sanitize @@ -93,6 +93,8 @@ run.c run.1 sim-abort.c sim-alu.h +sim-arange.c +sim-arange.h sim-assert.h sim-base.h sim-basics.h diff --git a/sim/common/ChangeLog b/sim/common/ChangeLog index daba533..511f4b9 100644 --- a/sim/common/ChangeLog +++ b/sim/common/ChangeLog @@ -1,3 +1,17 @@ +1998-12-04 Doug Evans + + * sim-arange.c: New file. + * sim-arange.h: New file. + +1998-12-03 Frank Ch. Eigler + + * sim-memopt.c (sim_memory_uninstall): Deallocate all memory + regions. + +1998-12-01 Doug Evans + + * sim-inline.c (SIM_INLINE_P): Fix typo. + start-sanitize-gxsim 1998-12-01 Frank Ch. Eigler diff --git a/sim/common/sim-arange.c b/sim/common/sim-arange.c new file mode 100644 index 0000000..43c5789 --- /dev/null +++ b/sim/common/sim-arange.c @@ -0,0 +1,290 @@ +/* Address ranges. + Copyright (C) 1998 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 2, 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, write to the Free Software Foundation, Inc., +59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +/* Tell sim-arange.h it's us. */ +#define SIM_ARANGE_C + +#include "sim-basics.h" +#include "sim-assert.h" + +#define DEFINE_INLINE_P (! defined (SIM_ARANGE_C_INCLUDED)) +#define DEFINE_NON_INLINE_P defined (SIM_ARANGE_C_INCLUDED) + +#if DEFINE_NON_INLINE_P + +/* 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. */ + 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. */ + free_search_tree (ar->range_tree); + build_search_tree (ar); +} + +#endif /* DEFINE_NON_INLINE_P */ + +#if DEFINE_INLINE_P + +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 /* DEFINE_INLINE_P */ diff --git a/sim/common/sim-arange.h b/sim/common/sim-arange.h new file mode 100644 index 0000000..10ba0f4 --- /dev/null +++ b/sim/common/sim-arange.h @@ -0,0 +1,83 @@ +/* Address ranges. + Copyright (C) 1998 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 2, 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, write to the Free Software Foundation, Inc., +59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +/* This file is meant to be included by sim-basics.h. */ + +#ifndef SIM_ARANGE_H +#define SIM_ARANGE_H + +/* A list of address ranges. */ + +typedef struct _addr_subrange { + struct _addr_subrange *next; + + /* Range of addresses to be traced is [start,end]. */ + address_word start,end; +} ADDR_SUBRANGE; + +/* For speed, searching is done on a tree. */ + +typedef struct _addr_range_tree { + struct _addr_range_tree *lower; + struct _addr_range_tree *higher; + + /* Range of addresses to be traced is [start,end]. */ + address_word start,end; +} ADDR_RANGE_TREE; + +/* The top level struct. */ + +typedef struct _addr_range { + ADDR_SUBRANGE *ranges; +#define ADDR_RANGE_RANGES(ar) ((ar)->ranges) + ADDR_RANGE_TREE *range_tree; +#define ADDR_RANGE_TREE(ar) ((ar)->range_tree) +} ADDR_RANGE; + +/* Add address range START,END to AR. */ +extern void sim_addr_range_add (ADDR_RANGE * /*ar*/, + address_word /*start*/, + address_word /*end*/); + +/* Delete address range START,END from AR. */ +extern void sim_addr_range_delete (ADDR_RANGE * /*ar*/, + address_word /*start*/, + address_word /*end*/); + +/* Return non-zero if ADDR is in range AR, traversing the entire tree. + If no range is specified, that is defined to mean "everything". */ +extern INLINE int +sim_addr_range_hit_p (ADDR_RANGE * /*ar*/, address_word /*addr*/); +#define ADDR_RANGE_HIT_P(ar, addr) \ + ((ar)->range_tree == NULL || sim_addr_range_hit_p ((ar), (addr))) + +#ifdef HAVE_INLINE +#ifdef SIM_ARANGE_C +#define SIM_ARANGE_INLINE INLINE +#else +#define SIM_ARANGE_INLINE EXTERN_INLINE +#endif +#include "sim-arange.c" +#else +#define SIM_ARANGE_INLINE +#endif +#define SIM_ARANGE_C_INCLUDED + +#endif /* SIM_ARANGE_H */ -- 2.7.4