15796c8dcSSimon Schubert /* addrmap.c --- implementation of address map data structure.
25796c8dcSSimon Schubert
3*ef5ccd6cSJohn Marino Copyright (C) 2007-2013 Free Software Foundation, Inc.
45796c8dcSSimon Schubert
55796c8dcSSimon Schubert This file is part of GDB.
65796c8dcSSimon Schubert
75796c8dcSSimon Schubert This program is free software; you can redistribute it and/or modify
85796c8dcSSimon Schubert it under the terms of the GNU General Public License as published by
95796c8dcSSimon Schubert the Free Software Foundation; either version 3 of the License, or
105796c8dcSSimon Schubert (at your option) any later version.
115796c8dcSSimon Schubert
125796c8dcSSimon Schubert This program is distributed in the hope that it will be useful,
135796c8dcSSimon Schubert but WITHOUT ANY WARRANTY; without even the implied warranty of
145796c8dcSSimon Schubert MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
155796c8dcSSimon Schubert GNU General Public License for more details.
165796c8dcSSimon Schubert
175796c8dcSSimon Schubert You should have received a copy of the GNU General Public License
185796c8dcSSimon Schubert along with this program. If not, see <http://www.gnu.org/licenses/>. */
195796c8dcSSimon Schubert
205796c8dcSSimon Schubert #include "defs.h"
215796c8dcSSimon Schubert
225796c8dcSSimon Schubert #include <stdlib.h>
235796c8dcSSimon Schubert
245796c8dcSSimon Schubert #include "splay-tree.h"
255796c8dcSSimon Schubert #include "gdb_obstack.h"
265796c8dcSSimon Schubert #include "addrmap.h"
275796c8dcSSimon Schubert #include "gdb_assert.h"
285796c8dcSSimon Schubert
295796c8dcSSimon Schubert
305796c8dcSSimon Schubert
315796c8dcSSimon Schubert /* The "abstract class". */
325796c8dcSSimon Schubert
335796c8dcSSimon Schubert /* Functions implementing the addrmap functions for a particular
345796c8dcSSimon Schubert implementation. */
355796c8dcSSimon Schubert struct addrmap_funcs
365796c8dcSSimon Schubert {
375796c8dcSSimon Schubert void (*set_empty) (struct addrmap *this,
385796c8dcSSimon Schubert CORE_ADDR start, CORE_ADDR end_inclusive,
395796c8dcSSimon Schubert void *obj);
405796c8dcSSimon Schubert void *(*find) (struct addrmap *this, CORE_ADDR addr);
415796c8dcSSimon Schubert struct addrmap *(*create_fixed) (struct addrmap *this,
425796c8dcSSimon Schubert struct obstack *obstack);
435796c8dcSSimon Schubert void (*relocate) (struct addrmap *this, CORE_ADDR offset);
44c50c785cSJohn Marino int (*foreach) (struct addrmap *this, addrmap_foreach_fn fn, void *data);
455796c8dcSSimon Schubert };
465796c8dcSSimon Schubert
475796c8dcSSimon Schubert
485796c8dcSSimon Schubert struct addrmap
495796c8dcSSimon Schubert {
505796c8dcSSimon Schubert const struct addrmap_funcs *funcs;
515796c8dcSSimon Schubert };
525796c8dcSSimon Schubert
535796c8dcSSimon Schubert
545796c8dcSSimon Schubert void
addrmap_set_empty(struct addrmap * map,CORE_ADDR start,CORE_ADDR end_inclusive,void * obj)555796c8dcSSimon Schubert addrmap_set_empty (struct addrmap *map,
565796c8dcSSimon Schubert CORE_ADDR start, CORE_ADDR end_inclusive,
575796c8dcSSimon Schubert void *obj)
585796c8dcSSimon Schubert {
595796c8dcSSimon Schubert map->funcs->set_empty (map, start, end_inclusive, obj);
605796c8dcSSimon Schubert }
615796c8dcSSimon Schubert
625796c8dcSSimon Schubert
635796c8dcSSimon Schubert void *
addrmap_find(struct addrmap * map,CORE_ADDR addr)645796c8dcSSimon Schubert addrmap_find (struct addrmap *map, CORE_ADDR addr)
655796c8dcSSimon Schubert {
665796c8dcSSimon Schubert return map->funcs->find (map, addr);
675796c8dcSSimon Schubert }
685796c8dcSSimon Schubert
695796c8dcSSimon Schubert
705796c8dcSSimon Schubert struct addrmap *
addrmap_create_fixed(struct addrmap * original,struct obstack * obstack)715796c8dcSSimon Schubert addrmap_create_fixed (struct addrmap *original, struct obstack *obstack)
725796c8dcSSimon Schubert {
735796c8dcSSimon Schubert return original->funcs->create_fixed (original, obstack);
745796c8dcSSimon Schubert }
755796c8dcSSimon Schubert
765796c8dcSSimon Schubert
775796c8dcSSimon Schubert /* Relocate all the addresses in MAP by OFFSET. (This can be applied
785796c8dcSSimon Schubert to either mutable or immutable maps.) */
795796c8dcSSimon Schubert void
addrmap_relocate(struct addrmap * map,CORE_ADDR offset)805796c8dcSSimon Schubert addrmap_relocate (struct addrmap *map, CORE_ADDR offset)
815796c8dcSSimon Schubert {
825796c8dcSSimon Schubert map->funcs->relocate (map, offset);
835796c8dcSSimon Schubert }
845796c8dcSSimon Schubert
855796c8dcSSimon Schubert
86c50c785cSJohn Marino int
addrmap_foreach(struct addrmap * map,addrmap_foreach_fn fn,void * data)87c50c785cSJohn Marino addrmap_foreach (struct addrmap *map, addrmap_foreach_fn fn, void *data)
88c50c785cSJohn Marino {
89c50c785cSJohn Marino return map->funcs->foreach (map, fn, data);
90c50c785cSJohn Marino }
915796c8dcSSimon Schubert
925796c8dcSSimon Schubert /* Fixed address maps. */
935796c8dcSSimon Schubert
945796c8dcSSimon Schubert /* A transition: a point in an address map where the value changes.
955796c8dcSSimon Schubert The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
965796c8dcSSimon Schubert something else. */
975796c8dcSSimon Schubert struct addrmap_transition
985796c8dcSSimon Schubert {
995796c8dcSSimon Schubert CORE_ADDR addr;
1005796c8dcSSimon Schubert void *value;
1015796c8dcSSimon Schubert };
1025796c8dcSSimon Schubert
1035796c8dcSSimon Schubert
1045796c8dcSSimon Schubert struct addrmap_fixed
1055796c8dcSSimon Schubert {
1065796c8dcSSimon Schubert struct addrmap addrmap;
1075796c8dcSSimon Schubert
1085796c8dcSSimon Schubert /* The number of transitions in TRANSITIONS. */
1095796c8dcSSimon Schubert size_t num_transitions;
1105796c8dcSSimon Schubert
1115796c8dcSSimon Schubert /* An array of transitions, sorted by address. For every point in
1125796c8dcSSimon Schubert the map where either ADDR == 0 or ADDR is mapped to one value and
1135796c8dcSSimon Schubert ADDR - 1 is mapped to something different, we have an entry here
1145796c8dcSSimon Schubert containing ADDR and VALUE. (Note that this means we always have
1155796c8dcSSimon Schubert an entry for address 0). */
1165796c8dcSSimon Schubert struct addrmap_transition transitions[1];
1175796c8dcSSimon Schubert };
1185796c8dcSSimon Schubert
1195796c8dcSSimon Schubert
1205796c8dcSSimon Schubert static void
addrmap_fixed_set_empty(struct addrmap * this,CORE_ADDR start,CORE_ADDR end_inclusive,void * obj)1215796c8dcSSimon Schubert addrmap_fixed_set_empty (struct addrmap *this,
1225796c8dcSSimon Schubert CORE_ADDR start, CORE_ADDR end_inclusive,
1235796c8dcSSimon Schubert void *obj)
1245796c8dcSSimon Schubert {
1255796c8dcSSimon Schubert internal_error (__FILE__, __LINE__,
1265796c8dcSSimon Schubert "addrmap_fixed_set_empty: "
1275796c8dcSSimon Schubert "fixed addrmaps can't be changed\n");
1285796c8dcSSimon Schubert }
1295796c8dcSSimon Schubert
1305796c8dcSSimon Schubert
1315796c8dcSSimon Schubert static void *
addrmap_fixed_find(struct addrmap * this,CORE_ADDR addr)1325796c8dcSSimon Schubert addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr)
1335796c8dcSSimon Schubert {
1345796c8dcSSimon Schubert struct addrmap_fixed *map = (struct addrmap_fixed *) this;
1355796c8dcSSimon Schubert struct addrmap_transition *bottom = &map->transitions[0];
1365796c8dcSSimon Schubert struct addrmap_transition *top = &map->transitions[map->num_transitions - 1];
1375796c8dcSSimon Schubert
1385796c8dcSSimon Schubert while (bottom < top)
1395796c8dcSSimon Schubert {
1405796c8dcSSimon Schubert /* This needs to round towards top, or else when top = bottom +
1415796c8dcSSimon Schubert 1 (i.e., two entries are under consideration), then mid ==
1425796c8dcSSimon Schubert bottom, and then we may not narrow the range when (mid->addr
1435796c8dcSSimon Schubert < addr). */
1445796c8dcSSimon Schubert struct addrmap_transition *mid = top - (top - bottom) / 2;
1455796c8dcSSimon Schubert
1465796c8dcSSimon Schubert if (mid->addr == addr)
1475796c8dcSSimon Schubert {
1485796c8dcSSimon Schubert bottom = mid;
1495796c8dcSSimon Schubert break;
1505796c8dcSSimon Schubert }
1515796c8dcSSimon Schubert else if (mid->addr < addr)
1525796c8dcSSimon Schubert /* We don't eliminate mid itself here, since each transition
1535796c8dcSSimon Schubert covers all subsequent addresses until the next. This is why
1545796c8dcSSimon Schubert we must round up in computing the midpoint. */
1555796c8dcSSimon Schubert bottom = mid;
1565796c8dcSSimon Schubert else
1575796c8dcSSimon Schubert top = mid - 1;
1585796c8dcSSimon Schubert }
1595796c8dcSSimon Schubert
1605796c8dcSSimon Schubert return bottom->value;
1615796c8dcSSimon Schubert }
1625796c8dcSSimon Schubert
1635796c8dcSSimon Schubert
1645796c8dcSSimon Schubert static struct addrmap *
addrmap_fixed_create_fixed(struct addrmap * this,struct obstack * obstack)1655796c8dcSSimon Schubert addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack)
1665796c8dcSSimon Schubert {
1675796c8dcSSimon Schubert internal_error (__FILE__, __LINE__,
1685796c8dcSSimon Schubert _("addrmap_create_fixed is not implemented yet "
1695796c8dcSSimon Schubert "for fixed addrmaps"));
1705796c8dcSSimon Schubert }
1715796c8dcSSimon Schubert
1725796c8dcSSimon Schubert
1735796c8dcSSimon Schubert static void
addrmap_fixed_relocate(struct addrmap * this,CORE_ADDR offset)1745796c8dcSSimon Schubert addrmap_fixed_relocate (struct addrmap *this, CORE_ADDR offset)
1755796c8dcSSimon Schubert {
1765796c8dcSSimon Schubert struct addrmap_fixed *map = (struct addrmap_fixed *) this;
1775796c8dcSSimon Schubert size_t i;
1785796c8dcSSimon Schubert
1795796c8dcSSimon Schubert for (i = 0; i < map->num_transitions; i++)
1805796c8dcSSimon Schubert map->transitions[i].addr += offset;
1815796c8dcSSimon Schubert }
1825796c8dcSSimon Schubert
1835796c8dcSSimon Schubert
184c50c785cSJohn Marino static int
addrmap_fixed_foreach(struct addrmap * this,addrmap_foreach_fn fn,void * data)185c50c785cSJohn Marino addrmap_fixed_foreach (struct addrmap *this, addrmap_foreach_fn fn,
186c50c785cSJohn Marino void *data)
187c50c785cSJohn Marino {
188c50c785cSJohn Marino struct addrmap_fixed *map = (struct addrmap_fixed *) this;
189c50c785cSJohn Marino size_t i;
190c50c785cSJohn Marino
191c50c785cSJohn Marino for (i = 0; i < map->num_transitions; i++)
192c50c785cSJohn Marino {
193c50c785cSJohn Marino int res = fn (data, map->transitions[i].addr, map->transitions[i].value);
194c50c785cSJohn Marino
195c50c785cSJohn Marino if (res != 0)
196c50c785cSJohn Marino return res;
197c50c785cSJohn Marino }
198c50c785cSJohn Marino
199c50c785cSJohn Marino return 0;
200c50c785cSJohn Marino }
201c50c785cSJohn Marino
202c50c785cSJohn Marino
2035796c8dcSSimon Schubert static const struct addrmap_funcs addrmap_fixed_funcs =
2045796c8dcSSimon Schubert {
2055796c8dcSSimon Schubert addrmap_fixed_set_empty,
2065796c8dcSSimon Schubert addrmap_fixed_find,
2075796c8dcSSimon Schubert addrmap_fixed_create_fixed,
208c50c785cSJohn Marino addrmap_fixed_relocate,
209c50c785cSJohn Marino addrmap_fixed_foreach
2105796c8dcSSimon Schubert };
2115796c8dcSSimon Schubert
2125796c8dcSSimon Schubert
2135796c8dcSSimon Schubert
2145796c8dcSSimon Schubert /* Mutable address maps. */
2155796c8dcSSimon Schubert
2165796c8dcSSimon Schubert struct addrmap_mutable
2175796c8dcSSimon Schubert {
2185796c8dcSSimon Schubert struct addrmap addrmap;
2195796c8dcSSimon Schubert
2205796c8dcSSimon Schubert /* The obstack to use for allocations for this map. */
2215796c8dcSSimon Schubert struct obstack *obstack;
2225796c8dcSSimon Schubert
2235796c8dcSSimon Schubert /* A splay tree, with a node for each transition; there is a
2245796c8dcSSimon Schubert transition at address T if T-1 and T map to different objects.
2255796c8dcSSimon Schubert
2265796c8dcSSimon Schubert Any addresses below the first node map to NULL. (Unlike
2275796c8dcSSimon Schubert fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't
2285796c8dcSSimon Schubert simplify enough.)
2295796c8dcSSimon Schubert
2305796c8dcSSimon Schubert The last region is assumed to end at CORE_ADDR_MAX.
2315796c8dcSSimon Schubert
2325796c8dcSSimon Schubert Since we can't know whether CORE_ADDR is larger or smaller than
2335796c8dcSSimon Schubert splay_tree_key (unsigned long) --- I think both are possible,
2345796c8dcSSimon Schubert given all combinations of 32- and 64-bit hosts and targets ---
2355796c8dcSSimon Schubert our keys are pointers to CORE_ADDR values. Since the splay tree
2365796c8dcSSimon Schubert library doesn't pass any closure pointer to the key free
2375796c8dcSSimon Schubert function, we can't keep a freelist for keys. Since mutable
2385796c8dcSSimon Schubert addrmaps are only used temporarily right now, we just leak keys
2395796c8dcSSimon Schubert from deleted nodes; they'll be freed when the obstack is freed. */
2405796c8dcSSimon Schubert splay_tree tree;
2415796c8dcSSimon Schubert
2425796c8dcSSimon Schubert /* A freelist for splay tree nodes, allocated on obstack, and
2435796c8dcSSimon Schubert chained together by their 'right' pointers. */
2445796c8dcSSimon Schubert splay_tree_node free_nodes;
2455796c8dcSSimon Schubert };
2465796c8dcSSimon Schubert
2475796c8dcSSimon Schubert
2485796c8dcSSimon Schubert /* Allocate a copy of CORE_ADDR in MAP's obstack. */
2495796c8dcSSimon Schubert static splay_tree_key
allocate_key(struct addrmap_mutable * map,CORE_ADDR addr)2505796c8dcSSimon Schubert allocate_key (struct addrmap_mutable *map, CORE_ADDR addr)
2515796c8dcSSimon Schubert {
2525796c8dcSSimon Schubert CORE_ADDR *key = obstack_alloc (map->obstack, sizeof (*key));
2535796c8dcSSimon Schubert
254cf7f2e2dSJohn Marino *key = addr;
2555796c8dcSSimon Schubert return (splay_tree_key) key;
2565796c8dcSSimon Schubert }
2575796c8dcSSimon Schubert
2585796c8dcSSimon Schubert
2595796c8dcSSimon Schubert /* Type-correct wrappers for splay tree access. */
2605796c8dcSSimon Schubert static splay_tree_node
addrmap_splay_tree_lookup(struct addrmap_mutable * map,CORE_ADDR addr)2615796c8dcSSimon Schubert addrmap_splay_tree_lookup (struct addrmap_mutable *map, CORE_ADDR addr)
2625796c8dcSSimon Schubert {
2635796c8dcSSimon Schubert return splay_tree_lookup (map->tree, (splay_tree_key) &addr);
2645796c8dcSSimon Schubert }
2655796c8dcSSimon Schubert
2665796c8dcSSimon Schubert
2675796c8dcSSimon Schubert static splay_tree_node
addrmap_splay_tree_predecessor(struct addrmap_mutable * map,CORE_ADDR addr)2685796c8dcSSimon Schubert addrmap_splay_tree_predecessor (struct addrmap_mutable *map, CORE_ADDR addr)
2695796c8dcSSimon Schubert {
2705796c8dcSSimon Schubert return splay_tree_predecessor (map->tree, (splay_tree_key) &addr);
2715796c8dcSSimon Schubert }
2725796c8dcSSimon Schubert
2735796c8dcSSimon Schubert
2745796c8dcSSimon Schubert static splay_tree_node
addrmap_splay_tree_successor(struct addrmap_mutable * map,CORE_ADDR addr)2755796c8dcSSimon Schubert addrmap_splay_tree_successor (struct addrmap_mutable *map, CORE_ADDR addr)
2765796c8dcSSimon Schubert {
2775796c8dcSSimon Schubert return splay_tree_successor (map->tree, (splay_tree_key) &addr);
2785796c8dcSSimon Schubert }
2795796c8dcSSimon Schubert
2805796c8dcSSimon Schubert
2815796c8dcSSimon Schubert static void
addrmap_splay_tree_remove(struct addrmap_mutable * map,CORE_ADDR addr)2825796c8dcSSimon Schubert addrmap_splay_tree_remove (struct addrmap_mutable *map, CORE_ADDR addr)
2835796c8dcSSimon Schubert {
2845796c8dcSSimon Schubert splay_tree_remove (map->tree, (splay_tree_key) &addr);
2855796c8dcSSimon Schubert }
2865796c8dcSSimon Schubert
2875796c8dcSSimon Schubert
2885796c8dcSSimon Schubert static CORE_ADDR
addrmap_node_key(splay_tree_node node)2895796c8dcSSimon Schubert addrmap_node_key (splay_tree_node node)
2905796c8dcSSimon Schubert {
2915796c8dcSSimon Schubert return * (CORE_ADDR *) node->key;
2925796c8dcSSimon Schubert }
2935796c8dcSSimon Schubert
2945796c8dcSSimon Schubert
2955796c8dcSSimon Schubert static void *
addrmap_node_value(splay_tree_node node)2965796c8dcSSimon Schubert addrmap_node_value (splay_tree_node node)
2975796c8dcSSimon Schubert {
2985796c8dcSSimon Schubert return (void *) node->value;
2995796c8dcSSimon Schubert }
3005796c8dcSSimon Schubert
3015796c8dcSSimon Schubert
3025796c8dcSSimon Schubert static void
addrmap_node_set_value(splay_tree_node node,void * value)3035796c8dcSSimon Schubert addrmap_node_set_value (splay_tree_node node, void *value)
3045796c8dcSSimon Schubert {
3055796c8dcSSimon Schubert node->value = (splay_tree_value) value;
3065796c8dcSSimon Schubert }
3075796c8dcSSimon Schubert
3085796c8dcSSimon Schubert
3095796c8dcSSimon Schubert static void
addrmap_splay_tree_insert(struct addrmap_mutable * map,CORE_ADDR key,void * value)310c50c785cSJohn Marino addrmap_splay_tree_insert (struct addrmap_mutable *map,
311c50c785cSJohn Marino CORE_ADDR key, void *value)
3125796c8dcSSimon Schubert {
3135796c8dcSSimon Schubert splay_tree_insert (map->tree,
3145796c8dcSSimon Schubert allocate_key (map, key),
3155796c8dcSSimon Schubert (splay_tree_value) value);
3165796c8dcSSimon Schubert }
3175796c8dcSSimon Schubert
3185796c8dcSSimon Schubert
3195796c8dcSSimon Schubert /* Without changing the mapping of any address, ensure that there is a
3205796c8dcSSimon Schubert tree node at ADDR, even if it would represent a "transition" from
3215796c8dcSSimon Schubert one value to the same value. */
3225796c8dcSSimon Schubert static void
force_transition(struct addrmap_mutable * this,CORE_ADDR addr)3235796c8dcSSimon Schubert force_transition (struct addrmap_mutable *this, CORE_ADDR addr)
3245796c8dcSSimon Schubert {
3255796c8dcSSimon Schubert splay_tree_node n
3265796c8dcSSimon Schubert = addrmap_splay_tree_lookup (this, addr);
3275796c8dcSSimon Schubert
3285796c8dcSSimon Schubert if (! n)
3295796c8dcSSimon Schubert {
3305796c8dcSSimon Schubert n = addrmap_splay_tree_predecessor (this, addr);
3315796c8dcSSimon Schubert addrmap_splay_tree_insert (this, addr,
3325796c8dcSSimon Schubert n ? addrmap_node_value (n) : NULL);
3335796c8dcSSimon Schubert }
3345796c8dcSSimon Schubert }
3355796c8dcSSimon Schubert
3365796c8dcSSimon Schubert
3375796c8dcSSimon Schubert static void
addrmap_mutable_set_empty(struct addrmap * this,CORE_ADDR start,CORE_ADDR end_inclusive,void * obj)3385796c8dcSSimon Schubert addrmap_mutable_set_empty (struct addrmap *this,
3395796c8dcSSimon Schubert CORE_ADDR start, CORE_ADDR end_inclusive,
3405796c8dcSSimon Schubert void *obj)
3415796c8dcSSimon Schubert {
3425796c8dcSSimon Schubert struct addrmap_mutable *map = (struct addrmap_mutable *) this;
3435796c8dcSSimon Schubert splay_tree_node n, next;
3445796c8dcSSimon Schubert void *prior_value;
3455796c8dcSSimon Schubert
3465796c8dcSSimon Schubert /* If we're being asked to set all empty portions of the given
3475796c8dcSSimon Schubert address range to empty, then probably the caller is confused.
3485796c8dcSSimon Schubert (If that turns out to be useful in some cases, then we can change
3495796c8dcSSimon Schubert this to simply return, since overriding NULL with NULL is a
3505796c8dcSSimon Schubert no-op.) */
3515796c8dcSSimon Schubert gdb_assert (obj);
3525796c8dcSSimon Schubert
3535796c8dcSSimon Schubert /* We take a two-pass approach, for simplicity.
3545796c8dcSSimon Schubert - Establish transitions where we think we might need them.
3555796c8dcSSimon Schubert - First pass: change all NULL regions to OBJ.
3565796c8dcSSimon Schubert - Second pass: remove any unnecessary transitions. */
3575796c8dcSSimon Schubert
3585796c8dcSSimon Schubert /* Establish transitions at the start and end. */
3595796c8dcSSimon Schubert force_transition (map, start);
3605796c8dcSSimon Schubert if (end_inclusive < CORE_ADDR_MAX)
3615796c8dcSSimon Schubert force_transition (map, end_inclusive + 1);
3625796c8dcSSimon Schubert
3635796c8dcSSimon Schubert /* Walk the area, changing all NULL regions to OBJ. */
3645796c8dcSSimon Schubert for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
3655796c8dcSSimon Schubert n && addrmap_node_key (n) <= end_inclusive;
3665796c8dcSSimon Schubert n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
3675796c8dcSSimon Schubert {
3685796c8dcSSimon Schubert if (! addrmap_node_value (n))
3695796c8dcSSimon Schubert addrmap_node_set_value (n, obj);
3705796c8dcSSimon Schubert }
3715796c8dcSSimon Schubert
3725796c8dcSSimon Schubert /* Walk the area again, removing transitions from any value to
3735796c8dcSSimon Schubert itself. Be sure to visit both the transitions we forced
3745796c8dcSSimon Schubert above. */
3755796c8dcSSimon Schubert n = addrmap_splay_tree_predecessor (map, start);
3765796c8dcSSimon Schubert prior_value = n ? addrmap_node_value (n) : NULL;
3775796c8dcSSimon Schubert for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
3785796c8dcSSimon Schubert n && (end_inclusive == CORE_ADDR_MAX
3795796c8dcSSimon Schubert || addrmap_node_key (n) <= end_inclusive + 1);
3805796c8dcSSimon Schubert n = next)
3815796c8dcSSimon Schubert {
3825796c8dcSSimon Schubert next = addrmap_splay_tree_successor (map, addrmap_node_key (n));
3835796c8dcSSimon Schubert if (addrmap_node_value (n) == prior_value)
3845796c8dcSSimon Schubert addrmap_splay_tree_remove (map, addrmap_node_key (n));
3855796c8dcSSimon Schubert else
3865796c8dcSSimon Schubert prior_value = addrmap_node_value (n);
3875796c8dcSSimon Schubert }
3885796c8dcSSimon Schubert }
3895796c8dcSSimon Schubert
3905796c8dcSSimon Schubert
3915796c8dcSSimon Schubert static void *
addrmap_mutable_find(struct addrmap * this,CORE_ADDR addr)3925796c8dcSSimon Schubert addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr)
3935796c8dcSSimon Schubert {
3945796c8dcSSimon Schubert /* Not needed yet. */
3955796c8dcSSimon Schubert internal_error (__FILE__, __LINE__,
3965796c8dcSSimon Schubert _("addrmap_find is not implemented yet "
3975796c8dcSSimon Schubert "for mutable addrmaps"));
3985796c8dcSSimon Schubert }
3995796c8dcSSimon Schubert
4005796c8dcSSimon Schubert
4015796c8dcSSimon Schubert /* A function to pass to splay_tree_foreach to count the number of nodes
4025796c8dcSSimon Schubert in the tree. */
4035796c8dcSSimon Schubert static int
splay_foreach_count(splay_tree_node n,void * closure)4045796c8dcSSimon Schubert splay_foreach_count (splay_tree_node n, void *closure)
4055796c8dcSSimon Schubert {
4065796c8dcSSimon Schubert size_t *count = (size_t *) closure;
4075796c8dcSSimon Schubert
4085796c8dcSSimon Schubert (*count)++;
4095796c8dcSSimon Schubert return 0;
4105796c8dcSSimon Schubert }
4115796c8dcSSimon Schubert
4125796c8dcSSimon Schubert
4135796c8dcSSimon Schubert /* A function to pass to splay_tree_foreach to copy entries into a
4145796c8dcSSimon Schubert fixed address map. */
4155796c8dcSSimon Schubert static int
splay_foreach_copy(splay_tree_node n,void * closure)4165796c8dcSSimon Schubert splay_foreach_copy (splay_tree_node n, void *closure)
4175796c8dcSSimon Schubert {
4185796c8dcSSimon Schubert struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure;
4195796c8dcSSimon Schubert struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions];
4205796c8dcSSimon Schubert
4215796c8dcSSimon Schubert t->addr = addrmap_node_key (n);
4225796c8dcSSimon Schubert t->value = addrmap_node_value (n);
4235796c8dcSSimon Schubert fixed->num_transitions++;
4245796c8dcSSimon Schubert
4255796c8dcSSimon Schubert return 0;
4265796c8dcSSimon Schubert }
4275796c8dcSSimon Schubert
4285796c8dcSSimon Schubert
4295796c8dcSSimon Schubert static struct addrmap *
addrmap_mutable_create_fixed(struct addrmap * this,struct obstack * obstack)4305796c8dcSSimon Schubert addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
4315796c8dcSSimon Schubert {
4325796c8dcSSimon Schubert struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
4335796c8dcSSimon Schubert struct addrmap_fixed *fixed;
4345796c8dcSSimon Schubert size_t num_transitions;
4355796c8dcSSimon Schubert
4365796c8dcSSimon Schubert /* Count the number of transitions in the tree. */
4375796c8dcSSimon Schubert num_transitions = 0;
4385796c8dcSSimon Schubert splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);
4395796c8dcSSimon Schubert
4405796c8dcSSimon Schubert /* Include an extra entry for the transition at zero (which fixed
4415796c8dcSSimon Schubert maps have, but mutable maps do not.) */
4425796c8dcSSimon Schubert num_transitions++;
4435796c8dcSSimon Schubert
4445796c8dcSSimon Schubert fixed = obstack_alloc (obstack,
4455796c8dcSSimon Schubert (sizeof (*fixed)
4465796c8dcSSimon Schubert + (num_transitions
4475796c8dcSSimon Schubert * sizeof (fixed->transitions[0]))));
4485796c8dcSSimon Schubert fixed->addrmap.funcs = &addrmap_fixed_funcs;
4495796c8dcSSimon Schubert fixed->num_transitions = 1;
4505796c8dcSSimon Schubert fixed->transitions[0].addr = 0;
4515796c8dcSSimon Schubert fixed->transitions[0].value = NULL;
4525796c8dcSSimon Schubert
4535796c8dcSSimon Schubert /* Copy all entries from the splay tree to the array, in order
4545796c8dcSSimon Schubert of increasing address. */
4555796c8dcSSimon Schubert splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);
4565796c8dcSSimon Schubert
4575796c8dcSSimon Schubert /* We should have filled the array. */
4585796c8dcSSimon Schubert gdb_assert (fixed->num_transitions == num_transitions);
4595796c8dcSSimon Schubert
4605796c8dcSSimon Schubert return (struct addrmap *) fixed;
4615796c8dcSSimon Schubert }
4625796c8dcSSimon Schubert
4635796c8dcSSimon Schubert
4645796c8dcSSimon Schubert static void
addrmap_mutable_relocate(struct addrmap * this,CORE_ADDR offset)4655796c8dcSSimon Schubert addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
4665796c8dcSSimon Schubert {
4675796c8dcSSimon Schubert /* Not needed yet. */
4685796c8dcSSimon Schubert internal_error (__FILE__, __LINE__,
4695796c8dcSSimon Schubert _("addrmap_relocate is not implemented yet "
4705796c8dcSSimon Schubert "for mutable addrmaps"));
4715796c8dcSSimon Schubert }
4725796c8dcSSimon Schubert
4735796c8dcSSimon Schubert
474c50c785cSJohn Marino /* Struct to map addrmap's foreach function to splay_tree's version. */
475c50c785cSJohn Marino struct mutable_foreach_data
476c50c785cSJohn Marino {
477c50c785cSJohn Marino addrmap_foreach_fn fn;
478c50c785cSJohn Marino void *data;
479c50c785cSJohn Marino };
480c50c785cSJohn Marino
481c50c785cSJohn Marino
482c50c785cSJohn Marino /* This is a splay_tree_foreach_fn. */
483c50c785cSJohn Marino
484c50c785cSJohn Marino static int
addrmap_mutable_foreach_worker(splay_tree_node node,void * data)485c50c785cSJohn Marino addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
486c50c785cSJohn Marino {
487c50c785cSJohn Marino struct mutable_foreach_data *foreach_data = data;
488c50c785cSJohn Marino
489c50c785cSJohn Marino return foreach_data->fn (foreach_data->data,
490c50c785cSJohn Marino addrmap_node_key (node),
491c50c785cSJohn Marino addrmap_node_value (node));
492c50c785cSJohn Marino }
493c50c785cSJohn Marino
494c50c785cSJohn Marino
495c50c785cSJohn Marino static int
addrmap_mutable_foreach(struct addrmap * this,addrmap_foreach_fn fn,void * data)496c50c785cSJohn Marino addrmap_mutable_foreach (struct addrmap *this, addrmap_foreach_fn fn,
497c50c785cSJohn Marino void *data)
498c50c785cSJohn Marino {
499c50c785cSJohn Marino struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
500c50c785cSJohn Marino struct mutable_foreach_data foreach_data;
501c50c785cSJohn Marino
502c50c785cSJohn Marino foreach_data.fn = fn;
503c50c785cSJohn Marino foreach_data.data = data;
504c50c785cSJohn Marino return splay_tree_foreach (mutable->tree, addrmap_mutable_foreach_worker,
505c50c785cSJohn Marino &foreach_data);
506c50c785cSJohn Marino }
507c50c785cSJohn Marino
508c50c785cSJohn Marino
5095796c8dcSSimon Schubert static const struct addrmap_funcs addrmap_mutable_funcs =
5105796c8dcSSimon Schubert {
5115796c8dcSSimon Schubert addrmap_mutable_set_empty,
5125796c8dcSSimon Schubert addrmap_mutable_find,
5135796c8dcSSimon Schubert addrmap_mutable_create_fixed,
514c50c785cSJohn Marino addrmap_mutable_relocate,
515c50c785cSJohn Marino addrmap_mutable_foreach
5165796c8dcSSimon Schubert };
5175796c8dcSSimon Schubert
5185796c8dcSSimon Schubert
5195796c8dcSSimon Schubert static void *
splay_obstack_alloc(int size,void * closure)5205796c8dcSSimon Schubert splay_obstack_alloc (int size, void *closure)
5215796c8dcSSimon Schubert {
5225796c8dcSSimon Schubert struct addrmap_mutable *map = closure;
5235796c8dcSSimon Schubert splay_tree_node n;
5245796c8dcSSimon Schubert
5255796c8dcSSimon Schubert /* We should only be asked to allocate nodes and larger things.
5265796c8dcSSimon Schubert (If, at some point in the future, this is no longer true, we can
5275796c8dcSSimon Schubert just round up the size to sizeof (*n).) */
5285796c8dcSSimon Schubert gdb_assert (size >= sizeof (*n));
5295796c8dcSSimon Schubert
5305796c8dcSSimon Schubert if (map->free_nodes)
5315796c8dcSSimon Schubert {
5325796c8dcSSimon Schubert n = map->free_nodes;
5335796c8dcSSimon Schubert map->free_nodes = n->right;
5345796c8dcSSimon Schubert return n;
5355796c8dcSSimon Schubert }
5365796c8dcSSimon Schubert else
5375796c8dcSSimon Schubert return obstack_alloc (map->obstack, size);
5385796c8dcSSimon Schubert }
5395796c8dcSSimon Schubert
5405796c8dcSSimon Schubert
5415796c8dcSSimon Schubert static void
splay_obstack_free(void * obj,void * closure)5425796c8dcSSimon Schubert splay_obstack_free (void *obj, void *closure)
5435796c8dcSSimon Schubert {
5445796c8dcSSimon Schubert struct addrmap_mutable *map = closure;
5455796c8dcSSimon Schubert splay_tree_node n = obj;
5465796c8dcSSimon Schubert
5475796c8dcSSimon Schubert /* We've asserted in the allocation function that we only allocate
5485796c8dcSSimon Schubert nodes or larger things, so it should be safe to put whatever
5495796c8dcSSimon Schubert we get passed back on the free list. */
5505796c8dcSSimon Schubert n->right = map->free_nodes;
5515796c8dcSSimon Schubert map->free_nodes = n;
5525796c8dcSSimon Schubert }
5535796c8dcSSimon Schubert
5545796c8dcSSimon Schubert
5555796c8dcSSimon Schubert /* Compare keys as CORE_ADDR * values. */
5565796c8dcSSimon Schubert static int
splay_compare_CORE_ADDR_ptr(splay_tree_key ak,splay_tree_key bk)5575796c8dcSSimon Schubert splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
5585796c8dcSSimon Schubert {
5595796c8dcSSimon Schubert CORE_ADDR a = * (CORE_ADDR *) ak;
5605796c8dcSSimon Schubert CORE_ADDR b = * (CORE_ADDR *) bk;
5615796c8dcSSimon Schubert
5625796c8dcSSimon Schubert /* We can't just return a-b here, because of over/underflow. */
5635796c8dcSSimon Schubert if (a < b)
5645796c8dcSSimon Schubert return -1;
5655796c8dcSSimon Schubert else if (a == b)
5665796c8dcSSimon Schubert return 0;
5675796c8dcSSimon Schubert else
5685796c8dcSSimon Schubert return 1;
5695796c8dcSSimon Schubert }
5705796c8dcSSimon Schubert
5715796c8dcSSimon Schubert
5725796c8dcSSimon Schubert struct addrmap *
addrmap_create_mutable(struct obstack * obstack)5735796c8dcSSimon Schubert addrmap_create_mutable (struct obstack *obstack)
5745796c8dcSSimon Schubert {
5755796c8dcSSimon Schubert struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
5765796c8dcSSimon Schubert
5775796c8dcSSimon Schubert map->addrmap.funcs = &addrmap_mutable_funcs;
5785796c8dcSSimon Schubert map->obstack = obstack;
5795796c8dcSSimon Schubert
5805796c8dcSSimon Schubert /* splay_tree_new_with_allocator uses the provided allocation
5815796c8dcSSimon Schubert function to allocate the main splay_tree structure itself, so our
5825796c8dcSSimon Schubert free list has to be initialized before we create the tree. */
5835796c8dcSSimon Schubert map->free_nodes = NULL;
5845796c8dcSSimon Schubert
5855796c8dcSSimon Schubert map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
5865796c8dcSSimon Schubert NULL, /* no delete key */
5875796c8dcSSimon Schubert NULL, /* no delete value */
5885796c8dcSSimon Schubert splay_obstack_alloc,
5895796c8dcSSimon Schubert splay_obstack_free,
5905796c8dcSSimon Schubert map);
5915796c8dcSSimon Schubert
5925796c8dcSSimon Schubert return (struct addrmap *) map;
5935796c8dcSSimon Schubert }
5945796c8dcSSimon Schubert
5955796c8dcSSimon Schubert
5965796c8dcSSimon Schubert
5975796c8dcSSimon Schubert /* Initialization. */
5985796c8dcSSimon Schubert
5995796c8dcSSimon Schubert /* Provide a prototype to silence -Wmissing-prototypes. */
6005796c8dcSSimon Schubert extern initialize_file_ftype _initialize_addrmap;
6015796c8dcSSimon Schubert
6025796c8dcSSimon Schubert void
_initialize_addrmap(void)6035796c8dcSSimon Schubert _initialize_addrmap (void)
6045796c8dcSSimon Schubert {
6055796c8dcSSimon Schubert /* Make sure splay trees can actually hold the values we want to
6065796c8dcSSimon Schubert store in them. */
6075796c8dcSSimon Schubert gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
6085796c8dcSSimon Schubert gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
6095796c8dcSSimon Schubert }
610