1 2 /*--------------------------------------------------------------------*/ 3 /*--- A mapping where the keys exactly cover the address space. ---*/ 4 /*--- pub_tool_rangemap.h ---*/ 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 #ifndef __PUB_TOOL_RANGEMAP_H 34 #define __PUB_TOOL_RANGEMAP_H 35 36 //-------------------------------------------------------------------- 37 // PURPOSE: a mapping from the host machine word (UWord) ranges to 38 // arbitrary other UWord values. The set of ranges exactly covers all 39 // possible UWord values. 40 // -------------------------------------------------------------------- 41 42 /* It's an abstract type. */ 43 typedef struct _RangeMap RangeMap; 44 45 /* Create a new RangeMap, using given allocation and free functions. 46 alloc_fn must not return NULL (that is, if it returns it must have 47 succeeded.) The new array will contain a single range covering the 48 entire key space, which will be bound to the value |initialVal|. 49 This function never returns NULL. */ 50 RangeMap* VG_(newRangeMap) ( void*(*alloc_fn)(const HChar*,SizeT), 51 const HChar* cc, 52 void(*free_fn)(void*), 53 UWord initialVal ); 54 55 /* Free all memory associated with a RangeMap. */ 56 void VG_(deleteRangeMap) ( RangeMap* ); 57 58 /* Bind the range [key_min, key_max] to val, overwriting any other 59 bindings existing in the range. Asserts if key_min > key_max. If 60 as a result of this addition, there come to be multiple adjacent 61 ranges with the same value, these ranges are merged together. Note 62 that this is slow: O(N) in the number of existing ranges. */ 63 void VG_(bindRangeMap) ( RangeMap* rm, 64 UWord key_min, UWord key_max, UWord val ); 65 66 /* Looks up |key| in the array and returns the associated value and 67 the key bounds. Can never fail since the RangeMap covers the 68 entire key space. This is fast: O(log N) in the number of 69 ranges. */ 70 void VG_(lookupRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max, 71 /*OUT*/UWord* val, const RangeMap* rm, UWord key ); 72 73 /* How many elements are there in the map? */ 74 Word VG_(sizeRangeMap) ( const RangeMap* rm ); 75 76 /* Get the i'th component */ 77 void VG_(indexRangeMap) ( /*OUT*/UWord* key_min, /*OUT*/UWord* key_max, 78 /*OUT*/UWord* val, const RangeMap* rm, Word ix ); 79 80 #endif // __PUB_TOOL_RANGEMAP_H 81 82 /*--------------------------------------------------------------------*/ 83 /*--- end pub_tool_rangemap.h ---*/ 84 /*--------------------------------------------------------------------*/ 85