sewardj | c5fc866 | 2014-03-20 23:00:09 +0000 | [diff] [blame] | 1 | |
| 2 | /*--------------------------------------------------------------------*/ |
| 3 | /*--- A mapping where the keys exactly cover the address space. ---*/ |
| 4 | /*--- m_rangemap.c ---*/ |
| 5 | /*--------------------------------------------------------------------*/ |
| 6 | |
| 7 | /* |
| 8 | This file is part of Valgrind, a dynamic binary instrumentation |
| 9 | framework. |
| 10 | |
| 11 | Copyright (C) 2014-2014 Mozilla Foundation |
| 12 | |
| 13 | This program is free software; you can redistribute it and/or |
| 14 | modify it under the terms of the GNU General Public License as |
| 15 | published by the Free Software Foundation; either version 2 of the |
| 16 | License, or (at your option) any later version. |
| 17 | |
| 18 | This program is distributed in the hope that it will be useful, but |
| 19 | WITHOUT ANY WARRANTY; without even the implied warranty of |
| 20 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 21 | General Public License for more details. |
| 22 | |
| 23 | You should have received a copy of the GNU General Public License |
| 24 | along with this program; if not, write to the Free Software |
| 25 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 26 | 02111-1307, USA. |
| 27 | |
| 28 | The GNU General Public License is contained in the file COPYING. |
| 29 | */ |
| 30 | |
| 31 | /* Contributed by Julian Seward <jseward@acm.org> */ |
| 32 | |
| 33 | #include "pub_core_basics.h" |
| 34 | #include "pub_core_libcassert.h" |
| 35 | #include "pub_core_libcprint.h" |
| 36 | #include "pub_core_xarray.h" |
| 37 | #include "pub_core_rangemap.h" /* self */ |
| 38 | |
| 39 | |
| 40 | /* See pub_tool_rangemap.h for details of what this is all about. */ |
| 41 | |
| 42 | #define UWORD_MIN ((UWord)0) |
| 43 | #define UWORD_MAX (~(UWord)0) |
| 44 | |
| 45 | typedef |
| 46 | struct { UWord key_min; UWord key_max; UWord val; } |
| 47 | Range; |
| 48 | |
| 49 | |
| 50 | struct _RangeMap { |
| 51 | void* (*alloc) ( const HChar*, SizeT ); /* alloc fn (nofail) */ |
| 52 | const HChar* cc; /* cost centre for alloc */ |
| 53 | void (*free) ( void* ); /* free fn */ |
| 54 | XArray* ranges; |
| 55 | }; |
| 56 | |
| 57 | |
| 58 | /* fwds */ |
| 59 | static void preen (/*MOD*/RangeMap* rm); |
| 60 | static Word find ( RangeMap* rm, UWord key ); |
| 61 | static void split_at ( /*MOD*/RangeMap* rm, UWord key ); |
| 62 | static void show ( RangeMap* rm ); |
| 63 | |
| 64 | |
| 65 | RangeMap* VG_(newRangeMap) ( void*(*alloc_fn)(const HChar*,SizeT), |
| 66 | const HChar* cc, |
| 67 | void(*free_fn)(void*), |
| 68 | UWord initialVal ) |
| 69 | { |
| 70 | /* check user-supplied info .. */ |
| 71 | vg_assert(alloc_fn); |
| 72 | vg_assert(free_fn); |
| 73 | RangeMap* rm = alloc_fn(cc, sizeof(RangeMap)); |
| 74 | vg_assert(rm); |
| 75 | rm->alloc = alloc_fn; |
| 76 | rm->cc = cc; |
| 77 | rm->free = free_fn; |
| 78 | rm->ranges = VG_(newXA)( alloc_fn, cc, free_fn, sizeof(Range) ); |
| 79 | vg_assert(rm->ranges); |
| 80 | /* Add the initial range */ |
| 81 | Range r; |
| 82 | r.key_min = UWORD_MIN; |
| 83 | r.key_max = UWORD_MAX; |
| 84 | r.val = initialVal; |
| 85 | Word i = VG_(addToXA)(rm->ranges, &r); |
| 86 | vg_assert(i == 0); |
| 87 | vg_assert(VG_(sizeXA)(rm->ranges) == 1); |
| 88 | /* */ |
| 89 | return rm; |
| 90 | } |
| 91 | |
| 92 | void VG_(deleteRangeMap) ( RangeMap* rm ) |
| 93 | { |
| 94 | vg_assert(rm); |
| 95 | vg_assert(rm->free); |
| 96 | vg_assert(rm->ranges); |
| 97 | VG_(deleteXA)(rm->ranges); |
| 98 | rm->free(rm); |
| 99 | } |
| 100 | |
| 101 | void VG_(bindRangeMap) ( RangeMap* rm, |
| 102 | UWord key_min, UWord key_max, UWord val ) |
| 103 | { |
| 104 | vg_assert(key_min <= key_max); |
| 105 | split_at(rm, key_min); |
| 106 | if (key_max < UWORD_MAX) |
| 107 | split_at(rm, key_max + 1); |
| 108 | Word iMin, iMax, i; |
| 109 | iMin = find(rm, key_min); |
| 110 | iMax = find(rm, key_max); |
| 111 | for (i = iMin; i <= iMax; i++) { |
| 112 | Range* rng = VG_(indexXA)(rm->ranges, i); |
| 113 | rng->val = val; |
| 114 | } |
| 115 | preen(rm); |
| 116 | } |
| 117 | |
| 118 | void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max, |
| 119 | /*OUT*/UWord* val, RangeMap* rm, UWord key ) |
| 120 | { |
| 121 | Word i = find(rm, key); |
| 122 | Range* rng = (Range*)VG_(indexXA)(rm->ranges, i); |
| 123 | *key_min = rng->key_min; |
| 124 | *key_max = rng->key_max; |
| 125 | *val = rng->val; |
| 126 | } |
| 127 | |
| 128 | Word VG_(sizeRangeMap) ( RangeMap* rm ) |
| 129 | { |
| 130 | vg_assert(rm && rm->ranges); |
| 131 | return VG_(sizeXA)(rm->ranges); |
| 132 | } |
| 133 | |
| 134 | void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max, |
| 135 | /*OUT*/UWord* val, RangeMap* rm, Word ix ) |
| 136 | { |
| 137 | vg_assert(rm && rm->ranges); |
| 138 | Range* rng = (Range*)VG_(indexXA)(rm->ranges, ix); |
| 139 | *key_min = rng->key_min; |
| 140 | *key_max = rng->key_max; |
| 141 | *val = rng->val; |
| 142 | } |
| 143 | |
| 144 | /* Helper functions, not externally visible. */ |
| 145 | |
| 146 | static void preen (/*MOD*/RangeMap* rm) |
| 147 | { |
| 148 | Word i; |
| 149 | XArray* ranges = rm->ranges; |
| 150 | for (i = 0; i < VG_(sizeXA)(ranges) - 1; i++) { |
| 151 | Range* rng0 = VG_(indexXA)(ranges, i+0); |
| 152 | Range* rng1 = VG_(indexXA)(ranges, i+1); |
| 153 | if (rng0->val != rng1->val) |
| 154 | continue; |
| 155 | rng0->key_max = rng1->key_max; |
| 156 | VG_(removeIndexXA)(ranges, i+1); |
| 157 | /* Back up one, so as not to miss an opportunity to merge with |
| 158 | the entry after this one. */ |
| 159 | i--; |
| 160 | } |
| 161 | } |
| 162 | |
| 163 | static Word find ( RangeMap* rm, UWord key ) |
| 164 | { |
| 165 | XArray* ranges = rm->ranges; |
| 166 | Word lo = 0; |
| 167 | Word hi = VG_(sizeXA)(ranges); |
| 168 | while (True) { |
| 169 | /* The unsearched space is lo .. hi inclusive */ |
| 170 | if (lo > hi) { |
| 171 | /* Not found. This can't happen. */ |
| 172 | VG_(core_panic)("RangeMap::find: not found"); |
| 173 | /*NOTREACHED*/ |
| 174 | return -1; |
| 175 | } |
| 176 | Word mid = (lo + hi) / 2; |
| 177 | Range* mid_rng = (Range*)VG_(indexXA)(ranges, mid); |
| 178 | UWord key_mid_min = mid_rng->key_min; |
| 179 | UWord key_mid_max = mid_rng->key_max; |
| 180 | if (key < key_mid_min) { hi = mid-1; continue; } |
| 181 | if (key > key_mid_max) { lo = mid+1; continue; } |
| 182 | return mid; |
| 183 | } |
| 184 | } |
| 185 | |
| 186 | static void split_at ( /*MOD*/RangeMap* rm, UWord key ) |
| 187 | { |
| 188 | XArray* ranges = rm->ranges; |
| 189 | Word i = find(rm, key); |
| 190 | Range rng_i0 = *(Range*)VG_(indexXA)( ranges, i+0 ); |
| 191 | if (rng_i0.key_min == key) |
| 192 | return; |
| 193 | VG_(insertIndexXA)( ranges, i+1, &rng_i0 ); |
| 194 | /* The insert could have relocated the payload, hence the |
| 195 | re-indexing of i+0 here. */ |
| 196 | Range* rng_i0p = (Range*)VG_(indexXA)( ranges, i+0 ); |
| 197 | Range* rng_i1p = (Range*)VG_(indexXA)( ranges, i+1 ); |
| 198 | rng_i0p->key_max = key-1; |
| 199 | rng_i1p->key_min = key; |
| 200 | } |
| 201 | |
| 202 | __attribute__((unused)) |
| 203 | static void show ( RangeMap* rm ) |
| 204 | { |
| 205 | Word i; |
| 206 | VG_(printf)("<< %ld entries:\n", VG_(sizeXA)(rm->ranges) ); |
| 207 | for (i = 0; i < VG_(sizeXA)(rm->ranges); i++) { |
| 208 | Range* rng = (Range*)VG_(indexXA)(rm->ranges, i); |
| 209 | VG_(printf)(" %016llx %016llx --> 0x%llx\n", |
| 210 | (ULong)rng->key_min, (ULong)rng->key_max, (ULong)rng->val); |
| 211 | } |
| 212 | VG_(printf)(">>\n"); |
| 213 | } |
| 214 | |
| 215 | |
| 216 | /*--------------------------------------------------------------------*/ |
| 217 | /*--- end m_rangemap.c ---*/ |
| 218 | /*--------------------------------------------------------------------*/ |