You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
218 lines
6.5 KiB
218 lines
6.5 KiB
|
|
/*--------------------------------------------------------------------*/ |
|
/*--- A mapping where the keys exactly cover the address space. ---*/ |
|
/*--- m_rangemap.c ---*/ |
|
/*--------------------------------------------------------------------*/ |
|
|
|
/* |
|
This file is part of Valgrind, a dynamic binary instrumentation |
|
framework. |
|
|
|
Copyright (C) 2014-2017 Mozilla Foundation |
|
|
|
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 (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. |
|
|
|
The GNU General Public License is contained in the file COPYING. |
|
*/ |
|
|
|
/* Contributed by Julian Seward <jseward@acm.org> */ |
|
|
|
#include "pub_core_basics.h" |
|
#include "pub_core_libcassert.h" |
|
#include "pub_core_libcprint.h" |
|
#include "pub_core_xarray.h" |
|
#include "pub_core_rangemap.h" /* self */ |
|
|
|
|
|
/* See pub_tool_rangemap.h for details of what this is all about. */ |
|
|
|
#define UWORD_MIN ((UWord)0) |
|
#define UWORD_MAX (~(UWord)0) |
|
|
|
typedef |
|
struct { UWord key_min; UWord key_max; UWord val; } |
|
Range; |
|
|
|
|
|
struct _RangeMap { |
|
Alloc_Fn_t alloc_fn; /* alloc fn (nofail) */ |
|
const HChar* cc; /* cost centre for alloc */ |
|
Free_Fn_t free_fn; /* free fn */ |
|
XArray* ranges; |
|
}; |
|
|
|
|
|
/* fwds */ |
|
static void preen (/*MOD*/RangeMap* rm); |
|
static Word find ( const RangeMap* rm, UWord key ); |
|
static void split_at ( /*MOD*/RangeMap* rm, UWord key ); |
|
static void show ( const RangeMap* rm ); |
|
|
|
|
|
RangeMap* VG_(newRangeMap) ( Alloc_Fn_t alloc_fn, |
|
const HChar* cc, |
|
Free_Fn_t free_fn, |
|
UWord initialVal ) |
|
{ |
|
/* check user-supplied info .. */ |
|
vg_assert(alloc_fn); |
|
vg_assert(free_fn); |
|
RangeMap* rm = alloc_fn(cc, sizeof(RangeMap)); |
|
rm->alloc_fn = alloc_fn; |
|
rm->cc = cc; |
|
rm->free_fn = free_fn; |
|
rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) ); |
|
/* Add the initial range */ |
|
Range r; |
|
r.key_min = UWORD_MIN; |
|
r.key_max = UWORD_MAX; |
|
r.val = initialVal; |
|
Word i = VG_(addToXA)(rm->ranges, &r); |
|
vg_assert(i == 0); |
|
vg_assert(VG_(sizeXA)(rm->ranges) == 1); |
|
/* */ |
|
return rm; |
|
} |
|
|
|
void VG_(deleteRangeMap) ( RangeMap* rm ) |
|
{ |
|
vg_assert(rm); |
|
vg_assert(rm->free_fn); |
|
vg_assert(rm->ranges); |
|
VG_(deleteXA)(rm->ranges); |
|
rm->free_fn(rm); |
|
} |
|
|
|
void VG_(bindRangeMap) ( RangeMap* rm, |
|
UWord key_min, UWord key_max, UWord val ) |
|
{ |
|
vg_assert(key_min <= key_max); |
|
split_at(rm, key_min); |
|
if (key_max < UWORD_MAX) |
|
split_at(rm, key_max + 1); |
|
Word iMin, iMax, i; |
|
iMin = find(rm, key_min); |
|
iMax = find(rm, key_max); |
|
for (i = iMin; i <= iMax; i++) { |
|
Range* rng = VG_(indexXA)(rm->ranges, i); |
|
rng->val = val; |
|
} |
|
preen(rm); |
|
} |
|
|
|
void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max, |
|
/*OUT*/UWord* val, const RangeMap* rm, UWord key ) |
|
{ |
|
Word i = find(rm, key); |
|
Range* rng = (Range*)VG_(indexXA)(rm->ranges, i); |
|
*key_min = rng->key_min; |
|
*key_max = rng->key_max; |
|
*val = rng->val; |
|
} |
|
|
|
UInt VG_(sizeRangeMap) ( const RangeMap* rm ) |
|
{ |
|
vg_assert(rm && rm->ranges); |
|
Word size = VG_(sizeXA)(rm->ranges); |
|
vg_assert(size >= 0); |
|
return size; |
|
} |
|
|
|
void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max, |
|
/*OUT*/UWord* val, const RangeMap* rm, Word ix ) |
|
{ |
|
vg_assert(rm && rm->ranges); |
|
Range* rng = (Range*)VG_(indexXA)(rm->ranges, ix); |
|
*key_min = rng->key_min; |
|
*key_max = rng->key_max; |
|
*val = rng->val; |
|
} |
|
|
|
/* Helper functions, not externally visible. */ |
|
|
|
static void preen (/*MOD*/RangeMap* rm) |
|
{ |
|
Word i; |
|
XArray* ranges = rm->ranges; |
|
for (i = 0; i < VG_(sizeXA)(ranges) - 1; i++) { |
|
Range* rng0 = VG_(indexXA)(ranges, i+0); |
|
Range* rng1 = VG_(indexXA)(ranges, i+1); |
|
if (rng0->val != rng1->val) |
|
continue; |
|
rng0->key_max = rng1->key_max; |
|
VG_(removeIndexXA)(ranges, i+1); |
|
/* Back up one, so as not to miss an opportunity to merge with |
|
the entry after this one. */ |
|
i--; |
|
} |
|
} |
|
|
|
static Word find ( const RangeMap* rm, UWord key ) |
|
{ |
|
XArray* ranges = rm->ranges; |
|
Word lo = 0; |
|
Word hi = VG_(sizeXA)(ranges); |
|
while (True) { |
|
/* The unsearched space is lo .. hi inclusive */ |
|
if (lo > hi) { |
|
/* Not found. This can't happen. */ |
|
VG_(core_panic)("RangeMap::find: not found"); |
|
/*NOTREACHED*/ |
|
return -1; |
|
} |
|
Word mid = (lo + hi) / 2; |
|
Range* mid_rng = (Range*)VG_(indexXA)(ranges, mid); |
|
UWord key_mid_min = mid_rng->key_min; |
|
UWord key_mid_max = mid_rng->key_max; |
|
if (key < key_mid_min) { hi = mid-1; continue; } |
|
if (key > key_mid_max) { lo = mid+1; continue; } |
|
return mid; |
|
} |
|
} |
|
|
|
static void split_at ( /*MOD*/RangeMap* rm, UWord key ) |
|
{ |
|
XArray* ranges = rm->ranges; |
|
Word i = find(rm, key); |
|
Range rng_i0 = *(Range*)VG_(indexXA)( ranges, i+0 ); |
|
if (rng_i0.key_min == key) |
|
return; |
|
VG_(insertIndexXA)( ranges, i+1, &rng_i0 ); |
|
/* The insert could have relocated the payload, hence the |
|
re-indexing of i+0 here. */ |
|
Range* rng_i0p = (Range*)VG_(indexXA)( ranges, i+0 ); |
|
Range* rng_i1p = (Range*)VG_(indexXA)( ranges, i+1 ); |
|
rng_i0p->key_max = key-1; |
|
rng_i1p->key_min = key; |
|
} |
|
|
|
__attribute__((unused)) |
|
static void show ( const RangeMap* rm ) |
|
{ |
|
Word i; |
|
VG_(printf)("<< %ld entries:\n", VG_(sizeXA)(rm->ranges) ); |
|
for (i = 0; i < VG_(sizeXA)(rm->ranges); i++) { |
|
Range* rng = (Range*)VG_(indexXA)(rm->ranges, i); |
|
VG_(printf)(" %016llx %016llx --> 0x%llx\n", |
|
(ULong)rng->key_min, (ULong)rng->key_max, (ULong)rng->val); |
|
} |
|
VG_(printf)(">>\n"); |
|
} |
|
|
|
|
|
/*--------------------------------------------------------------------*/ |
|
/*--- end m_rangemap.c ---*/ |
|
/*--------------------------------------------------------------------*/
|
|
|