/* addrmap.c --- implementation of address map data structure.
- Copyright (C) 2007 Free Software Foundation, Inc.
+ Copyright (C) 2007-2021 Free Software Foundation, Inc.
This file is part of GDB.
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 of the License, or
+ 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,
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., 51 Franklin Street, Fifth Floor,
- Boston, MA 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include "defs.h"
-
-#include <stdlib.h>
-
#include "splay-tree.h"
#include "gdb_obstack.h"
#include "addrmap.h"
-#include "gdb_assert.h"
+/* Make sure splay trees can actually hold the values we want to
+ store in them. */
+gdb_static_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
+gdb_static_assert (sizeof (splay_tree_value) >= sizeof (void *));
\f
/* The "abstract class". */
implementation. */
struct addrmap_funcs
{
- void (*set_empty) (struct addrmap *this,
- CORE_ADDR start, CORE_ADDR end_inclusive,
- void *obj);
- void *(*find) (struct addrmap *this, CORE_ADDR addr);
- struct addrmap *(*create_fixed) (struct addrmap *this,
- struct obstack *obstack);
- void (*relocate) (struct addrmap *this, CORE_ADDR offset);
+ void (*set_empty) (struct addrmap *self,
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj);
+ void *(*find) (struct addrmap *self, CORE_ADDR addr);
+ struct addrmap *(*create_fixed) (struct addrmap *self,
+ struct obstack *obstack);
+ void (*relocate) (struct addrmap *self, CORE_ADDR offset);
+ int (*foreach) (struct addrmap *self, addrmap_foreach_fn fn);
};
struct addrmap
{
- struct addrmap_funcs *funcs;
+ const struct addrmap_funcs *funcs;
};
void
addrmap_set_empty (struct addrmap *map,
- CORE_ADDR start, CORE_ADDR end_inclusive,
- void *obj)
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj)
{
map->funcs->set_empty (map, start, end_inclusive, obj);
}
}
+int
+addrmap_foreach (struct addrmap *map, addrmap_foreach_fn fn)
+{
+ return map->funcs->foreach (map, fn);
+}
\f
/* Fixed address maps. */
static void
-addrmap_fixed_set_empty (struct addrmap *this,
- CORE_ADDR start, CORE_ADDR end_inclusive,
- void *obj)
+addrmap_fixed_set_empty (struct addrmap *self,
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj)
{
internal_error (__FILE__, __LINE__,
- "addrmap_fixed_set_empty: "
- "fixed addrmaps can't be changed\n");
+ "addrmap_fixed_set_empty: "
+ "fixed addrmaps can't be changed\n");
}
static void *
-addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr)
+addrmap_fixed_find (struct addrmap *self, CORE_ADDR addr)
{
- struct addrmap_fixed *map = (struct addrmap_fixed *) this;
+ struct addrmap_fixed *map = (struct addrmap_fixed *) self;
struct addrmap_transition *bottom = &map->transitions[0];
struct addrmap_transition *top = &map->transitions[map->num_transitions - 1];
while (bottom < top)
{
/* This needs to round towards top, or else when top = bottom +
- 1 (i.e., two entries are under consideration), then mid ==
- bottom, and then we may not narrow the range when (mid->addr
- < addr). */
+ 1 (i.e., two entries are under consideration), then mid ==
+ bottom, and then we may not narrow the range when (mid->addr
+ < addr). */
struct addrmap_transition *mid = top - (top - bottom) / 2;
if (mid->addr == addr)
- {
- bottom = mid;
- break;
- }
+ {
+ bottom = mid;
+ break;
+ }
else if (mid->addr < addr)
- /* We don't eliminate mid itself here, since each transition
- covers all subsequent addresses until the next. This is why
- we must round up in computing the midpoint. */
- bottom = mid;
+ /* We don't eliminate mid itself here, since each transition
+ covers all subsequent addresses until the next. This is why
+ we must round up in computing the midpoint. */
+ bottom = mid;
else
- top = mid - 1;
+ top = mid - 1;
}
return bottom->value;
static struct addrmap *
-addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack)
+addrmap_fixed_create_fixed (struct addrmap *self, struct obstack *obstack)
{
- abort ();
+ internal_error (__FILE__, __LINE__,
+ _("addrmap_create_fixed is not implemented yet "
+ "for fixed addrmaps"));
}
static void
-addrmap_fixed_relocate (struct addrmap *this, CORE_ADDR offset)
+addrmap_fixed_relocate (struct addrmap *self, CORE_ADDR offset)
{
- struct addrmap_fixed *map = (struct addrmap_fixed *) this;
+ struct addrmap_fixed *map = (struct addrmap_fixed *) self;
size_t i;
for (i = 0; i < map->num_transitions; i++)
}
-static struct addrmap_funcs addrmap_fixed_funcs =
+static int
+addrmap_fixed_foreach (struct addrmap *self, addrmap_foreach_fn fn)
+{
+ struct addrmap_fixed *map = (struct addrmap_fixed *) self;
+ size_t i;
+
+ for (i = 0; i < map->num_transitions; i++)
+ {
+ int res = fn (map->transitions[i].addr, map->transitions[i].value);
+
+ if (res != 0)
+ return res;
+ }
+
+ return 0;
+}
+
+
+static const struct addrmap_funcs addrmap_fixed_funcs =
{
- .set_empty = addrmap_fixed_set_empty,
- .find = addrmap_fixed_find,
- .create_fixed = addrmap_fixed_create_fixed,
- .relocate = addrmap_fixed_relocate
+ addrmap_fixed_set_empty,
+ addrmap_fixed_find,
+ addrmap_fixed_create_fixed,
+ addrmap_fixed_relocate,
+ addrmap_fixed_foreach
};
static splay_tree_key
allocate_key (struct addrmap_mutable *map, CORE_ADDR addr)
{
- CORE_ADDR *key = obstack_alloc (map->obstack, sizeof (*key));
- *key = addr;
+ CORE_ADDR *key = XOBNEW (map->obstack, CORE_ADDR);
+ *key = addr;
return (splay_tree_key) key;
}
}
+static void
+addrmap_splay_tree_remove (struct addrmap_mutable *map, CORE_ADDR addr)
+{
+ splay_tree_remove (map->tree, (splay_tree_key) &addr);
+}
+
+
static CORE_ADDR
addrmap_node_key (splay_tree_node node)
{
static void
-addrmap_splay_tree_insert (struct addrmap_mutable *map, CORE_ADDR key, void *value)
+addrmap_splay_tree_insert (struct addrmap_mutable *map,
+ CORE_ADDR key, void *value)
{
splay_tree_insert (map->tree,
- allocate_key (map, key),
- (splay_tree_value) value);
+ allocate_key (map, key),
+ (splay_tree_value) value);
}
tree node at ADDR, even if it would represent a "transition" from
one value to the same value. */
static void
-force_transition (struct addrmap_mutable *this, CORE_ADDR addr)
+force_transition (struct addrmap_mutable *self, CORE_ADDR addr)
{
splay_tree_node n
- = addrmap_splay_tree_lookup (this, addr);
+ = addrmap_splay_tree_lookup (self, addr);
if (! n)
{
- n = addrmap_splay_tree_predecessor (this, addr);
- addrmap_splay_tree_insert (this, addr,
- n ? addrmap_node_value (n) : NULL);
+ n = addrmap_splay_tree_predecessor (self, addr);
+ addrmap_splay_tree_insert (self, addr,
+ n ? addrmap_node_value (n) : NULL);
}
}
static void
-addrmap_mutable_set_empty (struct addrmap *this,
- CORE_ADDR start, CORE_ADDR end_inclusive,
- void *obj)
+addrmap_mutable_set_empty (struct addrmap *self,
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj)
{
- struct addrmap_mutable *map = (struct addrmap_mutable *) this;
+ struct addrmap_mutable *map = (struct addrmap_mutable *) self;
splay_tree_node n, next;
void *prior_value;
n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
{
if (! addrmap_node_value (n))
- addrmap_node_set_value (n, obj);
+ addrmap_node_set_value (n, obj);
}
/* Walk the area again, removing transitions from any value to
prior_value = n ? addrmap_node_value (n) : NULL;
for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
n && (end_inclusive == CORE_ADDR_MAX
- || addrmap_node_key (n) <= end_inclusive + 1);
+ || addrmap_node_key (n) <= end_inclusive + 1);
n = next)
{
next = addrmap_splay_tree_successor (map, addrmap_node_key (n));
if (addrmap_node_value (n) == prior_value)
- splay_tree_remove (map->tree, addrmap_node_key (n));
+ addrmap_splay_tree_remove (map, addrmap_node_key (n));
else
- prior_value = addrmap_node_value (n);
+ prior_value = addrmap_node_value (n);
}
}
static void *
-addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr)
+addrmap_mutable_find (struct addrmap *self, CORE_ADDR addr)
{
/* Not needed yet. */
- abort ();
+ internal_error (__FILE__, __LINE__,
+ _("addrmap_find is not implemented yet "
+ "for mutable addrmaps"));
}
static struct addrmap *
-addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
+addrmap_mutable_create_fixed (struct addrmap *self, struct obstack *obstack)
{
- struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
+ struct addrmap_mutable *mutable_obj = (struct addrmap_mutable *) self;
struct addrmap_fixed *fixed;
size_t num_transitions;
+ size_t alloc_len;
/* Count the number of transitions in the tree. */
num_transitions = 0;
- splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);
+ splay_tree_foreach (mutable_obj->tree, splay_foreach_count, &num_transitions);
/* Include an extra entry for the transition at zero (which fixed
maps have, but mutable maps do not.) */
num_transitions++;
- fixed = obstack_alloc (obstack,
- (sizeof (*fixed)
- + (num_transitions
- * sizeof (fixed->transitions[0]))));
+ alloc_len = sizeof (*fixed)
+ + (num_transitions * sizeof (fixed->transitions[0]));
+ fixed = (struct addrmap_fixed *) obstack_alloc (obstack, alloc_len);
fixed->addrmap.funcs = &addrmap_fixed_funcs;
fixed->num_transitions = 1;
fixed->transitions[0].addr = 0;
/* Copy all entries from the splay tree to the array, in order
of increasing address. */
- splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);
+ splay_tree_foreach (mutable_obj->tree, splay_foreach_copy, fixed);
/* We should have filled the array. */
gdb_assert (fixed->num_transitions == num_transitions);
static void
-addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
+addrmap_mutable_relocate (struct addrmap *self, CORE_ADDR offset)
{
/* Not needed yet. */
- abort ();
+ internal_error (__FILE__, __LINE__,
+ _("addrmap_relocate is not implemented yet "
+ "for mutable addrmaps"));
+}
+
+
+/* This is a splay_tree_foreach_fn. */
+
+static int
+addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
+{
+ addrmap_foreach_fn *fn = (addrmap_foreach_fn *) data;
+
+ return (*fn) (addrmap_node_key (node), addrmap_node_value (node));
}
-static struct addrmap_funcs addrmap_mutable_funcs =
+static int
+addrmap_mutable_foreach (struct addrmap *self, addrmap_foreach_fn fn)
{
- .set_empty = addrmap_mutable_set_empty,
- .find = addrmap_mutable_find,
- .create_fixed = addrmap_mutable_create_fixed,
- .relocate = addrmap_mutable_relocate
+ struct addrmap_mutable *mutable_obj = (struct addrmap_mutable *) self;
+
+ return splay_tree_foreach (mutable_obj->tree, addrmap_mutable_foreach_worker,
+ &fn);
+}
+
+
+static const struct addrmap_funcs addrmap_mutable_funcs =
+{
+ addrmap_mutable_set_empty,
+ addrmap_mutable_find,
+ addrmap_mutable_create_fixed,
+ addrmap_mutable_relocate,
+ addrmap_mutable_foreach
};
static void *
splay_obstack_alloc (int size, void *closure)
{
- struct addrmap_mutable *map = closure;
+ struct addrmap_mutable *map = (struct addrmap_mutable *) closure;
splay_tree_node n;
/* We should only be asked to allocate nodes and larger things.
static void
splay_obstack_free (void *obj, void *closure)
{
- struct addrmap_mutable *map = closure;
- splay_tree_node n = obj;
+ struct addrmap_mutable *map = (struct addrmap_mutable *) closure;
+ splay_tree_node n = (splay_tree_node) obj;
/* We've asserted in the allocation function that we only allocate
nodes or larger things, so it should be safe to put whatever
struct addrmap *
addrmap_create_mutable (struct obstack *obstack)
{
- struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
+ struct addrmap_mutable *map = XOBNEW (obstack, struct addrmap_mutable);
map->addrmap.funcs = &addrmap_mutable_funcs;
map->obstack = obstack;
map->free_nodes = NULL;
map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
- NULL, /* no delete key */
- NULL, /* no delete value */
- splay_obstack_alloc,
- splay_obstack_free,
- map);
+ NULL, /* no delete key */
+ NULL, /* no delete value */
+ splay_obstack_alloc,
+ splay_obstack_free,
+ map);
return (struct addrmap *) map;
}
-
-
-\f
-/* Initialization. */
-
-void
-_initialize_addrmap (void)
-{
- /* Make sure splay trees can actually hold the values we want to
- store in them. */
- gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
- gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
-}